ЗМІСТ
РОЗДІЛ 1. БАЗОВІ ПОНЯТТЯ ТЕОРІЇ АЛГОРИТМІВ.................15

1.1. Визначення інформації.......................15

1.2. Визначення алгоритму.................17

1.3. Виконавці алгоритмів..................18

1.4. Способи описання алгоритмів..............20

1.5. Властивості аліпритмів.........................21

1.6. Поняття обчислювальної складності...........21

1.7. Класи алгоритмів..............22

1. 7.1. Експоненційні алгоритми та перебір..................22

1.7.2. Алгоритм із повернення назад...........23

1.7. 3. Машини Тюринга..................25

1. 7. 4. Рекурсія та її використання....28

1.7.5. Теза Чорча. Алгоритмічно нерозв'язані проблеми.........31

Резюме.............31

Контрольні питання.............32

Тести для закріплення матеріалу..............33

РОЗДІЛ 2. ПОНЯТТЯ Структури даних. Рівні подання структури даних.......... 35

2.1. Поняття структури даних...............35

2.2 Рівні описування даних........35

2.3. Класифікація структур даних у програмах користувача й у пам'яті комп'ютера..............36

2.4. Основні види складених типів даних..........37

2.5. Структури даних у пам'яті комп'ютера................37

2. 5. 1. Структури даних в оперативній пам'яті..........38

2. 5. 2. СД у зовнішній пам'яті.................38

Резюме.................38
Контрольні питання................39

Тести для закріплення матеріалу....................39

РОЗДІЛ 3. СТРУКТУРНІ ТА ЛІНІЙНІ ТИПИ ДАНИХ........41

3.1. Поняття структури даних типу "масив".....41

3.2. Набір допустимих операцій для СД типу "масив"................42

3.3. Дескриптор СД типу "масив"........42

3.4. Ефективність масивів............43

3.5. Зберігання багатовимірних масивів..........44

3.6. СД типу "множина".................46

3.7. СД типу "запис (прямий декартовий добуток)"...47

3.8. СД типу "таблиця".........49

3.9. СД типу «стек»....50

3.9.1. Дескриптор СД типу "стек"...........52

3.9.2. Області застосування СД типу "стек"......52

3.10. СД типу "черга"......53

3.11. СД типу "дек"....55

Резюме......60

Контрольні запитання.....60

Тести для закріплення матеріалу......61

РОЗДІЛ 4. ЗВ'ЯЗНИЙ РОЗДІЛ ПАМ'ЯТІ......64

4.1. СД типу вказівник....64

4.2. Статистичні й динамічні змінні...65

4.2.1. Відмінності між статистичними та динамічними змінними.....65

4.2.2. Створення та знищення динамічних змінних......65

4.3. Класифікація СД типу "зв'язний список"......66

4.4. СД типу "лінійний однозв'язний список"...67

4.5. СД типу "циклічний лінійний список"...69

4.6. СД типу "двозв'язний лінійний список"......69

4.7. Багатозв'язаний список. Приклади...........70

Резюме...........72

Контрольні запитання............72

Тести для закріплення матеріалу........73

РОЗДІЛ 5. ХЕШУВАННЯ ДАНИХ.....78

5.1. Поняття хеш-функції....78

5.2. Алгоритми хешування.....80

5.3. Динамічне хешування.....80

5.3.1. Означення динамічного хешування...80

5.3.2. Розширюване хешування... 81

5.3.3. Функції, що зберігають ключі...82

5.3. Методи розв'язування колізій.... 82

5.4. Переповнення таблиці і рехешування...85

5.5. Оцінювання якості хеш-функції.......86

Резюме....88

Контрольні запитання......89

Тести для закріплення матеріалу....89

РОЗДІЛ 6. НЕЛІНІЙНІ СТРУКТУРИ ДАНИХ: ДЕРЕВА....92

6.1. Дерево...92

6.1.2. Бінарне дерево....93

6.1.4. Алгоритми проходження дерев углиб і вшир.... 95

6.1.5. Подання дерев у вигляді бінарних....96

6.1.5. Застосування бінарних дерев в алгоритмах пошуку.... 100

6.1.6. Операція включення в СД типу "бінарне дерево".......101

Аналіз алгоритму пошуку ...102

6.1.7. Операція виключення з бінарного дерева..... 102

6.1.7. Операція виключення з бінарного дерева.....102

6.1.8. Застосування бінарних дерев.... 104

6.2. Види бінарних дерев..... 107

6.2.1. Збалансоване дерево.... 107

