Олимпиадное программирование в УлГТУ
Олимпиадное программирование в УлГТУ
  • Видео 47
  • Просмотров 249 006
Отрицательные циклы: проверка существования, вывод, пометка вершин, до которых нет кратчайшего пути
Это вторая, обновлённая версия видео, в которой рассмотрена проблема с выводом отрицательного цикла при помощи алгоритма Флойда (с 19:32).
Старая версия: ruclips.net/video/LnOOuNcRLIo/видео.html
Плейлист по кратчайшим путям в графах: ruclips.net/p/PLGhUJWLZ8uQ4EWdQwVyUFnz82kbeGRP97
Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Просмотров: 833

Видео

Идея алгоритма Флойда-Уоршелла
Просмотров 4,5 тыс.5 месяцев назад
Это вторая, обновлённая версия видео, в которой исправлены опечатки на слайдах. Старая версия: ruclips.net/video/kaA3_qNfpCA/видео.html Плейлист по кратчайшим путям в графах: ruclips.net/p/PLGhUJWLZ8uQ4EWdQwVyUFnz82kbeGRP97 Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными п...
Отрицательные циклы: почему они усложняют поиск кратчайших путей в графах
Просмотров 1,4 тыс.Год назад
Плейлист по кратчайшим путям в графах: ruclips.net/p/PLGhUJWLZ8uQ4EWdQwVyUFnz82kbeGRP97 Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Алгоритмы Флойда-Уоршелла и Джонсона
Просмотров 3,8 тыс.Год назад
Плейлист по кратчайшим путям в графах: ruclips.net/p/PLGhUJWLZ8uQ4EWdQwVyUFnz82kbeGRP97 Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Кратчайшие пути в ациклических ориентированных графах
Просмотров 2 тыс.Год назад
Плейлист по кратчайшим путям в графах: ruclips.net/p/PLGhUJWLZ8uQ4EWdQwVyUFnz82kbeGRP97 Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Алгоритм Форда-Беллмана и SPFA
Просмотров 11 тыс.Год назад
Плейлист по кратчайшим путям в графах: ruclips.net/p/PLGhUJWLZ8uQ4EWdQwVyUFnz82kbeGRP97 Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Отрицательные веса рёбер: почему алгоритм Дейкстры с ними не справляется
Просмотров 1,9 тыс.Год назад
Плейлист по кратчайшим путям в графах: ruclips.net/p/PLGhUJWLZ8uQ4EWdQwVyUFnz82kbeGRP97 Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Алгоритм Дейкстры: два варианта реализации
Просмотров 12 тыс.Год назад
Плейлист по кратчайшим путям в графах: ruclips.net/p/PLGhUJWLZ8uQ4EWdQwVyUFnz82kbeGRP97 Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Идея алгоритма Дейкстры
Просмотров 11 тыс.Год назад
Плейлист по кратчайшим путям в графах: ruclips.net/p/PLGhUJWLZ8uQ4EWdQwVyUFnz82kbeGRP97 Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Задачи на поиск в ширину: вершины и рёбра на кратчайших путях, неочевидные графы
Просмотров 2,4 тыс.Год назад
Плейлист по кратчайшим путям в графах: ruclips.net/p/PLGhUJWLZ8uQ4EWdQwVyUFnz82kbeGRP97 Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Задачи на поиск в ширину: лабиринты, BFS из нескольких стартовых вершин, 0-1-BFS
Просмотров 5 тыс.Год назад
Плейлист по кратчайшим путям в графах: ruclips.net/p/PLGhUJWLZ8uQ4EWdQwVyUFnz82kbeGRP97 Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Поиск в ширину (BFS)
Просмотров 28 тыс.Год назад
Плейлист по кратчайшим путям в графах: ruclips.net/p/PLGhUJWLZ8uQ4EWdQwVyUFnz82kbeGRP97 Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Очередь с приоритетами: эффективное построение двоичной кучи, сортировка кучей
Просмотров 1,9 тыс.Год назад
Плейлист по последовательным структурам данных: ruclips.net/p/PLGhUJWLZ8uQ4PVZ5sIyiJy8EQduBKEqRN Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Очередь с приоритетами: реализация на двоичной куче
Просмотров 4,1 тыс.Год назад
Плейлист по последовательным структурам данных: ruclips.net/p/PLGhUJWLZ8uQ4PVZ5sIyiJy8EQduBKEqRN Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Очередь и дек: варианты реализации, очередь с минимумом
Просмотров 2,6 тыс.Год назад
Плейлист по последовательным структурам данных: ruclips.net/p/PLGhUJWLZ8uQ4PVZ5sIyiJy8EQduBKEqRN Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Стек: ближайший больший элемент, стек с минимумом, стек в рекурсии
Просмотров 785Год назад
Стек: ближайший больший элемент, стек с минимумом, стек в рекурсии
Стек: реализация на массиве и списке, скобочные последовательности, постфиксная нотация
Просмотров 1,7 тыс.Год назад
Стек: реализация на массиве и списке, скобочные последовательности, постфиксная нотация
Двусвязный список
Просмотров 2,6 тыс.Год назад
Двусвязный список
Односвязный список
Просмотров 5 тыс.Год назад
Односвязный список
Расширяющийся массив: неправильные и правильные подходы к реализации
Просмотров 704Год назад
Расширяющийся массив: неправильные и правильные подходы к реализации
Массив
Просмотров 2 тыс.Год назад
Массив
Поиск компонент сильной связности в графе. Алгоритм Косараджу
Просмотров 8 тыс.Год назад
Поиск компонент сильной связности в графе. Алгоритм Косараджу
Топологическая сортировка графа
Просмотров 11 тыс.Год назад
Топологическая сортировка графа
Поиск циклов в неориентированном графе. Двудольность
Просмотров 4,8 тыс.Год назад
Поиск циклов в неориентированном графе. Двудольность
Поиск циклов в ориентированном графе. Восстановление цикла
Просмотров 8 тыс.Год назад
Поиск циклов в ориентированном графе. Восстановление цикла
Поиск компонент связности в неявном графе. DFS на графе-сетке
Просмотров 3,4 тыс.Год назад
Поиск компонент связности в неявном графе. DFS на графе-сетке
Поиск компонент связности в графе. Раскраска компонент связности
Просмотров 8 тыс.Год назад
Поиск компонент связности в графе. Раскраска компонент связности
Поиск в глубину (DFS)
Просмотров 20 тыс.Год назад
Поиск в глубину (DFS)
Способы представления графов: список рёбер, матрица смежности, списки смежности
Просмотров 11 тыс.Год назад
Способы представления графов: список рёбер, матрица смежности, списки смежности
Графы. Свойства графов
Просмотров 13 тыс.Год назад
Графы. Свойства графов

