Алгоритми та структури даних

Анотація курсу: Курс «Алгоритми та структури даних» має розвинути у студентів навички розробки та аналізу алгоритмів, а також розуміння та використання різноманітних структур даних для покращення роботи тих або інших алгоритмів. Курс включає в себе розгляд теорії складностей алгоритмів.

Теми:

Розділ І. Сортування

1. Вступ до алгоритмів. Сортування злиттям. Аналіз алгоритмів. Асимптотична

нотація.

2. Метод декомпозиції. Сортування злиттям. Інверсії. Рекурентні співвідношення.

3. Швидке сортування. Рандомізоване швидке сортування. Порядкові статистики.

Розділ ІІ. Структури даних

4. Піраміди. Черги з пріоритетами. Heapsort.

5. Бінарні дерева пошуку.

6. Хеш-таблиці. Хеш-функції.

Розділ ІІІ. Просунуті методи

7. Амортизаційний аналіз.

8. Жадібні алгоритми.

9. Динамічне програмування.

Розділ IV. Алгоритми на графах

10. Базові алгоритми на графах. Найкоротші шляхи.

11. Мережі та потоки.

Розділ V. Теорія складностей

12. Класи складності. Ефективні алгоритми. Задачі P та NP.

 

13. NP-повні задачі. Доведення NP-повноти типових задач.

Викладачі:

Дмитро Кушнір

Ключові факти:

Навчальний семестр:

Кількість кредитів: 6 ECTS

Освітня програма:

Комп’ютерні науки,

ІТ та бізнес-аналітика