Алгоритми та складність

Галузь знань: 12 Інформаційні технології
Спеціальність: 121 Інженерія програмного забезпечення
Освітня програма: Програмна інженерія

Викладачі: Викладається: в 3-му та 4-му семестрі бакалаврату.
Загальний обсяг: 210 год, з яких:
  • Лекції – 56 год.
  • Лабораторні заняння – 42 год.
  • Самостійна робота – 108 год.

Мета та завдання дисципліни

Мета та завдання дисципліни – детальне вивчення та аналіз складності основних алгоритмів і структур даних, що використовуються в програмуванні.

Предмет дисципліни

Предмет навчальної дисципліни Алгоритми та складність включає в себе розгляд низки різноманітних структур даних та алгоритмів, що використовуються в програмуванні з аналізом їх ефективності.

В результаті вивчення навчальної дисципліни студент повинен
знати:
  • основні структури даних і алгоритми, що використовуються в програмуванні та їх ефективність;
  • методи аналізу складності алгоритмів.
та вміти:
  • проводити аналіз ефективності алгоритмів;
  • вибирати оптимальні структури даних та алгоритми при розв'язанні конкретних задач;
  • за необхідності створювати власні алгоритми, що базуються на модифікації відомих технік і обґрунтовувати їх ефективність.

Вимоги до знань та вмінь

Для вивчення курсу Алгоритми та складність студент повинен прослухати наступні курси:
  • дискретна математика,
  • алгебра та геометрія,
  • математичний аналіз,
  • основи програмування,
  • програмування.

Програма курсу

Змістовий модуль 1: Вступ до аналізу алгоритмів. Ефективні сортування.

Тема 1: Вступ до предмету. Поняття алгоритму та аналізу алгоритмів.
  • Поняття алгоритму.
  • Приклади алгоритмів.
  • Алгоритм як технологія: процесс проектування та аналізу.
  • Базові структури даних та абстрактні типи даних.
  • Аналіз алгоритмів: просторова і часова ефективність.
  • Ефективність алгоритму в різних випадках: найкращому, найгіршому, в середньому.
Тема 2: Зростання функцій.
  • Порядок зростання функцій.
  • Асимптотичні позначення.
  • Порівняння функцій.
  • Основні асимптотичні класи ефективності.
  • P, NP та NP-повні задачі.
Тема 3: Аналіз нерекурсивних алгоритмів.
  • Загальна схема аналізу нерекурсивних алгоритмів.
  • Поняття інваріанту циклу.
  • Використання інваріантів циклу для доведення коректності алгоритму.
  • Метод декомпозиції (принцип "розподіляй та владарюй").
  • Приклади аналізу.
Тема 4: Аналіз рекурсивних алгоритмів. Рекурентні співвідношення.
  • Рекурсивні алгоритми.
  • Поняття рекурентного співвідношення.
  • Приклади рекурентних співвідношень для оцінки часу виконання алгоритмів.
  • Методи розв'язання рекурентних співвідношень:
    • методи підстановок,
    • метод дерев рекурсії,
    • основний метод.
Тема 5: Ефективні сортування.
  • Бінарна піраміда як структура даних та її властивості.
  • Пірамідальне сортування, його коректність і оцінка складності.
  • Реалізація черги з пріоритетами на основі піраміди.
  • Швидке сортування та його аналіз.
  • Сортування злиттям, його ефективність.
  • Нижня оцінка алгоритмів сортування, що використовують порівняння.
  • Алгоритми сортування за лінійний час та їх аналіз:
    • сортування підрахунком,
    • порозрядне сортування,
    • сортування черпаками.
  • Медіани та порядкові статистики, алгоритми їх пошуку за лінійний час.
Модульна контрольна робота 1

Змістовий модуль 2: Застосування різних методів проектування алгоритмів.

Тема 6: Декомпозиція та зменшення розміру задачі.
  • Алгоритми зі змінним зменшенням розміру задачі.
  • Інтерполяційний пошук.
  • Розв'язання нелінійних рівнянь.
  • Аналогії бінарного та інтерполяційного пошуків з методами дихотомії та хорд.
  • Метод декомпозиції при множенні великих чисел і матриць.
  • Алгоритм Карацуби.
  • Метод Штрассена.
Тема 7: Покращення вхідних даних. Алгоритми пошуку підрядка.
  • Постановка задачі пошуку підрядка.
  • Класифікація методів пошуку підрядка, мотивація вибору алгоритма.
  • Алгоритм Боєра-Мура та його варіації.
  • Алгоритм Кнута-Морріса-Пратта, пошук підрядків з використанням скінченних автоматів.
  • Z-функція та префікс-функція.
  • Алгоритм Рабіна-Карпа, алгоритм Shift-Or.
Модульна контрольна робота 2

Змістовий модуль 3: Структури даних.

