ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 2333
Скачиваний: 1
6
1.
ВВЕДЕННЯ В ТЕОРІЮ АЛГОРИТМІВ
1.1
Основні поняття теорії алгоритмів
Теорія алгоритмів – це наука, що вивчає загальні властивості та
закономірності алгоритмів, різноманітні формальні моделі їх подання. На
основі формалізації поняття алгоритму можливе порівняння алгоритмів за їх
ефективністю, перевірка їх еквівалентності, визначення областей
застосовності.
В даний час теорія алгоритмів утворює теоретичний фундамент
обчислювальних наук. Застосування теорії алгоритмів здійснюється як у
використанні самих результатів (особливо це стосується використання
розроблених алгоритмів), так і у виявленні нових понять і уточненні старих. З
її допомогою пояснюються такі поняття як доведеність, ефективність,
можливість розв’язання тощо.
У техніку термін «алгоритм» прийшов разом з кібернетикою. Поняття
алгоритму допомогло, наприклад, точно визначити, що означає ефективно
задати послідовність керуючих сигналів. Застосування ПК послужило
стимулом розвитку теорії алгоритмів і вивченню алгоритмічних моделей, до
самостійного вивчення алгоритмів з метою їх порівняння за робочими
характеристиками (числу дій, витраті пам'яті), а також їх оптимізації.
Виник важливий напрямок в теорії алгоритмів – складність алгоритмів і
обчислень. Почала складатися так звана метрична теорія алгоритмів,
основним змістом якої є класифікація задач за класами складності. Самі
алгоритми стали об'єктом точного дослідження як і ті об'єкти, для роботи з
якими вони призначені
В цій області природно виділяються завдання отримання верхніх і
нижніх оцінок складності алгоритмів. Методи вирішення цих завдань зовсім
різні. Для отримання верхніх оцінок досить інтуїтивного поняття алгоритму.
Для цього будується неформальний алгоритм вирішення конкретного
завдання і потім він формалізується для реалізації на придатній
алгоритмічній моделі.
Якщо показується, що складність (час або пам'ять) обчислення для цього
алгоритму не перевищує значення підходящої функції при всіх значеннях
аргументу, то ця функція оголошується верхньою оцінкою складності
рішення розглянутої задачі. В області знаходження верхніх оцінок отримано
7
багато яскравих результатів для конкретних задач. Серед них розроблені
швидкі алгоритми множення цілих чисел, багаточленів, матриць, рішення
лінійних систем рівнянь, які вимагають значно менше ресурсів, ніж
традиційні алгоритми.
Встановити нижню оцінку – значить довести, що ніякий алгоритм
обчислення не має складності меншої, ніж задана межа. Для отримання
результатів такого типу необхідна точна фіксація розглянутої алгоритмічної
моделі, і такі результати отримані тільки в дуже жорстких обчислювальних
моделях. У зв'язку з цим отримала розвиток проблематика отримання
«
відносних» нижніх оцінок, так звана теорія NP-повноти, яка пов'язана з
труднощами розв’язку задач перебору.
Розглянемо неформально, що саме в інтуїтивному понятті алгоритму
потребує уточнення.
Основні вимоги до алгоритмів.
1.
Кожен алгоритм має справу з даними – вхідними, проміжними,
вихідними. Для того, щоб уточнити поняття даних, фіксується кінцевий
алфавіт вихідних символів (цифри, букви і т.п.) і вказуються правила
побудови алгоритмічних об'єктів. Типовим використовуваним засобом є
індуктивна побудова. Наприклад, визначення ідентифікатора в Алгол:
ідентифікатор – це або буква, або ідентифікатор, до якого приписана
праворуч або буква, або цифра. Слова кінцевої довжини в кінцевих алфавітах
–
найбільш звичайний тип алгоритмічних даних, а число символів в слові –
природна міра об'єму даних. Інший випадок алгоритмічних об'єктів –
формули. Прикладом можуть служити формули алгебри предикатів і алгебри
висловлювань. У цьому випадку не кожне слово в алфавіті буде формулою.
2.
Алгоритм для розміщення даних вимагає пам'яті. Пам'ять
зазвичай вважається однорідною і дискретною, тобто вона складається з
однакових комірок, причому кожна комірка може містити один символ даних,
що дозволяє узгодити одиниці виміру обсягу даних і пам'яті.
3.
Алгоритм складається з окремих елементарних кроків, причому
множина різних кроків, з яких складений алгоритм, кінцеві. Типовий приклад
множини елементарних кроків – система команд процесора.
4.
Послідовність кроків алгоритму детермінована, тобто після
кожного кроку вказується, який крок слід виконувати далі, або вказується,
коли слід роботу алгоритму вважати закінченою.
8
5.
Алгоритм повинен бути результативним, тобто зупинятися після
кінцевого числа кроків (залежного від вхідних даних) з видачею результату.
Дана властивість іноді називають збіжністю алгоритму.
6.
Алгоритм передбачає наявність механізму реалізації, який за
описом алгоритму породжує процес обчислення на основі вхідних даних.
Передбачається, що опис алгоритму та механізм його реалізації кінцеві.
Можна помітити аналогію з обчислювальними машинами. Вимога 1
відповідає цифровій природі ПК, вимога 2 – пам'ять ПК, вимога 3 – програмі
машини, вимога 4 – її логічній природі, вимоги 5, 6 – обчислювальному
пристрою і його можливостям.
Є також деякі риси неформального поняття алгоритму, щодо яких не
досягнуто остаточної угоди. Ці риси сформулюються у вигляді запитань і
відповідей.
7.
Чи слід фіксувати кінцеву границю для розміру вхідних даних?
8.
Чи слід фіксувати кінцеву границю для числа елементарних
кроків?
9.
Чи слід фіксувати кінцеву границю для розміру пам'яті?
10.
Чи слід обмежити число кроків обчислення?
На всі ці питання далі приймається відповідь "НІ", хоча можливі й інші
варіанти відповідей, оскільки у фізично існуючих ПК відповідні розміри
обмежені. Проте теорія, що вивчає алгоритмічні обчислення, здійсненні в
принципі, не повинна рахуватися з такого роду обмеженнями, оскільки їх
можна подолати принаймні в принципі (наприклад, взагалі кажучи, будь-який
фіксований розмір пам'яті завжди можна збільшити на одну клітинку).
Таким чином, уточнення поняття алгоритму пов'язано з уточненням
алфавіту даних і форми їх подання, пам'яті і розміщення в ній даних,
елементарних кроків алгоритму та механізму реалізації алгоритму. Однак ці
поняття самі потребують уточнення. Ясно, що їхні словесні визначення
зажадають введення нових понять, для яких у свою чергу, знову будуть
потрібні уточнення і т.д. Тому в теорії алгоритмів прийнятий інший підхід,
заснований на конкретній алгоритмічної моделі, в якій всі сформульовані
вимоги виконуються очевидним чином. При цьому використовувані
алгоритмічні моделі універсальні, тобто моделюють будь-які інші розумні
алгоритмічні моделі, що дозволяє зняти можливе заперечення проти такого
підходу: Чи не приводить жорстка фіксація алгоритмічної моделі до втрати
9
спільності формалізації алгоритму? Тому дані алгоритмічні моделі
ототожнюються з формальним поняттям алгоритму. Надалі будуть розглянуті
основні типи алгоритмічних моделей, що розрізняються трактуваннями, що
таке алгоритм.
Перший тип трактує алгоритм як деякій детермінований пристрій,
здатний виконувати в кожен момент лише строго фіксовану множину
операцій. Основною теоретичною моделлю такого типу є машина Тьюринга,
запропонована ним у 30-х роках, яка зробила суттєвий вплив на розуміння
логічної природи розроблюваних ЕОМ. Іншою теоретичною моделлю даного
типу є машина довільного доступу (МДД) – введена досить недавно (у 70-х
роках) з метою моделювання реальних обчислювальних машин та отримання
оцінок складності обчислень.
Другий тип пов'язує поняття алгоритму з традиційним уявленням –
процедурами обчислення значень числових функцій. Основною теоретичною
моделлю цього типу є рекурсивні функції – історично перша формалізація
поняття алгоритму.
Третій тип алгоритмічних моделей – це перетворення слів у довільних
алфавітах, в яких операціями є заміни фрагментів слів іншим словом.
Основною теоретичною моделлю цього типу є нормальні алгоритми
Маркова.
Теорія алгоритмів має істотний вплив на розвиток ЕОМ і практику
програмування. В теорії алгоритмів передбачені основні концепції, які
закладені в апаратуру і мови програмування ЕОМ. Згадувані вище основні
алгоритмічні моделі математично еквівалентні. Але на практиці вони істотно
розрізняються ефектами складності, що виникають при реалізації алгоритмів,
і породили різні напрямки в програмуванні. Так, мікропрограмування
будується на ідеях машин Тьюринга, структурне програмування запозичило
свої конструкції з теорії рекурсивних функцій, мови символьної обробки
інформації (РЕФАЛ, ПРОЛОГ) беруть початок від нормальних алгоритмів
Маркова та систем Посту.
На основі теорії алгоритмів в даний час отримані практичні
рекомендації, що набувають все більшого поширення в області проектування
і розробки програмних систем. Результати теорії алгоритмів набувають
особливого значення для криптографії.
Першим алгоритмом у вигляді кінцевої послідовності елементарних дій,
що вирішують поставлену задачу, вважається запропонований Евклідом в III
10
столітті до нашої ери Алгоритм знаходження найбільшого загального
дільника двох чисел (алгоритм Евкліда).
Початковою точкою відліку сучасної теорії алгоритмів вважають роботу
німецького математика Курта Геделя [3] (1931 рік – теорема про неповноту
символічних логік.
Перші фундаментальні роботи з теорії алгоритмів були опубліковані
незалежно в 1936 році роки Аланом Тьюрингом, Алоізом Черчем і Емілем
Постом. Запропоновані ними машина Тьюринга, машина Посту і лямбда-
числення Черча були еквівалентними формалізмами алгоритму.
Важливим розвитком цих робіт стало формулювання і доказ алгоритмічно
нерозв'язних проблем.
У 1950-ті роки істотний внесок у теорію алгоритмів внесли роботи
Колмогорова і Маркова.
1.2
Історичний огляд
До 1960-70-их років оформилися наступні напрямки в теорії алгоритмів:
• Класична теорія алгоритмів :
-
формулювання завдань в термінах формальних мов,
-
поняття завдання дозволу,
-
введення класів складності,
-
формулювання в 1965 році Едмондсі проблеми P = NP,
-
відкриття класу NP-повних задач і його дослідження) [5].
• Теорія асимптотичного аналізу алгоритмів:
-
поняття складності і трудомісткості алгоритму,
-
критерії оцінки алгоритмів,
-
асимптотичний аналіз трудомісткості або часу виконання, в
розвиток якої внесли істотний внесок Кнут, Ахо, Хопкрофта,
Ульман, Карпо [1, 4].
• Теорія практичного аналізу обчислювальних алгоритмів:
-
одержання явних функції трудомісткості,
-
інтегральний аналіз функцій,
-
практичні критерії якості алгоритмів,
-
методика вибору раціональних алгоритмів, основоположною
роботою в цьому напрямку слід вважати фундаментальну працю
Д. Кнута «Мистецтво програмування для ЕОМ» [4].