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

• MAX-CUT: вероятностное округление/Задачи/Детерминированный 2-приближенный алгоритм для задачи MAX-CUT
  ... состоит не более чем из <m>|E|</m> ребер,
  то данный алгоритм гарантированно даст 2-приближенное решение задачи MAX-CUT).
  Разрезом называется разбиение <m>V</m> на два непересекающихся подмножества ...
  1 КБ (53 слова) - 06:50, 4 мая 2023
• MAX-SAT: дерандомизация/Задачи/ex-derand-maxsat-f0-f1
  ... алгоритма «alg-derand-max-sat» (кроме решения линейной релаксации) будет $O(mn)$.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  470 байт (10 слов) - 06:50, 4 мая 2023
• Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/amplify-optimization
  Есть оптимизационный алгоритм <tt>A</tt>, который для входа <tt>x</tt> находит оптимальное решение с вероятностью <tt>1/|x|</tt>.
  Как сделать из него максимально эффективный алгоритм <tt>B</tt>, ...
  565 байт (24 слова) - 06:50, 4 мая 2023
• Несложно о сложности. Примеры алгоритмов/Задачи/tsp-greedy-bad
  ... дешевые ребра к еще непосещенным вершинам, не гарантирует нахождение оптимального решения.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  625 байт (3 слова) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/lpt-rule-for-scheduling-min-lj
  ...
  <latex>
  \min l_j > OPT(x)/3
  </latex>
  этот алгоритм находит оптимальное решение.
  (OPT(x) — значение этого оптимального решения).
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  861 байт (21 слово) - 06:50, 4 мая 2023
• MAX-CUT: вероятностное округление/Задачи/ex-maxcut-trivial-greedy-1-2
  ... оставшиеся вершины, к множеству, с которым у этой вершины меньше ребер-связей.
  Прав ли студент?
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  673 байт (6 слов) - 06:50, 4 мая 2023
• MAX-CUT: вероятностное округление/Задачи/ex-min-maxmatching-1-2
  ... ) паросочетания минимального размера.
  Сложность алгоритма не больше $O( (n+m)^2 )$.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  507 байт (9 слов) - 06:50, 4 мая 2023
• MAX-SAT: дерандомизация/Задачи/2-приближенный алгоритм для максимальной совместной подсистемы
  ... совместной подсистемы системы линейных булевых уравнений (сложения и умножения по модулю 2).
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  586 байт (6 слов) - 06:50, 4 мая 2023
• MAX-SAT: дерандомизация/Задачи/shell-game
  ... - к разорению…
  Обоснуйте.
  Подсчитайте матожидание выигрыша для каждой из стратегий.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  3 КБ (23 слова) - 06:50, 4 мая 2023
• Вероятностная проверка тождеств/Задачи/determinant
  ... вероятности не больше ½
  для проверки этой матрицы на вырожденность ($\det A \equiv 0$).
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  641 байт (22 слова) - 06:50, 4 мая 2023
• Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/BPP in PSPACE
  ... Лаутемана (не палите из пушек по воробьям!).
  Просто посмотрите на определения обоих классов.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  447 байт (9 слов) - 06:50, 4 мая 2023
• Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/RP in PPoly
  Докажите, что <m>RP \subseteq P/poly </m>.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  229 байт (9 слов) - 06:50, 4 мая 2023
• Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/amplify-when-specific-error-bounded
  ... >
  * <tt>Prob(A(x)=w) <= ¼</tt>
  Можно ли как-то из <tt>A</tt> сделать полезный алгоритм?
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  604 байт (30 слов) - 06:50, 4 мая 2023
• Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/ex-fix-spoj-23
  ... алгоритм, который правильно вычисляет $F(x)$ с вероятностью не меньше $\frac{2}{3}$.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  2 КБ (31 слово) - 06:50, 4 мая 2023
• Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/ex-fix-spoj-recovery
  ... в опытную эксплуатацию),
  и нужно восстановить
  значение этой функции за время $O(N^2)$.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  660 байт (12 слов) - 06:50, 4 мая 2023
• Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/las-vegas-k-ammplification
  ... повторений для заданного уровня вероятности правильного ответа <tt>q</tt> в алгоритме <tt>B</tt>.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  754 байт (35 слов) - 06:50, 4 мая 2023
• Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/mc-amplification
  ...
  Если:
  * <m>p\left(|x|\right)=\frac{1}{|x|}</m>
  * <m>p\left(|x|\right)=\frac{1}{\log_2{|x|}}</m>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  673 байт (43 слова) - 06:50, 4 мая 2023
• Временная и пространственная сложность алгоритмов/Задачи/PSPACE in EXPTIME
  Докажите, что <m>PSPACE \subseteq EXPTIME </m>.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  234 байт (8 слов) - 06:50, 4 мая 2023

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