3MICT

РОЗДІЛ 1. БАЗОВІ ПОНЯТТЯ ТЕОРІЇ АЛГОРИТМІВ
1.1. Визначення інформації
1.2. Визначення алгоритму
1.3. Виконавці алгоритмів
1.4. Способи описання алгоритмів
1.5. Властивості алгоритмів
1.6. Поняття обчислювальної складності
1.7. Класи алгоритмів
1.7.1. Експоненційні алгоритми та перебір
1.7.2. Алгоритм із поверненнями назад
1.7.3. Машини Тьюринга
1.7.4. Рекурсія та її використання
1.7.5. Теза Чорча. Алгоритмічно нерозв'язні проблеми

РОЗДІЛ 2. ПОНЯТТЯ СТРУКТУРИ ДАНИХ. РІВНІ ПОДАННЯ СТРУКТУР ДАНИХ
2.1. Поняття структури даних
2.2. Рівні описування даних
2.3. Класифікація структур даних у програмах користувача й у пам'яті комп'ютера
2.4. Основні види складених типів даних
2.5. Структури даних у пам'яті комп'ютера
2.5.1. Структури даних в оперативній пам'яті
2.5.2. СД у зовнішній пам'яті

РОЗДІЛ 3. СТРУКТУРНІ ТА ЛІНІЙНІ ТИПИ ДАНИХ
3.1. Поняття структури даних типу «масив»
3.2. Набір допустимих операцій для СД типу «масив»
3.3. Дескриптор СД типу «масив»
3.4. Ефективність масивів
3.5. Зберігання багатовимірних масивів
3.6. СД типу «множина»
3.7. СД типу «запис (прямий декартовий добуток)»
3.8. СД типу «таблиця»
3.9. СД типу «стек»
3.9.1. Дескриптор СД типу «стек»
3.9.2. Області застосування СД типу «стек».
3.10. СД типу «черга»
3.11. СД типу «дек»

РОЗДІЛ 4. ЗВ'ЯЗНИЙ РОЗПОДІЛ ПАМ'ЯТІ
4.1. СД типу вказівник
4.2. Статичні й динамічні змінні
4.2.1. Відмінності між статичними та динамічними змінними
4.2.2. Створення та знищення динамічних змінних
4.3. Класифікація СД типу «зв'язний список»
4.4. СД типу «лінійний однозв'язний список
4.5. СД типу «циклічний лінійний список»
4.6. СД типу «двозв'язний лінійний список»
4.7. Багатозв'язний список. Приклади

РОЗДІЛ 5. ХЕШУВАННЯ ДАНИХ
5.1. Поняття хеш-функції
5.2. Алгоритми хешування
5.3. Динамічне хешування
5.3.1. Означення динамічного хешування
5.3.2. Розширюване хешування
5.3.3. Функції, що зберігають ключі
5.3. Методи розв'язування колізій
5.4. Переповнення таблиці і рехешування
5.5. Оцінювання якості хеш-функцій

РОЗДІЛ 6. НЕЛІНІЙНІ СТРУКТУРИ ДАНИХ: ДЕРЕВА
6.1. Дерево
6.1.1. Визначення дерева
6.1.2. Бінарне дерево
6.1.3. Подання дерев у зв'язній пам'яті комп'ютера
6.1.4. Алгоритми проходження дерев углиб і вшир
6.1.5. Подання дерев у вигляді бінарних
6.1.5. Застосування бінарних дерев в алгоритмах пошуку
6.1.6. Операція включення в СД типу «бінарне дерево». Аналіз алгоритму пошуку
6.1.7. Операція виключення з бінарного дерева
6.1.8. Застосування бінарних дерев
6.2. Види бінарних дерев
6.2.1. Збалансоване дерево
6.2.2. Червоно-чорне дерево

РОЗДІЛ 7. НЕЛІНІЙНІ СТРУКТУРИ ДАНИХ: ГРАФ
7.1. Поняття графу
7.2. Подання графу в пам'яті комп'ютера
7.3. Алгоритми проходження графу
7.3.1. Алгоритм проходження графу вглиб
7.3.2. Алгоритм проходження графу вшир
7.4. Інші задачі на графах
7.4.1. Топологічне сортування
7.4.2. Пошук мостів
7.4.3. Задача про максимальний потік
7.4.4. Найкоротша відстань між вершинами (алгоритм Дейкстри)

РОЗДІЛ 8. АЛГОРИТМИ ПОШУКУ
8.1. Загальна класифікація алгоритмів пошуку
8.2. Лінійний пошук
8.3. Двійковий (бінарний) пошук елемента в масиві
8.4. Пошук методом Фібоначчі
8.5. М-блоковий пошук
8.6. Методи обчислення адреси
8.7. Інтерполяційний пошук елемента в масиві
8.8. Бінарний пошук із визначенням найближчих вузлів
8.9. Пошук у таблиці
8.10. Прямий пошук рядка
8.11. Алгоритм Ахо – Корасик
8.12. Алгоритм Моріса – Прата
8.13. Алгоритм Кнута, Моріса і Пратта
8.14. Алгоритм Рабіна – Карпа
8.15. Алгоритм Боуера і Мура
8.16. Алгоритм Хорснула
8.17. Порівняння методів пошуку

РОЗДІЛ 9. АЛГОРИТМИ СОРТУВАННЯ
9.1. Методи внутрішнього сортування
9.1.1. Метод простого включення
9.1.3. Сортування шляхом підрахунку
9.1.2. Метод Шелла
9.1.4. Обмінне сортування
9.1.5. Сортування вибором
9.1.6. Сортування поділом (Хоара)
9.1.7. Сортування за допомогою дерева
9.1.8. Пірамідальне сортування
9.1.9. Побудова піраміди методом Флойда
9.1.10. Сортування злиттям
9.1.11. Методи порозрядного сортування
Порозрядне сортування для масивів
Ефективність порозрядного сортування
9.2. Методи зовнішнього сортування
9.2.1. Пряме злиття
9.2.2. Природне злиття
9.2.3. Збалансоване багатошляхове злиття
9.2.4. Багатофазне сортування

РОЗДІЛ 10. ЖАДІБНІ АЛГОРИТМИ
10.1. Поняття жадібного алгоритму
10.2. Відмінність між динамічним програмуванням і жадібним алгоритмом
10.3. Приклади жадібних алгоритмів
10.3.1. Алгоритм Краскала
10.3.2. Алгоритм Шеннона – Фано
10.3.3. Алгоритм Хафмана
10.3.4. Алгоритм Пріма

Резюме
Контрольні запитання
Тести для закріплення матеріалу
Список терміні
Література до теоретичного курсу
ДОДАТКИ

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

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

Гриф надано М-вом освіти і науки України