ВИДЕОУРОК №8. Графы. Часть 3
Основная цель этого урока – ознакомить студентов со структурами данных и понятием алгоритма. Рассмотрим асимптотическую сложность алгоритма, односвязные и двухсвязные связанные списки. Также научимся использовать О-нотации.
На занятии рассматриваются главные структуры данных. Объясняется политика роста динамического массива. Разберем главные методы работы с этими структурами данных и их реализацию, объединение, сечение, разность, симметричную разность двух множеств.
На занятии разъясняются главные виды сортировки данных. Демонстрируется их сущность и реализация. Сравниваются разные методы сортировки для разных назначений и предпосылок. Кратко объясняется суть новой сортировки Timsort.
На уроке рассматриваются две структуры данных: хэш-таблица и дерево. Разъясняется суть хэш-таблицы, принцип ее работы, хэш-функция и коллизии в хэш-таблицах. Рассматривается структура данных "Дерево", подробнее объясняется бинарное дерево поиска и добавление узлов в дерево.
Данный урок посвящен рассмотрению методов работы с бинарным деревом поиска: удаление узла из дерева (3 варианта удаления), поиск узла в дереве, прямой, обратный и симметричный обход дерева. Рассматривается сущность АВЛ-дерева как модернизация бинарного дерева поиска. Разъясняется суть балансировки АВЛ-дерева и способы реализации балансировки.
На уроке рассматривается популярная и сложная структура данных "Граф". Также поговорим о введении в теорию графов, способах задать граф и два варианта поиска по графу: в ширину и глубину.
На уроке рассматриваются темы по теории графов, например, связные компоненты, цикл Эйлера. Поговорим об известном алгоритме Ли. Объясняется нахождение кратчайшего пути между вершинами графа. Демонстрируется алгоритм дейкстры.
На занятии глубже рассмотрим теорию графов. Кратко излагается сущность и принцип алгоритма Флойда-Уоршелла. Разъясняется и показывается топологическая сортировка, а также поиск компонентов связности через обход в глубину.
На уроке рассматривается подход динамического программирования к решению многих задач. Объясняется сущность и принцип разных приёмов. Демонстрируются типовые задачи и их решение.