Файл: M51_21_-_kopia.pdf

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ 

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ХАРЧОВИХ ТЕХНОЛОГІЙ 

ЗАТВЕРДЖУЮ 

В.о. ректора  ______________ А. І. Українець 

(підпис) 

                                                                 «___» ____________2015 

р. 

Т.М. ГОРЛОВА 

К.Є. БОБРІВНИК 

Н.В. ЛІМАНСЬКА 

ТЕОРІЯ АЛГОРИТМІВ 

КОНСПЕКТ ЛЕКЦІЙ 

для студентів напряму підготовки 6.050101 «Комп'ютерні науки» 

денної та заочної форм навчання  

Всі цитати, цифровий та фактичний 
матеріал, бібліографічні відомості 
перевірені. Написання одиниць 
відповідає стандартам 

Підпис(и) автора(ів)________________ 

«____»  ______________ 2015 

р. 

СХВАЛЕНО 

на засіданні кафедри 

інформаційних систем 

Протокол № 10 

від 17.02.2015 р. 

Реєстраційний номер  
електронного конспекту лекцій 
у НМВ  51.21-12.03.2015  

КИЇВ НУХТ 2015 

2 

Горлова Т.М. Теорія алгоритмів. [Електронний ресурс]: конспект лекцій 

для  студентів  напряму  підготовки  6.050101  «Комп'ютерні  науки»  денної  та 
заочної  форм  навчання / Т.М. Горлова,  К.Є. Бобрівник,  Н.В. Ліманська  –  К.: 
НУХТ, 2015. – 95 с.

Рецензент: Маноха Л.Ю., канд. техн. наук, доц. 

Т.М. ГОРЛОВА, канд. техн. наук, доц. 

К.Є. БОБРІВНИК 

Н.В. ЛІМАНСЬКА 

Подано в авторський редакції 

©Т.М. Горлова, 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