≠ Собирай рюкзак по алгоритму, если будет NP=P
ฝัง
- เผยแพร่เมื่อ 3 ก.ค. 2024
- Есть задачи, которые решаются долго, но что значит «долго»? Все зависит от сложности алгоритма - объема работы и входных данных. Что такое задача коммивояжера, как собрать рюкзак в путешествие, и играть в тетрис в режиме Бога. Давайте разбираться вместе с математиком и может быть мы сможем решить задачу тысячелетия?
00:00 тетрис в режиме Бога
00:40 сложности задач P и NP
01:50 полиномиальные задачи, полиномиальное время
02:43 задача путешественника, как посетить все города, потратив меньше всего средств
04:06 NP недетерминированные полиномиальные
04:52 Что случится, если найдем алгоритм для решения задач NP
05:33 NP полные задачи
06:00 Задача как собрать рюкзак
06:50 опрос 100 ученых про задачи P и NP
#математика #РеальнаяМатематика #оптимизация #qwerty - วิทยาศาสตร์และเทคโนโลยี
![[UNCUT] ฝันรักห้วงนิทรา | EP.9 (3/4)](http://i.ytimg.com/vi/ikd1tEhXbp8/mqdefault.jpg)
00:00 тетрис в режиме Бога
00:40 сложности задач P и NP
01:50 полиномиальные задачи, полиномиальное время
02:43 задача путешественника, как посетить все города, потратив меньше всего средств
04:06 NP недетерминированные полиномиальные
04:52 Что случится, если найдем алгоритм для решения задач NP
05:33 NP полные задачи
06:00 Задача как собрать рюкзак
06:50 опрос 100 ученых про задачи P и NP
спс, было сложно но интересно).
очуметь..) _ кстати как раз, вовремя.. Недавно вспоминал, про степени и т.д.
Если возможно, то хотелось бы увидеть на будущее.. видео о комбинаторике.
(и какие бывают формулы решения задач о комбинаторике)
@@tinkerbel1955 Вполне вероятно, что сделаем! =)
За получение доступа ко всем зашифрованным данным на планете плата 1лям долларов) будем ждать))
А почему в умножении не 2 в степени n, умноженное на n? (2^n*n)
Типа одну цифру на другую определенное количество раз и умножить на такое же количество цифр - показывает количество вариантов
А ты с названием канала не запаривался)
Я пришёл, чтобы собирать сумку и не болело плечо, спасибо, теперь голова болит и плечо.
Только именитые учёные на вопрос типа да/нет могут сформировать 4 группы ответов
точно
А что тут формировать-то? По-моему всё просто: да нет, нет нет, нет да и да да.
Блондинка, которую уламывают на постель -- и та даёт эти же самые ответы, причём в том же порядке, стоит только подогнать под них заранее подготовленные вопросы.)
@@kotgav815 ору
@@kotgav815 xD
@@kotgav815 вспоминаем анекдот: сыну задают в школе расказать о родителях, сын приходит к отцу
-папа а сколько тебе лет?
Тот математик: -Десять лет назад мне было столько же сколько тебе умноженное на 2, а сейчас твой возраст и возраст твоей сестры умноженный на 2.
Сынок пишет: мой папа мудак.
Видос из разряда "Ничерта непонятно, но очень интересно!")
Если такие нравится, зайти в Яндекс.Рефераты и почитай =) ровно тоже самое =)))
Буквально сегодня была лекция по этой теме. Честно сказать, из видоса в 8 минут понял больше, чем за пару.
@@god_slayer-restart нет, это качество образования такое. Я тоже когда-то давно это в институте проходил, и слушал достаточно внимательно чтобы запомнить, что P - решается за полиноминальное время, а NP - нет. А вот что такое "полиноминальное время", объяснили только здесь.
@@bombazook поддерживаю. Если бы в институте остался и пытался бы понять алгоритмическую сложность то навряд ли бы понял хоть что-то. А сам разобрался весьма спокойно. Ещё можно перефразировать так, что это отношение времени к количеству данных. Всякое константное время, линейное приращение времени в зависимости от количества данных, полиномиальное и т.д.
Вот слушаю ребят умных и так хорошо становится от того, что что то понимаю... мало, но что то понимаю.... Причастен)))
0_o черт!), ты мне глаза раскрыл)). Я теперь понял, почему мне это интересно смотреть))
Именно по этой причине Перельман ходит не с рюкзаком, а с сумкой)
Задача про рюкзак - это одна из основных задач динамического программирования
И решается за n в квадрате по-моему
@@UnderKoBep
так это не возможно быстро решить, в любом случае придётся проверить все варианты, это как угадать в какой коробке больше вещей, не открывая все, получается решение и будет в степени. как сложить десятизнатные числа в два действия? только если повезёт и будет 8 нулей, или я чего-то не понял, смысл этого видео? для простых задач можно подобрать быстрое решение, а для максимально сложных и решение будет такое
@@UnderKoBep есть эвристические алгоритмы, позволяющие получить результат за приемлемое время, но с некоторыми оговорками, на которые на практике всем насрать. А в математике всё не так, там нужен точный алгоритм, срабатывающий всегда, иначе это не считается.
Рюкзак работает за O(MN) N - количество вещей, M - масса
А задачу про города можно перевести на граф с использованием алгоритма Дийкстры
Первый раз вижу объяснение этой задачи, понятным человеческим языком. Спасибо, вам!
Если кому-то интересна эта тема, есть отличная книга :Бхаргава Адитья Грокаем алгоритмы. В видео все примеры от туда
У меня «Эффект Баадера Майнхофа», 3 дня назад дочитал, а тут видео...
Подтверждаю
А если хотите окончательно сломать мозг: "Алгоритмы: построение и анализ" (с ветками на обложке)
А слово "грокаем" из Хайнлайна
М-да, "сумничал" называется. Я-то книгу про алгоритмы не читал и не видел, а там, оказывается, прямо на обложке цитата из Хайнлайна. Но я-то не из цитаты это знаю, а потому что прочитал "Чужак в стране чужой" от корки до корки. Дважды.
Про задачу с рюкзаком. Вы сказали, что задача переборная, но если я правильно понял смысл задачи, то мы же можем просто рассчитать стоимость каждого кубического см вещи и класть в рюкзак вещи с наибольшей плотностью дороговизны. Правда если мы положем например дорогущие сережки, дорогой телескоп, то для следующего прдемета по списку плотности дороговизны уже может места не хватит и придется искать менее плотные предметы. Пока писал комментарий- сам себя разубедил=)
Там еще сложность в каком месте рюкзака положить эти вещи, получается такой тетрис в 3D + задача оптимизации стоимости.
по обьему считать нельзя, потому что ты можешь не суметь расположить все предметы геометрически, тоесть у тебя мяч большой влезет, но для остальных предметов не хватит места
Там по-моему про вес было а не про объём.
@@artemmetra8 по весу тоже самое, только вместо тетриса в 3-ёх измерениях, у тебя будет тетрис в одномерном пространстве.
Например: рюкзак расчитан на 10 кг;
Список предметов: 2 слитка чистого золота по 5.1 кг: и 2 слитка золота низкой пробы по 5 кг.
если цена отличается не более чем в 2 раза, то выгоднее взять 2 слитка низкой пробы, не смотря на то, что цена за кг у них меньше.
На самом деле задачу о рюкзаке можно решить методом разбора её на подзадачи, то есть: рассчитать максимальную стоимость для 1 кг, потом для 2кг и тд. Если интересно: книга «Грокаем алгоритмы»
На математике просмотров наверно мало. Но было интересно. Правда не все с разу понятно пришлось подумать))
Обожаю выпуски Георгия. продолжайте 👍🙂
Спасибо! Это супер важная задача
Спасибо за видео, самое понятное объяснение про классы Р и NP
Крууть! Расскажи как-нибуть ещё про решения задач симплекс методом.
Спасибо за видео.
Дико интересно! Давайте больше мозголомательной математики!
Спасибо!
И как Вам мозг изнутри глаза не выдавил? ))
Он иногда играет в современные мейнстрим шутеры, чтобы контролировать рост
Не дождётесь
С начальной школы недолюбливаю математику. Но Георгий так доходчиво объясняет, что это интересно. Печально, что у нас в школах методика преподавания была другой...
Ну, технически это не математика школьного уровня, а программа теоретической информатики, которая ближе к универу.
просто в восторге, млн бачей за уничтожение мира
И если уничтожится, то куда их тратить?) Разве что подтереться.
Можно было ещё рассказать о том, какую роль в данном контексте играют квантовые компьютеры. Это тоже занятно)
Вот вот, было бы здорово послушать
А практически никакую, прочитайте книгу «золотой билет» как раз про p и np. Штука в том, что чтобы выгрузить из квантового компьютера результат вам потребуется np алгоритм , приблизительно так.
@@MySaluto , интересно. Тогда получатся, что вообще в квантовых компьютерах смысла нет?
тот неловкий момент, когда живешь в Братиславе :D
Слава славянской славакии.
Братиславе? Зачем жить в брате Славы?
У вас реально там такие дома?
Почему так мало - всего лишь миллион долларов за столь сложную и ценную для человечества задачу? Вот, некоторые у себя в квартире миллиарды держат, при этом ничего ценного для человечества не дали.
@@bearmagistr6879 снимают смешные видосики на ютубе? Фоткают жопы в инстаграм? Удачно инвестировали деньги в нужное время? Может, просто напиздили из гос бюджетов?...
А настоящие гении человечества при этом довольствуются объедками капитализма
@@ElimDax01 Не стоит так резко разбрасываться громкими словами, хотя в чем то вы правы.
Потому что это частная инициатива отдельного вуза
так мало, чтобы уменьшить стимул уничтожить криптографию
Спасибо, наконец-то разобралась, в Вики так себе было объяснение
Вот ради таких роликов я и подписался. Пусть редко, но мне хватит )))
Опять мне этот чувак взорвёт мозг.Лайк.
Спасибо
Рюкзак заполнить жёстким диском с биткоинами и калифорнием)
Класс
Ух ты!
Слишком тяжелая информация для меня. Посмотрю когда буду готовым к этому ролику))))
Заходи ко мне, я помогу с этим делом!):)
Это такой синоним слова никогда?
Юрий Якунин сильно много слов в одно превращаешь
лайк не глядя, пошла глядеть
Читал книгу Грокаем алгоритмы на питон и залетел сюда за дополнительной информацией. Стало понятнее
Я с такой грыжей сталкивался, когда ехал на регион по программированию. Было прикольно послушать
Что тут сказать, спасибо за идею по заработку 1 миллиона $$$
Уверен, есть более короткие пути по заработку миллиона)
Круто
как раз читаю книгу по алгоритмам и дошел до алгоритмов np сложности, и в качестве альтернативы показывают "жадные" алгоритмы, но не точные
10 классов проучился и впервые об этом слышу.
а школе, как правило, не учат такому, только в специальных математических. Такое тебе расскажут в универе на дисциплине: теория алгоритмов или сложность вычислений
👍
Хотелось бы ещё услышать про остальные задачи тысячилетия!!!!
нихуя не понял, но очень интересно
Очень интересно, хоть сложновато понять.
P.S. подскажи что за трек на фоне и в конце
Задача с рюкзаком самая важная. В Diablo постоянно с ней сталкиваюсь.
Заходи ко мне решать задачки:)
@@JuraSheingart нет
Я тут пришёл рюкзак собирать, а не задачи решать)
кстати, нынче умножают со сложностью n*log(n)
ZecosMAX примерно с 70-ых умножают быстро, и вот буквально месяц как вы написали)
Как же всё таки близки олимпиадное программирование и олимпиадная математика
А из каких фильмов взяты эпизоды?
Ничего не понял но очень интересно 🐒
Георгий
Богом молю, подскажите что у вас за наручные часы!
А ролик огонь, очень доходчиво все
Ничего не понял, но было интересно!
Не до конца вдуплился в тему выпуска. Но мне понравилось.
Что за карта использовалась на 4 минуте, странный выбор городов для отображения.
А я думал будет разбор задачи о рюкзаке по теории игр рассмотренной в качестве кооперативной игры
ничего не понял, но продолжайте )
Интересно, как изменится соотношение мнений учёных с течением времени.
*Ну чисто по моему это вычисляется вероятностью,то есть можно предположить что NP при каком-то условии равно P,ну то есть формулу можно написать так NP≝P,или же так NP≈P*
Не знаю зачем я полез в то что не знаю,но это чисто мое предположение
P.S мое предположение в том,что есть куча знаков равно,и какой то из них подходит для формулы,тупо но мало ли
На самом деле они либо равны, либо нет, и никак иначе. Они не могут быть примерно равны. Мы можем быть уверенны только в том что NP=P или NPXP, и еще возможно в том что доказать это не возможно.
Расскажите подробнее, что там Перельман доказал
Объяснили. Я понял.
Но зачем?
Тревожную музыку на фоне надо убрать
Что за фильм в видео показан относительно путешествий? (3:00)
Евротур.
Многочлен)
Хм. Проще простого. Нужно проверить каждую вещь по отдельности, бесконечно складывая её в рюкзак до тех пор, пока не будет учитанны все возможные варианты складывания этой вещи, потом вторую проверить и т.д., потом просто взять и наложить все возможные варианты друг на друга и посмотреть, ибо в таком случае только 1 комбинация будет единственная, когда все вещи будут сложенны в самом оптимизированном состоянии, при таком условии вместимости рюкзака.Остальные комбинации или невозможны, или недостаточно идеально оптимизированны. В общем NP≠P, это совсем другой класс решения задач, и я не математик, и не суперкомпьютер, и поэтому патаюсь найти наиболее точное решение такой задачи в голове. Однако такой алгоритм очень простой, и очень легёк в усвоении. И вы правы, благодаря такому алгоритму я решаю(примерно) все задачи вида NP. Например в играх пытаюсь просчитать лучшую тактику для ведения боя и т.п.
Псы. Я сказал глупо и не научно. Но черт возми правильно.
Разумная Ящерица слишком сложно, это тупо брутфорс
Не хочу быть дотошным, но
02:12 : "Сложность аглоритма увеличивается полномиально..."
Такие оговорки могут ввести в заблуждение человека , который никогда с этим не сталкивался
у меня есть способ решения задачи рюкзака за полим. время!! можете расскритиковать? как с вами связатся?
Ничего не понял, но было интересно.
Подумал что расскажут какой-нибудь математический способ собрать рюкзак комивояжёра а в итоге появилась фобия взлома личных данных
Задача на поиск оптимального маршрута из точки + посетить несколько точек + вернуться обратно решается за n! перебором (n количество точек что мы хотим посетить). Правильно ли я понял что если я смогу решить эту задачу за n^2 или log(n) то мне дадут миллион баксов?
за решение этой задачи скорее всего открутят голову... очень решительно.
Ничего не понял, но очень интересно
Может быть np задача сама формируется и решается по алгоритму,который тоже формируется сам в ходе ряда событий?То есть задача есть алгоритм.
"Я бы мог решить , но это слишком скучно " you
Для решения этой задачи не нужен алгоритм по скольку нету бесконечного числа переменных.
на коммивояжоре он поржал,а на многочлене сдержался!)))
А мне интересно, если Перельман решит эту задачу,он снова не возьмет деньги?
Будет зависеть от того, сможет ли он сложить деньги в рюкзак за полиномиальное время.
Я просто любитель, который пытается решить PvNP и уже убил около 9 лет на это. Я более чем уверен, что они не равны, но чтобы доказать это нужно: новая логика, новая теория множеств, новый тип комплексного анализа на недоступных кардиналах и суперконтиннумах. Это то что я понял, что мне нужно сделать с нуля. Поэтому я не думаю, что кто-то случайный сможет всё это решить так легко. А в вашем видео всё выглядит как-то скомкано и не досказано, даже для новичка. Краткий список претензий: где NP-Complete? где P/Poly, где NP-Intermediate, где рандомизированные и квантовые алгоритмы, где упоминание факторинга чисел, где полиномиальные редукции, где универсальная машина Тьюринга, где языки для этой машины(классы языков) и т.д.? Видео очень слабенькое, если берётесь за открытую математическую проблему, то уж хоть разъясняйте почему она сложная, а то опять будут сотни «доказательств последней теоремы ферма», которыми будут мучить профессиональных математиков). Ах да, а ещё и барьеры с Ораклами, булевыми схемами, алгебраизация. Тема просто фантастически объёмная и сложная. Позовите Александра Разборова из института Стеклова в Москве, я думаю он вам годноты напишет
наконец то понял че за дичь эта "нп = п" спасиб)
Я думал типо я такой умный пока не зашёл на видос. (думал N*P=P / 0*0=0)))))
O(n!).
Решается, но решаться будет по миллиардам лет.
Привет, Георгий ! 🌞😉👌
Вау ! - Это Круто ! 🌞🙌🙏😉👌
Решить Тера сложную задачу,
Послать к хренам всю безопасность в интернете,
и получить за это Милллллион ! 🌞😉✌
Круто, я согласен ! 😂🤣👌
Когда начинать ?
А у вас есть печенки, с чаем ?
Я очень люблю чёрный чай с кусочком лимона ! 🌞😉👍
3:07 это же Припять из сталкер ТЧ?
Я доказал, но не расскажу из добрых побуждений.
Всегда интересовало, правильно ли будет следующие утверждение: если инопланетяне, прямо сейчас, посмотрят в сверхмощный телескоп на нашу планету на расстоянии 100 млн световых лет, то увидят живых динозавров, хотя по факту, в настоящем, они уже давно вымерли?
оно правильно в своей сути, вероятно
мы и правда видим в небе прошлое, ученые так и изучают историю
смотрят куда нибудь далеко, и чем дальше, тем ближе по времени к началу времен
Задачу о рюкзаке можно решить за псевдополиномиальное время методами динамического программирования.
Nope. Unless under the term "pseudo-polynomial" you mean exponential but suppressed one ;o). You indeed may suppress exponent considerably yet, it remains to be exponent. Similarly with correcting algorithms for problem of allocation and coverage problem the time-exponent can be considerably suppressed as well. Although, the real-life cases for this problems may indeed on average take a polynomial time to solve similarly as the simplex-method does not warranty polynomial time for all cases but practically it shows P time for real life input data.
Очень интересное видео, но перегруз на петле прям боль 😢
О да. Ещё и хромакей лагает, когда он руками резко двигает.
42 !
P 42 NP
Вот и все
Чисто подставила единицу в эту формулу и доказала, что np=p, a p=np
Ничего непонятно, но очень интересно
Я может неправильно понял значение слова алгоритм применительно к этим задачам или еще что-то, но разве задачу с рюкзаком (если берем ограничение по весу и требуется максимальная стоимость) не решается так: для каждой вещи делим ее стоимость на вес, по полученному числу сортируем все вещи по убыванию, а затем набираем вещи сверху вниз пока рюкзак не заполнится по весу?
Нет, потому что вещи неделимые и могут быть ситуации, когдв выгоднее в рюкзак положить две вещи менее выгодные, чем одну более выгодную для более плотной упаковки. То есть пустого места в рюкзаке тоже должно остаться минимум.
Так я не поняла, рюкзак то как собирать? Где ответ на этот вопрос? Сижу уже у рюкзака и что дальше? 🤔
* в замешательстве... 🤯
Мой гуманитарный мозг ушел не сказав куда
P != NP at least for Turing/Von-Neumann machine. The proof: Black box of unknown origin has _N_ binary inputs and one binary output. The only known property of this black box is that only one specific input combination may cause "1" output and all other inputs will give "0" output. Apparently that number of all possible "black boxes" with such property == N^2. Randomly selected black box from set of all possible such black boxes will require on average (N^2)/2 operations to determine the input combination which gives "1" output for the specific randomly selected black box. The class of such black boxes belongs to NP class; the class of such black boxes has no other properties as only a single "1" output for all N^2 inputs => essentially it is defined to belong NP class. Thus, at least one example of NP!=P problem can be explicitly constructed; BTW, It has been shown that a non-local hidden variable quantum computer could implement a search for O(cubic_sqrt(N^2)) steps or O(sqrt(N^2)) for more traditional QC (Grover's algorithm).
У меня мир вокруг чуть полиномиальным не стал :)
Пожалуйста, больше не говори это слово :)))
Ахаха))) Заходи ко мне такие же комментарии писать:) (у меня видео очень короткие, прокачаешься)
Задача на жизнь: NP=P :D
Забавно. Тот, кто получит этот миллион не положит его в банк.
ничего не понял, но очень интересно
ТЕЕЕТТТРРРИИИИССС!!!
Ave Satan (на кадре с картой)
Освобождаю рюкзак для миллиона долларов!
По поводу сбора вещей в рюкзак. Почему нельзя найти отношение стоимость/вес каждого предмета и брать вещи с наибольшим этим коэффициентом?
Потому что тогда решение не обязательно будет самым оптимальным. Приведу пример.
Пускай вместимость рюкзака равна 7 кг и есть следующий набор предметов: а1 с весом 3 и стоимостью 3, а2 с весом 2 и стоимостью 2, а3 такая же, а4 весом 6 и стоимостью 6,5.
Вещи а1, а2 и а3 имеют соотношение 1, а4 - 1.08.
Если положим вещь с наибольшим соотношением, то никакая другая не влезет (остаётся всего 1 кг, а наиболее лёгкая вещь весит 2), получим стоимость 6,5.
Если положить 3 остальных вещи, то получим как раз 7 кг и стоимостью 7.
Наиболее оптимальное решение для данного примера исключает вещь с наилучшим соотношением.
задача с сбором содержимого сумки полиноминальна
но если предметы имеют больше измерений чем просто вес - все станет намного сложнее
хотя... и это можно обойти. придется знать "важность" каждого параметра
Если можно ложить только целое количество предметов, то эта задача становится NP
Было количество операций и вдруг стало количесво времени)
Количество времени пропорционально количеству операций
@@mihail-ln4rf это, как минимум, требует пояснения