Результаты поиска

• Жадный алгоритм в задаче о рюкзаке/Задачи/Тупая жадность - очень плохо
  ... (выбирать по отношению цена/вес) выберет \red{набор в~$k$ раз хуже оптимального}.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  516 байт (15 слов) - 06:50, 4 мая 2023
• Несложно о сложности. Примеры алгоритмов/Задачи/ex-dijksta-not-work-on-negative-weight
  ... , но без циклов отрицательной длины,
  для которого алгоритм Дейкстры даст неправильный ответ.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  432 байт (3 слова) - 06:50, 4 мая 2023
• Несложно о сложности. Примеры алгоритмов/Задачи/ex-network-reliability
  ... алгоритм нахождения наиболее надежных маршрутов между данным узлом и~всеми остальными.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  945 байт (16 слов) - 06:50, 4 мая 2023
• MAX-CUT: вероятностное округление/Задачи/2-boolean system
  ... каждом уравнении то они разные! Система уравнений из двух переменных это абсолютная банальщина}}
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  1 КБ (16 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3КНФ→Клика
  Постройте полиномиальную сводимость задачи 3SAT к задаче CLIQUE.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  286 байт (5 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/NPC «k бригад обслуживания»
  ... одной бригады обслуживания, которые вместе должны посетить
  все вершины графа без повторений.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  1 КБ (20 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Packing=MaxClique
  ... подмножеств) полиномиально эквивалентна задаче о нахождении максимальной клики в графе.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  557 байт (3 слова) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Tautology in coNP
  ... in coNP ===
  <blockquote>
  {{:Tautology}}
  </blockquote>
  Покажите, что эта задача в coNP.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  299 байт (10 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Vcover-clique
  ... максимального по числу вершин полного подграфа (клики) в графе
  * и задачи о вершинном покрытии
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  550 байт (4 слова) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-2sat-in-p
  Покажите, что задача 2SAT лежит в P.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  235 байт (5 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-equiv-in-3knf
  Выразите логическое отношение эквивалентности в виде 3-КНФ формулы.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  301 байт (4 слова) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-hamilton-cycle-in-np
  ... графов (т.,е. графов, не содержащих ни одного гамильтонова цикла)
  принадлежит coNP.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  608 байт (5 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-limited-3sat-npc
  ... трех раз, причем каждый литерал - не больше двух.
  Покажите, что и эта задача NP-полна.
  [[Category:Решенные задачи]]
  <!--Вообще-то, решения уже есть-->
  [[Категория:Теоретические задачи]]
  590 байт (8 слов) - 06:50, 4 мая 2023
• PCP и аппроксимируемость/Задачи/ex-max2sat-in-npc
  ... выполнить
  больше чем <tt>K</tt>, количество скобок.
  Покажите, что эта задача NP-полна.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  557 байт (12 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-p-in-np-and-conp
  Покажите, что <m>P \subseteq NP \cap coNP</m>.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  233 байт (10 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-polynomial-diofant-is-in-np
  ... NP$, т.к.
  если оракул-Мерлин предоставит решение $v$,
  доказывающее принадлежность полинома $p \in DFNT$, ... 0$.
  Прав ли студент?
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  686 байт (14 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-triange-in-p
  ... полиномиальный алгоритм для проверки, есть ли в заданном графе хотя бы один «треугольник».
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  363 байт (3 слова) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/nonapprox TSP
  ... с мультипликативной ошибкой не превышающей величины, зависящей только от числа вершин графа.
  [[Category:Решенные задачи]]
  <!--Вообще-то, решения уже есть-->
  [[Категория:Теоретические задачи]]
  539 байт (9 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/НМТ для Subset Sum
  {{:Subset Sum}}
  Постройте недетерминированный полиномиальный алгоритм для задачи [[Subset Sum]]
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  331 байт (7 слов) - 06:50, 4 мая 2023

Просмотреть (предыдущие 20 | следующие 20) (20 | 50 | 100 | 250 | 500)