≠ Собирай рюкзак по алгоритму, если будет NP=P

แชร์
ฝัง
  • เผยแพร่เมื่อ 1 ธ.ค. 2024

ความคิดเห็น • 370

  • @QWRTru
    @QWRTru  5 ปีที่แล้ว +37

    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
      @tinkerbel1955 5 ปีที่แล้ว +3

      спс, было сложно но интересно).
      очуметь..) _ кстати как раз, вовремя.. Недавно вспоминал, про степени и т.д.
      Если возможно, то хотелось бы увидеть на будущее.. видео о комбинаторике.
      (и какие бывают формулы решения задач о комбинаторике)

    • @QWRTru
      @QWRTru  5 ปีที่แล้ว +3

      @@tinkerbel1955 Вполне вероятно, что сделаем! =)

    • @angruthzwingen5394
      @angruthzwingen5394 5 ปีที่แล้ว +2

      За получение доступа ко всем зашифрованным данным на планете плата 1лям долларов) будем ждать))

    • @timedealer1996
      @timedealer1996 5 ปีที่แล้ว

      А почему в умножении не 2 в степени n, умноженное на n? (2^n*n)
      Типа одну цифру на другую определенное количество раз и умножить на такое же количество цифр - показывает количество вариантов

    • @veabmili8006
      @veabmili8006 5 ปีที่แล้ว +1

      А ты с названием канала не запаривался)

  • @Leonard_Gray
    @Leonard_Gray 5 ปีที่แล้ว +224

    Я пришёл, чтобы собирать сумку и не болело плечо, спасибо, теперь голова болит и плечо.

  • @nestor1208
    @nestor1208 5 ปีที่แล้ว +398

    Только именитые учёные на вопрос типа да/нет могут сформировать 4 группы ответов

    • @andriipurskyi23
      @andriipurskyi23 5 ปีที่แล้ว +3

      точно

    • @kotgav815
      @kotgav815 5 ปีที่แล้ว +33

      А что тут формировать-то? По-моему всё просто: да нет, нет нет, нет да и да да.
      Блондинка, которую уламывают на постель -- и та даёт эти же самые ответы, причём в том же порядке, стоит только подогнать под них заранее подготовленные вопросы.)

    • @framemake
      @framemake 5 ปีที่แล้ว +1

      @@kotgav815 ору

    • @CosWeLL23
      @CosWeLL23 5 ปีที่แล้ว +1

      @@kotgav815 xD

    • @Trickylionc
      @Trickylionc 5 ปีที่แล้ว +10

      @@kotgav815 вспоминаем анекдот: сыну задают в школе расказать о родителях, сын приходит к отцу
      -папа а сколько тебе лет?
      Тот математик: -Десять лет назад мне было столько же сколько тебе умноженное на 2, а сейчас твой возраст и возраст твоей сестры умноженный на 2.
      Сынок пишет: мой папа мудак.

  • @kotgav815
    @kotgav815 5 ปีที่แล้ว +93

    Видос из разряда "Ничерта непонятно, но очень интересно!")

    • @ДанилПопов-н3п
      @ДанилПопов-н3п 5 ปีที่แล้ว

      Если такие нравится, зайти в Яндекс.Рефераты и почитай =) ровно тоже самое =)))

  • @Alpha_1918
    @Alpha_1918 5 ปีที่แล้ว +16

    Буквально сегодня была лекция по этой теме. Честно сказать, из видоса в 8 минут понял больше, чем за пару.

    • @Kmiarg
      @Kmiarg 5 ปีที่แล้ว +6

      @@god_slayer-restart нет, это качество образования такое. Я тоже когда-то давно это в институте проходил, и слушал достаточно внимательно чтобы запомнить, что P - решается за полиноминальное время, а NP - нет. А вот что такое "полиноминальное время", объяснили только здесь.

    • @CraBiKun
      @CraBiKun 5 ปีที่แล้ว

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

  • @r199971
    @r199971 5 ปีที่แล้ว +32

    Если кому-то интересна эта тема, есть отличная книга :Бхаргава Адитья Грокаем алгоритмы. В видео все примеры от туда

    • @Spartanci000
      @Spartanci000 5 ปีที่แล้ว +1

      У меня «Эффект Баадера Майнхофа», 3 дня назад дочитал, а тут видео...

    • @astanovemil
      @astanovemil 5 ปีที่แล้ว +2

      Подтверждаю

    • @naa8844
      @naa8844 5 ปีที่แล้ว +3

      А если хотите окончательно сломать мозг: "Алгоритмы: построение и анализ" (с ветками на обложке)

    • @love_SF
      @love_SF 5 ปีที่แล้ว

      А слово "грокаем" из Хайнлайна

    • @love_SF
      @love_SF 5 ปีที่แล้ว

      М-да, "сумничал" называется. Я-то книгу про алгоритмы не читал и не видел, а там, оказывается, прямо на обложке цитата из Хайнлайна. Но я-то не из цитаты это знаю, а потому что прочитал "Чужак в стране чужой" от корки до корки. Дважды.

  • @АлексейПросвиряков-й4о
    @АлексейПросвиряков-й4о 5 ปีที่แล้ว +8

    Вот слушаю ребят умных и так хорошо становится от того, что что то понимаю... мало, но что то понимаю.... Причастен)))

    • @tinkerbel1955
      @tinkerbel1955 5 ปีที่แล้ว +3

      0_o черт!), ты мне глаза раскрыл)). Я теперь понял, почему мне это интересно смотреть))

  • @ИльяМаковоз-ж8л
    @ИльяМаковоз-ж8л 5 ปีที่แล้ว +40

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

    • @MrSevenZZZ
      @MrSevenZZZ 5 ปีที่แล้ว +1

      Там еще сложность в каком месте рюкзака положить эти вещи, получается такой тетрис в 3D + задача оптимизации стоимости.

    • @vadimsimonenko6543
      @vadimsimonenko6543 5 ปีที่แล้ว +1

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

    • @artemmetra8
      @artemmetra8 5 ปีที่แล้ว +1

      Там по-моему про вес было а не про объём.

    • @Kmiarg
      @Kmiarg 5 ปีที่แล้ว +2

      @@artemmetra8 по весу тоже самое, только вместо тетриса в 3-ёх измерениях, у тебя будет тетрис в одномерном пространстве.
      Например: рюкзак расчитан на 10 кг;
      Список предметов: 2 слитка чистого золота по 5.1 кг: и 2 слитка золота низкой пробы по 5 кг.
      если цена отличается не более чем в 2 раза, то выгоднее взять 2 слитка низкой пробы, не смотря на то, что цена за кг у них меньше.

    • @Spartanci000
      @Spartanci000 5 ปีที่แล้ว +1

      На самом деле задачу о рюкзаке можно решить методом разбора её на подзадачи, то есть: рассчитать максимальную стоимость для 1 кг, потом для 2кг и тд. Если интересно: книга «Грокаем алгоритмы»

  • @ComatoseNick
    @ComatoseNick 5 ปีที่แล้ว +13

    Именно по этой причине Перельман ходит не с рюкзаком, а с сумкой)

  • @andreidoronin3164
    @andreidoronin3164 5 ปีที่แล้ว +4

    С начальной школы недолюбливаю математику. Но Георгий так доходчиво объясняет, что это интересно. Печально, что у нас в школах методика преподавания была другой...

    • @tegeranchikrus4389
      @tegeranchikrus4389 5 ปีที่แล้ว +1

      Ну, технически это не математика школьного уровня, а программа теоретической информатики, которая ближе к универу.

  • @СТАНИСЛАВСКИЙ-й5ж
    @СТАНИСЛАВСКИЙ-й5ж 5 ปีที่แล้ว +23

    Задача про рюкзак - это одна из основных задач динамического программирования

    • @UnderKoBep
      @UnderKoBep 5 ปีที่แล้ว +3

      И решается за n в квадрате по-моему

    • @omoloni
      @omoloni 5 ปีที่แล้ว

      @@UnderKoBep
      так это не возможно быстро решить, в любом случае придётся проверить все варианты, это как угадать в какой коробке больше вещей, не открывая все, получается решение и будет в степени. как сложить десятизнатные числа в два действия? только если повезёт и будет 8 нулей, или я чего-то не понял, смысл этого видео? для простых задач можно подобрать быстрое решение, а для максимально сложных и решение будет такое

    • @ИмяФамилия-э4ф7в
      @ИмяФамилия-э4ф7в 5 ปีที่แล้ว +1

      @@UnderKoBep есть эвристические алгоритмы, позволяющие получить результат за приемлемое время, но с некоторыми оговорками, на которые на практике всем насрать. А в математике всё не так, там нужен точный алгоритм, срабатывающий всегда, иначе это не считается.

    • @Liberty5_3000
      @Liberty5_3000 4 ปีที่แล้ว +1

      Рюкзак работает за O(MN) N - количество вещей, M - масса

    • @МихайлоЖелудченко
      @МихайлоЖелудченко 4 ปีที่แล้ว +2

      А задачу про города можно перевести на граф с использованием алгоритма Дийкстры

  • @IvanTheDraggo
    @IvanTheDraggo 5 ปีที่แล้ว +152

    И как Вам мозг изнутри глаза не выдавил? ))

  • @dmitrykukushkin4960
    @dmitrykukushkin4960 5 ปีที่แล้ว +47

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

    • @ElimDax01
      @ElimDax01 5 ปีที่แล้ว +11

      @@bearmagistr6879 снимают смешные видосики на ютубе? Фоткают жопы в инстаграм? Удачно инвестировали деньги в нужное время? Может, просто напиздили из гос бюджетов?...
      А настоящие гении человечества при этом довольствуются объедками капитализма

    • @МиколаКалько
      @МиколаКалько 5 ปีที่แล้ว +3

      @@ElimDax01 Не стоит так резко разбрасываться громкими словами, хотя в чем то вы правы.

    • @alexanderkhoroshavin6921
      @alexanderkhoroshavin6921 5 ปีที่แล้ว +4

      Потому что это частная инициатива отдельного вуза

    • @dNix
      @dNix 5 ปีที่แล้ว +5

      так мало, чтобы уменьшить стимул уничтожить криптографию

  • @nerdomania24
    @nerdomania24 5 ปีที่แล้ว +1

    Я просто любитель, который пытается решить PvNP и уже убил около 9 лет на это. Я более чем уверен, что они не равны, но чтобы доказать это нужно: новая логика, новая теория множеств, новый тип комплексного анализа на недоступных кардиналах и суперконтиннумах. Это то что я понял, что мне нужно сделать с нуля. Поэтому я не думаю, что кто-то случайный сможет всё это решить так легко. А в вашем видео всё выглядит как-то скомкано и не досказано, даже для новичка. Краткий список претензий: где NP-Complete? где P/Poly, где NP-Intermediate, где рандомизированные и квантовые алгоритмы, где упоминание факторинга чисел, где полиномиальные редукции, где универсальная машина Тьюринга, где языки для этой машины(классы языков) и т.д.? Видео очень слабенькое, если берётесь за открытую математическую проблему, то уж хоть разъясняйте почему она сложная, а то опять будут сотни «доказательств последней теоремы ферма», которыми будут мучить профессиональных математиков). Ах да, а ещё и барьеры с Ораклами, булевыми схемами, алгебраизация. Тема просто фантастически объёмная и сложная. Позовите Александра Разборова из института Стеклова в Москве, я думаю он вам годноты напишет

    • @neil9315
      @neil9315 4 หลายเดือนก่อน

      А с чего именно вы подступились к подобной задаче? На первый взгляд она кажется неприступной

  • @Alexanderius
    @Alexanderius 5 ปีที่แล้ว +29

    Обожаю выпуски Георгия. продолжайте 👍🙂

  • @Max-kr4ie
    @Max-kr4ie 5 ปีที่แล้ว +20

    На математике просмотров наверно мало. Но было интересно. Правда не все с разу понятно пришлось подумать))

  • @ИльяП-к4й
    @ИльяП-к4й 5 ปีที่แล้ว +10

    Можно было ещё рассказать о том, какую роль в данном контексте играют квантовые компьютеры. Это тоже занятно)

    • @lis_petrovskij
      @lis_petrovskij 5 ปีที่แล้ว

      Вот вот, было бы здорово послушать

    • @MySaluto
      @MySaluto 5 ปีที่แล้ว +3

      А практически никакую, прочитайте книгу «золотой билет» как раз про p и np. Штука в том, что чтобы выгрузить из квантового компьютера результат вам потребуется np алгоритм , приблизительно так.

    • @ИльяП-к4й
      @ИльяП-к4й 5 ปีที่แล้ว

      @@MySaluto , интересно. Тогда получатся, что вообще в квантовых компьютерах смысла нет?

  • @ruslanakhmetzyanov4337
    @ruslanakhmetzyanov4337 3 ปีที่แล้ว +1

    Спасибо за видео, самое понятное объяснение про классы Р и NP

  • @vselivanov
    @vselivanov 5 ปีที่แล้ว +24

    тот неловкий момент, когда живешь в Братиславе :D

    • @ЕвгенийЗабродин-ш8ч
      @ЕвгенийЗабродин-ш8ч 5 ปีที่แล้ว

      Слава славянской славакии.

    • @happyblood9397
      @happyblood9397 5 ปีที่แล้ว +1

      Братиславе? Зачем жить в брате Славы?

    • @drovoseg
      @drovoseg 5 ปีที่แล้ว

      У вас реально там такие дома?

  • @sk100500
    @sk100500 5 ปีที่แล้ว +21

    просто в восторге, млн бачей за уничтожение мира

    • @Павло-х1ф
      @Павло-х1ф 5 ปีที่แล้ว

      И если уничтожится, то куда их тратить?) Разве что подтереться.

  • @Kmiarg
    @Kmiarg 5 ปีที่แล้ว

    Первый раз вижу объяснение этой задачи, понятным человеческим языком. Спасибо, вам!

  • @woohooD
    @woohooD 5 ปีที่แล้ว +19

    Рюкзак заполнить жёстким диском с биткоинами и калифорнием)

  • @helgo_shiro9428
    @helgo_shiro9428 5 ปีที่แล้ว +1

    *Ну чисто по моему это вычисляется вероятностью,то есть можно предположить что NP при каком-то условии равно P,ну то есть формулу можно написать так NP≝P,или же так NP≈P*
    Не знаю зачем я полез в то что не знаю,но это чисто мое предположение
    P.S мое предположение в том,что есть куча знаков равно,и какой то из них подходит для формулы,тупо но мало ли

    • @МиколаКалько
      @МиколаКалько 5 ปีที่แล้ว

      На самом деле они либо равны, либо нет, и никак иначе. Они не могут быть примерно равны. Мы можем быть уверенны только в том что NP=P или NPXP, и еще возможно в том что доказать это не возможно.

  • @РазумнаяЯщерица
    @РазумнаяЯщерица 5 ปีที่แล้ว

    Хм. Проще простого. Нужно проверить каждую вещь по отдельности, бесконечно складывая её в рюкзак до тех пор, пока не будет учитанны все возможные варианты складывания этой вещи, потом вторую проверить и т.д., потом просто взять и наложить все возможные варианты друг на друга и посмотреть, ибо в таком случае только 1 комбинация будет единственная, когда все вещи будут сложенны в самом оптимизированном состоянии, при таком условии вместимости рюкзака.Остальные комбинации или невозможны, или недостаточно идеально оптимизированны. В общем NP≠P, это совсем другой класс решения задач, и я не математик, и не суперкомпьютер, и поэтому патаюсь найти наиболее точное решение такой задачи в голове. Однако такой алгоритм очень простой, и очень легёк в усвоении. И вы правы, благодаря такому алгоритму я решаю(примерно) все задачи вида NP. Например в играх пытаюсь просчитать лучшую тактику для ведения боя и т.п.
    Псы. Я сказал глупо и не научно. Но черт возми правильно.

    • @DaVinci-io
      @DaVinci-io 5 ปีที่แล้ว

      Разумная Ящерица слишком сложно, это тупо брутфорс

  • @МихаилХолостов-р1п
    @МихаилХолостов-р1п 2 ปีที่แล้ว

    Читал книгу Грокаем алгоритмы на питон и залетел сюда за дополнительной информацией. Стало понятнее

  • @ЮрийК-г6с
    @ЮрийК-г6с 5 ปีที่แล้ว +2

    Вот ради таких роликов я и подписался. Пусть редко, но мне хватит )))

  • @VlAdIsLaV5000
    @VlAdIsLaV5000 5 ปีที่แล้ว +4

    10 классов проучился и впервые об этом слышу.

    • @user_gmg8607
      @user_gmg8607 5 ปีที่แล้ว

      а школе, как правило, не учат такому, только в специальных математических. Такое тебе расскажут в универе на дисциплине: теория алгоритмов или сложность вычислений

  • @SeeVonBlood
    @SeeVonBlood 5 ปีที่แล้ว +6

    Что тут сказать, спасибо за идею по заработку 1 миллиона $$$

    • @pianomusic8160
      @pianomusic8160 5 ปีที่แล้ว +2

      Уверен, есть более короткие пути по заработку миллиона)

  • @bashirallahyarov474
    @bashirallahyarov474 5 ปีที่แล้ว +1

    Слишком тяжелая информация для меня. Посмотрю когда буду готовым к этому ролику))))

    • @JuraSheingart
      @JuraSheingart 5 ปีที่แล้ว

      Заходи ко мне, я помогу с этим делом!):)

    • @Trickylionc
      @Trickylionc 5 ปีที่แล้ว

      Это такой синоним слова никогда?

    • @JuraSheingart
      @JuraSheingart 5 ปีที่แล้ว

      Юрий Якунин сильно много слов в одно превращаешь

  • @OyLesha
    @OyLesha 5 ปีที่แล้ว

    Дико интересно! Давайте больше мозголомательной математики!

  • @TheOnlyTima
    @TheOnlyTima 5 ปีที่แล้ว

    Как же всё таки близки олимпиадное программирование и олимпиадная математика

  • @ВованД-у2й
    @ВованД-у2й 5 ปีที่แล้ว +1

    Задача с рюкзаком самая важная. В Diablo постоянно с ней сталкиваюсь.

    • @JuraSheingart
      @JuraSheingart 5 ปีที่แล้ว

      Заходи ко мне решать задачки:)

    • @Trickylionc
      @Trickylionc 5 ปีที่แล้ว

      @@JuraSheingart нет

  • @MoksDev
    @MoksDev 5 ปีที่แล้ว +2

    как раз читаю книгу по алгоритмам и дошел до алгоритмов np сложности, и в качестве альтернативы показывают "жадные" алгоритмы, но не точные

  • @revelia3183
    @revelia3183 5 ปีที่แล้ว +3

    Не хочу быть дотошным, но
    02:12 : "Сложность аглоритма увеличивается полномиально..."
    Такие оговорки могут ввести в заблуждение человека , который никогда с этим не сталкивался

  • @vilkillian
    @vilkillian 5 ปีที่แล้ว +5

    кстати, нынче умножают со сложностью n*log(n)

    • @MySaluto
      @MySaluto 5 ปีที่แล้ว +1

      ZecosMAX примерно с 70-ых умножают быстро, и вот буквально месяц как вы написали)

  • @ПавелБелоусов-г3р
    @ПавелБелоусов-г3р 5 ปีที่แล้ว

    Опять мне этот чувак взорвёт мозг.Лайк.

  • @shinigamineko333
    @shinigamineko333 5 ปีที่แล้ว

    Крууть! Расскажи как-нибуть ещё про решения задач симплекс методом.

  • @XPandoruM
    @XPandoruM 5 ปีที่แล้ว +6

    Хотелось бы ещё услышать про остальные задачи тысячилетия!!!!

  • @johnwhite4393
    @johnwhite4393 5 ปีที่แล้ว +1

    Всегда интересовало, правильно ли будет следующие утверждение: если инопланетяне, прямо сейчас, посмотрят в сверхмощный телескоп на нашу планету на расстоянии 100 млн световых лет, то увидят живых динозавров, хотя по факту, в настоящем, они уже давно вымерли?

    • @howuhh8960
      @howuhh8960 5 ปีที่แล้ว

      оно правильно в своей сути, вероятно
      мы и правда видим в небе прошлое, ученые так и изучают историю
      смотрят куда нибудь далеко, и чем дальше, тем ближе по времени к началу времен

  • @ЯрославБаранов_98
    @ЯрославБаранов_98 5 ปีที่แล้ว +33

    нихуя не понял, но очень интересно

  • @ander-cs2hl
    @ander-cs2hl 5 ปีที่แล้ว

    Я с такой грыжей сталкивался, когда ехал на регион по программированию. Было прикольно послушать

  • @user-asyau
    @user-asyau 5 ปีที่แล้ว

    Спасибо, наконец-то разобралась, в Вики так себе было объяснение

  • @joint831
    @joint831 5 ปีที่แล้ว +8

    Тревожную музыку на фоне надо убрать

  • @atkin8451
    @atkin8451 5 ปีที่แล้ว +3

    Может быть np задача сама формируется и решается по алгоритму,который тоже формируется сам в ходе ряда событий?То есть задача есть алгоритм.

    • @cav4906
      @cav4906 5 ปีที่แล้ว

      "Я бы мог решить , но это слишком скучно " you

    • @МиколаКалько
      @МиколаКалько 5 ปีที่แล้ว +1

      Для решения этой задачи не нужен алгоритм по скольку нету бесконечного числа переменных.

  • @olegkhokhlov
    @olegkhokhlov 5 ปีที่แล้ว

    Спасибо! Это супер важная задача

  • @Кён-д2у
    @Кён-д2у 5 ปีที่แล้ว +2

    Я тут пришёл рюкзак собирать, а не задачи решать)

  • @СергейВ-т3д
    @СергейВ-т3д 5 ปีที่แล้ว +1

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

    • @respect4war
      @respect4war 5 ปีที่แล้ว

      Если можно ложить только целое количество предметов, то эта задача становится NP

  • @the_black_cat_plays
    @the_black_cat_plays 5 ปีที่แล้ว +1

    Забавно. Тот, кто получит этот миллион не положит его в банк.

  • @moewww6328
    @moewww6328 5 ปีที่แล้ว

    *Составить список имеющихся вещей, разбить по категориям и выдать каждому предмету баллы от 1 до 100 по их полезности, а затем получим сумму балов за каждый кубический сантиметр каждого предмета. Складываем в рюкзак самые ценные сантиметры из каждой категории*

  • @timreizin9854
    @timreizin9854 5 ปีที่แล้ว +2

    Задачу о рюкзаке можно решить за псевдополиномиальное время методами динамического программирования.

    • @stefanbanev
      @stefanbanev 5 ปีที่แล้ว

      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.

  • @ОлжасСахабай
    @ОлжасСахабай 5 ปีที่แล้ว

    Для задачи с рюкзаком видел жадный алгоритм. Он представляет из себя что то такое:
    1) делим массу каждого предмета на его стоимость. Таким образом получая "удельную стоимость"
    2) предметы с максимальной удельной стоимостью кладём в рюкзак пока не закончится место

  • @greenavoy4148
    @greenavoy4148 5 ปีที่แล้ว

    Самое приятное, это конечно не парить мозги с матаном, а браться решать задачу коммивояжера. Если вы не шизоид, то сами сложите все идеи, вопросы и методы работы с данными в своб математику. А вопрос интерпретации дело пустяковое.
    Так, я решаю коммивояжера порядка двух лет и с радостью могу поделиться тем, что достиг успехов.
    Сам топик видео говорит о том, что математики креативят и у них есть простые решения определенных примеров задачи,это подразумевает, что пляска от верного ответа к поиску самого алгоритма/метода решения имеет место быть. А диссонанс мозга происходит, когда ты по сути уже решил задачу и ищешь зацепку, т. е. проблему/ошибку. Её же там нет. Но и неправильного ответа нет, потому что неправильные ответы используют неправильный алгоритм/метод. А правильного метода нет. Интересно получается.

    • @greenavoy4148
      @greenavoy4148 5 ปีที่แล้ว

      Так, лучший способ работы с математической задачей является:
      1 сбор информации о том, что вы решаете. Определение сути задачи.
      2 упрощение задачи с сохранением ее целостности.
      3 составление вариаций данной задачи.
      4 поиск закономерностей данных, т. е. определение категорий (групп, зависимостей).
      *здесь важно отметить, что вы тратите свое время не на слепой перебор решения задачи, а слепой перебор на выявление закономерностей в ней, т. е. данный процесс избыточен и является сбором информации о задаче.
      5 определение связи закономерностей друг относительно друга с целью отбора уникальных закономерностей от основных (априорных).
      6 проверка наличия основных закономерностей на остальных вариациях задачи.
      7 аргументация/обоснование существования уникальных закономерностей.
      8 проверка наличия уникальных закономерностей в остальных вариациях задачи.
      9 определение противоречия, т. е. когда определение наличия или отсутствия уникальных закономерностей в остальных вариациях задачи и обоснование их уникальности.
      10. Определение категорий уникальных закономерностей в вариациях задачи и нахождение их взаимосвязи (если они в одной категории).
      11 обоснование отсутствия уникальности данных закономерностей, т. е. мы поясняем, почему это не новое, а измененное старое. Сводим уникальность закономерностей в класс основных/ априорных закономерностей.
      12. Находим взаимосвязь или закономерности между закономерностями УЖЕ одной категории (т.е. категории основных, априорных закономерностей).
      13. Определяем суть новых основных закономерностей и подводим итог, т. е. Определяем суть решения и проверяем.

  • @gcomsu5819
    @gcomsu5819 5 ปีที่แล้ว

    С задачей про рюкзак изи, без всякого перебора... просто у каждой вещи считаем цена одного грамма (делим ценность на ее вес), потом сортируем от большей ценности к меньшей... далее отбираем более ценные вещи (считая их вес) пока не дойдем до максимального веса который может выдержать рюкзак...

    • @nerdomania24
      @nerdomania24 5 ปีที่แล้ว

      Тут вопрос не в алгоритме в целом, а в количестве операция на шмотку, т.е. 2^n - брутфорс для NP, да так проблемы решаются, но ты спроси себя, что если у тебя будет хотя бы 100 шмоток или больше? Вот тут-то и нужно всё сводить к n^3 хотя бы)

    • @mr.geekman8526
      @mr.geekman8526 5 ปีที่แล้ว

      Вы не совсем корректно, наверное, поняли задачу. Ваше решение отлично подойдет, если бы в рюкзак складывали крупы, т.е. мы без проблем могли бы взять лишь часть предмета. В нашем же случае возможна ситуация, которая ломает ваше решение. Рассмотрим несколько предметов: ноутбук (стоимость 113, масса 9), мяч (стоимость 75, масса 6), книга (стоимость 20, масса 2), бутылка с водой (стоимость 20, масса 2). Ваш алгоритм возьмет только ноутбук (остальные предметы не влезут), в то же время совершенно ясно, что выгоднее взять мяч, книгу и бутылку с водой.

    • @gcomsu5819
      @gcomsu5819 5 ปีที่แล้ว

      @@mr.geekman8526 я понял о чем вы... хотя вы допустили ошибку... масса книги, бутылки и воды больше массы ноутбука :)))

    • @mr.geekman8526
      @mr.geekman8526 5 ปีที่แล้ว

      @@gcomsu5819 Я забыл указать, что наш рюкзак может вместить лишь вещи массой 10. Задача же состоит в максимизации стоимости предметов в нем. Причем нам совершенно без разницы, какова масса предметов в рюкзаке, если она не превышает 10, главное - суммарная стоимость. Надеюсь, что теперь понятна сложность задачи.

  • @silentcat8632
    @silentcat8632 5 ปีที่แล้ว

    Я может неправильно понял значение слова алгоритм применительно к этим задачам или еще что-то, но разве задачу с рюкзаком (если берем ограничение по весу и требуется максимальная стоимость) не решается так: для каждой вещи делим ее стоимость на вес, по полученному числу сортируем все вещи по убыванию, а затем набираем вещи сверху вниз пока рюкзак не заполнится по весу?

    • @pnlabs
      @pnlabs 5 ปีที่แล้ว

      Нет, потому что вещи неделимые и могут быть ситуации, когдв выгоднее в рюкзак положить две вещи менее выгодные, чем одну более выгодную для более плотной упаковки. То есть пустого места в рюкзаке тоже должно остаться минимум.

  • @vladsa7
    @vladsa7 5 ปีที่แล้ว +3

    А мне интересно, если Перельман решит эту задачу,он снова не возьмет деньги?

    • @seriych
      @seriych 5 ปีที่แล้ว

      Будет зависеть от того, сможет ли он сложить деньги в рюкзак за полиномиальное время.

  • @evgeniyblinov4948
    @evgeniyblinov4948 5 ปีที่แล้ว +1

    за решение этой задачи скорее всего открутят голову... очень решительно.

  • @ВикторКонтуров-ч6л
    @ВикторКонтуров-ч6л 5 ปีที่แล้ว

    Если P=NP, то задача доказательства-тоже NP задача. Если это можно доказать, то всё сходится, а если нельзя, то мы нашли не П, а НП задачу. То есть, доказали неравенство. Значит, если П=НП, это можно доказать. Если не равно, а доказать можно, то мы найдём одну НП=П. Но всё в порядке-единичный случай ничего не показывает. Если доказать это нельзя, то одна "нерешаемая" НП задача найдена. Но всё в порядке-единичный случай ничего не показывает.
    Если NP=P, то это можно доказать, а если NPне =P, то насчёт доказательства- неопределённость.

  • @stefanbanev
    @stefanbanev 5 ปีที่แล้ว

    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).

  • @ahdruxa355
    @ahdruxa355 5 ปีที่แล้ว

    Про задачу с рюкзаком
    Берем и вычисляем для каждой вещи значение = стоимость/масса.
    Затем пихаем в рюкзак вещи в порядке убывания этого значения

    • @karenyaylyan2243
      @karenyaylyan2243 5 ปีที่แล้ว

      Ahdruxa неверный подход ввиду того, что запихивая в первую очередь самые ценные вещи у вас может не полностью использоваться пространство
      Контрпример вашего суждения:
      93 кг 10000р
      5 кг 5000р
      3 кг 2900р
      4 кг 3880р

    • @loafius
      @loafius 5 ปีที่แล้ว

      @@karenyaylyan2243 зато в игрульках самый кайф, потом можно вручную откорректировать.

  • @seltsame_kopf2100
    @seltsame_kopf2100 5 ปีที่แล้ว

    Очень интересно, хоть сложновато понять.
    P.S. подскажи что за трек на фоне и в конце

  • @МаксимШевченко-д7и
    @МаксимШевченко-д7и 5 ปีที่แล้ว +3

    Ничего не понял но очень интересно 🐒

  • @МихаилС-г2в
    @МихаилС-г2в 5 ปีที่แล้ว

    Раньше в ВУЗах всю категорию NP определяли как нелинейное программирование. сюда также относили задачу коммивояжера. А теперь вопрос: зачем менять название на непонятное, чтобы возникала необходимость объяснять сущность полинома и еще больше усложнять? Современные авторы учебников совсем забыли бритву Оккама.

  • @recursivedude6561
    @recursivedude6561 2 ปีที่แล้ว

    Георгий
    Богом молю, подскажите что у вас за наручные часы!
    А ролик огонь, очень доходчиво все

  • @Ирина-б2с4х
    @Ирина-б2с4х 5 ปีที่แล้ว

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

  • @akimac
    @akimac 5 ปีที่แล้ว +1

    Так я не поняла, рюкзак то как собирать? Где ответ на этот вопрос? Сижу уже у рюкзака и что дальше? 🤔
    * в замешательстве... 🤯

  • @1984Telin
    @1984Telin 5 ปีที่แล้ว

    Что за карта использовалась на 4 минуте, странный выбор городов для отображения.

  • @lourence8548
    @lourence8548 5 ปีที่แล้ว

    Подумал что расскажут какой-нибудь математический способ собрать рюкзак комивояжёра а в итоге появилась фобия взлома личных данных

  • @fenixlast3898
    @fenixlast3898 5 ปีที่แล้ว

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

  • @timox2822
    @timox2822 5 ปีที่แล้ว

    По поводу сбора вещей в рюкзак. Почему нельзя найти отношение стоимость/вес каждого предмета и брать вещи с наибольшим этим коэффициентом?

    • @ivankovtun5999
      @ivankovtun5999 5 ปีที่แล้ว

      Потому что тогда решение не обязательно будет самым оптимальным. Приведу пример.
      Пускай вместимость рюкзака равна 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.
      Наиболее оптимальное решение для данного примера исключает вещь с наилучшим соотношением.

  • @sergeifilipin5922
    @sergeifilipin5922 5 ปีที่แล้ว

    Если серьёзно,то вопрос задачи по-человечески звучит так, - "Можно ли выучить китайский, тайский и айский за 5 минут, используя некий алгоритм формул?" И за его нахождение тебе дадут мильон. Сразу попробую предположить, что такой алгоритм существует и его существование описано в Новом Завете, когда неграмотные апостолы в одно мгновенье заговорили на нескольких иностранных языках при многочисленных свидетелях. Поэтому исторически зафиксированно его существование и можно сделать вывод что NP=P. Но как найти такой алгоритм? Видимо нужно подключить режим Бога.

  • @maxxam2628
    @maxxam2628 5 ปีที่แล้ว

    на коммивояжоре он поржал,а на многочлене сдержался!)))

  • @Optimus888Amicus
    @Optimus888Amicus 5 ปีที่แล้ว

    Привет, Георгий ! 🌞😉👌
    Вау ! - Это Круто ! 🌞🙌🙏😉👌
    Решить Тера сложную задачу,
    Послать к хренам всю безопасность в интернете,
    и получить за это Милллллион ! 🌞😉✌
    Круто, я согласен ! 😂🤣👌
    Когда начинать ?
    А у вас есть печенки, с чаем ?
    Я очень люблю чёрный чай с кусочком лимона ! 🌞😉👍

  • @georrgy
    @georrgy 5 ปีที่แล้ว

    Спасибо!

  • @mauzeroffc
    @mauzeroffc 3 ปีที่แล้ว

    O(n!).
    Решается, но решаться будет по миллиардам лет.

  • @ДИваннаСусанина
    @ДИваннаСусанина 5 ปีที่แล้ว

    А из каких фильмов взяты эпизоды?

  • @СанФранциск-о8м
    @СанФранциск-о8м 5 ปีที่แล้ว

    Расскажите подробнее, что там Перельман доказал

  • @benben8733
    @benben8733 5 ปีที่แล้ว

    Интересно, как изменится соотношение мнений учёных с течением времени.

  • @СергейПанов-з3ц
    @СергейПанов-з3ц 5 ปีที่แล้ว

    Не до конца вдуплился в тему выпуска. Но мне понравилось.

  • @viyacheslav.
    @viyacheslav. 5 ปีที่แล้ว +1

    Я доказал, но не расскажу из добрых побуждений.

  • @timedealer1996
    @timedealer1996 5 ปีที่แล้ว

    Что за фильм в видео показан относительно путешествий? (3:00)

    • @dnshn
      @dnshn 5 ปีที่แล้ว

      Евротур.

  • @МихаилВикторович-р2я
    @МихаилВикторович-р2я 5 ปีที่แล้ว

    Задача на поиск оптимального маршрута из точки + посетить несколько точек + вернуться обратно решается за n! перебором (n количество точек что мы хотим посетить). Правильно ли я понял что если я смогу решить эту задачу за n^2 или log(n) то мне дадут миллион баксов?

  • @МашаКрасильникова-ф8д
    @МашаКрасильникова-ф8д 5 ปีที่แล้ว

    лайк не глядя, пошла глядеть

  • @MusinMihail
    @MusinMihail 5 ปีที่แล้ว +5

    Объяснили. Я понял.
    Но зачем?

  • @СашаКирилов-у4н
    @СашаКирилов-у4н ปีที่แล้ว

    Для единственной вселенной Np =P для мульти вселенных Np не решаема, так как события дублируются до бесконечности!

  • @ЭлизабетХатсан
    @ЭлизабетХатсан 5 ปีที่แล้ว

    Чисто подставила единицу в эту формулу и доказала, что np=p, a p=np

  • @Alexchib1
    @Alexchib1 5 ปีที่แล้ว

    А вот про рюкзак не понял, нужно установить назовем это "удельный вес" или "ценность груза", и по этому параметру решать брать его или нет. типа толи он сильно тяжелый толи сильно ценный. Типа вес поделить на стоимость. И вывести соотношение сколько такого товара с данным коэффициентом надо взять. Ну все все решается.

    • @Alexchib1
      @Alexchib1 5 ปีที่แล้ว

      @@couldntcareless7884 Ну не важно объем и форма это тоже параметры которые нам извести и чем больше эти параметры там менее ценен для нас этот груз. Значит это тоже идет в знаменатель. В общем вполне реально вывести формулу и решать эту задачку

    • @Alexchib1
      @Alexchib1 5 ปีที่แล้ว

      @@couldntcareless7884 нет, не слишком много (параметров может быть сколько угодно, это не усложняет задачу если они все известны) главное понимать этот параметр (сумма или произведение характеристик) увеличивает условную ценность или уменьшает.

  • @aleksandr27893
    @aleksandr27893 5 ปีที่แล้ว +1

    У меня мир вокруг чуть полиномиальным не стал :)
    Пожалуйста, больше не говори это слово :)))

    • @JuraSheingart
      @JuraSheingart 5 ปีที่แล้ว

      Ахаха))) Заходи ко мне такие же комментарии писать:) (у меня видео очень короткие, прокачаешься)

  • @VladykaVladykov
    @VladykaVladykov 5 ปีที่แล้ว +2

    Было количество операций и вдруг стало количесво времени)

    • @mihail-ln4rf
      @mihail-ln4rf 5 ปีที่แล้ว

      Количество времени пропорционально количеству операций

    • @VladykaVladykov
      @VladykaVladykov 5 ปีที่แล้ว

      @@mihail-ln4rf это, как минимум, требует пояснения

  • @XanderEVGs
    @XanderEVGs 5 ปีที่แล้ว

    наконец то понял че за дичь эта "нп = п" спасиб)

    • @wastedlmobilegames7879
      @wastedlmobilegames7879 5 ปีที่แล้ว

      Я думал типо я такой умный пока не зашёл на видос. (думал N*P=P / 0*0=0)))))

  • @АлександрЕвсеев-н3у
    @АлександрЕвсеев-н3у 5 ปีที่แล้ว +5

    Хм, нужен ли будет миллион долларов, если есть доступ ко всем банковским картам?)

    • @Kmiarg
      @Kmiarg 5 ปีที่แล้ว +4

      1) А если окажется, что P =/= NP ? Тогда доступа ко всем банковским картам у тебя не будет, а вот миллион за доказательство получить можно.
      2) Чтобы получить миллион за решение этой задачи, достаточно доказать существование алгоритма, решающего NP задачи за время P, а не предъявлять пример такого алгоритма. Может быть, доказать его существование значительно проще, чем найти сам алгоритм. В таком случаи доступа к картам не будет.
      3) Может оказаться так, что P=NP и алгоритм решения NP за время P будет найден, но при этом сложность этого алгоритма всё равно окажется непомерно высокой для современных компьютеров. Даже при сложности алгоритма n^100 ( n в степени 100 ) взломать с его помощью банк используя частный компьютер будет практически невозможно (во всяком случаи это будет дольше человеческой жизни), при сложности n^1000 в мире едва ли надётся компьютер способный на это (даже все кластеры google вместе взятые, или даже все компьютеры подключённые к интернету вместе взятые), а при сложности n^10000 такую задачу, не решит даже компьютер размером с Землю (по крайней мере за время меньше человеческой жизни.)

    • @DigiMakc
      @DigiMakc 5 ปีที่แล้ว

      @@Kmiarg , мощность среднестатистического домашнего компьютера примерно 3-15 тераФЛОПС.
      Но мощность сети биткойн в прошлом году была 67260548 ПетаФЛОПС.
      Сколько времени нужно, чтобы такой мощностью выполнить рассчеты?
      Пс. Видюха уровня 1050-1060 взламывает пароль wi-fi состоящий из 8 цифр за 15 минут.

    • @ghaydn
      @ghaydn 5 ปีที่แล้ว

      @@Kmiarg можно ещё доказать, что эта задача в принципе не решаема. И тоже получить свой лям.

    • @Kmiarg
      @Kmiarg 5 ปีที่แล้ว +7

      @@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, но для нижней оценки по времени сгодиться и так.

    • @howuhh8960
      @howuhh8960 5 ปีที่แล้ว

      @@Kmiarg ахуенна

  • @iaroslavtsepkov
    @iaroslavtsepkov 5 ปีที่แล้ว

    А я думал будет разбор задачи о рюкзаке по теории игр рассмотренной в качестве кооперативной игры

  • @robsimonyan6296
    @robsimonyan6296 5 ปีที่แล้ว

    Класс

  • @АртурПирожков-ц5у
    @АртурПирожков-ц5у 5 ปีที่แล้ว

    А разве проверка одного варианта из задачи комивояжера не является N задачей? С ростом числа городов количество операций растет линейно. Где там полиномиальность?

    • @Rot9711
      @Rot9711 3 ปีที่แล้ว

      линейная функция - полином первой степени

  • @JustJaneK
    @JustJaneK 5 ปีที่แล้ว +2

    Очень интересное видео, но перегруз на петле прям боль 😢

    • @ghaydn
      @ghaydn 5 ปีที่แล้ว

      О да. Ещё и хромакей лагает, когда он руками резко двигает.

  • @ВладимирЯсенко-щ9ч
    @ВладимирЯсенко-щ9ч 5 ปีที่แล้ว

    так почем нельзя составить алгоритм в ИИ(Искусственном интелекте), что бы он подобрал нужный алгоритм для PN and P типов задач

  • @TheMrXSENOS
    @TheMrXSENOS 5 ปีที่แล้ว

    А что за фильм, где пацан складывает Фейнмановские книги?

  • @ДерзкийМотохару
    @ДерзкийМотохару 5 ปีที่แล้ว

    Ничего не понял, но было интересно!

  • @СветланаИвановнаБерендеева-п8и

    Ух ты!

  • @Shpebr
    @Shpebr 5 ปีที่แล้ว

    Я решил эту задачу, но поле для комментариев слишком маленькое чтобы написать решение здесь...

  • @duartyom3468
    @duartyom3468 5 ปีที่แล้ว

    Насчет рюкзака. Делим стоимость вещи на ее массу и сраниваем показатели

    • @antares-the-one
      @antares-the-one 5 ปีที่แล้ว +1

      Скорее эта задача про предметы различной формы. Задача вместить как можно больше. Практическое применение - раскрой листовых материалов. Я думаю, в видео перепутали массу и размеры.