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
спс, было сложно но интересно). очуметь..) _ кстати как раз, вовремя.. Недавно вспоминал, про степени и т.д. Если возможно, то хотелось бы увидеть на будущее.. видео о комбинаторике. (и какие бывают формулы решения задач о комбинаторике)
А почему в умножении не 2 в степени n, умноженное на n? (2^n*n) Типа одну цифру на другую определенное количество раз и умножить на такое же количество цифр - показывает количество вариантов
А что тут формировать-то? По-моему всё просто: да нет, нет нет, нет да и да да. Блондинка, которую уламывают на постель -- и та даёт эти же самые ответы, причём в том же порядке, стоит только подогнать под них заранее подготовленные вопросы.)
@@kotgav815 вспоминаем анекдот: сыну задают в школе расказать о родителях, сын приходит к отцу -папа а сколько тебе лет? Тот математик: -Десять лет назад мне было столько же сколько тебе умноженное на 2, а сейчас твой возраст и возраст твоей сестры умноженный на 2. Сынок пишет: мой папа мудак.
@@god_slayer-restart нет, это качество образования такое. Я тоже когда-то давно это в институте проходил, и слушал достаточно внимательно чтобы запомнить, что P - решается за полиноминальное время, а NP - нет. А вот что такое "полиноминальное время", объяснили только здесь.
@@bombazook поддерживаю. Если бы в институте остался и пытался бы понять алгоритмическую сложность то навряд ли бы понял хоть что-то. А сам разобрался весьма спокойно. Ещё можно перефразировать так, что это отношение времени к количеству данных. Всякое константное время, линейное приращение времени в зависимости от количества данных, полиномиальное и т.д.
Про задачу с рюкзаком. Вы сказали, что задача переборная, но если я правильно понял смысл задачи, то мы же можем просто рассчитать стоимость каждого кубического см вещи и класть в рюкзак вещи с наибольшей плотностью дороговизны. Правда если мы положем например дорогущие сережки, дорогой телескоп, то для следующего прдемета по списку плотности дороговизны уже может места не хватит и придется искать менее плотные предметы. Пока писал комментарий- сам себя разубедил=)
по обьему считать нельзя, потому что ты можешь не суметь расположить все предметы геометрически, тоесть у тебя мяч большой влезет, но для остальных предметов не хватит места
@@artemmetra8 по весу тоже самое, только вместо тетриса в 3-ёх измерениях, у тебя будет тетрис в одномерном пространстве. Например: рюкзак расчитан на 10 кг; Список предметов: 2 слитка чистого золота по 5.1 кг: и 2 слитка золота низкой пробы по 5 кг. если цена отличается не более чем в 2 раза, то выгоднее взять 2 слитка низкой пробы, не смотря на то, что цена за кг у них меньше.
На самом деле задачу о рюкзаке можно решить методом разбора её на подзадачи, то есть: рассчитать максимальную стоимость для 1 кг, потом для 2кг и тд. Если интересно: книга «Грокаем алгоритмы»
М-да, "сумничал" называется. Я-то книгу про алгоритмы не читал и не видел, а там, оказывается, прямо на обложке цитата из Хайнлайна. Но я-то не из цитаты это знаю, а потому что прочитал "Чужак в стране чужой" от корки до корки. Дважды.
@@UnderKoBep так это не возможно быстро решить, в любом случае придётся проверить все варианты, это как угадать в какой коробке больше вещей, не открывая все, получается решение и будет в степени. как сложить десятизнатные числа в два действия? только если повезёт и будет 8 нулей, или я чего-то не понял, смысл этого видео? для простых задач можно подобрать быстрое решение, а для максимально сложных и решение будет такое
@@UnderKoBep есть эвристические алгоритмы, позволяющие получить результат за приемлемое время, но с некоторыми оговорками, на которые на практике всем насрать. А в математике всё не так, там нужен точный алгоритм, срабатывающий всегда, иначе это не считается.
С начальной школы недолюбливаю математику. Но Георгий так доходчиво объясняет, что это интересно. Печально, что у нас в школах методика преподавания была другой...
Почему так мало - всего лишь миллион долларов за столь сложную и ценную для человечества задачу? Вот, некоторые у себя в квартире миллиарды держат, при этом ничего ценного для человечества не дали.
@@bearmagistr6879 снимают смешные видосики на ютубе? Фоткают жопы в инстаграм? Удачно инвестировали деньги в нужное время? Может, просто напиздили из гос бюджетов?... А настоящие гении человечества при этом довольствуются объедками капитализма
А практически никакую, прочитайте книгу «золотой билет» как раз про p и np. Штука в том, что чтобы выгрузить из квантового компьютера результат вам потребуется np алгоритм , приблизительно так.
Я просто любитель, который пытается решить PvNP и уже убил около 9 лет на это. Я более чем уверен, что они не равны, но чтобы доказать это нужно: новая логика, новая теория множеств, новый тип комплексного анализа на недоступных кардиналах и суперконтиннумах. Это то что я понял, что мне нужно сделать с нуля. Поэтому я не думаю, что кто-то случайный сможет всё это решить так легко. А в вашем видео всё выглядит как-то скомкано и не досказано, даже для новичка. Краткий список претензий: где NP-Complete? где P/Poly, где NP-Intermediate, где рандомизированные и квантовые алгоритмы, где упоминание факторинга чисел, где полиномиальные редукции, где универсальная машина Тьюринга, где языки для этой машины(классы языков) и т.д.? Видео очень слабенькое, если берётесь за открытую математическую проблему, то уж хоть разъясняйте почему она сложная, а то опять будут сотни «доказательств последней теоремы ферма», которыми будут мучить профессиональных математиков). Ах да, а ещё и барьеры с Ораклами, булевыми схемами, алгебраизация. Тема просто фантастически объёмная и сложная. Позовите Александра Разборова из института Стеклова в Москве, я думаю он вам годноты напишет
а школе, как правило, не учат такому, только в специальных математических. Такое тебе расскажут в универе на дисциплине: теория алгоритмов или сложность вычислений
*Ну чисто по моему это вычисляется вероятностью,то есть можно предположить что NP при каком-то условии равно P,ну то есть формулу можно написать так NP≝P,или же так NP≈P* Не знаю зачем я полез в то что не знаю,но это чисто мое предположение P.S мое предположение в том,что есть куча знаков равно,и какой то из них подходит для формулы,тупо но мало ли
На самом деле они либо равны, либо нет, и никак иначе. Они не могут быть примерно равны. Мы можем быть уверенны только в том что NP=P или NPXP, и еще возможно в том что доказать это не возможно.
Хм. Проще простого. Нужно проверить каждую вещь по отдельности, бесконечно складывая её в рюкзак до тех пор, пока не будет учитанны все возможные варианты складывания этой вещи, потом вторую проверить и т.д., потом просто взять и наложить все возможные варианты друг на друга и посмотреть, ибо в таком случае только 1 комбинация будет единственная, когда все вещи будут сложенны в самом оптимизированном состоянии, при таком условии вместимости рюкзака.Остальные комбинации или невозможны, или недостаточно идеально оптимизированны. В общем NP≠P, это совсем другой класс решения задач, и я не математик, и не суперкомпьютер, и поэтому патаюсь найти наиболее точное решение такой задачи в голове. Однако такой алгоритм очень простой, и очень легёк в усвоении. И вы правы, благодаря такому алгоритму я решаю(примерно) все задачи вида NP. Например в играх пытаюсь просчитать лучшую тактику для ведения боя и т.п. Псы. Я сказал глупо и не научно. Но черт возми правильно.
Не хочу быть дотошным, но 02:12 : "Сложность аглоритма увеличивается полномиально..." Такие оговорки могут ввести в заблуждение человека , который никогда с этим не сталкивался
задача с сбором содержимого сумки полиноминальна но если предметы имеют больше измерений чем просто вес - все станет намного сложнее хотя... и это можно обойти. придется знать "важность" каждого параметра
Всегда интересовало, правильно ли будет следующие утверждение: если инопланетяне, прямо сейчас, посмотрят в сверхмощный телескоп на нашу планету на расстоянии 100 млн световых лет, то увидят живых динозавров, хотя по факту, в настоящем, они уже давно вымерли?
оно правильно в своей сути, вероятно мы и правда видим в небе прошлое, ученые так и изучают историю смотрят куда нибудь далеко, и чем дальше, тем ближе по времени к началу времен
Привет, Георгий ! 🌞😉👌 Вау ! - Это Круто ! 🌞🙌🙏😉👌 Решить Тера сложную задачу, Послать к хренам всю безопасность в интернете, и получить за это Милллллион ! 🌞😉✌ Круто, я согласен ! 😂🤣👌 Когда начинать ? А у вас есть печенки, с чаем ? Я очень люблю чёрный чай с кусочком лимона ! 🌞😉👍
С задачей про рюкзак изи, без всякого перебора... просто у каждой вещи считаем цена одного грамма (делим ценность на ее вес), потом сортируем от большей ценности к меньшей... далее отбираем более ценные вещи (считая их вес) пока не дойдем до максимального веса который может выдержать рюкзак...
Тут вопрос не в алгоритме в целом, а в количестве операция на шмотку, т.е. 2^n - брутфорс для NP, да так проблемы решаются, но ты спроси себя, что если у тебя будет хотя бы 100 шмоток или больше? Вот тут-то и нужно всё сводить к n^3 хотя бы)
Вы не совсем корректно, наверное, поняли задачу. Ваше решение отлично подойдет, если бы в рюкзак складывали крупы, т.е. мы без проблем могли бы взять лишь часть предмета. В нашем же случае возможна ситуация, которая ломает ваше решение. Рассмотрим несколько предметов: ноутбук (стоимость 113, масса 9), мяч (стоимость 75, масса 6), книга (стоимость 20, масса 2), бутылка с водой (стоимость 20, масса 2). Ваш алгоритм возьмет только ноутбук (остальные предметы не влезут), в то же время совершенно ясно, что выгоднее взять мяч, книгу и бутылку с водой.
@@gcomsu5819 Я забыл указать, что наш рюкзак может вместить лишь вещи массой 10. Задача же состоит в максимизации стоимости предметов в нем. Причем нам совершенно без разницы, какова масса предметов в рюкзаке, если она не превышает 10, главное - суммарная стоимость. Надеюсь, что теперь понятна сложность задачи.
Для задачи с рюкзаком видел жадный алгоритм. Он представляет из себя что то такое: 1) делим массу каждого предмета на его стоимость. Таким образом получая "удельную стоимость" 2) предметы с максимальной удельной стоимостью кладём в рюкзак пока не закончится место
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.
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).
Ahdruxa неверный подход ввиду того, что запихивая в первую очередь самые ценные вещи у вас может не полностью использоваться пространство Контрпример вашего суждения: 93 кг 10000р 5 кг 5000р 3 кг 2900р 4 кг 3880р
Самое приятное, это конечно не парить мозги с матаном, а браться решать задачу коммивояжера. Если вы не шизоид, то сами сложите все идеи, вопросы и методы работы с данными в своб математику. А вопрос интерпретации дело пустяковое. Так, я решаю коммивояжера порядка двух лет и с радостью могу поделиться тем, что достиг успехов. Сам топик видео говорит о том, что математики креативят и у них есть простые решения определенных примеров задачи,это подразумевает, что пляска от верного ответа к поиску самого алгоритма/метода решения имеет место быть. А диссонанс мозга происходит, когда ты по сути уже решил задачу и ищешь зацепку, т. е. проблему/ошибку. Её же там нет. Но и неправильного ответа нет, потому что неправильные ответы используют неправильный алгоритм/метод. А правильного метода нет. Интересно получается.
Так, лучший способ работы с математической задачей является: 1 сбор информации о том, что вы решаете. Определение сути задачи. 2 упрощение задачи с сохранением ее целостности. 3 составление вариаций данной задачи. 4 поиск закономерностей данных, т. е. определение категорий (групп, зависимостей). *здесь важно отметить, что вы тратите свое время не на слепой перебор решения задачи, а слепой перебор на выявление закономерностей в ней, т. е. данный процесс избыточен и является сбором информации о задаче. 5 определение связи закономерностей друг относительно друга с целью отбора уникальных закономерностей от основных (априорных). 6 проверка наличия основных закономерностей на остальных вариациях задачи. 7 аргументация/обоснование существования уникальных закономерностей. 8 проверка наличия уникальных закономерностей в остальных вариациях задачи. 9 определение противоречия, т. е. когда определение наличия или отсутствия уникальных закономерностей в остальных вариациях задачи и обоснование их уникальности. 10. Определение категорий уникальных закономерностей в вариациях задачи и нахождение их взаимосвязи (если они в одной категории). 11 обоснование отсутствия уникальности данных закономерностей, т. е. мы поясняем, почему это не новое, а измененное старое. Сводим уникальность закономерностей в класс основных/ априорных закономерностей. 12. Находим взаимосвязь или закономерности между закономерностями УЖЕ одной категории (т.е. категории основных, априорных закономерностей). 13. Определяем суть новых основных закономерностей и подводим итог, т. е. Определяем суть решения и проверяем.
Раньше в ВУЗах всю категорию NP определяли как нелинейное программирование. сюда также относили задачу коммивояжера. А теперь вопрос: зачем менять название на непонятное, чтобы возникала необходимость объяснять сущность полинома и еще больше усложнять? Современные авторы учебников совсем забыли бритву Оккама.
*Составить список имеющихся вещей, разбить по категориям и выдать каждому предмету баллы от 1 до 100 по их полезности, а затем получим сумму балов за каждый кубический сантиметр каждого предмета. Складываем в рюкзак самые ценные сантиметры из каждой категории*
1) А если окажется, что P =/= NP ? Тогда доступа ко всем банковским картам у тебя не будет, а вот миллион за доказательство получить можно. 2) Чтобы получить миллион за решение этой задачи, достаточно доказать существование алгоритма, решающего NP задачи за время P, а не предъявлять пример такого алгоритма. Может быть, доказать его существование значительно проще, чем найти сам алгоритм. В таком случаи доступа к картам не будет. 3) Может оказаться так, что P=NP и алгоритм решения NP за время P будет найден, но при этом сложность этого алгоритма всё равно окажется непомерно высокой для современных компьютеров. Даже при сложности алгоритма n^100 ( n в степени 100 ) взломать с его помощью банк используя частный компьютер будет практически невозможно (во всяком случаи это будет дольше человеческой жизни), при сложности n^1000 в мире едва ли надётся компьютер способный на это (даже все кластеры google вместе взятые, или даже все компьютеры подключённые к интернету вместе взятые), а при сложности n^10000 такую задачу, не решит даже компьютер размером с Землю (по крайней мере за время меньше человеческой жизни.)
@@Kmiarg , мощность среднестатистического домашнего компьютера примерно 3-15 тераФЛОПС. Но мощность сети биткойн в прошлом году была 67260548 ПетаФЛОПС. Сколько времени нужно, чтобы такой мощностью выполнить рассчеты? Пс. Видюха уровня 1050-1060 взламывает пароль wi-fi состоящий из 8 цифр за 15 минут.
@@DigiMakc на самом деле я лишь предположил цифры что написал выше, чтобы примерно показать что такое степенной рост, реальные расчёты сильно зависили бы от коэффициентов перед n. Но раз вас интересуют более точные расчёты, вот что могу сказать о приведённых вами цифрах: 1) возмём для примера мощность домашнего компьютера раную 2 тераФЛОПС, тогда во сколько раз мощность сети биткойн больше? Ответ: в 2^26 раз, это чуть меньше чем 10^8. Кажется, только теперь я начал понимать, какой невероятно огромный космический запас я заложил между n^100 и n^1000, потому что разница между ними в n^900 раз, это явно перебор. 2) если пароль или система шифрования не содержит известных уязвимостей, то сложность такой задачи составляет ~ 16^8. поскольку каждый символ в wi-fi пароле может принимать лишь 1 из 16 возможных значений, и это число мы возводим в 8 степень из-за длинны пароля. итак если пароль из 8 символов подбирается за 15 минут, то пароль из 9 символов будет подбираться в 16 раз дольше, то есть 240 мин = 4 часа, пароль из 10 символов 64 часа = 5+1/3 суток, пароль из 11 символов - 85 дней, из 12 симв. - 3,7 лет, из 13 симв. - 59,8 лет из 14 симв. - 957 лет из 15 симв. - 15 321 год - и это всё лишь в том случаи, исходный алгоритм не содержал каких-то оптимизаций по времени, за счёт увеличения затрат памяти. (а если препологает то сроки будут ещё больше, когда закончиться память видеокарты и оперативная память, и придётся активно загружать данные с диска) из 16 симв. - 245 146 лет. Кстати именно 16 сивольные пароли используются сейчас. И тут стоить вспомнить, что для шифрования финансовых данных сейчас используются файл-ключи или USB-ключи. Быстрый поиск показал, что сейчас в продаже есть USB-ключи с паролем длинной 32Кб, 64Кб, 128Кб. И там каждый байт(символ) может быть любым от 0 до 255, то есть сложность их взлома будет от 256^(1024*32) до 256^(1024*128)... это число 2^(2^20) Если кто смотрел видео про число Гремма или знаком со стрелочной нотацией, то это число можно записать как 2↑20 , или просто 2 в более чем миллионной степени... у такого числа даже названия вряд ли найдётся. PS это я ещё не учитывал, что более длинные пароли и ключи надо проверять на более длинных блоках данных, что так же занимает всё больше и больше времени с ростом n. Из-за этой особенности программы полного перебора имеют сложность n^n или подобную. Я же рассматривал в примере const^n , что значительно меньше n^n, но для нижней оценки по времени сгодиться и так.
Вроде как необходимость в поике алгоритма решения NP задач скоро может отпасть, за счет квантовых компьютеров. Таким образом эта задача перейдет из разряда практических в разряд чисто научных.
Если P=NP, то задача доказательства-тоже NP задача. Если это можно доказать, то всё сходится, а если нельзя, то мы нашли не П, а НП задачу. То есть, доказали неравенство. Значит, если П=НП, это можно доказать. Если не равно, а доказать можно, то мы найдём одну НП=П. Но всё в порядке-единичный случай ничего не показывает. Если доказать это нельзя, то одна "нерешаемая" НП задача найдена. Но всё в порядке-единичный случай ничего не показывает. Если NP=P, то это можно доказать, а если NPне =P, то насчёт доказательства- неопределённость.
Я может неправильно понял значение слова алгоритм применительно к этим задачам или еще что-то, но разве задачу с рюкзаком (если берем ограничение по весу и требуется максимальная стоимость) не решается так: для каждой вещи делим ее стоимость на вес, по полученному числу сортируем все вещи по убыванию, а затем набираем вещи сверху вниз пока рюкзак не заполнится по весу?
Нет, потому что вещи неделимые и могут быть ситуации, когдв выгоднее в рюкзак положить две вещи менее выгодные, чем одну более выгодную для более плотной упаковки. То есть пустого места в рюкзаке тоже должно остаться минимум.
Если серьёзно,то вопрос задачи по-человечески звучит так, - "Можно ли выучить китайский, тайский и айский за 5 минут, используя некий алгоритм формул?" И за его нахождение тебе дадут мильон. Сразу попробую предположить, что такой алгоритм существует и его существование описано в Новом Завете, когда неграмотные апостолы в одно мгновенье заговорили на нескольких иностранных языках при многочисленных свидетелях. Поэтому исторически зафиксированно его существование и можно сделать вывод что NP=P. Но как найти такой алгоритм? Видимо нужно подключить режим Бога.
Потому что тогда решение не обязательно будет самым оптимальным. Приведу пример. Пускай вместимость рюкзака равна 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. Наиболее оптимальное решение для данного примера исключает вещь с наилучшим соотношением.
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 черт!), ты мне глаза раскрыл)). Я теперь понял, почему мне это интересно смотреть))
Про задачу с рюкзаком. Вы сказали, что задача переборная, но если я правильно понял смысл задачи, то мы же можем просто рассчитать стоимость каждого кубического см вещи и класть в рюкзак вещи с наибольшей плотностью дороговизны. Правда если мы положем например дорогущие сережки, дорогой телескоп, то для следующего прдемета по списку плотности дороговизны уже может места не хватит и придется искать менее плотные предметы. Пока писал комментарий- сам себя разубедил=)
Там еще сложность в каком месте рюкзака положить эти вещи, получается такой тетрис в 3D + задача оптимизации стоимости.
по обьему считать нельзя, потому что ты можешь не суметь расположить все предметы геометрически, тоесть у тебя мяч большой влезет, но для остальных предметов не хватит места
Там по-моему про вес было а не про объём.
@@artemmetra8 по весу тоже самое, только вместо тетриса в 3-ёх измерениях, у тебя будет тетрис в одномерном пространстве.
Например: рюкзак расчитан на 10 кг;
Список предметов: 2 слитка чистого золота по 5.1 кг: и 2 слитка золота низкой пробы по 5 кг.
если цена отличается не более чем в 2 раза, то выгоднее взять 2 слитка низкой пробы, не смотря на то, что цена за кг у них меньше.
На самом деле задачу о рюкзаке можно решить методом разбора её на подзадачи, то есть: рассчитать максимальную стоимость для 1 кг, потом для 2кг и тд. Если интересно: книга «Грокаем алгоритмы»
Если кому-то интересна эта тема, есть отличная книга :Бхаргава Адитья Грокаем алгоритмы. В видео все примеры от туда
У меня «Эффект Баадера Майнхофа», 3 дня назад дочитал, а тут видео...
Подтверждаю
А если хотите окончательно сломать мозг: "Алгоритмы: построение и анализ" (с ветками на обложке)
А слово "грокаем" из Хайнлайна
М-да, "сумничал" называется. Я-то книгу про алгоритмы не читал и не видел, а там, оказывается, прямо на обложке цитата из Хайнлайна. Но я-то не из цитаты это знаю, а потому что прочитал "Чужак в стране чужой" от корки до корки. Дважды.
Задача про рюкзак - это одна из основных задач динамического программирования
И решается за n в квадрате по-моему
@@UnderKoBep
так это не возможно быстро решить, в любом случае придётся проверить все варианты, это как угадать в какой коробке больше вещей, не открывая все, получается решение и будет в степени. как сложить десятизнатные числа в два действия? только если повезёт и будет 8 нулей, или я чего-то не понял, смысл этого видео? для простых задач можно подобрать быстрое решение, а для максимально сложных и решение будет такое
@@UnderKoBep есть эвристические алгоритмы, позволяющие получить результат за приемлемое время, но с некоторыми оговорками, на которые на практике всем насрать. А в математике всё не так, там нужен точный алгоритм, срабатывающий всегда, иначе это не считается.
Рюкзак работает за O(MN) N - количество вещей, M - масса
А задачу про города можно перевести на граф с использованием алгоритма Дийкстры
С начальной школы недолюбливаю математику. Но Георгий так доходчиво объясняет, что это интересно. Печально, что у нас в школах методика преподавания была другой...
Ну, технически это не математика школьного уровня, а программа теоретической информатики, которая ближе к универу.
Именно по этой причине Перельман ходит не с рюкзаком, а с сумкой)
Почему так мало - всего лишь миллион долларов за столь сложную и ценную для человечества задачу? Вот, некоторые у себя в квартире миллиарды держат, при этом ничего ценного для человечества не дали.
@@bearmagistr6879 снимают смешные видосики на ютубе? Фоткают жопы в инстаграм? Удачно инвестировали деньги в нужное время? Может, просто напиздили из гос бюджетов?...
А настоящие гении человечества при этом довольствуются объедками капитализма
@@ElimDax01 Не стоит так резко разбрасываться громкими словами, хотя в чем то вы правы.
Потому что это частная инициатива отдельного вуза
так мало, чтобы уменьшить стимул уничтожить криптографию
И как Вам мозг изнутри глаза не выдавил? ))
Он иногда играет в современные мейнстрим шутеры, чтобы контролировать рост
Не дождётесь
На математике просмотров наверно мало. Но было интересно. Правда не все с разу понятно пришлось подумать))
Обожаю выпуски Георгия. продолжайте 👍🙂
Первый раз вижу объяснение этой задачи, понятным человеческим языком. Спасибо, вам!
просто в восторге, млн бачей за уничтожение мира
И если уничтожится, то куда их тратить?) Разве что подтереться.
Спасибо за видео, самое понятное объяснение про классы Р и NP
Рюкзак заполнить жёстким диском с биткоинами и калифорнием)
тот неловкий момент, когда живешь в Братиславе :D
Слава славянской славакии.
Братиславе? Зачем жить в брате Славы?
У вас реально там такие дома?
Можно было ещё рассказать о том, какую роль в данном контексте играют квантовые компьютеры. Это тоже занятно)
Вот вот, было бы здорово послушать
А практически никакую, прочитайте книгу «золотой билет» как раз про p и np. Штука в том, что чтобы выгрузить из квантового компьютера результат вам потребуется np алгоритм , приблизительно так.
@@MySaluto , интересно. Тогда получатся, что вообще в квантовых компьютерах смысла нет?
Слишком тяжелая информация для меня. Посмотрю когда буду готовым к этому ролику))))
Заходи ко мне, я помогу с этим делом!):)
Это такой синоним слова никогда?
Юрий Якунин сильно много слов в одно превращаешь
нихуя не понял, но очень интересно
Что тут сказать, спасибо за идею по заработку 1 миллиона $$$
Уверен, есть более короткие пути по заработку миллиона)
Дико интересно! Давайте больше мозголомательной математики!
Читал книгу Грокаем алгоритмы на питон и залетел сюда за дополнительной информацией. Стало понятнее
Я просто любитель, который пытается решить PvNP и уже убил около 9 лет на это. Я более чем уверен, что они не равны, но чтобы доказать это нужно: новая логика, новая теория множеств, новый тип комплексного анализа на недоступных кардиналах и суперконтиннумах. Это то что я понял, что мне нужно сделать с нуля. Поэтому я не думаю, что кто-то случайный сможет всё это решить так легко. А в вашем видео всё выглядит как-то скомкано и не досказано, даже для новичка. Краткий список претензий: где NP-Complete? где P/Poly, где NP-Intermediate, где рандомизированные и квантовые алгоритмы, где упоминание факторинга чисел, где полиномиальные редукции, где универсальная машина Тьюринга, где языки для этой машины(классы языков) и т.д.? Видео очень слабенькое, если берётесь за открытую математическую проблему, то уж хоть разъясняйте почему она сложная, а то опять будут сотни «доказательств последней теоремы ферма», которыми будут мучить профессиональных математиков). Ах да, а ещё и барьеры с Ораклами, булевыми схемами, алгебраизация. Тема просто фантастически объёмная и сложная. Позовите Александра Разборова из института Стеклова в Москве, я думаю он вам годноты напишет
А с чего именно вы подступились к подобной задаче? На первый взгляд она кажется неприступной
Задача с рюкзаком самая важная. В Diablo постоянно с ней сталкиваюсь.
Заходи ко мне решать задачки:)
@@JuraSheingart нет
10 классов проучился и впервые об этом слышу.
а школе, как правило, не учат такому, только в специальных математических. Такое тебе расскажут в универе на дисциплине: теория алгоритмов или сложность вычислений
Вот ради таких роликов я и подписался. Пусть редко, но мне хватит )))
Опять мне этот чувак взорвёт мозг.Лайк.
Крууть! Расскажи как-нибуть ещё про решения задач симплекс методом.
Я с такой грыжей сталкивался, когда ехал на регион по программированию. Было прикольно послушать
Как же всё таки близки олимпиадное программирование и олимпиадная математика
Хотелось бы ещё услышать про остальные задачи тысячилетия!!!!
*Ну чисто по моему это вычисляется вероятностью,то есть можно предположить что NP при каком-то условии равно P,ну то есть формулу можно написать так NP≝P,или же так NP≈P*
Не знаю зачем я полез в то что не знаю,но это чисто мое предположение
P.S мое предположение в том,что есть куча знаков равно,и какой то из них подходит для формулы,тупо но мало ли
На самом деле они либо равны, либо нет, и никак иначе. Они не могут быть примерно равны. Мы можем быть уверенны только в том что NP=P или NPXP, и еще возможно в том что доказать это не возможно.
как раз читаю книгу по алгоритмам и дошел до алгоритмов np сложности, и в качестве альтернативы показывают "жадные" алгоритмы, но не точные
Я тут пришёл рюкзак собирать, а не задачи решать)
Спасибо, наконец-то разобралась, в Вики так себе было объяснение
Георгий
Богом молю, подскажите что у вас за наручные часы!
А ролик огонь, очень доходчиво все
Спасибо! Это супер важная задача
Тревожную музыку на фоне надо убрать
кстати, нынче умножают со сложностью n*log(n)
ZecosMAX примерно с 70-ых умножают быстро, и вот буквально месяц как вы написали)
Хм. Проще простого. Нужно проверить каждую вещь по отдельности, бесконечно складывая её в рюкзак до тех пор, пока не будет учитанны все возможные варианты складывания этой вещи, потом вторую проверить и т.д., потом просто взять и наложить все возможные варианты друг на друга и посмотреть, ибо в таком случае только 1 комбинация будет единственная, когда все вещи будут сложенны в самом оптимизированном состоянии, при таком условии вместимости рюкзака.Остальные комбинации или невозможны, или недостаточно идеально оптимизированны. В общем NP≠P, это совсем другой класс решения задач, и я не математик, и не суперкомпьютер, и поэтому патаюсь найти наиболее точное решение такой задачи в голове. Однако такой алгоритм очень простой, и очень легёк в усвоении. И вы правы, благодаря такому алгоритму я решаю(примерно) все задачи вида NP. Например в играх пытаюсь просчитать лучшую тактику для ведения боя и т.п.
Псы. Я сказал глупо и не научно. Но черт возми правильно.
Разумная Ящерица слишком сложно, это тупо брутфорс
Спасибо за видео.
Забавно. Тот, кто получит этот миллион не положит его в банк.
Не хочу быть дотошным, но
02:12 : "Сложность аглоритма увеличивается полномиально..."
Такие оговорки могут ввести в заблуждение человека , который никогда с этим не сталкивался
задача с сбором содержимого сумки полиноминальна
но если предметы имеют больше измерений чем просто вес - все станет намного сложнее
хотя... и это можно обойти. придется знать "важность" каждого параметра
Если можно ложить только целое количество предметов, то эта задача становится NP
Подумал что расскажут какой-нибудь математический способ собрать рюкзак комивояжёра а в итоге появилась фобия взлома личных данных
Очень интересно, хоть сложновато понять.
P.S. подскажи что за трек на фоне и в конце
Спасибо!
за решение этой задачи скорее всего открутят голову... очень решительно.
Всегда интересовало, правильно ли будет следующие утверждение: если инопланетяне, прямо сейчас, посмотрят в сверхмощный телескоп на нашу планету на расстоянии 100 млн световых лет, то увидят живых динозавров, хотя по факту, в настоящем, они уже давно вымерли?
оно правильно в своей сути, вероятно
мы и правда видим в небе прошлое, ученые так и изучают историю
смотрят куда нибудь далеко, и чем дальше, тем ближе по времени к началу времен
А мне интересно, если Перельман решит эту задачу,он снова не возьмет деньги?
Будет зависеть от того, сможет ли он сложить деньги в рюкзак за полиномиальное время.
Привет, Георгий ! 🌞😉👌
Вау ! - Это Круто ! 🌞🙌🙏😉👌
Решить Тера сложную задачу,
Послать к хренам всю безопасность в интернете,
и получить за это Милллллион ! 🌞😉✌
Круто, я согласен ! 😂🤣👌
Когда начинать ?
А у вас есть печенки, с чаем ?
Я очень люблю чёрный чай с кусочком лимона ! 🌞😉👍
на коммивояжоре он поржал,а на многочлене сдержался!)))
Было количество операций и вдруг стало количесво времени)
Количество времени пропорционально количеству операций
@@mihail-ln4rf это, как минимум, требует пояснения
Ничего не понял но очень интересно 🐒
O(n!).
Решается, но решаться будет по миллиардам лет.
Может быть np задача сама формируется и решается по алгоритму,который тоже формируется сам в ходе ряда событий?То есть задача есть алгоритм.
"Я бы мог решить , но это слишком скучно " you
Для решения этой задачи не нужен алгоритм по скольку нету бесконечного числа переменных.
А я думал будет разбор задачи о рюкзаке по теории игр рассмотренной в качестве кооперативной игры
Ух ты!
Класс
Я доказал, но не расскажу из добрых побуждений.
Не до конца вдуплился в тему выпуска. Но мне понравилось.
С задачей про рюкзак изи, без всякого перебора... просто у каждой вещи считаем цена одного грамма (делим ценность на ее вес), потом сортируем от большей ценности к меньшей... далее отбираем более ценные вещи (считая их вес) пока не дойдем до максимального веса который может выдержать рюкзак...
Тут вопрос не в алгоритме в целом, а в количестве операция на шмотку, т.е. 2^n - брутфорс для NP, да так проблемы решаются, но ты спроси себя, что если у тебя будет хотя бы 100 шмоток или больше? Вот тут-то и нужно всё сводить к n^3 хотя бы)
Вы не совсем корректно, наверное, поняли задачу. Ваше решение отлично подойдет, если бы в рюкзак складывали крупы, т.е. мы без проблем могли бы взять лишь часть предмета. В нашем же случае возможна ситуация, которая ломает ваше решение. Рассмотрим несколько предметов: ноутбук (стоимость 113, масса 9), мяч (стоимость 75, масса 6), книга (стоимость 20, масса 2), бутылка с водой (стоимость 20, масса 2). Ваш алгоритм возьмет только ноутбук (остальные предметы не влезут), в то же время совершенно ясно, что выгоднее взять мяч, книгу и бутылку с водой.
@@mr.geekman8526 я понял о чем вы... хотя вы допустили ошибку... масса книги, бутылки и воды больше массы ноутбука :)))
@@gcomsu5819 Я забыл указать, что наш рюкзак может вместить лишь вещи массой 10. Задача же состоит в максимизации стоимости предметов в нем. Причем нам совершенно без разницы, какова масса предметов в рюкзаке, если она не превышает 10, главное - суммарная стоимость. Надеюсь, что теперь понятна сложность задачи.
Для задачи с рюкзаком видел жадный алгоритм. Он представляет из себя что то такое:
1) делим массу каждого предмета на его стоимость. Таким образом получая "удельную стоимость"
2) предметы с максимальной удельной стоимостью кладём в рюкзак пока не закончится место
Alexander Kostrov это да
Объяснили. Я понял.
Но зачем?
Расскажите подробнее, что там Перельман доказал
А из каких фильмов взяты эпизоды?
наконец то понял че за дичь эта "нп = п" спасиб)
Я думал типо я такой умный пока не зашёл на видос. (думал N*P=P / 0*0=0)))))
Спасибо
Задачу о рюкзаке можно решить за псевдополиномиальное время методами динамического программирования.
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.
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).
Что за фильм в видео показан относительно путешествий? (3:00)
Евротур.
Про задачу с рюкзаком
Берем и вычисляем для каждой вещи значение = стоимость/масса.
Затем пихаем в рюкзак вещи в порядке убывания этого значения
Ahdruxa неверный подход ввиду того, что запихивая в первую очередь самые ценные вещи у вас может не полностью использоваться пространство
Контрпример вашего суждения:
93 кг 10000р
5 кг 5000р
3 кг 2900р
4 кг 3880р
@@karenyaylyan2243 зато в игрульках самый кайф, потом можно вручную откорректировать.
Мой гуманитарный мозг ушел не сказав куда
У меня мир вокруг чуть полиномиальным не стал :)
Пожалуйста, больше не говори это слово :)))
Ахаха))) Заходи ко мне такие же комментарии писать:) (у меня видео очень короткие, прокачаешься)
Самое приятное, это конечно не парить мозги с матаном, а браться решать задачу коммивояжера. Если вы не шизоид, то сами сложите все идеи, вопросы и методы работы с данными в своб математику. А вопрос интерпретации дело пустяковое.
Так, я решаю коммивояжера порядка двух лет и с радостью могу поделиться тем, что достиг успехов.
Сам топик видео говорит о том, что математики креативят и у них есть простые решения определенных примеров задачи,это подразумевает, что пляска от верного ответа к поиску самого алгоритма/метода решения имеет место быть. А диссонанс мозга происходит, когда ты по сути уже решил задачу и ищешь зацепку, т. е. проблему/ошибку. Её же там нет. Но и неправильного ответа нет, потому что неправильные ответы используют неправильный алгоритм/метод. А правильного метода нет. Интересно получается.
Так, лучший способ работы с математической задачей является:
1 сбор информации о том, что вы решаете. Определение сути задачи.
2 упрощение задачи с сохранением ее целостности.
3 составление вариаций данной задачи.
4 поиск закономерностей данных, т. е. определение категорий (групп, зависимостей).
*здесь важно отметить, что вы тратите свое время не на слепой перебор решения задачи, а слепой перебор на выявление закономерностей в ней, т. е. данный процесс избыточен и является сбором информации о задаче.
5 определение связи закономерностей друг относительно друга с целью отбора уникальных закономерностей от основных (априорных).
6 проверка наличия основных закономерностей на остальных вариациях задачи.
7 аргументация/обоснование существования уникальных закономерностей.
8 проверка наличия уникальных закономерностей в остальных вариациях задачи.
9 определение противоречия, т. е. когда определение наличия или отсутствия уникальных закономерностей в остальных вариациях задачи и обоснование их уникальности.
10. Определение категорий уникальных закономерностей в вариациях задачи и нахождение их взаимосвязи (если они в одной категории).
11 обоснование отсутствия уникальности данных закономерностей, т. е. мы поясняем, почему это не новое, а измененное старое. Сводим уникальность закономерностей в класс основных/ априорных закономерностей.
12. Находим взаимосвязь или закономерности между закономерностями УЖЕ одной категории (т.е. категории основных, априорных закономерностей).
13. Определяем суть новых основных закономерностей и подводим итог, т. е. Определяем суть решения и проверяем.
Чисто подставила единицу в эту формулу и доказала, что np=p, a p=np
Раньше в ВУЗах всю категорию NP определяли как нелинейное программирование. сюда также относили задачу коммивояжера. А теперь вопрос: зачем менять название на непонятное, чтобы возникала необходимость объяснять сущность полинома и еще больше усложнять? Современные авторы учебников совсем забыли бритву Оккама.
Очень интересное видео, но перегруз на петле прям боль 😢
О да. Ещё и хромакей лагает, когда он руками резко двигает.
Думаю если кто-то решит данную задачу, то будет взламывать счета и воровать деньги
Как будто без этой задачи не взламывают и не воруют!
Ничего не понял, но было интересно!
*Составить список имеющихся вещей, разбить по категориям и выдать каждому предмету баллы от 1 до 100 по их полезности, а затем получим сумму балов за каждый кубический сантиметр каждого предмета. Складываем в рюкзак самые ценные сантиметры из каждой категории*
Хм, нужен ли будет миллион долларов, если есть доступ ко всем банковским картам?)
1) А если окажется, что P =/= NP ? Тогда доступа ко всем банковским картам у тебя не будет, а вот миллион за доказательство получить можно.
2) Чтобы получить миллион за решение этой задачи, достаточно доказать существование алгоритма, решающего NP задачи за время P, а не предъявлять пример такого алгоритма. Может быть, доказать его существование значительно проще, чем найти сам алгоритм. В таком случаи доступа к картам не будет.
3) Может оказаться так, что P=NP и алгоритм решения NP за время P будет найден, но при этом сложность этого алгоритма всё равно окажется непомерно высокой для современных компьютеров. Даже при сложности алгоритма n^100 ( n в степени 100 ) взломать с его помощью банк используя частный компьютер будет практически невозможно (во всяком случаи это будет дольше человеческой жизни), при сложности n^1000 в мире едва ли надётся компьютер способный на это (даже все кластеры google вместе взятые, или даже все компьютеры подключённые к интернету вместе взятые), а при сложности n^10000 такую задачу, не решит даже компьютер размером с Землю (по крайней мере за время меньше человеческой жизни.)
@@Kmiarg , мощность среднестатистического домашнего компьютера примерно 3-15 тераФЛОПС.
Но мощность сети биткойн в прошлом году была 67260548 ПетаФЛОПС.
Сколько времени нужно, чтобы такой мощностью выполнить рассчеты?
Пс. Видюха уровня 1050-1060 взламывает пароль wi-fi состоящий из 8 цифр за 15 минут.
@@Kmiarg можно ещё доказать, что эта задача в принципе не решаема. И тоже получить свой лям.
@@DigiMakc на самом деле я лишь предположил цифры что написал выше, чтобы примерно показать что такое степенной рост, реальные расчёты сильно зависили бы от коэффициентов перед n. Но раз вас интересуют более точные расчёты, вот что могу сказать о приведённых вами цифрах:
1) возмём для примера мощность домашнего компьютера раную 2 тераФЛОПС, тогда во сколько раз мощность сети биткойн больше? Ответ: в 2^26 раз, это чуть меньше чем 10^8. Кажется, только теперь я начал понимать, какой невероятно огромный космический запас я заложил между n^100 и n^1000, потому что разница между ними в n^900 раз, это явно перебор.
2) если пароль или система шифрования не содержит известных уязвимостей, то сложность такой задачи составляет ~ 16^8. поскольку каждый символ в wi-fi пароле может принимать лишь 1 из 16 возможных значений, и это число мы возводим в 8 степень из-за длинны пароля.
итак если пароль из 8 символов подбирается за 15 минут, то
пароль из 9 символов будет подбираться в 16 раз дольше, то есть 240 мин = 4 часа,
пароль из 10 символов 64 часа = 5+1/3 суток,
пароль из 11 символов - 85 дней,
из 12 симв. - 3,7 лет,
из 13 симв. - 59,8 лет
из 14 симв. - 957 лет
из 15 симв. - 15 321 год - и это всё лишь в том случаи, исходный алгоритм не содержал каких-то оптимизаций по времени, за счёт увеличения затрат памяти. (а если препологает то сроки будут ещё больше, когда закончиться память видеокарты и оперативная память, и придётся активно загружать данные с диска)
из 16 симв. - 245 146 лет. Кстати именно 16 сивольные пароли используются сейчас.
И тут стоить вспомнить, что для шифрования финансовых данных сейчас используются файл-ключи или USB-ключи. Быстрый поиск показал, что сейчас в продаже есть USB-ключи с паролем длинной 32Кб, 64Кб, 128Кб. И там каждый байт(символ) может быть любым от 0 до 255, то есть сложность их взлома будет от 256^(1024*32) до 256^(1024*128)... это число 2^(2^20)
Если кто смотрел видео про число Гремма или знаком со стрелочной нотацией, то это число можно записать как 2↑20 , или просто 2 в более чем миллионной степени... у такого числа даже названия вряд ли найдётся.
PS это я ещё не учитывал, что более длинные пароли и ключи надо проверять на более длинных блоках данных, что так же занимает всё больше и больше времени с ростом n. Из-за этой особенности программы полного перебора имеют сложность n^n или подобную. Я же рассматривал в примере const^n , что значительно меньше n^n, но для нижней оценки по времени сгодиться и так.
@@Kmiarg ахуенна
Вроде как необходимость в поике алгоритма решения NP задач скоро может отпасть, за счет квантовых компьютеров. Таким образом эта задача перейдет из разряда практических в разряд чисто научных.
лайк не глядя, пошла глядеть
Что за карта использовалась на 4 минуте, странный выбор городов для отображения.
42 !
P 42 NP
Вот и все
Походу ботаники остались дома, рассчитывать влезут ли вещи в рюкзак и хватит ли денег на бензин )))
Освобождаю рюкзак для миллиона долларов!
Так я не поняла, рюкзак то как собирать? Где ответ на этот вопрос? Сижу уже у рюкзака и что дальше? 🤔
* в замешательстве... 🤯
Если P=NP, то задача доказательства-тоже NP задача. Если это можно доказать, то всё сходится, а если нельзя, то мы нашли не П, а НП задачу. То есть, доказали неравенство. Значит, если П=НП, это можно доказать. Если не равно, а доказать можно, то мы найдём одну НП=П. Но всё в порядке-единичный случай ничего не показывает. Если доказать это нельзя, то одна "нерешаемая" НП задача найдена. Но всё в порядке-единичный случай ничего не показывает.
Если NP=P, то это можно доказать, а если NPне =P, то насчёт доказательства- неопределённость.
у меня есть способ решения задачи рюкзака за полим. время!! можете расскритиковать? как с вами связатся?
Я может неправильно понял значение слова алгоритм применительно к этим задачам или еще что-то, но разве задачу с рюкзаком (если берем ограничение по весу и требуется максимальная стоимость) не решается так: для каждой вещи делим ее стоимость на вес, по полученному числу сортируем все вещи по убыванию, а затем набираем вещи сверху вниз пока рюкзак не заполнится по весу?
Нет, потому что вещи неделимые и могут быть ситуации, когдв выгоднее в рюкзак положить две вещи менее выгодные, чем одну более выгодную для более плотной упаковки. То есть пустого места в рюкзаке тоже должно остаться минимум.
Если серьёзно,то вопрос задачи по-человечески звучит так, - "Можно ли выучить китайский, тайский и айский за 5 минут, используя некий алгоритм формул?" И за его нахождение тебе дадут мильон. Сразу попробую предположить, что такой алгоритм существует и его существование описано в Новом Завете, когда неграмотные апостолы в одно мгновенье заговорили на нескольких иностранных языках при многочисленных свидетелях. Поэтому исторически зафиксированно его существование и можно сделать вывод что NP=P. Но как найти такой алгоритм? Видимо нужно подключить режим Бога.
Ничего не понял, но очень интересно!
По поводу сбора вещей в рюкзак. Почему нельзя найти отношение стоимость/вес каждого предмета и брать вещи с наибольшим этим коэффициентом?
Потому что тогда решение не обязательно будет самым оптимальным. Приведу пример.
Пускай вместимость рюкзака равна 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.
Наиболее оптимальное решение для данного примера исключает вещь с наилучшим соотношением.
Интересно, как изменится соотношение мнений учёных с течением времени.