6.2.2. Червоно-чорне дерево.....107

Резюме....114

Контрольні запитання...115

Тести для закріплення матеріалу....115

РОЗДІЛ 7. НЕЛІНІЙНІ СТРУКТУРИ ДАНИХ: ГРАФ... 118

7.1. Поняття графу ....118

7.2. Поняття графу в пам'яті комп'ютера.....119

7.3. Алгоритми проходження графу.....121

7.3.1. Алгоритми проходження графу в глиб....122

7.3.2. Алгоритм проходження графу вшир...124

7.4. Інші задачі на графах ....125

7.4.1. Топологічне сортування....125

7.4.2. Пошук мостів.....125

7.4.3. Задача про максимальний потік...126

7.4.4. Найкоротша відстань між вершинами (алгоритм Дейкстри)....127

Резюме....128

Контрольні завдання... 129

Тести для закріплення матеріалу...129

РОЗДІЛ 8. АЛГОРИТМИ ПОШУКУ

8.1. Загальна класифікація алгоритмів пошуку......132

8.2. Лінійний пошук .............132

8.3. Двійковий (бінарний) пошук елемента в масиві ..............133

8.4. Пошук методом Фібоначчі ............134

8.5. М-блоковий пошук..........135

8.6. Методи обчислення адреси.......136

8.7. Інтерполяційний пошук елемента в масиві...... 137

8.8. Бінарний пошук із визначенням найближчих вузлів....138

8.9. Пошук у таблиці.....140

8.10. Прямий пошук рядка....141

8.11. Алгоритм Ахо-Корасик....142

8.12. Алгоритм Моріса-Прата....142

8.13. Алгоритм Кнута, Моріса і Пратта....144

8.14. Алгоритм Рабіна-Карпа....145

8.15. Алгоритм Боуера і Мура.... 147

8.16. Алгоритм Хорепула......148

8.17. Порівняння методів пошуку.....149

Резюме...150

Контрольні запитання...150

Тести для закріплення матеріалу......150

РОЗДІЛ 9. АЛГОРИТМИ СОРТУВАННЯ......152

9.1. Методи внутрішнього сортування......152

9.1.1. Медод простого включення...153

9.1.3. Сортування шляхом підрахунку...155

9.1.2. Метод Шелла....155

9.1.4. Обмінне сортування....157

9.1.5. Сортування вибором....160

9.1.6. Сортування поділом (Хоара)....161

9.1.7. Сортування за допомогою дерева.....162

9.1.8. Пірамідальне сортування....165

9.1.9. Побудова піраміди методом Флойда.... 168

9.1.10. Сортування злиттям....169

9.1.11. Методи порозрядного сортування.....171

9.2. Методи зовнішнього сортування.....176

9.2.1. Пряме злиття.... 177

9.2.2. Природне злиття....178

9.2.3. Збалансоване багатошляхове злиття....181

9.2.4. Багатофазне сортування....181

Резюме....181

Контрольні запитання....182

Тести для закріплення матеріалу....182

РОЗДІЛ 10. ЖАДІБНІ АЛГОРИТМИ......186

10.1. Поняття жадібного алгоритму.....186

10.2. Відмінність між динамічним програмуванням і жадібним алгоритмом....188

10.3. Приклади жадібних алгоритмів .....188

10.3.2. Алгоритми Шеннона-Фано....188

10.3.3. Алгоритм Хафмана....193

10.3.4. Алгоритм Пріма......193

Резюме ....193

Контрольні запитання...194

Тести для закріплення матеріалу....194

Список термінів....195

Література до теоритичного курсу....198

ДОДАТКИ....199


ЗАВДАННЯ ДО ЛАБОРАТОРНИХ РОБІТ.....199

Лабораторна робота №1.......199

Лабораторна робота №2.........199

Лабораторна робота №3......200

Лабораторна робота №4......203

Лабораторна робота №5.....205

Лабораторна робота №6.....207

Лабораторна робота №7....209

Лабораторна робота №8....209

Лабораторна робота №9......210

Лабораторна робота №10....2111

У посібнику розглядаються статистичні й динамічні структури даних і методи роботи з деревами та грифами. Проаналізовано алгоритми пошуку та сортування. Уводиться поняття хеш-функції та подаються правила її вибирання. Проаналізовано поняття обчислювальної складності, визначено класи алгоритмів та задач. Буде корисним для студентів, що навчаються за напрямом підготовки фахівців "Комп'ютерної науки", "Системний аналіз".