Основні властивості алгоритму

1. Детермінованість – визначення кроків алгоритму, тобто після кожного кроку або зазначається, який крок необхідно робити далі, або дається команда на закінчення, після чого робота алгоритму вважається закінченою.

2. Масовість – алгоритм може бути використаний для розв’язання цілого класу задач одного типу, наприклад, квадратного рівняння з різними коефіцієнтами.

3. Результативність (скінченність, збіжність) – виконання алгоритму має або закінчуватися результатом, або інформацією про те, чому не може бути одержаний результат, причому множина кроків, з яких складено алгоритм, є скінченною.

4. Зрозумілість – алгоритм має бути зрозумілим конкретному виконавцю, який повинен виконати кожну команду алгоритму у строгій відповідності з її призначенням.

5. Дискретність – можливість розбиття алгоритму на скінченну кількість етапів, причому результати попереднього етапу є вихідними для наступного.

Приклад 1. Дано два натуральних числа X та Y. Необхідно знайти їх найбільший спільний дільник (НСД).

Розв’язання. Застосовуючи алгоритм Евкліда, метод розв’язання задачі є таким:

Крок 1. Початок

Крок 2. Ввести до розгляду числа X та Y.

Крок 3. Якщо X = Y, то перейти до кроку 7, інакше – до кроку 4.

Крок 4. Якщо X < Y, то перейти до кроку 5, інакше – до кроку 6.

Крок 5. Зменшити Y на значення X, перейти до кроку 3.

Крок 6. Зменшити X на значення Y, перейти до кроку 3.

Крок 7. Прийняти НСД рівним X.

Крок 8. Кінець.

Це приклад числового алгоритму, який зводить розв’язання наведеної задачі до арифметичних дій над числами.

Логічні алгоритми – це алгоритми, що містять розпорядження, яке стосується не цифр, а об’єктів будь-якої природи.

Приклад 2. Пошук шляху в скінченному лабіринті. Лабіринт зобразимо у вигляді графа, де вершини – це майданчики лабіринту, дуги – його коридори. Нехай треба з’ясувати, чи досяжний майданчик f із майданчика a, і якщо це так, то знайти шлях з a в f, а якщо ні – повернутися в a. Припускається, що заздалегідь нічого не відомо про будову цього лабіринту.

Розв’язання. Нехай людина, яка шукає шлях у лабіринті, має у своєму розпорядженні нитку, кінець якої закріплено на майданчику a, та, рухаючись по лабіринту, може розмотувати клубок (Р) або навпаки, намотувати (Н) на нього нитку.

Можна робити позначки на прохідних коридорах і розрізняти потім коридори: ще жодного разу не пройдені (зелені – З), пройдені один раз (жовті – Ж ) та пройдені двічі (червоні – Ч).

Метод пошуку може бути заданий такою схемою:

1) майданчик f – зупинка (мету досягуто);

2 ) петля (П) – намотування нит­ки (від майданчика роз­хо­дять­ся принаймні два жовтих ко­ри­дори);

3) зелена вулиця (ЗВ) – роз­мотування нитки (від май­данчика виходить при­найм­ні один зелений коридор);

4) майданчик а – зупинка (початковий пункт);

5

Рис. 1

) відсутність усіх поперед­ніх ознак (ВО) – на­мо­ту­ван­ня нитки.

Потрапивши на деякий майданчик, потрібно звіритися зі схемою ознак у зазначеному порядку і зробити черговий хід відповідно до першої виявленої ознаки, не перевіряючи інших ознак доти, доки не настане зупинка. Один із можливих варіантів пошуку шляху в лабіринті (рис. 1) містить ходи, наведені в таблиці

Номер ходу	Ознака	Хід	Пройдений коридор	Колір коридору після його проходу
1	ЗВ	Р	ab	Ж
2	Те саме	Те саме	bc	Те саме
3	Те саме	Те саме	cd	Те саме
4	Те саме	Те саме	dg	Те саме
5	Те саме	Те саме	gh	Те саме
6	ВО	Н	hg	Ч
7	Те саме	Те саме	gd	Те саме
8	ЗВ	Р	db	Ж
9	П	Н	bd	Ч
10	ЗВ	Р	df	Ж

Якщо перерахувати коридори, які залишилися жовтими (ab, bc, cd, df), то дістанемо шлях від a до f.

