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

• Жадный алгоритм в задачах о покрытии/Задачи/minimum-multicover-approx-with-linear-relaxation
  ... ]].
  Придумайте приближенный алгоритм, основанный на линейной релаксации задачи линейного программирования, который находит
  P-оптимальное решение, где <m>P=\max_i\sum_ja_{ij}</m>
  [[Категория ...
  506 байт (16 слов) - 06:50, 4 мая 2023
• MAX-SAT: вероятностное округление/Задачи/max-sat-local-opt--1-2
  ... -03-01-p116 -->
  Опишите алгоритм локального поиска для MAX-SAT, покажите, что он находит решение не хуже половины от оптимума.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  342 байт (6 слов) - 06:50, 4 мая 2023
• Полиномиальный в среднем алгоритм для SAT/Задачи/ex-greedy-sat-is-2-approx
  ... алгоритм [[Greedy algorithm for SAT]] находит 2-приближенное решение для MAX SAT (т.е. не хуже оптимального больше чем в два раза).
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  378 байт (12 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/knights-np-complete
  <latex>
  Доказать, что следующая проблема принятия решения NP-полная. Пусть есть $n$ рыцарей, и множество пар рыцарей, являющихся врагами. Возможно ли рассадить (расположить) рыцарей у ...
  557 байт (5 слов) - 06:50, 4 мая 2023
• 2001-gre-math.pdf/Q52
  ... II и III
  === Объяснение ===
  {{cstest-source|2001-gre-math.pdf|46|52}}
  Вектор (0, 0, 0) является решением уравнения при любом b, значит утверждение II истинно. При этом если b = 4, то строки матрицы ...
  2 КБ (53 слова) - 13:51, 13 января 2025
• MAX-CUT: вероятностное округление/Задачи/Верхняя оценка разреза в случайном графе
  ... зарождения ребра — ½.
  ;Hint: Сначала надо правильно решить [[MAX-CUT: вероятностное округление/Задачи/Матожидание разреза]].
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  589 байт (8 слов) - 06:50, 4 мая 2023
• MAX-CUT: вероятностное округление/Задачи/0.5-приближенный вероятностный для MAX-CUT
  ... ($p=1/2$) приписать к~множеству $T$ или $S$.
  Докажите, что этот вероятностный алгоритм является $0.5$-приближенным.
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  582 байт (6 слов) - 06:50, 4 мая 2023
• MAX-CUT: вероятностное округление/Задачи/merge-vertices
  ... 3--5
  }
  </neato>
  ----
  Доказать, что вероятностный алгоритм вычисляет минимальный разрез с вероятностью <m>P \ge \frac{2}{n(n-1)}</m>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  2 КБ (92 слова) - 06:50, 4 мая 2023
• MAX-CUT: вероятностное округление/Задачи/Матожидание разреза
  ... формулу матожидания средней величины разреза по всем таким случайным графам из <tt>n</tt>-вершин.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  499 байт (7 слов) - 06:50, 4 мая 2023
• MAX-SAT: вероятностное округление/Задачи/MAX-3ESAT
  ... «MAX-SAT», только в КНФ в каждой скобке ровно три литерала.
  Предложите вероятностный алгоритм с точностью <m>\frac{7}{8}</m>.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  382 байт (6 слов) - 06:50, 4 мая 2023
• MAX-SAT: вероятностное округление/Задачи/не более половины скобок
  ... ), для которой на любом наборе переменных выполнено не более половины скобок.
  * А менее половины скобок?
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  515 байт (1 слово) - 06:50, 4 мая 2023
• MAX-SAT: дерандомизация/Задачи/Комбинированная дерандомизация
  ... путем дерандомизации построения
  <m>\frac{3}{4}</m>-приближенного детерминированного полиномиального алгоритма для задачи MAX-SAT?
  [[Category:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  366 байт (6 слов) - 06:50, 4 мая 2023
• PCP и аппроксимируемость/Задачи/TSP-approx
  ... алгоритм для задачи о коммивояжере на полном графе с положительными весами, где f любая функция, то P=NP.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  417 байт (6 слов) - 06:50, 4 мая 2023
• Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/ex-zpp-notnull
  ... для времени работы $T_M(x)$ машины M выполняется:
  \[
  \mathrm{E} T_M(x) \leq p(|x|).
  \]
  Докажите, что $ZPP_{NotNull}=ZPP$.
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  617 байт (24 слова) - 06:50, 4 мая 2023
• Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/Необратимое семейство перестановок
  ... <m>n</m> вероятность события <m>A(f_n(x))=x</m> меньше (случайно взятый <m>x</m> длины <m>n</m> и случайное бросание алгоритма).
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  769 байт (26 слов) - 06:50, 4 мая 2023

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