Довідка

Практичне заняття 14. Фундаментальні алгоритми на графах та деревах

Дізнаємось

Що таке графи та дерева як структури даних.
Які бувають типи графів (орієнтовані, неорієнтовані, зважені).
Як представляти графи у вигляді списку суміжності та матриці суміжності.
Як працюють алгоритми обходу графів: DFS і BFS.
Що таке дерево пошуку та як його будувати.
Як виконувати базові операції з вузлами дерева (додавання, пошук, видалення).

Навчимось

Реалізовувати графи різними способами в Python.
Виконувати пошук у глибину (DFS) і пошук у ширину (BFS).
Створювати та обходити двійкові дерева.
Аналізувати зв’язність графів.
Використовувати структури графів для розв’язання задач реального світу.

Матеріали

Доступно тільки для зареєстрованих користувачів

Проблемні питання

Доступно тільки для зареєстрованих користувачів

Д.з.

Доступно тільки для зареєстрованих користувачів

№	Тема
3 лекції
1	Лекція 1. Поняття структур даних та їх класифікація. Формалізація поняття алгоритму. Основні напрямки в теорії алгоритмів
2	Лекція 2. Масиви. Стеки. Черги. Дек
3	Лекція 3. Зв’язні списки. Хеш-таблиці
4	Лекція 4. Пряма адресація. Хеш-функції.
5	Лекція 5. Двійкові дерева пошуку
6	Лекція 6. Сортування вибором та обмінне сортування. Сортування злиттям. Швидке сортування
7	Лекція 7. Сортування заздалегідь. Збалансовані дерева пошуку
8	Лекція 8. Послідовний пошук. Бінарний пошук. Методи, засновані на порівнянні ключів або на цифрових властивостях ключів
9	Лекція 9. Генератори псевдо випадкових чисел. Властивості випадкових та псевдо випадкових чисел. Недоліки генераторів псевдовипадкових чисел. Лінійний конгруентний метод.
10	Лекція 10. Представлення графа. Вершини. Ребра. Орієнтовані та неорієнтовані графи. Список суміжних вершин. Матриця суміжності. Пошук в ширину та в глибину. Дерева пошуку
11	Лекція 11. Властивості відрізків. Опукла комбінація. Векторний добуток. Обмежуючий прямокутник. Обчислення опуклої оболонки. Задача комівояжера. Задача про рюкзак. Задача про призначення
12	Лекція 12. Поняття хеш-функції. Метод відкритого хешування. Метод закритого кешування. Вибір хеш-функції
13	Лекція 13. Швидкість росту функцій. Логарифмічний, лінійний, квадратичний експоненціальний рости.
14	Лекція 14. Поняття про рекурсію. Умови застосування рекурсії. Аналіз рекурсивних алгоритмів. Методи розв’язання рекурсивних рівнянь. Дерево рекурсій.
15	Лекція 15. Динамічне програмування. Задача про множення матриць. Оцінка складності алгоритму задач про множення матриць.
16	Лекція 16. Жадібні алгоритми. Використання жадібних алгоритмів у програмуванні
3 практичні заняття
1	Практичне заняття 1. Вступ до структур даних та алгоритмів.
2	Практичне заняття 2. Базові структури даних
3	Практичне заняття 3. Базові структури даних. Хеш-таблиці
4	Практичне заняття 4. Базові структури даних. Дерева
5	Практичне заняття 5. Алгоритми пошуку. Лінійний пошук
6	Практичне заняття 6. Алгоритми пошуку. Бінарний пошук
7	Практичне заняття 7. Алгоритми сортування. Сортування бульбашкою
8	Практичне заняття 8. Алгоритми сортування. Сортування вибором
9	Практичне заняття 9. Алгоритми сортування. Сортування вставкою
10	Практичне заняття 10. Алгоритми сортування. Швидке сортування
11	Практичне заняття 11. Алгоритми сортування. Сортування підрахунком
12	Практичне заняття 12. Алгоритми сортування. Сортування за розрядами
13	Практичне заняття 13. Комбінаторні алгоритми
14	Практичне заняття 14. Фундаментальні алгоритми на графах та деревах
15	Практичне заняття 15. Рекурсія
16	Практичне заняття 16. Динамічне програмування
17	Практичне заняття 17. Жадібні алгоритми

Загальнонаціональна хвилина мовчання за загиблими внаслідок збройної агресії рф проти України

60