В. о ректора А. І. Українець (підпис) 2015 р. Т. М. Горлова к.Є. Бобрівник н. В. Ліманська теорія алгоритмів конспект

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ХАРЧОВИХ ТЕХНОЛОГІЙ
ЗАТВЕРДЖУЮ
В.о. ректора ______________ А. І. Українець
(підпис)
«___» ____________2015
р.
Т.М. ГОРЛОВА
К.Є. БОБРІВНИК
Н.В. ЛІМАНСЬКА
ТЕОРІЯ АЛГОРИТМІВ
КОНСПЕКТ ЛЕКЦІЙ
для студентів напряму підготовки 6.050101 «Комп'ютерні науки» денної та заочної форм навчання
Всі цитати, цифровий та фактичний матеріал, бібліографічні відомості перевірені. Написання одиниць відповідає стандартам
Підпис(и) автора(ів)________________
«____» ______________ 2015 р.
СХВАЛЕНО на засіданні кафедри
інформаційних систем
Протокол № 10 від 17.02.2015 р.
Реєстраційний номер електронного конспекту лекцій у НМВ 51.21-12.03.2015
КИЇВ НУХТ 2015

3
ЗМІСТ
1.ВВЕДЕННЯ В ТЕОРІЮ АЛГОРИТМІВ …………………………….…... 6 1.1 Основні поняття теорії алгоритмів ……………………………….. 6 1.2 Історичний огляд …………………………………………………… 10 1.3 Цілі і завдання теорії алгоритмів …………………………………. 11 1.4 Практичне застосування результатів теорії алгоритмів …………. 11 1.5 Формалізація поняття алгоритму …………………………………. 12 1.6 Питання для самоконтролю ……………………………………….. 14 2. МАШИНА ПОСТА ………………………………………………………. 15 2.1 Основні поняття та операції ………………………………………. 15 2.2 Фінітний 1 – процес ……………………………………………...... 16 2.3 Спосіб завдання проблеми та формулювання 1 …………………. 16 2.4 Принцип роботи …………………………………………………… 17 2.5 Питання для самоконтролю ………………………………………. 23 3. МАШИНА ТЬЮРІНГА ТА ПРОБЛЕМИ, ЯКІ НЕ
РОЗВ’ЯЗУЮТЬСЯ АЛГОРИТМІЧНО ………………………………….. 24 3.1. Машина Тьюринга ………………………………………………… 24 3.2 Властивості машини Тьюринга як алгоритму ……………………. 29 3.3 Проблеми, які не розв'язуються алгоритмічно ………………….. 30 3.4 Питання для самоконтролю ……………………………………….. 33 4. ВСТУП ДО АНАЛІЗУ АЛГОРИТМІВ ………………………………….. 34 4.1 Порівняльні оцінки алгоритмів …………………………………… 34 4.2 Система позначень в аналізі алгоритмів …………………………. 35 4.3 Класифікація алгоритмів по виду функції трудомісткості ……… 36 4.4 Асимптотичний аналіз функцій ………………………………....... 38 4.5 Питання для самоконтролю ……………………………………….. 40 5. ТРУДОМІСТЬ АЛГОРИТМІВ ТА ЇХ ЧАСОВІ ОЦІНКИ ………....... 42 5.1. Елементарні операції в мові запису алгоритмів ………………… 42 5.2 Приклади аналізу простих алгоритмів …………………………… 43 5
.3 Перехід до часових оцінок ………………………………………… 45 5.4 Приклад поопераційного часового аналізу ………………………. 48 5.5 Питання для самоконтролю ……………………………………….. 50

