Информатика на 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

  • @johnrom8787
    @johnrom87872 ай бұрын

    Нужно понимать, что кроме графов есть еще герцоги, бароны и короли. Так что работы предстоит еще много

  • @ziegimondvishneuski3317

    @ziegimondvishneuski3317

    2 ай бұрын

    Острите на очках в армии.

  • @Tiolych

    @Tiolych

    2 ай бұрын

    @@ziegimondvishneuski3317 нее, мы приложим все усилия и материальные средства, чтоб избежать любые взаимодействия с армейкой. Там могилизация. Нам не надо.

  • @vanoosbond8591

    @vanoosbond8591

    2 ай бұрын

    Типо ахахах

  • @Tiolych

    @Tiolych

    2 ай бұрын

    Пойди их всех обойди )))

  • @user-ec9om5kp9e

    @user-ec9om5kp9e

    2 ай бұрын

    забыли про императора

  • @legohistory8039
    @legohistory80392 ай бұрын

    Только Вас вспоминал и вот новая лекция! 👏

  • @Sosed2024
    @Sosed20242 ай бұрын

    Здравствуйте! Благодарю за труд, очень ждал продолжения... Мирного неба над головой!

  • @amoteo9725

    @amoteo9725

    2 ай бұрын

    Это не к спикеру)) Он подерживает войну)) и говорит что с Россией бог

  • @Sosed2024

    @Sosed2024

    2 ай бұрын

    Бытует устоявшееся мнение, что если кто-то озвучивает в комментариях Утверждение без пруфоф (доказательств), значит в 99,99% случаев это брехня или троллинг, а может ботоферма работает. Удачи!

  • @A1eqsey

    @A1eqsey

    2 ай бұрын

    @@amoteo9725 и он безусловно прав.

  • @user-wv8lb7ow6k
    @user-wv8lb7ow6k2 ай бұрын

    спасибо за лекцию, когда нибудь до них дойду

  • @dejavu2744
    @dejavu27442 ай бұрын

    Настальгия, помню как зубрил алгоритм дейкстры по книге грокаем алгоритмы

  • @timecode2024
    @timecode20243 күн бұрын

    Здравствуйте! Тайм-коды\конспект для этого видео: 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 пытаюсь показать визуализацию, не получилось. Заканчиваем Желаем Вам успехов в обучении!

  • @WrldsporteventsR.Y..V.1992
    @WrldsporteventsR.Y..V.19922 ай бұрын

    Бомба.🎉

  • @nonamenonametansh337
    @nonamenonametansh3372 ай бұрын

    42:20 на ваших лекциях даже ребенок смеется )

  • @user-ks5sv6jn2g
    @user-ks5sv6jn2g2 ай бұрын

    Здравствуйте, подскажите пожалуйста хорошие книги по программированию по Python с логикой программирования?! Заранее спасибо за советы

  • @tkhirianov

    @tkhirianov

    2 ай бұрын

    Что именно вы понимаете под логикой программирования? Синтаксис языка? Математическую логику в применении к программированию? Или принципы построения программ?

  • @user-ks5sv6jn2g

    @user-ks5sv6jn2g

    2 ай бұрын

    Математической с логикой, какие темы подтянуть, какие важные темы в для программирования

  • @predatel_rodini
    @predatel_rodini2 ай бұрын

    Пора уже переходить на лекции по Go. Python уже не модно молодёжно и жутко медленно

  • @dsr19750222

    @dsr19750222

    2 ай бұрын

    Со следующего года, небось. Или через год, в 26

  • @predatel_rodini

    @predatel_rodini

    2 ай бұрын

    @@dsr19750222 с чего так решил?

  • @predatel_rodini

    @predatel_rodini

    2 ай бұрын

    @@johnrom8787 просто посмотри бенчмарки

  • @A1eqsey

    @A1eqsey

    2 ай бұрын

    @@johnrom8787 ну надо смотреть и считать стоит ли овчинка выделки. Иногда стОит.

  • @johnrom8787

    @johnrom8787

    2 ай бұрын

    @@A1eqsey может быть. У каждого свои задачи