Комментарии

  • @ДенисЯкушев-р8ы
    @ДенисЯкушев-р8ы 5 дней назад

    Мне очень повезло найти Ваш канал, спасибо!

  • @Norsik_IT
    @Norsik_IT 6 дней назад

    Спасибо, более понятного курса по графам в русском сегменте просто нет, вы сделали огромную работу

  • @maksymshyshkov2787
    @maksymshyshkov2787 22 дня назад

    самое лучшее обьяснение графов который я нашел! спасибо

  • @ПафнутийАбдристандилов

    Очень плохо

  • @naronwaz7824
    @naronwaz7824 29 дней назад

    На сколько же это объяснение проще понять, чем читать переводы китайских статей

  • @ghostmane8961
    @ghostmane8961 Месяц назад

    Почему на 5:14 в самом начале выполнилось 10 елементарных операций если тогда elementCount был 0 и цикл for в reserve не сделал не одну операцию? Не правильнее будет в push_back вставить ops+=capacity перед вызова reserve чтобы не брать в расчет последние 10 ячеек которые не будут участвовать в цикле for?

    • @op_ulstu
      @op_ulstu Месяц назад

      Сложность оператора new[] в общем случае линейна относительно количества выделяемых ячеек. Так что здесь мы учитываем не столько операции копирования, сколько операции выделения новой памяти. Впрочем, вы можете модифицировать этот вспомогательный подсчёт так, как считаете более правильным. Ожидается, что в конце вы придёте к тем же выводам о сложности push_back() при разных способах увеличения размера массива.

    • @ghostmane8961
      @ghostmane8961 Месяц назад

      @@op_ulstu спасибо за объяснение)

  • @Nachtvaohal
    @Nachtvaohal Месяц назад

    Потрясающий материал! Спасибо огромное, за то, что вы делаете!

  • @aastapchik8991
    @aastapchik8991 Месяц назад

    3:10 Я со своим ответом 7 ^_^

  • @ГлебК-н1г
    @ГлебК-н1г Месяц назад

    Лучший канал, отличное объяснение

  • @andd3dfx
    @andd3dfx Месяц назад

    Благодарю)

  • @MikeDev-Sooworr
    @MikeDev-Sooworr 2 месяца назад

    Исключительно качественное видео! Жаль только, что реализация не на пайтон.

  • @KartoplyanaHata
    @KartoplyanaHata 2 месяца назад

    Качественный разбор.

  • @q1ncite
    @q1ncite 2 месяца назад

    а как вы делайте такие анимации?

  • @redgamer4958
    @redgamer4958 2 месяца назад

    Спасибо за видео

  • @jagdinsky
    @jagdinsky 2 месяца назад

    Спс!!

  • @ГлебК-н1г
    @ГлебК-н1г 2 месяца назад

    Отличное видео, спасибо!!!

  • @myxapg4758
    @myxapg4758 2 месяца назад

    Очень наглядно, спасибо 👍

  • @МатвейКурченко-о9б
    @МатвейКурченко-о9б 2 месяца назад

    Как найти все циклы в графе?

    • @op_ulstu
      @op_ulstu 2 месяца назад

      В общем случае сделать это невозможно - циклов может быть слишком много. Представьте граф, в котором каждая вершина соединена со всеми остальными. В таком графе через любое подмножество из двух или более вершин проходит цикл.

  • @dmtr_ptrv
    @dmtr_ptrv 2 месяца назад

    Это самый лучший ролик по теме из тех что я видел

  • @CAXAROK2010
    @CAXAROK2010 2 месяца назад

    Замечательный алгоритм и его объяснение 😀

  • @Answizar
    @Answizar 3 месяца назад

    Огромное спасибо! Вы очень помогли. Я долго не мог понять в чем ошибка, и с первой же минуты ролика понял, что у меня как раз левая ситуация, о которой я не подумал

  • @userryanelb
    @userryanelb 3 месяца назад

    у меня задачу про ряд деревьев получилось сделать без классов и мэпов, а просто хэш массивом p. s. задачу про максимальную подстроку где каждый элемент не превышает k тоже

  • @ТимурАбдрахимов-ч6я
    @ТимурАбдрахимов-ч6я 3 месяца назад

    Здравствуйте, отличные видео! А будут ли видео про красно-чёрные деревья?

  • @lobiritus1512
    @lobiritus1512 3 месяца назад

    Спасибо за столь понятное объяснение)

  • @_nikolAss_78
    @_nikolAss_78 3 месяца назад

    это было ооочень понятно. я, кажется, давно так не преисполнялся. большое спасибо!!

  • @ВалерийЖмышенко-ъ4ц
    @ВалерийЖмышенко-ъ4ц 3 месяца назад

    Ахуеть, Спасибо, Папаша!

  • @vrakitine
    @vrakitine 3 месяца назад

    В институте я много слышал про конечные автоматы (КА), но это всё было теорией - как облака в небе: воды в них много, а напиться нельзя. Корпел три месяца после института, пока не реализовал свой КА в коде в 1981 году. Сейчас существует методология программирования на этой основе - v-agent oriented programming (VAOP) - и множество примеров её реализации. Лучше начать знакомство с VAOP с этой статьи на Medium: "Bagels and Muffins of Programming or How Easy It Is to Convert a Bagel into a Black Hole" или на Хабре: "Бублики и Коржики Программирования".

  • @makarov...
    @makarov... 3 месяца назад

    Откуда взялась вершина 4 если визуально её нигде нет? Чуть повозившись с gpt, он мне разжевал, что в данном случае, вначале задается количество вершин - 8, далее идут ребра. Заполняется массив вершин 1..8 получается [1,2,3,4,5,6,7,8]. Далее мы как бы между вершин натягиваем ребра.Так как вершина 4 была сгенерирована, но у неё было ребер, она остается изолированной вершиной. Таким образом у нас два компонента связности: [1,2,3,5,6,7,8] и [4].

    • @op_ulstu
      @op_ulstu 3 месяца назад

      Граф, который используется в примерах, был показан в предыдущем видео плейлиста: ruclips.net/video/3-XLRh2M5YI/видео.html Вершина 4 (в 0-индексации - 3) действительно не содержит смежных рёбер и образует отдельную компоненту связности в этом графе.

  • @georgevonfloydmann1797
    @georgevonfloydmann1797 3 месяца назад

    О да, легендарное ПиВо, ака КуРево, ака ДеРамида. Было бы интересно услышать от Вас про Авл и красночерные деревья

  • @makarov...
    @makarov... 3 месяца назад

    V (vertex) - вершина E (edge) - ребро

  • @indominusmonster6433
    @indominusmonster6433 4 месяца назад

    пытаться переписать этот код на python - трэш

    • @op_ulstu
      @op_ulstu 4 месяца назад

      Да ладно вам. ideone.com/SlQ8Cy

    • @indominusmonster6433
      @indominusmonster6433 4 месяца назад

      @@op_ulstu о, спасибо

    • @indominusmonster6433
      @indominusmonster6433 4 месяца назад

      ​@@op_ulstu спасибо за код. Пришлось, конечно, доделывать чтобы найти и вернуть цикл (индексация в списках без -1 и пустые ретерны), но в целом прога рабочая

  • @jetairliner5706
    @jetairliner5706 4 месяца назад

    От души всё растолковано, спасибо

  • @nekoie6150
    @nekoie6150 4 месяца назад

    спасибо вам огромное!!

  • @RedFeuer.
    @RedFeuer. 4 месяца назад

    Спасибо!

  • @STUPAkns
    @STUPAkns 4 месяца назад

    круто!

  • @adventureswithstan1026
    @adventureswithstan1026 4 месяца назад

    Спасибо, очено помогли,единственный нормально объяснение на ютубе

  • @tusman4ik
    @tusman4ik 4 месяца назад

    А стоит ли на олимпиаде этим заниматься? Я про тестинг автоматический.. Ведь время жмет.

    • @op_ulstu
      @op_ulstu 4 месяца назад

      На последних часах пятичасовых соревнований нередко есть выбор между поиском ошибки в решении одной задачи или написанием с нуля решения другой задачи. Стресс-тестирование в такой ситуации может очень сильно помочь. Кроме того, есть форматы соревнований, когда решения отправляются «втёмную» (то есть итоговый вердикт становится известен только после окончания). В этом случае стресс-тестирование просто незаменимо.

  • @adventureswithstan1026
    @adventureswithstan1026 4 месяца назад

    Идеальный канал,спасибо

  • @antonnesterov8711
    @antonnesterov8711 4 месяца назад

    3:10 - почему сдвинули R на 40, а не на 43?

    • @op_ulstu
      @op_ulstu 4 месяца назад

      Спасибо за наблюдательность, здесь на слайдах ошибка. Правильная последовательность шагов при поиске элемента 33: L = 0, R = 19, M = 9; A[M] > 33, смещаем R на M - 1 L = 0, R = 8, M = 4; A[M] < 33, смещаем L на M + 1 L = 5, R = 8, M = 6; A[M] > 33, смещаем R на M - 1 L = 5, R = 5, M = 5; A[M] < 33, смещаем L на M + 1 L = 6, R = 5; индексы зашли друг за друга, следовательно, элемента 33 в массиве нет.

    • @antonnesterov8711
      @antonnesterov8711 4 месяца назад

      @@op_ulstu понял, большое спасибо за уточнение! И за курс в целом - он отличный!

  • @quirenceh4ndeir156
    @quirenceh4ndeir156 4 месяца назад

    Легенда. Спасибо. Добавьте еще дополнительные задачи про мосты и точки сочленения, все люди, грокающие графы, будут благодарны

  • @ducbyk8169
    @ducbyk8169 4 месяца назад

    Большое вам спасибо за наглядные примеры и код.

  • @Лев-й7я
    @Лев-й7я 5 месяцев назад

    Найс

  • @Лев-й7я
    @Лев-й7я 5 месяцев назад

    Нааааайс

  • @Лев-й7я
    @Лев-й7я 5 месяцев назад

    Топ

  • @lobiritus1512
    @lobiritus1512 5 месяцев назад

    Спасибо за такое понятное и подробное объяснение!

  • @aveok1
    @aveok1 5 месяцев назад

    Спасибо вам болшое

  • @Лев-й7я
    @Лев-й7я 5 месяцев назад

    Огонь 🔥

  • @Bibliophilos
    @Bibliophilos 5 месяцев назад

    Коммент в поддержку канала, большое дело делает автор.

  • @Bibliophilos
    @Bibliophilos 5 месяцев назад

    Спасибо огромное за видео! Пожалуйста, объясните для чайника, когда мы пишем l = m+1, r = m - 1; а когда просто приравниваем m? Первый случай только для поиска конкретного элемента?

    • @op_ulstu
      @op_ulstu 5 месяцев назад

      Мы начали с такого примера и такого решения потому, что для начинающих зрителей они являются более понятными и естественными. Далее мы придём к более общему решению. Задача, которая решается при помощи бинпоиска, чаще состоит не в том, чтобы найти какое-то заданное значение, а в том, чтобы найти первый или последний элемент, обладающий определённым свойством. Для таких задач уже проще запомнить общее решение, когда цикл while идёт до 2 элементов, а l и r всегда смещаются на m (без +1/-1). Подробнее об этом рассказано в следующем видео: ruclips.net/video/_u2yypDA6R0/видео.html Когда нужен поиск заданного значения в массиве, его можно выполнять так, как показано здесь, но можно воспользоваться и вышеупомянутой общей схемой, например, искать первый элемент, который больше или равен заданному значению (цикл while в этом случае идёт до 2 элементов, l и r смещаются на m).

    • @Bibliophilos
      @Bibliophilos 5 месяцев назад

      @@op_ulstu благодарю! Вы один из топовых авторов по объяснению алгоритмов.

  • @lekopin1783
    @lekopin1783 5 месяцев назад

    Спасибо большое! Отличный урок!