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

Видео

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

Комментарии

  • @vladimirbien634
    @vladimirbien634 5 дней назад

    Огромное СПАСИБО! Объяснение ГРОССМЕЙСТЕРА...Каждое выражение подчеркивает мастерство и знание предмета.

  • @Yo_mik375
    @Yo_mik375 7 дней назад

    6:30

  • @Blood_mode_Ghoul
    @Blood_mode_Ghoul 7 дней назад

    спасибо за объяснение!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

  • @karbofos8
    @karbofos8 11 дней назад

    Это разъеб, отец!

  • @honeycatcher9565
    @honeycatcher9565 24 дня назад

    Классный канал! Было бы круто, если юы видео возобновились

  • @Слава-о1х6з
    @Слава-о1х6з 24 дня назад

    Нихуя непонятно

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

    ребята, чего же вы такие крутые?! Это самое лучшее объяснение обхода в ширину, что я видел!

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

    Когда не понял: 😢 Когда понял: 😎

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

    Спасибо!

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

    Благодаря вам понял дфс и бфс, спасибо большое!

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

    Вы - золото!

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

    Спасибо большое за ролик! Немного жаль что речь не шла про асинтотику памяти, но не сильно важно. А то по аналогии просто можно сделать вывод, чем больше мы capacity сделаем, тем круче, ведь тебе будем переслздавать массив, но тогда больше шанс на неиспользованную память. Также жду когда на канал вернётся видео про до, там же тоже можно в несколько серий сделать, про до, про ленивые обновления, про ндо, пдо и другие. Хотя про просто до очень хотелось бы видеть видео

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

    Это лучший канал на ютубе по олпрограммированию. Огромное спасибо автору! Было бы классно увидеть код из видео где-то в описании или коментариях, потому что не всегда удобно переписывать или конспектировать, но в новых видео вроде такоц проблемы нет. Ещё раз спасибо!

  • @Мансур-с7т
    @Мансур-с7т Месяц назад

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

  • @Каркуша-ш5е
    @Каркуша-ш5е 2 месяца назад

    Ваши видео просто кайф, спасение на методах программирования, спасибо большое!

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

    добрый день. спасибо большое за алгоритм!

  • @СашаКочетов-г3в
    @СашаКочетов-г3в 2 месяца назад

    Здравствуйте, можете пожалуйста выпустить видео про дерево отрезков ?

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

    ошибка сегментации

  • @Поварих
    @Поварих 2 месяца назад

    Наверное самое лучшее видео по этой теме, что можно только найти.

  • @ДенисЯкушев-р8ы
    @ДенисЯкушев-р8ы 2 месяца назад

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

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

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

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

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

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

    Очень плохо

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Благодарю)

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

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

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

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

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

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

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

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

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

    Спс!!

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

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

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

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

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

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

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

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

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

      забавный момент заключается в том, что число всех циклов а графе это одна из олимпиадных задач, но вся забава заключается в том, что решается она без графов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    В институте я много слышал про конечные автоматы (КА), но это всё было теорией - как облака в небе: воды в них много, а напиться нельзя. Корпел три месяца после института, пока не реализовал свой КА в коде в 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... 6 месяцев назад

    Откуда взялась вершина 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 6 месяцев назад

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

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

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

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

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

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

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

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

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

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

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

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

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