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

• Вероятностные вычисления. Классы 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
• Динамическое программирование для задачи о рюкзаке/Задачи/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

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