ВІДЕОУРОК № 8. Графи. Частина 3
Основна мета цього уроку – ознайомити студентів зі структурами даних та поняттям алгоритму. Ми розглянемо асимптотичну складність алгоритму, однозв'язкові та двозв'язкові зв'язані списки. Також навчимося використовувати О-нотації.
На занятті розглядаються основні структури даних. Пояснюється політика зростання динамічного масиву. Розберемо основні способи роботи з цими структурами даних та його реалізацію, об'єднання, перетин, різницю, симетричну різницю двох множин.
На занятті пояснюються основні види сортування даних. Демонструється їх суть та реалізація. Порівнюються різні методи сортування для різних призначень та передумов. Коротко пояснюється суть нового сортування Timsort.
На уроці розглядається дві структури даних: хеш-таблиця та дерево. Роз'яснюється суть хеш-таблиці, принцип її роботи, хеш-функція та колізії у хеш-таблицях. Розглядається структура даних «Дерево», детальніше пояснюється бінарне дерево пошуку та додавання вузлів у дерево.
Даний урок присвячений розгляду методів роботи з бінарним деревом пошуку: видалення вузла з дерева (3 варіанти видалення), пошук вузла в дереві, прямий, зворотний і симетричний обходи дерева. Розглядається суть АВЛ-дерева як модернізація бінарного дерева пошуку. Роз'яснюється суть балансування АВЛ-дерева та способи реалізації балансування.
На уроці розглядається популярна та складна структура даних «Граф». Також поговоримо про введення в теорію графів, способи задати граф та два варіанти пошуку за графом: у ширину та глибину.
На уроці розглядаються теми з теорії графів, як-от зв'язкові компоненти, цикл Ейлера. Поговоримо про відомий алгоритм Лі. Пояснюється знаходження найкоротшого шляху між вершинами графа. Демонструється алгоритм Дейкстри.
На занятті глибше розглянемо теорію графів. Коротко викладається суть та принцип алгоритму Флойда-Уоршелла. Роз'яснюється та демонструється топологічне сортування та пошук компонентів зв'язності через обхід у глибину.
На уроці розглядається підхід динамічного програмування до розв’язання багатьох завдань. Пояснюється сутність і принцип різних прийомів. Демонструються типові завдання та їх розв’язання.