Информатика на Python, семестр 2, лекция 5, ФБВТ МФТИ (2024)

Таймкоды:
00:00 - Вступление
04:27 - Алгоритм Кана
07:16 - Алгоритм Тарьяна
11:51 - Реализация алгоритма Тарьяна
21:34 - Демонстрация работы алгоритма Тарьяна
31:53 - Алгоритм Косарайю
54:50 - Реализация Алгоритма Косарайю
01:00:04 - Взвешенные графы, способы их хранения
01:08:45 - Алгоритм Флойда-Уоршелла

[BRED_Sosed]

О, чудесно, Благодарю за труд. Я ждал =)
Желаю Вам мирного неба над головой и благополучия!

[r-yzf]

Топ преподаватель ! Пушка, бомба, петарда !

[Тайм-коды-]

Здравствуйте!
Тайм-коды\конспект для этого видео:

0:00 вступление
1:05 вы должны понимать устройство алгоритма, структуры данных
2:48 ориентированные графы без циклов (Directed Acyclic Graphs, DAG). Если орграф не содержит циклов, то в нём возможно осуществить топологическую сортировку вершин, т.е. пронумеровать их так, чтобы все ребра шли по возрастанию индексов
4:54 Алгоритм Кана не является эффективным. O(N^2) от количества вершин
7:15 алгоритм Тарьяна. Эффективный алгоритм с асимптотикой O(N) от количества вершин
9:20 пример
12:00 реализация алгоритма Тарьяна топологической сортировкой
12:50 ввод графа в виде словаря смежности
13:10 итак, что мы делаем...(мы делаем обход в глубину)
15:50 обратите внимание на особенность этого dfs(функции)
16:00 вспомнил, для чего мне grey \грей, для того, чтобы отслеживать, что текущий обход в глубину не должен попасть на циклическую зависимость
17:15 в третьем семестре будет более продвинутый Python, тогда я вам расскажу про exception (исключение)
19:40 вопросы по реализации?
20:00 реализация алгоритма Косарайю выделения сильно связных компонент орграфа
21:50 рисую произвольный ориентированный граф
23:10 пробуем найти компоненты сильной связности
25:40 это отдельная компонента
26:40 рисую компоненты. Рассмотрим граф состоящий из компонент
28:40 почему это ациклический граф DAC?
29:40 как быстро найти компоненты сильной связности. Для этого есть алгоритм Касарайю
32:10 мы будем делать следующее... нам нужен транспонированный граф
34:10 для оригинального графа делаем серию DFS в обратном order, новая вершина (белая) - новая сильная компонента
35:40 почему мы делаем для транспоненты
38:30 минута тишины для усвоения знаний
39:05 поймали случайно вершину. Обратите внимание. Называем вершины: А, В, С, D, ... Начинаем обход в глубину с вершины H
39:30 буквы будут удобней, обозначаем. Начинаем с вершины H в D, и т.д.
43:20 обход закончился...много разных вершин этот обход в глубину затронул
45:30 далее мы делаем серию обходов в глубину
47:42 можем провести топологическую сортировку
49:35 я иду дальше
51:30 согласитесь, красиво!
53:00 всем понятно? Правда красиво?
54:32 коротко показываю текст, код
57:30 теперь используя обратный порядок
59:52 алгоритм Флойда-Уоршелла - это алгоритм поиска кратчайших путей, во взвешенном графе с положительным или отрицательным весом ребер (но без ... циклов)
1:00:30 про взвешенные графы (у каждого ребра вес). Как хранить взвешенный граф?
1) весовая матрица (это плохая идея, т.к. много памяти занимает),
2) словарь весов,
3) словарь словарей,
1:08:40 алгоритм Краскала и Прима. Оставляю вам их на экзамен ;), Алгоритм Флойда-Уоршелла
1:12:10 идея алгоритма Флойда-Уоршелла в том, что...
Алгоритм Беллмана — Форда
1:14:30 новая матрица расстояний формируется случайным образом...O(N^3)

Желаем Вам удачи в обучении!

[eugenij_bojarov]

Тимофей, спасибо Вам огромное, за ещё одну прекрасную лекцию!)

[boderaner]

Поскольку Косарайю на самом деле Косараджу (Sambasiva Rao Kosaraju), он не японец, а индиец 😀. Точнее, индо-американец.
Зато научрук его докторской японец был, Хисао Ямада.