Тема 8: Елементарні структури даних.
  • Динамічні множини та типові операції на них.
  • Елементарні структури даних (стеки, черги, зв'язані списки), їх реалізація та аналіз.
  • Реалізація вказівників та об'єктів, управління пам'яттю.
  • Представлення дерев з коренем.
Тема 9: Хеш-таблиці.
  • Поняття хеш-таблиці, її застосування.
  • Таблиці з прямою адресацією.
  • Колізії та їх розв'язання методом ланцюжків.
  • Хеш-функції.
  • Методи побудови хеш-функцій:
    • метод поділу,
    • метод множення,
    • універсальне хешування.
  • Відкрита адресація: методи і їх аналіз.
  • Ідеальне хешування.
Тема 10: Бінарні дерева пошуку. Збалансовані дерева пошуку.
  • Дерево пошуку як структура даних.
  • Аналіз операцій над бінарними деревами пошуку.
  • Випадок однакових ключів.
  • Збалансовані дерева пошуку.
  • Червоно-чорні дерева, їх властивості, представлення і аналіз.
  • Повороти.
  • Вставка та видалення вузла з червоно-чорного дерева, відновлення червоно-чорних властивостей.
  • Огляд інших збалансованих дерев пошуку:
    • АВЛ-дерева,
    • АА-дерева,
    • розширювані дерева,
    • декартові дерева.
Тема 11: Розширення структур даних.
  • Задачі розширення структур даних.
  • Розширення структур даних на прикладі розширення червоно-чорних дерев: дерево порядкової статистики.
  • Теорема про розширення червоно-чорних дерев.
  • Персистентні динамічні множини.
Тема 12: В-дерева.
  • В-дерева як узагальнення дерев пошуку.
  • Структури даних у вторинній пам'яті.
  • Означення та властивості В-дерева.
  • Основні операції над В-деревом, їх аналіз; розбиття вузла.
  • Різновиди В-дерев:
    • В+-дерева,
    • В*-дерева,
    • 2-3 дерева,
    • 2-3-4-дерева.
Тема 13: Піраміди злиття.
  • Поняття пірамід злиття.
  • Біноміальні дерева, лема про їх властивості.
  • Біноміальна піраміда.
  • Представлення біноміальних пірамід.
  • Основні операції та їх аналіз.
  • Злиття біноміальних пірамід.
  • Поняття пірамід Фібоначчі: означення і представлення.
  • Функція потенціалу для пірамід Фібоначчі.
  • Невпорядковані біноміальні дерева, їх властивості.
  • Основні операції над пірамідами Фібоначчі та їх аналіз.
  • Оцінка максимальної степені вузла.
Тема 14: Дерева ван Емде Боаса.
  • Поняття дерева ван Емде Боаса.
  • Основні операції та їх аналіз.
  • Особливості, переваги і недоліки дерева ван Емде Боаса.
Модульна контрольна робота 3

Змістовий модуль 4: Алгоритми на графах.

Тема 15: Представлення графів. Елементарні алгоритми на графах.
  • Стандартні представлення графів.
  • Пошук в глибину, класифікація ребер.
  • Пошук в ширину.
  • Топологічне сортування.
  • Зв'язність, сильно зв'язні компоненти.
  • Ейлерові цикли.
Тема 16: Жадібні алгоритми. Пошук мінімального кістякового дерева.
  • Жадібний підхід до розв'язання задач.
  • Кістякові дерева.
  • Задача побудови мінімального кістякового дерева.
  • Алгоритми Прима та Крускала.
Тема 17: Пошук найкоротших шляхів з однієї вершини.
  • Постановки задач про найкоротші шляхи.
  • Найкоротші шляхи та ослаблення (релаксація).
  • Алгоритм Беллмана-Форда.
  • Найкоротші шляхи з однієї вершини в орієнтованих ациклічних графах.
  • Алгоритм Дейкстри.
Тема 18: Динамічне програмування. Пошук найкоротших шляхів між усіма парами вершин.
  • Елементи динамічного програмування.
  • Задача про найкоротші шляхи та множення матриць.
  • Алгоритми Воршелла і Флойда.
Модульна контрольна робота 4

Рекомендована література

Основна:

  1. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Стайн. Алгоритмы – построение и анализ. Второе издание. – М.: ИД "Вильямс", 2005.
  2. А. Левитин. Алгоритмы: введение в разработку и анализ. – М.: ИД "Вильямс", 2006.
  3. Д. Кнут. Искусство программирования. Т.1: Основные алгоритмы. – М.: Мир, 1976.
  4. Д. Кнут. Искусство программирования. Т.2: Получисленные алгоритмы. – М.: Мир, 1976.
  5. Д. Кнут Искусство программирования. Т.3: Сортировка и поиск. – М.: Мир, 1976.

Додаткова:

  1. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы. – М.: ИД "Вильямс", 2000.
  2. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
  3. Дж. Макконнелл. Основы современных алгоритмов. Второе издание. – М.: Техносфера, 2004.
  4. Р. Седжвик. Фундаментальные алгоритмы на C++. – М.: DiaSoft, 2001.
  5. Д. Гасфилд. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. – СПб.: BHV-СПб, 2008.