АЛГОРИТМ І ЙОГО ВЛАСТИВОСТІ

1.1. Різні підходи до поняття «АЛГОРИТМ»

Поняття алгоритму - одне з фундаментальних понять інформатики. Алгоритмізація поряд з моделюванням виступає в якості загального методу інформатики. До реалізації певних алгоритмів зводяться процеси управління в різних системах, що робить поняття алгоритму близьким і кібернетики.
Алгоритми є об'єктом систематичного дослідження прикордонної між математикою та інформатикою наукової дисципліни, що примикає до математичної логіки - теорії алгоритмів.
Особливість становища полягає в тому, що при вирішенні практичних завдань, які передбачають розробку алгоритмів для реалізації на ЕОМ, і тим більше при використанні на практиці інформаційних технологій, можна, як правило, не спиратися на високу формалізацію даного поняття. Тому видається доцільним познайомитися з алгоритмами і алгоритмізацією на основі змістовного тлумачення сутності поняття алгоритму і розгляду основних його властивостей. При такому підході алгоритмізація більш виступає як набір певних практичних прийомів, особливих специфічних навичок раціонального мислення в рамках заданих мовних засобів. Можна провести аналогію між цією обставиною і розглянутим вище підходом до вимірювання інформації: тонкі математичні побудови при «кібернетичному" підході не дуже потрібні при використанні значно більш простого «об'ємного» підходу при практичній роботі з комп'ютером.
Саме слово «алгоритм» походить від algorithmi - латинської форми написання імені великого математика IX століття аль-Хорезмі, який сформулював правила виконання арифметичних дій. Спочатку під алгоритмами і розуміли тільки правила виконання чотирьох арифметичних дій над багатозначними числами.

1.2. ПОНЯТТЯ ВИКОНАВЦЯ АЛГОРИТМУ

Поняття виконавця неможливо визначити за допомогою будь-якої формалізації. Виконавцем може бути людина, група людей, робот, верстат, комп'ютер, мова програмування і т.д. Дуже важливою властивістю, що характеризує будь-якого з цих виконавців, є те, що виконавець уміє виконувати деякі команди. Так, виконавець-людина вміє виконувати такі команди як «стати», «сісти», «включити комп'ютер» і т.д., а виконавець-мова програмування Бейсік - команди PRINT, END, LIST та інші аналогічні. Вся сукупність команд, які даний виконавець уміє виконувати, називається системою команд виконавця (СКІ).
В якості прикладу (ріс.1.11) розглянемо виконавця-робота, робота якого полягає у власному переміщенні по робочому полю (квадрату довільного розміру, розділеному на клітини) і переміщенні об'єктів, в початковий момент часу знаходяться на «складі» (права верхня клітина).

Ріс.1.11. Виконавець-робот

Одне з принципових обставин полягає в тому, що виконавець не вникає у зміст того, що він робить, але отримує необхідний результат. У такому випадку говорять, що виконавець діє формально, тобто відволікається від змісту поставленого завдання і тільки строго виконує деякі правила, інструкції.
Це - важлива особливість алгоритмів. Наявність алгоритму формалізує процес вирішення завдання, виключає міркування виконавця. Використання алгоритму дає можливість вирішувати завдання формально, механічно виконуючи команди алгоритму у зазначеній послідовності. Доцільність передбачаються алгоритмом дій забезпечується точним аналізом з боку того, хто складає цей алгоритм.
Введення в розгляд поняття «виконавець» дозволяє визначити алгоритм як зрозуміле і точне розпорядження виконавцю здійснити послідовність дій, спрямованих на досягнення поставленої мети. У випадку виконавця-робота ми маємо приклад алгоритму «в обстановці», що характеризується відсутністю будь-яких величин. Найбільш ж поширеними і звичними є алгоритми роботи з величинами - числовими, символьними, логічними і т.д.

1.3. ГРАФІЧНЕ ПОДАННЯ АЛГОРИТМІВ

Алгоритм

1.4. ВЛАСТИВОСТІ АЛГОРИТМІВ

