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

• Жадный алгоритм в задачах о покрытии/Задачи/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
• Временная и пространственная сложность алгоритмов/Задачи/QSAT in PSPACE
  {{:QSAT}}
  Докажите, что [[QSAT]] in [[PSPACE]].
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  235 байт (7 слов) - 06:50, 4 мая 2023
• Временная и пространственная сложность алгоритмов/Задачи/ex-braces-parse-in-logspace
  ... ldots
  \item[$\notin L$] $)($, \ldots
  \end{description}
  Докажите, что $L \in LOGSPACE$.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  488 байт (26 слов) - 06:50, 4 мая 2023
• Временная и пространственная сложность алгоритмов/Задачи/ex-limited-halt
  ... \MT{M} останавливается на $x$ не позже, чем через $t$ шагов.
  Докажите: $L \in EXPTIME$.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  447 байт (18 слов) - 06:50, 4 мая 2023
• Временная и пространственная сложность алгоритмов/Задачи/ex-logspace-in-p
  <latex>
  \[
  LOGSPACE=DSPACE(O(\log n)).
  \]
  Покажите, что $LOGSPACE \subseteq P$.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  276 байт (13 слов) - 06:50, 4 мая 2023
• Временная и пространственная сложность алгоритмов/Задачи/st-connectivity-log-diameter
  ... только через вершины имеющие не больше $777$ соседей, и <<0>> в противном случае.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  711 байт (19 слов) - 06:50, 4 мая 2023

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