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

• Файл:Minimum Test Collection 2023-12-21 14-52-00 image0.png [[Category:На_проверку]] [[Category:Проблемы_в_решении]] (1802 × 733 (70 КБ)) - 11:52, 21 декабря 2023

• 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
• Вероятность/Задачи/alice-bob-three-strange-dice
  ... первой кости Бобу.
  Покажите, что несмотря на это «благородство», что вероятность выигрыша Алисы больше ½.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  1 КБ (3 слова) - 06:50, 4 мая 2023
• Вероятность/Задачи/coin-game-n-k
  ... выиграет <tt>n</tt>-раз.
  Какова вероятность, что проигравший к концу игры выиграет <tt>k</tt>-раундов?
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  519 байт (9 слов) - 06:50, 4 мая 2023
• Вероятность/Задачи/coin-ten-times
  ... >0<i<6</tt>, <tt>i</tt>-й и <tt>11-i</tt>-й броски будут одинаковы.
  * Будет выброшено подряд четыре «орла».
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  551 байт (11 слов) - 06:50, 4 мая 2023
• Вероятность/Задачи/estimate-probability
  ... некоторое число <m>\kappa</m> экспериментов и взяв среднее значение. Оценить сверху <m>\kappa</m> как функцию от <m>\delta</m>.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  665 байт (20 слов) - 06:50, 4 мая 2023

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