У посібнику розглядаються статичні й динамічні структури даних і методи роботи з деревами та графами. Проаналізовано алгоритми пошуку та сортування. Уводиться поняття хеш-функції та подаються правила її вибирання. Проаналізовано поняття обчислювальної складності, визначено класи алгоритмів та задач. Буде корисним для студентів, що навчаються за напрямом підготовки фахівців "Комп'ютерні науки", "Системний аналіз". ЗМІСТ РОЗДІЛ 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. Алгоритми хешування 79 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.1. Визначення дерева 92 6.1.2. Бінарне дерево 93 6.1.3. Подання дерев у зв'язній пам'яті комп'ютера 93 6.1.4. Алгоритми проходження дерев углиб і вшир 95 6.1.5. Подання дерев у вигляді бінарних 96 6.1.6. Застосування бінарних дерев в алгоритмах пошуку 100 6.1.7. Операція включення в СД типу "бінарне дерево" 101 Аналіз алгоритму пошуку 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. Поняття графу '18 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. АЛГОРИТМИ ПОШУКУ 132 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 Порозрядне сортування для масивів 175 Ефективність порозрядного сортування 176 9.2. Методи зовнішнього сортування 176 9.2.1. Пряме злиття 177 9.2.2. Природне злиття 178 9.2.3. Збалансоване багатошляхове злиття 178 9.2.4. Багатофазне сортування 181 Резюме 181 Контрольні запитання 182 Тести для закріплення матеріалу 182 РОЗДІЛ 10. ЖАДІБНІ АЛГОРИТМИ 186 10.1. Поняття жадібного алгоритму 186 10.2. Відмінність між динамічним програмуванням і жадібним алгоритмом 188 10.3. Приклади жадібних алгоритмів 188 10.3.1. Алгоритм Краскала 188 10.3.2. Алгоритм Шеннона-Фано 188 10.3.3. Алгоритм Хафмана 189 10.3.4. Алгоритм Пріма 193 Резюме 1^3 Контрольні запитання 194 Тести для закріплення матеріалу 194 Список термінів 195 Література до теоретичного курсу 198 ДОДАТКИ. 199 ЗАВДАННЯ ДО ЛАБОРАТОРНИХ РОБІТ 199 Лабораторна робота МІ 199 Лабораторна робота N?2 200 Лабораторна робота №3 201 Лабораторна робота №4 203 Лабораторна робота М5 205 Лабораторна робота №6 207 Лабораторна робота М7. 209 Лабораторна робота №8 209 Лабораторна робота М9 210 Лабораторна робота №10 211