Алгоритм повинен бути складений таким чином, щоб виконавець, у розрахунку на якого він створений, міг однозначно і точно слідувати командам алгоритму і ефективно отримувати певний результат. Це накладає на запису алгоритмів ряд обов'язкових вимог, суть яких випливає, взагалі кажучи, з наведеного вище неформального тлумачення поняття алгоритму. Сформулюємо ці вимоги у вигляді переліку властивостей, яким повинні задовольняти алгоритми, адресовані заданому виконавцю.
1. Одне з перших вимог, яка пред'являється до алгоритму, полягає в тому, що описуваний процес повинен бути розбитий на послідовність окремих кроків. Що виникає в результаті такого розбиття запис являє собою упорядковану сукупність чітко розділених один від одного приписів (директив, команд, операторів), які утворюють переривчастим (або, як кажуть, дискретну) структуру алгоритму. Тільки виконавши вимоги одного приписи, можна приступити до виконання наступного. Дискретна структура алгоритмічної запису може. Наприклад, підкреслено наскрізною нумерацією окремих команд алгоритму, хоча ця вимога не є обов'язковим. Розглянуте властивість алгоритмів називають дискретністю.
2. Використовувані на практиці алгоритми складаються з орієнтацією на певного виконавця. Щоб скласти для нього алгоритм, потрібно знати, які команди цей виконавець може зрозуміти і виконати, а які - не може. Ми знаємо, що у кожного виконавця є своя система команд. Очевидно, складаючи запис алгоритму для певного виконавця, можна використовувати лише ті команди, які є в його СКІ. Це властивість алгоритмів будемо називати зрозумілістю.
3. Будучи зрозумілим, алгоритм не повинен містити розпоряджень, зміст яких може сприйматися неоднозначно, тобто одна й та ж команда, будучи зрозуміла різним виконавцям, після виконання кожним з них повинна давати однаковий результат.
Запис алгоритму повинна бути настільки чіткої, повної і продуманої в деталях, щоб у виконавця не могло виникнути потреби у прийнятті рішень, не передбачених упорядником алгоритму. Говорячи інакше, алгоритм не повинен залишати місця для свавілля виконавця. Крім того, в алгоритмах неприпустимі також ситуації, коли після виконання чергової команди алгоритму виконавцю незрозуміло, яка з команд алгоритму повинна виконуватися на наступному кроці.
Зазначене властивості алгоритмів називають визначеністю або детермінованістю.
4. Обов'язкова вимога до алгоритмів - результативність. Сенс цієї вимоги полягає в тому, що при точному виконанні всіх розпоряджень алгоритму процес повинен припинитися за кінцеве число кроків і при цьому має вийти певний результат. Висновок про те, що рішення не існує - теж результат.
5. Найбільш поширені алгоритми, що забезпечують рішення не однієї конкретної задачі, а деякого класу задач даного типу. Це властивість алгоритму називають масовістю. У найпростішому випадку масовість забезпечує можливість використання різних вихідних даних.

1.5. Поняття алгоритмічного МОВИ

