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

• Динамическое программирование для задачи о рюкзаке/Задачи/Dynamic Voltage Scaling
  ... добиться минимального энергопотребления.
  Сведите задачу к классическому оптимизационному рюкзаку.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  1 КБ (42 слова) - 06:50, 4 мая 2023
• Динамическое программирование для задачи о рюкзаке/Задачи/workaholic
  ... представить входные данные <m>h, l</m>, на которых жадный алгоритм выдаст в <m>k</m> раз худшее решение.
  * Разработайте оптимальный полиномиальный алгоритм, чтобы найти максимальный объем работ за ...
  2 КБ (60 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/ex-greedy-covering-bound-asymptotic
  ... жадного алгоритма в задаче о покрытии множеств оценка <m>1+\ln m</m> достигается асимптотически.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  390 байт (7 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/ex-greedy-k-covering-bound-asymptotic
  ... , что оценка точности $1-e^{-1}$ для задачи о~$k$-покрытии асимптотически достижима.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  351 байт (9 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/ex-max-maxmatching-1-2
  ... алгоритм с точностью <m>\frac{1}{2}</m> для нахождения паросочетания максимального размера.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  371 байт (6 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/ex-min-maxmatching-1-2
  ... {1}{2}$ для нахождения максимального (по включению) паросочетания минимального объема.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  436 байт (7 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/exersize-greedy-covering-1
  ... мультипликативной ошибки жадного алгоритма для задачи покрытия множеств достигается
  по порядку.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  426 байт (8 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/vertex-cover
  ... «этот алгоритм с паросочетаниями» строит покрытие с числом вершин
  <m> \ge 2 \cdot OPT</m>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  523 байт (9 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задаче о рюкзаке/Задачи/Greedy-Subset-Sum
  ... ошибку не превышающую 2 (целевая функция — минимизировать максимум по весам в обоих кучах).
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  774 байт (3 слова) - 06:50, 4 мая 2023
• Жадный алгоритм в задаче о рюкзаке/Задачи/sorted weight and cost
  ... с порядком сортировки по уменьшению cтоимости. Сформулируйте эффективный алгоритм для поиска оптимального решения этой разновидности задачи о рюкзаке и обоснуйте его корректность.
  [[Категория ...
  606 байт (1 слово) - 06:50, 4 мая 2023
• Жадный алгоритм в задаче о рюкзаке/Задачи/Нижняя оценка точности модифицированного жадного
  ... , на которых модифицированный жадный алгоритм дает (хотя бы в пределе) наихудшую оценку точности.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  397 байт (3 слова) - 06:50, 4 мая 2023
• Жадный алгоритм в задаче о рюкзаке/Задачи/Тупая жадность - очень плохо
  ... (выбирать по отношению цена/вес) выберет \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

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