Існують різні способи опису алгоритму (словесний, табличний, псевдоход, графічний тощо). Алгоритм для ЕОМ найзручніше зображати графічно у вигляді схем.

Схеми алгоритмів складаються з символів, що мають задане значення, короткого пояснювального тексту і сполучних ліній.

Схема програми складається з:

1. символів процесу, які показують операції оброблення даних (включаючи символи, що визначають шлях, якого варто дотримуватися з урахуванням логічних умов);

2. лінійних символів, що показують потік керування;

3. спеціальних символів, що використовуються для полегшення написання та читання програми.

Існують три основних типи процесів оброблення інформації: лінійний, розгалужувальний й циклічний. При лінійному процесі оброблення інформації здійснюється послідовно, одна дія за іншою, і кожен етап алгоритму виконується тільки однин раз.

При розгалужуваному процесі інформація обробляється по одному з двох можливих шляхів, тобто ті чи інші дії виконуються залежно від деякої умови.

При циклічному процесі ті самі дії з оброблення інформації потрібно виконувати багаторазово. Їм відповідають базові структури (конструкції) алгоритмів: проходження (лінійна структура), розгалуження (структура, що розгалужується), повторення (циклічна структура). Реальний алгоритм будь-якого ступеня складності можна задати комбінацією зазначених базових структур.

Для першого прикладу граф зображено на рис. 2.

Такий граф, в якому вершинам відповідають кроки, а ребрам – переходи між ними, називається схемою алгоритму. Його вершини можуть бути двох типів: вершини, з яких виходить одне ребро (оператори), і вершини, з яких виходять два ребра (логічні умови або предикати). Крім того, існує єдиний оператор кінця, з якого не виходить жодного ребра, та єдиний оператор початку.

За допомогою схем можна кілька алгоритмів, що розглядаються як блоки, зв’язати в один алгоритм. Зокрема, якщо алгоритм А₁, який обчислює функцію y = f₁(x), сполучений з алгоритмом А₂, що обчислює функцію f₂(y) (рис. 3), і при цьому початковими даними для А₂ є результат А₁, то утворена схема задає алгоритм, який обчислює f₂(f₁(x)), тобто композицію f₁ й f₂. Таке сполучення алгоритмів називається їх комбінацією. Опис алгоритму – це граф; процес реалізації – шлях у ньому. Різні шляхи в одному і тому самому графі виникають при різних даних, які створюють різні логічні умови в точках розгалуження.

Відсутність збіжності означає, що в процесі обчислення не виникають умови, які ведуть до кінця, і процес йде по нескінченному шляху (зациклюється).

Мова схем досить груба та відображає зв’язки лише за управлінням (що робити в наступний момент, тобто якому блоку передати управляння), а не за інформацією. Наприклад, рис. 3 при виконанні дій в певній послідовності зображає обчислення композиції f₂(f₁(x)), однак він же міг відображати послідовне обчислення двох незалежних функцій f₁(x) й f₂(y).

Схеми не містять відомостей ні про дані, ні про пам’ять, ні про набір елементарних кроків, який використовується. По суті, схеми – це засіб опису детермінізму алгоритму. Виявляється, що будь-який логічний алгоритм можна досить простими методами звести до числового.

Твердження. Будь-яку алгоритмічну проблему можна звести до обчислення значень деякої цілочислової функції цілочислових аргументів.

Існують три основні типи алгоритмічних моделей, які розрізняються початковими евристичними міркуваннями щодо того, що таке алгоритм.

Перший тип зв’язує поняття алгоритму з найтрадиційнішими поняттями математики – обчисленнями та числовими функціями. Найбільш розвинена і вивчена модель цього типу – рекурсивні функції – є історично першою формалізацією алгоритму.

Другий тип ґрунтується на уявленні про алгоритм як про деякий детермінований пристрій, здатний виконувати в кожний окремий момент лише дуже примітивні операції. Основною теоретичною моделлю цього типу є машина Тьюринга.

Третій тип алгоритмічних моделей – це перетворення слів у довільних алфавітах, в яких елементарними операціями є підстановки, тобто заміни частини слова (підслова) іншим словом. Переваги цього типу – в його максимальній абстрактності та можливості застосувати поняття алгоритму до об’єктів довільної (не обов’язково) числової природи. Приклади моделей цього типу – нормальні алгоритми Маркова.