Вимоги до алгоритмів

Поняття алгоритму

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

Під алгоритмом також розуміють:

– опис послідовності дій для розв’язання задачі або досягнення поставленої мети;

– правила виконання основних операцій обробки даних;

– опис обчислень за математичними формулами.

Термін "алгоритм" походить від "algorithmi" – латинської форми написання імені великого математика аль-Хорезмі, який сформулював правила виконання арифметичних дій. Тому спочатку під алгоритмом розуміли тільки правила виконання чотирьох арифметичних дій над багатоцифровими числами в десятковій системі числення. Зараз він є одним із фундаментальних понять інформатики.

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

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

Рішення: Позначимо дівчат і молодих людей Д1, Д2, М1, М2, переїзд на правий берег →, переїзд на лівий берег ←. Можна записати алгоритм:

1) Д1, Д2 →

2) Д1 ←

3) М1, М2 →

4) М1 ←

5) Д1, М1 →

У 30-х роках минулого століття зародилася і бурхливо розвивається наука, яка називається теорією алгоритмів.

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

На основі формалізації поняття алгоритму можливі наступні дії:

– порівняння алгоритмів за їх ефективністю;

– перевірка їх еквівалентності;

– визначення областей застосування.

Початковою точкою відліку сучасної теорії алгоритмів вважають роботу німецького математика Курта Геделя (1931 рік – теорема про неповноту символічних логік). Перші фундаментальні роботи з теорії алгоритмів були опубліковані незалежно в 1936 році роки Аланом Тьюрингом, Алоізом Черчем і Емілем Постом. Запропоновані ними машина Тьюринга, машина Посту і лямбдачислення Черча були еквівалентними формалізмами алгоритму. Важливим розвитком цих робіт стало формулювання і доказ алгоритмічно нерозв'язних проблем. У 50-ті роки минулого століття істотний внесок у теорію алгоритмів внесли роботи Колмогорова і Маркова.

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

У техніку термін "алгоритм" прийшов разом з кібернетикою. Застосування ПК послужило стимулом розвитку теорії алгоритмів і вивченню алгоритмічних моделей, до самостійного вивчення алгоритмів з метою їх порівняння за робочими характеристиками (числу дій, витраті пам'яті), а також їх оптимізації. Виник важливий напрямок в теорії алгоритмів – складність алгоритмів і обчислень.

Вимоги до алгоритмів

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

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

2. Алгоритм для розміщення даних вимагає пам'яті. Пам'ять зазвичай вважається однорідною і дискретною, тобто вона складається з однакових комірок, причому кожна комірка може містити один символ даних, що дозволяє узгодити одиниці виміру обсягу даних і пам'яті.

3. Алгоритм складається з окремих елементарних кроків, причому множина різних кроків, з яких складений алгоритм, скінченні. Типовий приклад множини елементарних кроків – система команд процесора.

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

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

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

Вимога 1 відповідає цифровій природі ПК, вимога 2 – пам'ять ПК, вимога 3 – програмі машини, вимога 4 – її логічній природі, вимоги 5, 6 – обчислювальному пристрою та його можливостям.