- Видео 47
- Просмотров 286 104
Олимпиадное программирование в УлГТУ
Россия
Добавлен 1 июл 2020
Отрицательные циклы: проверка существования, вывод, пометка вершин, до которых нет кратчайшего пути
Это вторая, обновлённая версия видео, в которой рассмотрена проблема с выводом отрицательного цикла при помощи алгоритма Флойда (с 19:32).
Старая версия: ruclips.net/video/LnOOuNcRLIo/видео.html
Плейлист по кратчайшим путям в графах: ruclips.net/p/PLGhUJWLZ8uQ4EWdQwVyUFnz82kbeGRP97
Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Старая версия: 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 тыс.Год назад
Стек: реализация на массиве и списке, скобочные последовательности, постфиксная нотация
Расширяющийся массив: неправильные и правильные подходы к реализации
Просмотров 779Год назад
Расширяющийся массив: неправильные и правильные подходы к реализации
Поиск компонент сильной связности в графе. Алгоритм Косараджу
Просмотров 9 тыс.Год назад
Поиск компонент сильной связности в графе. Алгоритм Косараджу
Поиск циклов в неориентированном графе. Двудольность
Просмотров 5 тыс.Год назад
Поиск циклов в неориентированном графе. Двудольность
Поиск циклов в ориентированном графе. Восстановление цикла
Просмотров 9 тыс.Год назад
Поиск циклов в ориентированном графе. Восстановление цикла
Поиск компонент связности в неявном графе. DFS на графе-сетке
Просмотров 4 тыс.Год назад
Поиск компонент связности в неявном графе. DFS на графе-сетке
Поиск компонент связности в графе. Раскраска компонент связности
Просмотров 9 тыс.Год назад
Поиск компонент связности в графе. Раскраска компонент связности
Способы представления графов: список рёбер, матрица смежности, списки смежности
Просмотров 13 тыс.Год назад
Способы представления графов: список рёбер, матрица смежности, списки смежности
Огромное СПАСИБО! Объяснение ГРОССМЕЙСТЕРА...Каждое выражение подчеркивает мастерство и знание предмета.
6:30
спасибо за объяснение!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Это разъеб, отец!
Классный канал! Было бы круто, если юы видео возобновились
Нихуя непонятно
ребята, чего же вы такие крутые?! Это самое лучшее объяснение обхода в ширину, что я видел!
Когда не понял: 😢 Когда понял: 😎
Спасибо!
Благодаря вам понял дфс и бфс, спасибо большое!
Вы - золото!
Спасибо большое за ролик! Немного жаль что речь не шла про асинтотику памяти, но не сильно важно. А то по аналогии просто можно сделать вывод, чем больше мы capacity сделаем, тем круче, ведь тебе будем переслздавать массив, но тогда больше шанс на неиспользованную память. Также жду когда на канал вернётся видео про до, там же тоже можно в несколько серий сделать, про до, про ленивые обновления, про ндо, пдо и другие. Хотя про просто до очень хотелось бы видеть видео
Это лучший канал на ютубе по олпрограммированию. Огромное спасибо автору! Было бы классно увидеть код из видео где-то в описании или коментариях, потому что не всегда удобно переписывать или конспектировать, но в новых видео вроде такоц проблемы нет. Ещё раз спасибо!
Спасибо за видео!
Ваши видео просто кайф, спасение на методах программирования, спасибо большое!
добрый день. спасибо большое за алгоритм!
Здравствуйте, можете пожалуйста выпустить видео про дерево отрезков ?
ошибка сегментации
Наверное самое лучшее видео по этой теме, что можно только найти.
Мне очень повезло найти Ваш канал, спасибо!
Спасибо, более понятного курса по графам в русском сегменте просто нет, вы сделали огромную работу
самое лучшее обьяснение графов который я нашел! спасибо
Очень плохо
На сколько же это объяснение проще понять, чем читать переводы китайских статей
Почему на 5:14 в самом начале выполнилось 10 елементарных операций если тогда elementCount был 0 и цикл for в reserve не сделал не одну операцию? Не правильнее будет в push_back вставить ops+=capacity перед вызова reserve чтобы не брать в расчет последние 10 ячеек которые не будут участвовать в цикле for?
Сложность оператора new[] в общем случае линейна относительно количества выделяемых ячеек. Так что здесь мы учитываем не столько операции копирования, сколько операции выделения новой памяти. Впрочем, вы можете модифицировать этот вспомогательный подсчёт так, как считаете более правильным. Ожидается, что в конце вы придёте к тем же выводам о сложности push_back() при разных способах увеличения размера массива.
@@op_ulstu спасибо за объяснение)
Потрясающий материал! Спасибо огромное, за то, что вы делаете!
3:10 Я со своим ответом 7 ^_^
Лучший канал, отличное объяснение
Благодарю)
Исключительно качественное видео! Жаль только, что реализация не на пайтон.
Качественный разбор.
а как вы делайте такие анимации?
Спасибо за видео
Спс!!
Отличное видео, спасибо!!!
Очень наглядно, спасибо 👍
Как найти все циклы в графе?
В общем случае сделать это невозможно - циклов может быть слишком много. Представьте граф, в котором каждая вершина соединена со всеми остальными. В таком графе через любое подмножество из двух или более вершин проходит цикл.
забавный момент заключается в том, что число всех циклов а графе это одна из олимпиадных задач, но вся забава заключается в том, что решается она без графов
Это самый лучший ролик по теме из тех что я видел
Замечательный алгоритм и его объяснение 😀
Огромное спасибо! Вы очень помогли. Я долго не мог понять в чем ошибка, и с первой же минуты ролика понял, что у меня как раз левая ситуация, о которой я не подумал
у меня задачу про ряд деревьев получилось сделать без классов и мэпов, а просто хэш массивом p. s. задачу про максимальную подстроку где каждый элемент не превышает k тоже
Здравствуйте, отличные видео! А будут ли видео про красно-чёрные деревья?
Спасибо за столь понятное объяснение)
это было ооочень понятно. я, кажется, давно так не преисполнялся. большое спасибо!!
Ахуеть, Спасибо, Папаша!
В институте я много слышал про конечные автоматы (КА), но это всё было теорией - как облака в небе: воды в них много, а напиться нельзя. Корпел три месяца после института, пока не реализовал свой КА в коде в 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" или на Хабре: "Бублики и Коржики Программирования".
Откуда взялась вершина 4 если визуально её нигде нет? Чуть повозившись с gpt, он мне разжевал, что в данном случае, вначале задается количество вершин - 8, далее идут ребра. Заполняется массив вершин 1..8 получается [1,2,3,4,5,6,7,8]. Далее мы как бы между вершин натягиваем ребра.Так как вершина 4 была сгенерирована, но у неё было ребер, она остается изолированной вершиной. Таким образом у нас два компонента связности: [1,2,3,5,6,7,8] и [4].
Граф, который используется в примерах, был показан в предыдущем видео плейлиста: ruclips.net/video/3-XLRh2M5YI/видео.html Вершина 4 (в 0-индексации - 3) действительно не содержит смежных рёбер и образует отдельную компоненту связности в этом графе.
О да, легендарное ПиВо, ака КуРево, ака ДеРамида. Было бы интересно услышать от Вас про Авл и красночерные деревья
V (vertex) - вершина E (edge) - ребро
пытаться переписать этот код на python - трэш
Да ладно вам. ideone.com/SlQ8Cy
@@op_ulstu о, спасибо
@@op_ulstu спасибо за код. Пришлось, конечно, доделывать чтобы найти и вернуть цикл (индексация в списках без -1 и пустые ретерны), но в целом прога рабочая