4 6. ТЕОРІЇ СКЛАДНОСТІ ОБЧИСЛЕНЬ І КЛАСИ СКЛАДНОСТІ
ЗАДАЧ …………………………………………………………………….. 51 6.1 Теоретична межа трудомісткості завдання ……………………….. 51 6.2 Класи складності задач ……………………………………………. 52 6.3 Проблема P = NP …………………………………………………… 53 6.4 Клас NPC (NP – повні задачі) …………………………………....... 54 6.5 Приклади NP – повних задач ……………………………………… 56 6.5.1 Задача про виконуваність схеми ………………………………… 56 6.5.2 Задача про суму …………………………………………............... 57 6.5.3 Задача про клік …………………………………………………… 57 6.6 Питання для самоконтролю ……………………………………….. 58 7. ПРИКЛАД ПОВНОГО АНАЛІЗУ АЛГОРИТМУ ВИРІШЕННЯ
ЗАДАЧІ ПРО СУМУ …………………………………………………….. 59 7.1
Формулювання задачі і асимптотична оцінка ……………………. 59 7.2
Алгоритм точного рішення задачі про суму
(метод перебору) ……………………………………………………. 60 7.3
Аналіз алгоритму точного рішення задачі про суму …………….. 61 7.4
Питання для самоконтролю ………………………………………. 63 8. РЕКУРСИВНІ ФУНКЦІЇ І АЛГОРИТМИ ……………………………… 64 8.1 Рекурсивні функції ………………………………………………… 64 8.2 Рекурсивні процедури і функції ………………………………....... 66 8.3 Аналіз трудомісткості рекурсивних алгоритмів методом підрахунку вершин дерева рекурсії ……………………………….. 70 8.4 Рекурсивна реалізація алгоритмів ………………………………… 71 8.5 Аналіз трудомісткості алгоритму обчислення факторіала ….…… 74 8.6 Питання для самоконтролю ……………………………………….. 75 9. РЕКУРСИВНИЕ АЛГОРИТМИ І МЕТОДИ ЇХ АНАЛІЗУ ……………. 76 9.1 Логарифмічні тотожності ………………………………………….. 76 9.2 Методи рішення рекурсивних співвідношень …………………… 76 9.3 Рекурсивні алгоритми …………………………………………....... 78 9.4 Основна теорема про рекурентних співвідношеннях …………… 78 9.5 Питання для самоконтролю ……………………………………….. 79 10. ПРЯМИЙ АНАЛІЗ РЕКУРСИВНОГО ДЕРЕВА ВИКЛИКІВ ……….. 80

5 10.1 Алгоритм сортування злиттям …………………………………… 80 10.2 Злиття відсортованих частин (Merge) …………………………… 80 10.3 Підрахунок вершин в дереві рекурсивних викликів ………........ 81 10.4 Аналіз трудомісткості алгоритму сортування злиттям ………… 82 10.5 Питання для самоконтролю ……………………………………… 84 11. ТЕОРІЯ І АЛГОРИТМИ МОДУЛЯРНОЇ АРИФМЕТИКИ ………....... 85 11.1 Алгоритм зведення числа в цілу ступінь ………………………... 85 11.2
Відомості з теорії простих чисел ………………………………... 88 11.3
Питання для самоконтролю ……………………………………… 89 12.
КРИПТОСИСТЕМА RSA І ТЕОРІЯ АЛГОРИТМІВ ……………....... 90 12.1
Мультиплікативна група відрахувань за модулем n ……………. 90 12.2
Ступені елементів в Zn* і пошук великих простих чисел …....... 91 12.3
Криптосистема RSA ……………………………………………… 92 12.4 Крипостійкість RSA і складність алгоритмів
Факторизації ……………………………………………………… 93 12.5 Питання для самоконтролю ……………………………………… 94
ЛІТЕРАТУРА …………………………………………………………….......
95

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].

11
1.3
Цілі і завдання теорії алгоритмів
Можна виділити наступні цілі і співвіднесені з ними завдання, які вирішуються в теорії алгоритмів:
• формалізація поняття «алгоритм» і дослідження формальних алгоритмічних систем;
• формальний доказ алгоритмічної нерозв'язності ряду задач;
• класифікація завдань, визначення і дослідження класів складності;
• вивчення поняття складності алгоритмів;
• дослідження і аналіз рекурсивних алгоритмів;
• отримання явних функцій трудомісткості в цілях порівняльного аналізу алгоритмів;
• розробка критеріїв порівняльної оцінки якості алгоритмів.
1.4
Практичне застосування результатів теорії алгоритмів
Виділяють наступні два аспекти:
Теоретичний аспект: при дослідженні деякої задачі результати теорії алгоритмів дозволяють відповісти на питання чи є ця задача в принципі алгоритмічно вирішуваною.
У разі алгоритмічної розв'язності задачі – наступне важливе питання про приналежність цього завдання до класу NP-повних задач, при позитивному відповіді на який, можна говорити про істотні тимчасових витратах для отримання точного рішення для великих розмінностей вихідних даних.
Практичний аспект: методи та методики теорії алгоритмів дозволяють здійснити:
• раціональний вибір з відомої безлічі алгоритмів вирішення даного завдання з урахуванням особливостей їх застосування (наприклад, при обмеженнях на розмірність вихідних даних або обсягу додаткової пам'яті);
• отримання тимчасових оцінок вирішення складних завдань;
• отримання достовірних оцінок неможливості вирішення деякої задачі за певний час, що важливо для криптографічних методів;
• розробку і вдосконалення ефективних алгоритмів рішення задач в