Код и структуры данных из видео - это просто шаблон. В реальных языках порядок поиска и обхода может отличаться. Более подробно об этом в телеграм канале - t.me/Alek_OS
как врач могу сказать, что использовать слово "ребра" и в картинку вставлять бедреные кости - несколько сбивает с толку. С другой стороны, натуральные ребра не отражали бы идею прямой "грани", они же изогнутые. А те, которые не сильно изогнутые (например, ребра некоторых животных), не будут узнаваемыми "ребрами". Хотя и бедра - не очень узнаваемые "ребра")
Все круто, но алгоритм Дейкстры для поиска именно пути обычно так не рассказывают в вузах. Принято все таки при обновлении значения хранить и вершину из которой ведет минимальный маршрут. По памяти будет также линейно, но и по времени сделается линейным (от количества вершин в минимальном пути). В вашем же случае, если граф является полносвязным (что часто так и бывает), то вам придется при обратном проходе постоянно перебирать все вершины, чтобы все же найти откуда мы пришли.
19:10 а можно просто попутно для каждой вершины сохранять номер предшествующей ей вершины. И тогда путь автоматически будет готов под конец (правда в обратном порядке, но реверснуть его не сложно)
Мне кажется, что путь, которому мы добрались до назначения не обязательно самый короткий: например, если бы путь от C до D был бы равен 1, то обратно машина поехала бы по нему.
Фактически, когда мы вычисляем кратчайшие расстояния до точек, двигаемся мы по всему графу, так как метод calculateTimeToEachNode крутит цикл до тех пор, пока unprocessedNodes не пуст, а unprocessedNodes заполняется всеми точками графа. Когда метод заканчивается, остановиться мы могли на любой точке графа(в видео это обговаривается, когда автор из точки B двигается не в D, а в E; а в точке E мог быть тупик) , но уже зная все кратчайшие пути от точки start до остальных, поэтому обратный путь приходится вычислять таким способом. В своих примерах я постоянно говорю, что то-то могло быть равно тому-то, потому что в видео выбран довольно неудачный пример графа, из-за чего не видна вся суть алгоритма Дейкстры. @@Secvad
Да и в коде в конце метода calcutaleTimeToEachNode не видно, чтобы мы как-то сохраняли даже последнюю точку, поэтому мы в метод getPath передаём и стартовую, и последнюю точки.@@Secvad
Спасибо за классный контент! Но есть несколько вопросов: 04:33 Вообще не понял, что за структура. 05:04 Зачем тут нужен -1? 06:47 Значения узлов? Это вершины? Почему это минус? А веса могут быть любыми - они значения массива, а не индексы. 07:09 Ну с деревьями такая структура ещё используется (dom, xml), но вот с обычными графами - никогда не встречал. И её жирный минус - большое потребление памяти. 11:25 А как мы можем достать из стека посещённый узел, если проверяем посещённость перед тем, как его туда положить? 12:16 Обёртку теперь можно объединить с обходом. 13:17 Стоило отметить, что из passed теперь ещё и удаляются вершины. Ну и это будет жутко медленно. 20:48 Цикл по хэштаблице асимптотику портит же? Очередь приоритетов была бы лучше.
Наверное, первый ролик на канале, который разочаровал. При этом я подписан и считаю автора топовым по качеству изложения материала. И не понимаю восторгов в комментариях именно к этому видео, т. к. похоже, большинство дальше заголовка не идет, или смотрит на перемотке и строчит коменты по привычке, "за былые заслуги" (а остальные ролики, действительно, выше всяких похвал). Если я не прав, и дело во мне, буду благодарем, если мне объяснят хотя бы следующую идею из видео. Я понимаю, что можно взять учебник и вспомнить/разобраться во все самостоятельно, но я пытался честно вникнуть во все, что хотел донести автор, и КМК, один из немногих, . Первый раз "завис" на 4:30 идее "оставить в виде двумерного массива". Что значит "оставить", если смысл хранимых данных полностью меняется? Что означает "каждая ячейка будет являться отдельным узлом"? Какие данные будут храниться в "каждой ячейке"? Судя по картинке, номер узла? Зачем тут вообще ДВУМЕРНЫЙ массив? И что означает "отсутствие узла"? В итоге на 4:55 список "минусов" (каждый пункт, не буду повторять) и картинка выглядят, мягко говоря, станными. Лучше бы проиллюстрировали, какую топологию описывает данная "структура"... Еще больше вопросов в комментарии ув. @QwDragon. Буду признателен, если кто-то из разобравшихся ответит на них. Вообще, зная качество остальных роликов, эти неясности кажутся результатом неаккуратного монтажа. Если так - с нетерпением буду ждать "расширенную" версию.
Да, жаль конечно, что автор не разъясняет до конца, что происходит в видео. Сам на красно-чёрных деревьях завис, потому что некоторые методы надо было поменять или тонкости реализации не упомянуты. Однако я считаю, что это можно простить автору, потому что, по-моему, главная цель видео - описать логику реализации различных структур данных в коде, работу с ними, их плюсы и минусы. А то, что мы не понимаем некоторых моментов, - это уже наша проблема. Более того, если достаточно долго поработать со структурой данных, то начинаешь понимать смысл её реализаций и сам можешь разбираться в этом.
@@_mrix_534да я вообще готов автору простить все за талант просто объяснять сложные вещи :) Тут скорее не претензия, а фидбек от "аудитории". "Ничего не понял, но очень интересно". Хотелось бы каких-нибудь пояснений, хотя, конечно, все можно "допилить" самостоятельно (гугл, лекции, учебники...)
Полезное видео, лайк! Для интересующихся графами рекомендую свободно распространяемую электронную книгу «Графомания» (автор Деревенец О.В.). Даны решения задач с исходными текстами и контрольными примерами. Рассмотрены следующие темы: Задачи на множествах: • разбиение множества на подмножества; • задача о наименьшем разбиении (ЗНР); • задача о наименьшем покрытии (ЗНП). Группа задач на достижимость: • взаимная достижимость вершин; • кратчайшие пути между вершинами; • выделение сильно связанных компонент. Группа задач на размещение: • независимые вершины и клики; • доминирующие множества; • раскраски; • центры; • p-центры; • p-медианы. Остовные деревья Группа задач о потоках: • максимальный поток в сети; • поток, ограниченный сверху и снизу; • минимальная стоимость потока. Паросочетания на взвешенных графах: • паросочетание в двудольном графе; • паросочетание в произвольном графе. Цикл Эйлера и задача почтальона на взвешенных графах: • на неориентированном графе; • на орграфе. Задачи Гамильтона и коммивояжёра на взвешенных графах: • разомкнутая задача Гамильтона; • замкнутая задача Гамильтона (контур); • комбинирование методов для задач Гамильтона; • замкнутая и разомкнутая задачи коммивояжёра.
Ютуб не отдаёт анализ просмотра ролика пользователями из России. Так что, не имеет никакого значения пропускают или смотрят рекламу. Рекламодатель ориентируется на общее число просмотров видео у каждого автора. Кроме того, реклама остаётся навечно - она вшита в ролик и её будут смотреть спустя годы и века....
@@Piixel2517 понял, что не моё. Родители были программистами, все остальные в семье - тоже. Я думал, что стать программистом - моя судьба, продолжал что-то изучать, делать... Никогда у меня это занятие не вызывало подлинного интереса. Это начинало понемножку "убивать" меня. Я выгорел, мне было очень плохо, я не понимал, что со мной происходит. Решил всё-таки сменить курс, как только понял, что не замечал истинную страсть. 8 лет своей жизни я просто просрал, ведь думал, что раз все избрали именно этот путь, то и мне будет там хорошо...
Отлично как всегда! Немного быстро, но это не проблема ведь можно пересматривать и замедлять :-) Когда же мы изучим как обходить и перепрыгивать рекламу на автомате )))) это самый востребованный сейчас бот в мире, чтоб распознавал и перескакивал или если перескочить нельзя (на ТВ), то глушил сразу звук и замещал отсчётом времени или своей картинкой "Отдохните n-минут, посмотрите на своего котика" )))
Будучи студентом, и участвуя в олимпиадах по программированию от вуза в разных городах, часто были задачки - найти кратчайший путь и тп. В лучшем случае на Паскале
Как же у меня сгорело от двух частей видео (во мне проснулся мастер по спортивному программированию и я начал ломать код в видео) 1 Нерекурсивный обход в глубину - вы не сохраняете состояние обхода дочерних узлов - получается что для каждой вершины обход совершается в квадратическое время от количества потомков вместо линейного - это недопустимое упрощение (представте граф-звезда тогда будет квадрат от количества вершин время обхода). Нерекурсивная реализация рекурсии - это очень сложная задача когда я в первый раз ее писал вышло в 2 раза медленее обычной рекурсии по быстродействию В олимпиадной жизни да в крайних случаях приходится писать такое если время на задачу осталось и больше решать нечего а в реальной жизни можно в опции компилятора увеличить размер стека. 2 Двунаправленный поиск в ширину - что??? meet-in-the-middle да есть такой вид перебора очень редкий вид задач в реальной жизни слышал про взломы защит таким способом Вместо 2^n получаем 2^(n/2) * что-нибудь типа n^2 (проверки совместимости половинок) тут реально есть смысл. А в графе что? В лучшем случае в 2 раза выйгрыш неимоверными усилиями не факт что так будет. Граф цепочка - и тогда путь между концами диаметра графа будет всегда n вершин - выйгрыша не будет зато помучаетесь немного с реализацией и будет расходоваться доп память для быстрой проверки принадлежности дереву поиска второй половинки. Неудачный просто пример вышел.
Не бывает самой минимальной или самой максимальной величины. Бывает минимальная или самая малая и максимальная или самая большая. А самая мин. или самая макс - это как масло масляное.
Хаха, ты даже не представляешь как ты мне помог. Дело в том, что я делаю стратегию и игровая карта как раз таки представляет граф :) От сюда я почерпнул много инфы, которую я сейчас принимаю на практике.
читал это и слушал много раз за последние 30 лет, но так и не понял чем это отличается от двумерных массивов или структур в Си/Паскале, без всякого ООП. Я всегда пользовался каким-то движком БД и SQL. Там то же хеширование для двумерных массивов. Скорость огромная. Память? Ну оно всегда так - либо быстро либо мало памяти. Задачи на память конечно бывают, в тех же МК, где порой оперативки 1-16 Кб, но там и SQL нет.
Видос класс. Единственное в алгоритме Дейкстры при обратном обходе не совсем понятно, что происходит если несколько ребер соответствуют условию равенства!
Продлевать слово это как заполнять паузу пока думаешь что сказать, можно просто сказать в обычном темпе и сделать паузу чтобы зритель мог обдумать сказанное
Вопрос по алгоритму Дейкстры. Для восстановления пути мы можем запоминать родителя той или иной вершины, ну и менять родителя при необходимости. Так разве не проще, чем восстанавливать путь по значениям расстояний?
Картинки красивые и стильные. Но речь очень сложно воспринимать. Например такая фраза: "Минус один здесь снова обозначает отсутсвие узла и получается, что если у одного узла есть три ребра, которые ведут на три его дочерних элемента, то в масиве под каждые из этих ребер будет создано три записи". Как одно из другого следует? Почему эти две фразы слиты в одну посредством "и получается"? 🥱
Насколько я знаю, cg pods так и не показали своё производство. А это значит, что с большой вероятностью, они таскают наушники из Китая и переклеивают шильдики. Об этом есть масса инфы в интернете, на пикабу в частности...
@@ЕвгенийСахаров-т7ы бизнес. любой товар найдет своего покупателя. дураков хватает. если человек мамонт, пусть его стригут, зачем препятствовать? люди, которым действительно нужен хороший звук, не будут покупать хлам.
За ролик огромное спасибо! А вот реклама наушников меня насмешила))) Реально штоль кто-то покупает наушники за 5000? Или тем более за 12000+?))) У меня весь телефон стока стоит, а наушники мы отхватили за 150 рублей на китайской распродаже, и шикарные оказались))) Два года проработали, пока аккумуляторы не сдохли!
Понимание алгоритмов важно для решения практических задач, что демонстрируют примеры с графами и структурами данных ✦ 00:00 Алгоритмы ценны для решения нетипичных задач ✦ 03:03 Стать хакером в белой шляпе и освоить кибератаки ✦ 06:05 Представление графов с помощью связных списков. ✦ 09:05 Обход графа может быть выполнен в глубину или в ширину для поиска путей между узлами ✦ 11:57 Алгоритм поиска путей между узлами в графе ✦ 14:45 Поиск в ширину находит кратчайший путь из точки A в точку B ✦ 17:21 Алгоритм Dextras находит кратчайшие пути во взвешенных графах ✦ 20:03 Вычисление кратчайшего пути с помощью хэш-таблицы и связного списка
Более детально: ✦ *00:00** Алгоритмы полезны для решения нетипичных задач* Примеры включают поиск кратчайших маршрутов, решение лабиринтов и выявление общих друзей в социальных сетях. Понимание структур данных и специальных алгоритмов необходимо для эффективного решения задач Графы - это структура данных, используемая для представления перекрестков и дорог, и может применяться в языках программирования В ориентированном графе все ребра имеют определенное направление Специалисты по кибербезопасности востребованы из-за риска кражи данных ✦ *03:03** Станьте хакером в белой шляпе и освойте кибератаки* Научиться защищать системы и находить уязвимости в онлайн-школе Освоить операционные системы Linux и Windows, а также программирование на Python ✦ *06:05** Представление графов с помощью связанных списков.* Узлы хранят свое собственное значение, ссылку на ребра и ребро родителя. Граф действует как хэш-таблица с уникальными значениями узлов в качестве ключей. Метод добавления узлов в граф и создания ребер между ними. ✦ *09:05** Обход графа может быть выполнен в глубину или в ширину для поиска путей между узлами.* Обход графа похож на обход двоичного дерева. Чтобы избежать циклов, используйте хэш-таблицу для отслеживания посещенных узлов Метод обхода работает только для связных графов Если узлов слишком много, рекурсивный алгоритм может привести к переполнению стека. Для обхода проблемы переполнения стека можно использовать альтернативный алгоритм с использованием циклов ✦ *11:57** Алгоритм поиска путей между узлами в графе* - Алгоритм предполагает перебор дочерних узлов и рекурсивный поиск пути к нужному узлу. - Он может найти как первый путь, так и все пути между двумя узлами ✦ *14:45** Поиск по ширине находит кратчайший путь из точки A в точку B* Поиск по ширине сначала проходит через каждый уровень графа, прежде чем перейти к следующему уровню. Создается специальная обертка, чтобы гарантировать, что все элементы графа будут пройдены Алгоритм может быть дополнительно оптимизирован путем одновременного прохождения с двух сторон ✦ *17:21** Алгоритм Dextras находит кратчайшие пути во взвешенных графах* Алгоритм позволяет находить кратчайшие пути, рассматривая веса ребер как время в пути между узлами. Он работает, вычисляя время пути до дочерних узлов из начальной точки. Затем он рассматривает каждый дочерний узел и выбирает тот, который имеет наименьшее время в пути Вычисляется время в пути до конечного узла и выбирается кратчайший результат. Алгоритм будет работать, только если значения ребер являются положительными числами ✦ *20:03** Вычисление кратчайшего пути с помощью хэш-таблицы и связного списка* Перебираем узлы и вычисляем минимальное время для каждого узла Если время остается числом, это означает, что из начальной точки к узлу ведет только один путь. Создаем связный список для сохранения кратчайшего пути и перебираем узлы от конца к началу.
Так, сразу стоп, я не понял... Зачем представлять переходы в виде данных?? Переходы надо делать, а не представлять. Тогда зачем данные, когда всё-ровно всё сведётся к переходам в коде. Jmp, jne, call, ret, int... Сразу пишем код, ну и флаги состояний.
Код и структуры данных из видео - это просто шаблон.
В реальных языках порядок поиска и обхода может отличаться.
Более подробно об этом в телеграм канале - t.me/Alek_OS
как врач могу сказать, что использовать слово "ребра" и в картинку вставлять бедреные кости - несколько сбивает с толку. С другой стороны, натуральные ребра не отражали бы идею прямой "грани", они же изогнутые. А те, которые не сильно изогнутые (например, ребра некоторых животных), не будут узнаваемыми "ребрами". Хотя и бедра - не очень узнаваемые "ребра")
Графы не работают - это делают крепостные. Единственным широко известным исключением в истории, и то с большими оговорками, является Л.Н. Толстой.
Черт, ты меня опередил! Я хотел это сказать!!!
@@ВладиславСубботин-з1э ничего, бывает) Комментарий, конечно, напрашивался.
Кому как не крепостным фашистким федерастам этого не знать
То чувство, когда гуманитарий решил зайти на видос по программированию
@@romansmirnov5813 Точно))
Ооооооо. Ништяк. Заморочки на ноч грядущую подъехали. Спасибо
Все круто, но алгоритм Дейкстры для поиска именно пути обычно так не рассказывают в вузах. Принято все таки при обновлении значения хранить и вершину из которой ведет минимальный маршрут. По памяти будет также линейно, но и по времени сделается линейным (от количества вершин в минимальном пути). В вашем же случае, если граф является полносвязным (что часто так и бывает), то вам придется при обратном проходе постоянно перебирать все вершины, чтобы все же найти откуда мы пришли.
Так ждала этот видос. Большое спасибо. Очень люблю вашу лаконичную подачу материала.
Это супер полезное видео. Информация и визуализация и звук, тут все прекрасно
ОоО как раз начал изучать алгоритмы и структуры данных спасибо
спасибо огромное за твои видео! я не видел больше таких понятных, интересных, и приятных обьяснений таких тем, спасибо!
Очень крутой видос, спасибо)
Вовремя зашел! Топ контент, благодарю!
сказал ребро, а на картинке бедренная кость! и как теперь доверять?😄
19:10 а можно просто попутно для каждой вершины сохранять номер предшествующей ей вершины. И тогда путь автоматически будет готов под конец (правда в обратном порядке, но реверснуть его не сложно)
Тоже вариант
Мне кажется, что путь, которому мы добрались до назначения не обязательно самый короткий: например, если бы путь от C до D был бы равен 1, то обратно машина поехала бы по нему.
@@_mrix_534так... В смысле?
Фактически, когда мы вычисляем кратчайшие расстояния до точек, двигаемся мы по всему графу, так как метод calculateTimeToEachNode крутит цикл до тех пор, пока unprocessedNodes не пуст, а unprocessedNodes заполняется всеми точками графа. Когда метод заканчивается, остановиться мы могли на любой точке графа(в видео это обговаривается, когда автор из точки B двигается не в D, а в E; а в точке E мог быть тупик) , но уже зная все кратчайшие пути от точки start до остальных, поэтому обратный путь приходится вычислять таким способом. В своих примерах я постоянно говорю, что то-то могло быть равно тому-то, потому что в видео выбран довольно неудачный пример графа, из-за чего не видна вся суть алгоритма Дейкстры. @@Secvad
Да и в коде в конце метода calcutaleTimeToEachNode не видно, чтобы мы как-то сохраняли даже последнюю точку, поэтому мы в метод getPath передаём и стартовую, и последнюю точки.@@Secvad
Кто-то: "Аристократов на фонарь!"
Тем временем графы:
Спасибо за видео, теперь хоть стало понятно как работает навигатор под капотом )
Класс🎉уважение за качество материала и за такой труд
Спасибо за классный контент!
Но есть несколько вопросов:
04:33 Вообще не понял, что за структура.
05:04 Зачем тут нужен -1?
06:47 Значения узлов? Это вершины? Почему это минус? А веса могут быть любыми - они значения массива, а не индексы.
07:09 Ну с деревьями такая структура ещё используется (dom, xml), но вот с обычными графами - никогда не встречал. И её жирный минус - большое потребление памяти.
11:25 А как мы можем достать из стека посещённый узел, если проверяем посещённость перед тем, как его туда положить?
12:16 Обёртку теперь можно объединить с обходом.
13:17 Стоило отметить, что из passed теперь ещё и удаляются вершины. Ну и это будет жутко медленно.
20:48 Цикл по хэштаблице асимптотику портит же? Очередь приоритетов была бы лучше.
классно тебе ответили чувак 😂
Наверное, первый ролик на канале, который разочаровал. При этом я подписан и считаю автора топовым по качеству изложения материала. И не понимаю восторгов в комментариях именно к этому видео, т. к. похоже, большинство дальше заголовка не идет, или смотрит на перемотке и строчит коменты по привычке, "за былые заслуги" (а остальные ролики, действительно, выше всяких похвал). Если я не прав, и дело во мне, буду благодарем, если мне объяснят хотя бы следующую идею из видео. Я понимаю, что можно взять учебник и вспомнить/разобраться во все самостоятельно, но я пытался честно вникнуть во все, что хотел донести автор, и КМК, один из немногих, . Первый раз "завис" на 4:30 идее "оставить в виде двумерного массива".
Что значит "оставить", если смысл хранимых данных полностью меняется?
Что означает "каждая ячейка будет являться отдельным узлом"? Какие данные будут храниться в "каждой ячейке"? Судя по картинке, номер узла?
Зачем тут вообще ДВУМЕРНЫЙ массив?
И что означает "отсутствие узла"?
В итоге на 4:55 список "минусов" (каждый пункт, не буду повторять) и картинка выглядят, мягко говоря, станными. Лучше бы проиллюстрировали, какую топологию описывает данная "структура"...
Еще больше вопросов в комментарии ув. @QwDragon. Буду признателен, если кто-то из разобравшихся ответит на них.
Вообще, зная качество остальных роликов, эти неясности кажутся результатом неаккуратного монтажа. Если так - с нетерпением буду ждать "расширенную" версию.
Да, жаль конечно, что автор не разъясняет до конца, что происходит в видео. Сам на красно-чёрных деревьях завис, потому что некоторые методы надо было поменять или тонкости реализации не упомянуты. Однако я считаю, что это можно простить автору, потому что, по-моему, главная цель видео - описать логику реализации различных структур данных в коде, работу с ними, их плюсы и минусы. А то, что мы не понимаем некоторых моментов, - это уже наша проблема. Более того, если достаточно долго поработать со структурой данных, то начинаешь понимать смысл её реализаций и сам можешь разбираться в этом.
@@_mrix_534да я вообще готов автору простить все за талант просто объяснять сложные вещи :) Тут скорее не претензия, а фидбек от "аудитории". "Ничего не понял, но очень интересно". Хотелось бы каких-нибудь пояснений, хотя, конечно, все можно "допилить" самостоятельно (гугл, лекции, учебники...)
Спасибо большое за труд, очень классные видео!
Напишу просто чтобы ютубчик продвигал в реки, а так видосик как обычно топовый, а когда видос по третьей части ассемблера?
Когда думал что оптимизируешь а на самом деле оказалось...
Полезное видео, лайк!
Для интересующихся графами рекомендую свободно распространяемую электронную книгу «Графомания» (автор Деревенец О.В.). Даны решения задач с исходными текстами и контрольными примерами. Рассмотрены следующие темы:
Задачи на множествах:
• разбиение множества на подмножества;
• задача о наименьшем разбиении (ЗНР);
• задача о наименьшем покрытии (ЗНП).
Группа задач на достижимость:
• взаимная достижимость вершин;
• кратчайшие пути между вершинами;
• выделение сильно связанных компонент.
Группа задач на размещение:
• независимые вершины и клики;
• доминирующие множества;
• раскраски;
• центры;
• p-центры;
• p-медианы.
Остовные деревья
Группа задач о потоках:
• максимальный поток в сети;
• поток, ограниченный сверху и снизу;
• минимальная стоимость потока.
Паросочетания на взвешенных графах:
• паросочетание в двудольном графе;
• паросочетание в произвольном графе.
Цикл Эйлера и задача почтальона на взвешенных графах:
• на неориентированном графе;
• на орграфе.
Задачи Гамильтона и коммивояжёра на взвешенных графах:
• разомкнутая задача Гамильтона;
• замкнутая задача Гамильтона (контур);
• комбинирование методов для задач Гамильтона;
• замкнутая и разомкнутая задачи коммивояжёра.
Впервые не пропускаю рекламу, в дань уважения к автору за такие максимально понятные и разжëваные видеоролики👍
Я по прежнему пропускаю
ФУУУ, ТЕРПИЛА
У меня авто пропуск реклыммых интерграций)
Не очень умно. Как поможет автору просмотр рекламы, он что от этого больше денег получит?
Ютуб не отдаёт анализ просмотра ролика пользователями из России.
Так что, не имеет никакого значения пропускают или смотрят рекламу.
Рекламодатель ориентируется на общее число просмотров видео у каждого автора.
Кроме того, реклама остаётся навечно - она вшита в ролик и её будут смотреть спустя годы и века....
Когда мы ищем путь или кратчайший путь от точки A до точки B нам не нужны несвязанные графы - они не могут привести нас из точки A в точку B.
Золотой, золотой ты человек
Круто
Очень круто
Большое спасибо за видео
Однозначно вижу популяризацию знаний ставлю лайк ❤
чувство, будто бы кто-то написал приятные конспекты и дает почитать
Делал задачу на графы - буквально нашёл решение в твоём новом ролике! Спасибо!
смотрю этот канал, ничего не понимая, чисто офигеваю со сложности программирования
Вот наконец-то нашёл человека, который реально шарит
Пятый раз уже пересматриваю чтобы сделать свою реализацию
Если графы работают, значит произошла революция
Красава. Как всегда доступно только сжато.
Забросил программирование и математику уже как пол года, но всё же интересно
Почему?
@@Piixel2517 понял, что не моё. Родители были программистами, все остальные в семье - тоже. Я думал, что стать программистом - моя судьба, продолжал что-то изучать, делать... Никогда у меня это занятие не вызывало подлинного интереса. Это начинало понемножку "убивать" меня. Я выгорел, мне было очень плохо, я не понимал, что со мной происходит. Решил всё-таки сменить курс, как только понял, что не замечал истинную страсть. 8 лет своей жизни я просто просрал, ведь думал, что раз все избрали именно этот путь, то и мне будет там хорошо...
@@Aristotle314 а если не секрет, то в какой степь двигаешься?
@@Piixel2517 биологию я для себя открыл
@@Aristotle314 звучит круто, успехов тебе)
Тема родителя номер 1 и родителя номер 2 не раскрыта в графах...
Отлично как всегда! Немного быстро, но это не проблема ведь можно пересматривать и замедлять :-) Когда же мы изучим как обходить и перепрыгивать рекламу на автомате )))) это самый востребованный сейчас бот в мире, чтоб распознавал и перескакивал или если перескочить нельзя (на ТВ), то глушил сразу звук и замещал отсчётом времени или своей картинкой "Отдохните n-минут, посмотрите на своего котика" )))
Я уже давно смотрю канал Артём граф, но никогда не знал ничего про графы. Спасибо
А канал то хороший, Артем крайне воспитанный и начитанный молодой человек, не то что эти ваши блогеры современные
Крутейкий ролик! Буду думать где такое применить... Может "Навител" переписать 😁
А то тащит вечно в непонятные графы
Ждем разбор алгоритмов поиска А-стар и Суурбалле! )
Круто рассказываешь! но этот звук карандаша... просто жесть..
У автора талант преподавания !
Будучи студентом, и участвуя в олимпиадах по программированию от вуза в разных городах, часто были задачки - найти кратчайший путь и тп. В лучшем случае на Паскале
Братан, просто респект 🫡
круто !!! просто нет слов !!! В универе .....
лучшее видео про графы
Как же у меня сгорело от двух частей видео (во мне проснулся мастер по спортивному программированию и я начал ломать код в видео)
1 Нерекурсивный обход в глубину - вы не сохраняете состояние обхода дочерних узлов - получается что для каждой вершины обход совершается в квадратическое время от количества потомков вместо линейного - это недопустимое упрощение (представте граф-звезда тогда будет квадрат от количества вершин время обхода). Нерекурсивная реализация рекурсии - это очень сложная задача когда я в первый раз ее писал вышло в 2 раза медленее обычной рекурсии по быстродействию В олимпиадной жизни да в крайних случаях приходится писать такое если время на задачу осталось и больше решать нечего а в реальной жизни можно в опции компилятора увеличить размер стека.
2 Двунаправленный поиск в ширину - что??? meet-in-the-middle да есть такой вид перебора очень редкий вид задач в реальной жизни слышал про взломы защит таким способом Вместо 2^n получаем 2^(n/2) * что-нибудь типа n^2 (проверки совместимости половинок) тут реально есть смысл. А в графе что? В лучшем случае в 2 раза выйгрыш неимоверными усилиями не факт что так будет. Граф цепочка - и тогда путь между концами диаметра графа будет всегда n вершин - выйгрыша не будет зато помучаетесь немного с реализацией и будет расходоваться доп память для быстрой проверки принадлежности дереву поиска второй половинки. Неудачный просто пример вышел.
В ОГЭ по информатике есть задача по алгоритму Дейкстры, получается.
На мой взгляд тоненькая книжка под названием "Грокаем Алгоритмы" лучше объясняет алгоритмы чем такой видос
Хотелось бы ещё узнать про алгоритм А*
Спасибо за видео!
Вот только узлы это не классы, а объекты (классов). 7:18
4:41 ааа, скрип карандаша о бумагу(вернее, наверное об доску)
7:17 ааа, опять
Можешь показать как это делается в Lua?
Не бывает самой минимальной или самой максимальной величины. Бывает минимальная или самая малая и максимальная или самая большая. А самая мин. или самая макс - это как масло масляное.
Как всегда афигенное подробное видео, где всё разложено по полочкам 👍👍👍
4:25
Ужснх! Вы б ещё пенопластом по стеклу посребли >.
Тиканье фоном крайне раздражает, сделайте тише в будущем.
Учёный под названием Дейкстра)
Thanks a million!
Спасибо бро
имба тема, топовые видео, ахуенный чел, все до тапок хорошо
Хаха, ты даже не представляешь как ты мне помог. Дело в том, что я делаю стратегию и игровая карта как раз таки представляет граф :) От сюда я почерпнул много инфы, которую я сейчас принимаю на практике.
Не influence случайно?)
@@zmeyotkusitel Нет, но я ей вдохновлялся. Хорошая игра в своем жанре:)
Подробнее с алгоритмами поиска кратчайшего пути в направленных графах поверхностно можно ознакомится в книге Т.Х. Кармена Алгоритмы:Вводный курс.
Даёшь разбор алгоритма Тарьяна и Кхана
читал это и слушал много раз за последние 30 лет, но так и не понял чем это отличается от двумерных массивов или структур в Си/Паскале, без всякого ООП. Я всегда пользовался каким-то движком БД и SQL. Там то же хеширование для двумерных массивов. Скорость огромная. Память? Ну оно всегда так - либо быстро либо мало памяти. Задачи на память конечно бывают, в тех же МК, где порой оперативки 1-16 Кб, но там и SQL нет.
Как работают графы?
Странный вопрос. Графы дворяне, они не работают! )))
Если убрать всю рекламу и воду, останется 5 минут полезной информации. Но автор ценит только своё время
Видос класс. Единственное в алгоритме Дейкстры при обратном обходе не совсем понятно, что происходит если несколько ребер соответствуют условию равенства!
Продлевать слово это как заполнять паузу пока думаешь что сказать, можно просто сказать в обычном темпе и сделать паузу чтобы зритель мог обдумать сказанное
cgpods, блин. понимаю, что реклама необходима, но надо же достоинство иметь. так и до онлайн казино скатиться можно.
Вопрос по алгоритму Дейкстры. Для восстановления пути мы можем запоминать родителя той или иной вершины, ну и менять родителя при необходимости. Так разве не проще, чем восстанавливать путь по значениям расстояний?
проще, я так и делаю
Картинки красивые и стильные. Но речь очень сложно воспринимать. Например такая фраза: "Минус один здесь снова обозначает отсутсвие узла и получается, что если у одного узла есть три ребра, которые ведут на три его дочерних элемента, то в масиве под каждые из этих ребер будет создано три записи". Как одно из другого следует? Почему эти две фразы слиты в одну посредством "и получается"? 🥱
неплохое видео, но алгоритм дейкстры плоховато рассказан, есть куда проще и понятнее реализации
кости не ребряные а бедряные)
Семестр теории графов в университете или видео на 22 минуты? Сложный выбор.
графы это алгоритм поиска или структура данных?
10 из 10 👍
В методе getPath после цикла забыл return false;
Уважаемый, у вас там не рёбра, а бёдра))
Спасибо
Как раз в унике проходим графы. На парах это очень уныло, в ролике достаточно показательно и информативно. Спасибо.
Видео не смотрел. Графы не работают. На графов работают.
АлекОС - провидец. Только мы начали тему графов в учебке - и тут как тут с видосом)))
Насколько я знаю, cg pods так и не показали своё производство. А это значит, что с большой вероятностью, они таскают наушники из Китая и переклеивают шильдики. Об этом есть масса инфы в интернете, на пикабу в частности...
вот те на, удивил. пожалуй, большая часть производства находится в Китае.
@XitriyLis-km9kj они-то позиционируют, что у них производство там, где они сидят...
@@ЕвгенийСахаров-т7ы бизнес. любой товар найдет своего покупателя. дураков хватает. если человек мамонт, пусть его стригут, зачем препятствовать?
люди, которым действительно нужен хороший звук, не будут покупать хлам.
@@ЕвгенийСахаров-т7ы ля, чего только стоят всякие леомаксы с отдельными каналами для вещания своего говна 24 на 7 по тв)))
Дискретная математика 2 курс)
говорит про ребра, а показывает бедренную кость.
Продвигаем твой контент комментарием.
Сложно, но познавательно.
А если граф неориентированный, кто будет его родителями?(parents)
Лайк не глядя, комментарий для статистики любимого канала
Ничего не понял с двумерных массивов(
Автор бедренную кость (это та, которая ходить мало-мало) называет ребрами. Вопрос - как он называет другую кость, голову?
Открывай школу )) 😅
За ролик огромное спасибо!
А вот реклама наушников меня насмешила)))
Реально штоль кто-то покупает наушники за 5000? Или тем более за 12000+?)))
У меня весь телефон стока стоит, а наушники мы отхватили за 150 рублей на китайской распродаже, и шикарные оказались)))
Два года проработали, пока аккумуляторы не сдохли!
Графы я так и не осилил. Теория просто проваливается без понимания, а практических задач решать так и не приходилось.
Даров
А можно как-то просто объяснить где дешевле использовать рекурсию, а где цикл? В общем случае
Лучше всего использовать циклы, рекурсии могут вызвать переполнение стека
Okey❤
Понимание алгоритмов важно для решения практических задач, что демонстрируют примеры с графами и структурами данных
✦ 00:00 Алгоритмы ценны для решения нетипичных задач
✦ 03:03 Стать хакером в белой шляпе и освоить кибератаки
✦ 06:05 Представление графов с помощью связных списков.
✦ 09:05 Обход графа может быть выполнен в глубину или в ширину для поиска путей между узлами
✦ 11:57 Алгоритм поиска путей между узлами в графе
✦ 14:45 Поиск в ширину находит кратчайший путь из точки A в точку B
✦ 17:21 Алгоритм Dextras находит кратчайшие пути во взвешенных графах
✦ 20:03 Вычисление кратчайшего пути с помощью хэш-таблицы и связного списка
Более детально:
✦
*00:00** Алгоритмы полезны для решения нетипичных задач*
Примеры включают поиск кратчайших маршрутов, решение лабиринтов и выявление общих друзей в социальных сетях.
Понимание структур данных и специальных алгоритмов необходимо для эффективного решения задач
Графы - это структура данных, используемая для представления перекрестков и дорог, и может применяться в языках программирования
В ориентированном графе все ребра имеют определенное направление
Специалисты по кибербезопасности востребованы из-за риска кражи данных
✦
*03:03** Станьте хакером в белой шляпе и освойте кибератаки*
Научиться защищать системы и находить уязвимости в онлайн-школе
Освоить операционные системы Linux и Windows, а также программирование на Python
✦
*06:05** Представление графов с помощью связанных списков.*
Узлы хранят свое собственное значение, ссылку на ребра и ребро родителя.
Граф действует как хэш-таблица с уникальными значениями узлов в качестве ключей.
Метод добавления узлов в граф и создания ребер между ними.
✦
*09:05** Обход графа может быть выполнен в глубину или в ширину для поиска путей между узлами.*
Обход графа похож на обход двоичного дерева.
Чтобы избежать циклов, используйте хэш-таблицу для отслеживания посещенных узлов
Метод обхода работает только для связных графов
Если узлов слишком много, рекурсивный алгоритм может привести к переполнению стека.
Для обхода проблемы переполнения стека можно использовать альтернативный алгоритм с использованием циклов
✦
*11:57** Алгоритм поиска путей между узлами в графе*
- Алгоритм предполагает перебор дочерних узлов и рекурсивный поиск пути к нужному узлу.
- Он может найти как первый путь, так и все пути между двумя узлами
✦
*14:45** Поиск по ширине находит кратчайший путь из точки A в точку B*
Поиск по ширине сначала проходит через каждый уровень графа, прежде чем перейти к следующему уровню.
Создается специальная обертка, чтобы гарантировать, что все элементы графа будут пройдены
Алгоритм может быть дополнительно оптимизирован путем одновременного прохождения с двух сторон
✦
*17:21** Алгоритм Dextras находит кратчайшие пути во взвешенных графах*
Алгоритм позволяет находить кратчайшие пути, рассматривая веса ребер как время в пути между узлами.
Он работает, вычисляя время пути до дочерних узлов из начальной точки.
Затем он рассматривает каждый дочерний узел и выбирает тот, который имеет наименьшее время в пути
Вычисляется время в пути до конечного узла и выбирается кратчайший результат.
Алгоритм будет работать, только если значения ребер являются положительными числами
✦
*20:03** Вычисление кратчайшего пути с помощью хэш-таблицы и связного списка*
Перебираем узлы и вычисляем минимальное время для каждого узла
Если время остается числом, это означает, что из начальной точки к узлу ведет только один путь.
Создаем связный список для сохранения кратчайшего пути и перебираем узлы от конца к началу.
Так, сразу стоп, я не понял... Зачем представлять переходы в виде данных?? Переходы надо делать, а не представлять. Тогда зачем данные, когда всё-ровно всё сведётся к переходам в коде. Jmp, jne, call, ret, int... Сразу пишем код, ну и флаги состояний.