Результаты поиска
Материал из DISCOPAL
Показаны 201-250 из 532 результатов запроса Решение, выполненного за 0.001 секунд. Статистика:
- ... {1}{2}$ для нахождения максимального (по включению) паросочетания минимального объема.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]436 байт (7 слов) - 06:50, 4 мая 2023 - ... мультипликативной ошибки жадного алгоритма для задачи покрытия множеств достигается
по порядку.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]426 байт (8 слов) - 06:50, 4 мая 2023 - ... «этот алгоритм с паросочетаниями» строит покрытие с числом вершин
<m> \ge 2 \cdot OPT</m>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]523 байт (9 слов) - 06:50, 4 мая 2023 - ... ошибку не превышающую 2 (целевая функция — минимизировать максимум по весам в обоих кучах).
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]774 байт (3 слова) - 06:50, 4 мая 2023 - ... с порядком сортировки по уменьшению cтоимости. Сформулируйте эффективный алгоритм для поиска оптимального решения этой разновидности задачи о рюкзаке и обоснуйте его корректность.
[[Категория ...606 байт (1 слово) - 06:50, 4 мая 2023 - ... , на которых модифицированный жадный алгоритм дает (хотя бы в пределе) наихудшую оценку точности.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]397 байт (3 слова) - 06:50, 4 мая 2023 - ... (выбирать по отношению цена/вес) выберет \red{набор в~$k$ раз хуже оптимального}.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]516 байт (15 слов) - 06:50, 4 мая 2023 - ... , но без циклов отрицательной длины,
для которого алгоритм Дейкстры даст неправильный ответ.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]432 байт (3 слова) - 06:50, 4 мая 2023 - ... алгоритм нахождения наиболее надежных маршрутов между данным узлом и~всеми остальными.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]945 байт (16 слов) - 06:50, 4 мая 2023 - ... каждом уравнении то они разные! Система уравнений из двух переменных это абсолютная банальщина}}
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]1 КБ (16 слов) - 06:50, 4 мая 2023 - Постройте полиномиальную сводимость задачи 3SAT к задаче CLIQUE.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]286 байт (5 слов) - 06:50, 4 мая 2023 - ... одной бригады обслуживания, которые вместе должны посетить
все вершины графа без повторений.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]1 КБ (20 слов) - 06:50, 4 мая 2023 - ... подмножеств) полиномиально эквивалентна задаче о нахождении максимальной клики в графе.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]557 байт (3 слова) - 06:50, 4 мая 2023 - ... in coNP ===
<blockquote>
{{:Tautology}}
</blockquote>
Покажите, что эта задача в coNP.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]299 байт (10 слов) - 06:50, 4 мая 2023 - ... максимального по числу вершин полного подграфа (клики) в графе
* и задачи о вершинном покрытии
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]550 байт (4 слова) - 06:50, 4 мая 2023 - Покажите, что задача 2SAT лежит в P.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]235 байт (5 слов) - 06:50, 4 мая 2023 - Выразите логическое отношение эквивалентности в виде 3-КНФ формулы.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]301 байт (4 слова) - 06:50, 4 мая 2023 - ... графов (т.,е. графов, не содержащих ни одного гамильтонова цикла)
принадлежит coNP.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]608 байт (5 слов) - 06:50, 4 мая 2023 - ... трех раз, причем каждый литерал - не больше двух.
Покажите, что и эта задача NP-полна.
[[Category:Решенные задачи]]
<!--Вообще-то, решения уже есть-->
[[Категория:Теоретические задачи]]590 байт (8 слов) - 06:50, 4 мая 2023 - ... выполнить
больше чем <tt>K</tt>, количество скобок.
Покажите, что эта задача NP-полна.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]557 байт (12 слов) - 06:50, 4 мая 2023 - Покажите, что <m>P \subseteq NP \cap coNP</m>.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]233 байт (10 слов) - 06:50, 4 мая 2023 - ... NP$, т.к.
если оракул-Мерлин предоставит решение $v$,
доказывающее принадлежность полинома $p \in DFNT$, ... 0$.
Прав ли студент?
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]686 байт (14 слов) - 06:50, 4 мая 2023 - ... полиномиальный алгоритм для проверки, есть ли в заданном графе хотя бы один «треугольник».
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]363 байт (3 слова) - 06:50, 4 мая 2023 - ... с мультипликативной ошибкой не превышающей величины, зависящей только от числа вершин графа.
[[Category:Решенные задачи]]
<!--Вообще-то, решения уже есть-->
[[Категория:Теоретические задачи]]539 байт (9 слов) - 06:50, 4 мая 2023 - {{:Subset Sum}}
Постройте недетерминированный полиномиальный алгоритм для задачи [[Subset Sum]]
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]331 байт (7 слов) - 06:50, 4 мая 2023 - ... графа в два цвета ==
Постройте полиномиальный алгоритм для раскраски графа в два цвета.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]411 байт (3 слова) - 06:50, 4 мая 2023 - ...
<latex>
\mathrm{E} \max_k|N_kN_k| \leq \sum_{k=1}^m {\binom{m}{k}} \mathrm{P}(k).
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]372 байт (21 слово) - 06:50, 4 мая 2023 - Какие входные данные для алгоритма «alg-sat-dynp» заставят его работать экспоненциально долго?
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]341 байт (4 слова) - 06:50, 4 мая 2023 - На каких входных данных алгоритм из этой темы, будет работать <m>O(m)</m>?
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]302 байт (7 слов) - 06:50, 4 мая 2023 - ... распределение: Вероятность появления каждой входной строки.
;<m>x_n</m>: вход длины n.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]680 байт (35 слов) - 06:50, 4 мая 2023 - ... для упаковки
заставят его работать экспоненциально долго?
* А какие — за <m>O(n^3)</m>?
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]451 байт (7 слов) - 06:50, 4 мая 2023 - ... слове», т.е. для данной МТ <tt>T</tt> определить,
остановится ли она на пустом слове.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]453 байт (7 слов) - 06:50, 4 мая 2023 - ... 4815162342» встречается в десятичном разложении числа
$\pi$ не менее чем $n$ раз подряд.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]463 байт (11 слов) - 06:50, 4 мая 2023 - ... за
другой все машины Тьюринга, которые не останавливаются, будучи
запущенными на пустой ленте.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]465 байт (3 слова) - 06:50, 4 мая 2023 - ... : попадет ли машина в это
состояние хотя бы для одного входного слова <tt>x</tt>?
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]581 байт (14 слов) - 06:50, 4 мая 2023 - ... можно сказать про $T'(n)$,
которое есть минимальное время ее работы на входах длины $n$?
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]815 байт (21 слово) - 06:50, 4 мая 2023 - ... любой вычислимой всюду
определенной функции $b(n)$, то есть $\lim [T(n)/b(n)]=+\infty$.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]690 байт (20 слов) - 06:50, 4 мая 2023 - ... >
Докажите, для разрешимых языков $L_1$ и $L_2$, язык $L=L_1 \cup L_2$ также разрешим.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]322 байт (11 слов) - 06:50, 4 мая 2023 - ... существуют невычислимые по Тьюрингу
функции <tt>y=f(x)</tt>, используя мощностные соображения.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]364 байт (8 слов) - 06:50, 4 мая 2023 - Покажите, что метод случайного блуждания не работает для решения задачи связности на ориентированных графах.
Представьте пример ориентированного графа c ''n'' вершинами, в котором даже есть путь из ...650 байт (11 слов) - 06:50, 4 мая 2023 - ... и для любого n>3,
существует экземпляр TSP с n-городами, на котором этот алгоритм будет находить решение, в С раз
хуже (т.е. больше).
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]705 байт (15 слов) - 06:50, 4 мая 2023 - ... : для любого i>0, сконструируйте входную задачу, где NN-алгоритм будет находить решение, минимум в (i+2)/6 раз большее оптимального.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]792 байт (11 слов) - 06:50, 4 мая 2023 - ...
\frac{M_{LPT}}{OPT(x)} = \frac{1}{3} ( 4 — \frac1p )
</m>
* OPT(x) — значение этого оптимального решения.
* <m>M_{LPT}</m> — значение, найденное алгоритмом.
См. также [[Жадный алгоритм в задачах ...1023 байт (30 слов) - 06:50, 4 мая 2023 - ... < \frac{1}{3} ( 4 — \frac1p )
</m>
* OPT(x) — значение этого оптимального решения.
* <m>M_{LPT}</m> — значение, найденное алгоритмом
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]878 байт (28 слов) - 06:50, 4 мая 2023 - ... [https://en.wikipedia.org/wiki/Bin_packing_problem First Fit], обобщенный для многомерности,
найдет (d+1)-оптимальное решение.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]1 КБ (33 слова) - 06:50, 4 мая 2023
Просмотреть (предыдущие 50 | следующие 50) (20 | 50 | 100 | 250 | 500)