Информатика на Python, семестр 2, лекция 4, ФБВТ МФТИ (2024)
Вставка
- Опубліковано 25 чер 2024
- 2 семестр, лекция 4: Обходы графов
Таймкоды:
00:00 Вступление
02:37 Направленный ациклический граф (DAG)
22:50 Неориентированный граф с циклами
25:13 Обход графа в глубину (DFS)
42:30 Граф-дерево и остовное дерево
50:50 Двудольный граф
56:00 Обход графа в ширину (BFS)
01:07:50 Реализация кода
Плейлист с лекциями 1-го курса ФБВТ МФТИ: • 2023 ФБВТ Информатика ...
Снял и смонтировал видео: youtube.com/@antonoreshkin?si...
Нужно понимать, что кроме графов есть еще герцоги, бароны и короли. Так что работы предстоит еще много
Острите на очках в армии.
@@ziegimondvishneuski3317 нее, мы приложим все усилия и материальные средства, чтоб избежать любые взаимодействия с армейкой. Там могилизация. Нам не надо.
Типо ахахах
Пойди их всех обойди )))
забыли про императора
Только Вас вспоминал и вот новая лекция! 👏
спасибо за лекцию, когда нибудь до них дойду
Настальгия, помню как зубрил алгоритм дейкстры по книге грокаем алгоритмы
Здравствуйте!
Благодарю за труд, очень ждал продолжения...
Мирного неба над головой!
Это не к спикеру)) Он подерживает войну)) и говорит что с Россией бог
Бытует устоявшееся мнение, что если кто-то озвучивает в комментариях Утверждение без пруфоф (доказательств), значит в 99,99% случаев это брехня или троллинг, а может ботоферма работает.
Удачи!
@@amoteo9725 и он безусловно прав.
Здравствуйте!
Тайм-коды\конспект для этого видео:
0:00 обход графа (traversals - путешествие, обход)
0:55 есть такая тонкость
2:28 пример графа. Ориентированный
4:45 в чём польза таких графов? - Они хорошо отображают...
5:10 представьте себе Университет демократический
6:40 еще интересный момент. Не должен возникать циклический импорт (зависимость). Существует простой способ перебора всех траекторий
8:10 смысл в следующем: прописываем программу
10:10 прописываем текущую вершину
13:30 почему я сейчас пишу путь, как последовательность вершин
15:30 что будет возникать
17:20 траектории бывают разными
20:40 если путь содержит все вершины
23:20 что я могу сделать. Обход первый - в глубину
25:40 правила такие. Пример с друзьями
28:00 текущая вершина всегда одна
30:40 в этом графе есть цикл. Поиск циклов в графе
31:40 мы доходим до крайнего случая. Далее происходит возврат рекурсии
35:30 его скорость примерно такая
36:20 пример с соц. сетями
37:50 важный момент
39:20 я научился выделять компоненту связности
41:30 про дерево обхода
42:35 дерево - это связный граф, без простых циклов
43:40 "∀ для любых вершин а и b принадлежащих ∈V существует ∃! простой путь из а в b
44:40 в древности у евреев не было царя, а только во время войны. "Власть царя (Саула) испортила"
46:30 сразу выстраивается иерархия по уровням (например Дерево каталогов)
47:45 свойство графа
48:20 у любого связного графа, есть подграф у которого есть дерево. Остовное дерево - это некий подграф...
50:20 проверка его двудольности. Пример с двумя столами, вечеринка, где есть враги
52:30 возникает вопрос. Красим вершины (в противоположный цвет)
54:50 проверка двудольности завершена
56:05 BFS - обход в ширину. Стартовал: вершина А красится в серый цвет
59:10 пример с "Ковидлой". Пациент №1
1:01:00 это получается цикл у нас. Заражение ближних
1:01:40 в очереди остается последним, очередь пуста. Мы можем увидеть траектории заражения
1:06:20 это и есть уровни иерархии
1:07:58 практика, пишем код
1:08:30 переписываю код графа (повторяем)
1:10:50 создаю пустые множества смежностей
1:13:00 посмотрите, какой хороший алгоритм
1:14:30 суть подсчета компоненты связности. Смотрим код
1:15:40 получаем результат
1:16:28 проверка двудольности
1:18:45 отредактировали код, получили результат
1:21:00 пытаюсь показать визуализацию, не получилось. Заканчиваем
Желаем Вам успехов в обучении!
Бомба.🎉
42:20 на ваших лекциях даже ребенок смеется )
Здравствуйте, подскажите пожалуйста хорошие книги по программированию по Python с логикой программирования?! Заранее спасибо за советы
Что именно вы понимаете под логикой программирования?
Синтаксис языка? Математическую логику в применении к программированию? Или принципы построения программ?
Математической с логикой, какие темы подтянуть, какие важные темы в для программирования
Пора уже переходить на лекции по Go. Python уже не модно молодёжно и жутко медленно
Со следующего года, небось. Или через год, в 26
@@dsr19750222 с чего так решил?
@@johnrom8787 просто посмотри бенчмарки
@@johnrom8787 ну надо смотреть и считать стоит ли овчинка выделки. Иногда стОит.
@@A1eqsey может быть. У каждого свои задачи