Результаты поиска
Материал из DISCOPAL
Показаны 181-200 из 531 результатов запроса Решение, выполненного за 0.003 секунд. Статистика:
- решен найдено 6179 раз в 2218 документах
- ... вероятности не больше ½
для проверки этой матрицы на вырожденность ($\det A \equiv 0$).
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]641 байт (22 слова) - 06:50, 4 мая 2023 - ... Лаутемана (не палите из пушек по воробьям!).
Просто посмотрите на определения обоих классов.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]447 байт (9 слов) - 06:50, 4 мая 2023 - Докажите, что <m>RP \subseteq P/poly </m>.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]229 байт (9 слов) - 06:50, 4 мая 2023 - ... >
* <tt>Prob(A(x)=w) <= ¼</tt>
Можно ли как-то из <tt>A</tt> сделать полезный алгоритм?
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]604 байт (30 слов) - 06:50, 4 мая 2023 - ... алгоритм, который правильно вычисляет $F(x)$ с вероятностью не меньше $\frac{2}{3}$.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]2 КБ (31 слово) - 06:50, 4 мая 2023 - ... в опытную эксплуатацию),
и нужно восстановить
значение этой функции за время $O(N^2)$.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]660 байт (12 слов) - 06:50, 4 мая 2023 - ... повторений для заданного уровня вероятности правильного ответа <tt>q</tt> в алгоритме <tt>B</tt>.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]754 байт (35 слов) - 06:50, 4 мая 2023 - ...
Если:
* <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 - Докажите, что <m>PSPACE \subseteq EXPTIME </m>.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]234 байт (8 слов) - 06:50, 4 мая 2023 - {{:QSAT}}
Докажите, что [[QSAT]] in [[PSPACE]].
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]235 байт (7 слов) - 06:50, 4 мая 2023 - ... ldots
\item[$\notin L$] $)($, \ldots
\end{description}
Докажите, что $L \in LOGSPACE$.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]488 байт (26 слов) - 06:50, 4 мая 2023 - ... \MT{M} останавливается на $x$ не позже, чем через $t$ шагов.
Докажите: $L \in EXPTIME$.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]447 байт (18 слов) - 06:50, 4 мая 2023 - <latex>
\[
LOGSPACE=DSPACE(O(\log n)).
\]
Покажите, что $LOGSPACE \subseteq P$.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]276 байт (13 слов) - 06:50, 4 мая 2023 - ... только через вершины имеющие не больше $777$ соседей, и <<0>> в противном случае.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]711 байт (19 слов) - 06:50, 4 мая 2023 - ... добиться минимального энергопотребления.
Сведите задачу к классическому оптимизационному рюкзаку.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]1 КБ (42 слова) - 06:50, 4 мая 2023 - ... представить входные данные <m>h, l</m>, на которых жадный алгоритм выдаст в <m>k</m> раз худшее решение.
* Разработайте оптимальный полиномиальный алгоритм, чтобы найти максимальный объем работ за ...2 КБ (60 слов) - 06:50, 4 мая 2023 - ... жадного алгоритма в задаче о покрытии множеств оценка <m>1+\ln m</m> достигается асимптотически.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]390 байт (7 слов) - 06:50, 4 мая 2023 - ... , что оценка точности $1-e^{-1}$ для задачи о~$k$-покрытии асимптотически достижима.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]351 байт (9 слов) - 06:50, 4 мая 2023 - ... алгоритм с точностью <m>\frac{1}{2}</m> для нахождения паросочетания максимального размера.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]371 байт (6 слов) - 06:50, 4 мая 2023 - ... {1}{2}$ для нахождения максимального (по включению) паросочетания минимального объема.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]436 байт (7 слов) - 06:50, 4 мая 2023
Просмотреть (предыдущие 20 | следующие 20) (20 | 50 | 100 | 250 | 500)