Досить поширеним способом представлення алгоритму є його запис на алгоритмічній мові, представляє в загальному випадку систему позначень і правил для однакової і точного запису алгоритмів і виконання їх. Відзначимо, що між поняттями «алгоритмічна мова» і «мови програмування» є відмінність; перш за все, під виконавцем у алгоритмічній мові може матися на увазі не тільки комп'ютер, але й пристрій для роботи «в обстановці». Програма, записана на алгоритмічній мові, не обов'язково призначена комп'ютера. Практична ж реалізація алгоритмічної мови - окреме питання в кожному конкретному випадку.
Як і кожна мова, алгоритмічна мова має свій словник. Основу цього словника складають слова, що вживаються для запису команд, що входять у систему команд виконавця того чи іншого алгоритму. Такі команди називають простими командами. У алгоритмічній мові використовують слова, зміст і спосіб вживання яких заданий раз і назавжди. Ці слова називають службовими. Використання службових слів робить запис алгоритму більш наочною, а форму подання різних алгоритмів - однакової.
Алгоритм, записаний на алгоритмічній мові, повинен мати назву. Назва бажано вибирати так, щоб було ясно, рішення якої задачі описує даний алгоритм. Для виділення назви алгоритму перед ним записують службове слово Алг (алгоритм). За назвою алгоритму (зазвичай з нового рядка) записують його команди. Для вказівки початку і кінця алгоритму його команди укладають в пару службових слів НАЧ (початок) і КОН (кінець). Команди записують послідовно.
Послідовність запису алгоритму:
Алг назву алгоритму
НАЧ
серія команд алгоритму
КОН
Наприклад, алгоритм, який визначає рух виконавця-робота, може мати вигляд:
Алг в_склад
НАЧ
вперед
поворот на 90 ° праворуч
вперед
КОН
При побудові нових алгоритмів можуть використовуватися алгоритми, складені раніше. Алгоритми, цілком використовувані у складі інших алгоритмів, називають допоміжними алгоритмами. Допоміжним може виявитися будь-який алгоритм з числа раніше складених. Не виключається також, що допоміжним в певній ситуації може виявитися алгоритм, сам містить посилання на допоміжні алгоритми.
Дуже часто при складанні алгоритмів виникає необхідність використання в якості допоміжного одного і того ж алгоритму, який до того ж може бути досить складним і громіздким. Було б нераціонально, починаючи роботу, кожен раз заново складати і запам'ятовувати такий алгоритм для його подальшого використання. Тому в практиці широко використовують, так звані, вбудовані (або стандартні) допоміжні алгоритми, тобто такі алгоритми, які постійно є в розпорядженні виконавця. Звернення до таких алгоритмам здійснюється так само, як і до «звичайним» допоміжним алгоритмам. У виконавця-робота вбудованим допоміжним алгоритмом може бути переміщення в склад з будь-якої точки робочого поля; у виконавця-мова програмування Бейсік це, наприклад, вбудований алгоритм «SIN».
Алгоритм може містити звернення до самого себе як допоміжного і в цьому випадку його називають рекурсивним. Якщо команда звернення алгоритму до самого себе знаходиться в самому алгоритмі, то таку рекурсію називають прямою. Можливі випадки, коли рекурсивний виклик даного алгоритму відбувається з допоміжного алгоритму, до якого в даному алгоритмі є звернення. Така рекурсія називається непрямої. Приклад прямої рекурсії:
Алг рух
НАЧ
вперед
вперед
вправо
рух
КОН
Алгоритми, при виконанні яких порядок проходження команд визначається в залежності від результатів перевірки деяких умов, називають розгалужуються. Для їх опису в алгоритмічній мові використовують спеціальну складову команду - команда розгалуження. Вона відповідає блок-схемі «альтернатива» і також може мати повну або скорочену форму. Стосовно до виконавця-роботу умовою може бути перевірка знаходження робота у краю робочого поля (край / не_край); перевірка наявності об'єкта в поточній клітині (є / немає) і деякі інші:
ЯКЩО умова ЯКЩО умова ЯКЩО край
ТО серія 1 ТО серія ТО вправо
ІНАКШЕ серія2 ВСЕ ІНШЕ вперед
ВСІ ВСЕ
Нижче наводиться запис на алгоритмічній мові команди вибору (див. ріс.1.14, б), що є розвитком команди розгалуження:
ВИБІР
ПРИ умова 1: серія 1
ПРИ умова 2: серія 2
...
ПРИ умова N: серія N
ІНАКШЕ серія N +1
ВСІ
Алгоритми, при виконанні яких окремі команди або серії команд виконуються неодноразово, називають циклічними. Для організації циклічних алгоритмів у алгоритмічній мові використовують спеціальну складову команду циклу. Вона відповідає блок-схемами типу «ітерація» і може приймати наступний вигляд:
ПОКИ умова НЦ
НЦ серія
Серія ДО умова
КЦ КЦ
У разі складання алгоритмів роботи з величинами можна розглянути і інші можливі алгоритмічні конструкції, наприклад, цикл з параметром або вибір. Докладно ці конструкції будуть розглядатися при знайомстві з реальними мовами програмування.
На закінчення даного параграфа наведемо алгоритм, складений для виконавця-робота, за яким робот переносить всі об'єкти зі складу в лівий нижній кут робочого поля (поле може мати довільні розміри):
Алг перенесення Алг в_угол3 Алг до_края
НАЧ НАЧ НАЧ
в_угол3 до_края ПОКИ не_край
ЯКЩО є вправо НЦ
ТО до_края вперед
взяти вправо КЦ
в_угол3 КОН КОН
встановити
перенесення
ІНАКШЕ
в_угол3
ВСІ
КОН