Информатика на Python, семестр 2, лекция 4, ФБВТ МФТИ (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...
Пікірлер: 26
Нужно понимать, что кроме графов есть еще герцоги, бароны и короли. Так что работы предстоит еще много
@ziegimondvishneuski3317
2 ай бұрын
Острите на очках в армии.
@Tiolych
2 ай бұрын
@@ziegimondvishneuski3317 нее, мы приложим все усилия и материальные средства, чтоб избежать любые взаимодействия с армейкой. Там могилизация. Нам не надо.
@vanoosbond8591
2 ай бұрын
Типо ахахах
@Tiolych
2 ай бұрын
Пойди их всех обойди )))
@user-ec9om5kp9e
2 ай бұрын
забыли про императора
Только Вас вспоминал и вот новая лекция! 👏
Здравствуйте! Благодарю за труд, очень ждал продолжения... Мирного неба над головой!
@amoteo9725
2 ай бұрын
Это не к спикеру)) Он подерживает войну)) и говорит что с Россией бог
@Sosed2024
2 ай бұрын
Бытует устоявшееся мнение, что если кто-то озвучивает в комментариях Утверждение без пруфоф (доказательств), значит в 99,99% случаев это брехня или троллинг, а может ботоферма работает. Удачи!
@A1eqsey
2 ай бұрын
@@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 с логикой программирования?! Заранее спасибо за советы
@tkhirianov
2 ай бұрын
Что именно вы понимаете под логикой программирования? Синтаксис языка? Математическую логику в применении к программированию? Или принципы построения программ?
@user-ks5sv6jn2g
2 ай бұрын
Математической с логикой, какие темы подтянуть, какие важные темы в для программирования
Пора уже переходить на лекции по Go. Python уже не модно молодёжно и жутко медленно
@dsr19750222
2 ай бұрын
Со следующего года, небось. Или через год, в 26
@predatel_rodini
2 ай бұрын
@@dsr19750222 с чего так решил?
@predatel_rodini
2 ай бұрын
@@johnrom8787 просто посмотри бенчмарки
@A1eqsey
2 ай бұрын
@@johnrom8787 ну надо смотреть и считать стоит ли овчинка выделки. Иногда стОит.
@johnrom8787
2 ай бұрын
@@A1eqsey может быть. У каждого свои задачи