Результаты поиска
Материал из DISCOPAL
Показаны 1-250 из 531 результатов запроса Решение, выполненного за 0.001 секунд. Статистика:
Файл:Эксперимент — улучшаем старые решения 2024-03-28 16-04-56 image0.png (676 × 411 (40 КБ)) - 13:04, 28 марта 2024- ... входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]360 байт (3 слова) - 06:50, 4 мая 2023 - ... входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]360 байт (3 слова) - 06:50, 4 мая 2023 - ... . Классы NP, coNP, NPC/Задачи/3КНФ→Клика]], но дополнительно требуется, чтобы количество решений сохранялось.
Т.е. если 3КНФ <tt>F</tt> полиномиально преобразуется в (граф <tt>G</tt>, число <tt ...773 байт (22 слова) - 06:50, 4 мая 2023 - ... {Доказать, что задача поиска решения уравнения}
\\
x^k = n, \ \ \ k,n \ \in \ N, \\ \text{в натуральных числах разрешима за полиномиальное время.}
</latex>
[[Категория:Решенные задачи]]
[[Категория ...373 байт (11 слов) - 06:50, 4 мая 2023 - ... комбинаций в колоде (52!) получим искомую вероятность.
----
13 * binomial[4,3] * 12 * binomial[4,2] * 5! * (52-5)! / 52! = 6/4165
[[Category:Решение]]4 КБ (64 слова) - 16:18, 16 декабря 2013 - ... redirect=no
category=Sorting
category=Solved
ignore=Permission denied
ignore=Решенные практические задачи
silent=true
</templatedpagelist>
=== Numbers ===
<templatedpagelist>
showtotal=yes
namespace ...2 КБ (141 слово) - 14:48, 21 мая 2023 - #перенаправление [[Несложно о сложности. Примеры алгоритмов/Задачи/Поиск решения уравнения за полиномиальное время/Решение Ракутин]]244 байт (0 слов) - 21:03, 22 марта 2017
- #перенаправление [[Несложно о сложности. Примеры алгоритмов/Задачи/Поиск решения уравнения за полиномиальное время/решение Дмитрий Карпов]]257 байт (0 слов) - 21:03, 22 марта 2017
- ... один проход по таблице сравнивается с входными параметрами всех правил. Если совпадения не найдено, решения нет.
Если есть совпадение для $i$-го правила, то выходные значение этого правила $X_{out ...2 КБ (52 слова) - 17:21, 28 декабря 2014 - Непринятые решения (полностью, или частично неверные).
__NOCATEGORYCOLUMNS__44 вхождения (0 подкатегорий, 10 файлов) - 08:13, 20 декабря 2013 - Решенные студентами задачи.
См. также [[:Category:Нерешенные задачи]]
__NOCATEGORYCOLUMNS__
[[Category:Упражнения]]172 вхождения (0 подкатегорий, 0 файлов) - 04:49, 26 октября 2012 - ... предыдущим рассуждениям.
Итак, мы получаем ответ:
<latex>\[\sum\limits_{\ell = 0}^{n-1}\frac{C_{n+k - 1}^{k}}{C_{n+\ell - 1}^{\ell}}\]</latex>
P.S. Решение неверное, можете не проверять.2 КБ (66 слов) - 20:54, 30 июня 2013 - #перенаправление [[Random-cloning-n-times Решение Рубановой Ю.]]96 байт (1 слово) - 18:26, 8 ноября 2013
- #перенаправление [[Жадный алгоритм в задаче о рюкзаке/Задачи/sorted weight and cost/Решение Иваничкина]]171 байт (4 слова) - 16:59, 6 декабря 2013
- #перенаправление [[Временная и пространственная сложность алгоритмов/Задачи/QSAT in PSPACE/Решение Иваничкина]]194 байт (3 слова) - 17:01, 6 декабря 2013
- #перенаправление [[MAX-SAT: вероятностное округление/Задачи/MAX-3ESAT/Решение Иваничкина]]151 байт (3 слова) - 17:03, 6 декабря 2013
- #перенаправление [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/las-vegas-k-ammplification/Решение Иваничкина]]192 байт (5 слов) - 17:03, 6 декабря 2013
- #перенаправление [[Несложно о сложности. Примеры алгоритмов/Задачи/ex-dijksta-not-work-on-negative-weight/Решение Иваничкина]]199 байт (1 слово) - 17:05, 6 декабря 2013
- #перенаправление [[Жадный алгоритм в задачах о покрытии/Задачи/ex-breath-tree-for-vertex-covering-1-2/Решение Иваничкина]]191 байт (2 слова) - 17:05, 6 декабря 2013
- #перенаправление [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3КНФ→Клика/Решение Иваничкина]]215 байт (4 слова) - 17:06, 6 декабря 2013
- #перенаправление [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/BPP in PSPACE/Решение Рубановой]]177 байт (7 слов) - 19:10, 10 декабря 2013
- #перенаправление [[Вероятностная проверка тождеств/Задачи/determinant/Решение Рубановой]]155 байт (1 слово) - 19:11, 10 декабря 2013
- #перенаправление [[Динамическое программирование для задачи о рюкзаке/Задачи/Dynamic Voltage Scaling/Решение Рубановой]]202 байт (3 слова) - 19:12, 10 декабря 2013
- #перенаправление [[Полиномиальный в среднем алгоритм для SAT/Задачи/ex-sat-average-expect-max-nk/Решение Рубановой]]186 байт (2 слова) - 19:13, 10 декабря 2013
- #перенаправление [[Жадный алгоритм в задаче о рюкзаке/Задачи/Greedy-Subset-Sum/Решение Рубановой]]164 байт (1 слово) - 19:13, 10 декабря 2013
- #перенаправление [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Packing=MaxClique/Решение Рубановой]]210 байт (6 слов) - 19:14, 10 декабря 2013
- #перенаправление [[Вероятность/Задачи/random-cloning-n-times/Решение Рубановой Ю.]]132 байт (1 слово) - 19:14, 10 декабря 2013
- #перенаправление [[MAX-SAT: дерандомизация/Задачи/shell-game/Решение Рубановой]]131 байт (2 слова) - 19:15, 10 декабря 2013
- #перенаправление [[Несложно о сложности. Примеры алгоритмов/Задачи/tsp-greedy-bad/Решение Рубановой]]173 байт (1 слово) - 19:15, 10 декабря 2013
- #перенаправление [[Жадный алгоритм в задачах о покрытии/Задачи/vertex-cover/Решение Рубановой]]163 байт (1 слово) - 19:16, 10 декабря 2013
- <latex>Решение предложенной студентами задачи:
Задан набор точек $\left\{x_1,\dots,x_n\right\}$, где $x_i \in \mathcal{R}$.
Необходимо покрыть все ...2 КБ (95 слов) - 17:21, 17 декабря 2013 - #перенаправление [[Попытка решения PSPACE in EXPTIME. Бойко Дмитрий, 175.]]116 байт (3 слова) - 10:47, 18 мая 2014
- #перенаправление [[Динамическое программирование для задачи о рюкзаке/Задачи/Гвоздики/Решение Гилязева Руслана]]208 байт (0 слов) - 18:00, 3 июня 2015
- Подход к решению.
*1. Лексикографически упорядочить отрезки.
*2. Показать, что прямая существует, если выпуклые оболочки концов отрезков не пересекаются.277 байт (0 слов) - 01:22, 11 декабря 2016 - Подсказка при решении: Лучше двигать смоделированные ленты, а не их начала.137 байт (0 слов) - 11:11, 13 декабря 2016
- #перенаправление [[Несложно о сложности. Примеры алгоритмов/Задачи/Поиск решения уравнения за полиномиальное время]]214 байт (0 слов) - 21:03, 22 марта 2017
- ... записано в виде {f(1), f(2), ...}, где f - вычислимая функция, все значения которой различны.
Решение подзадачи: пусть A - алгоритм, перечисляющий M. Алгоритм B, вычисляющий f: на входе n B запускает ...2 КБ (53 слова) - 22:58, 10 мая 2017 - ... конфигурации (символ, на который указывает головка МТ и состояние МТ). Значит, МТ зациклится.
Решение исходной задачи: модернизируем универсальную МТ так, что она моделирует работу М в пределах зоны ...2 КБ (6 слов) - 13:24, 13 мая 2017 - #перенаправление [[Временная и пространственная сложность алгоритмов/Машина Тьюринга. Количество./ Решение Шульц]]210 байт (0 слов) - 15:50, 15 мая 2019
- #перенаправление [[Временная и пространственная сложность алгоритмов/Машина Тьюринга. Количество./Решение Александрова]]223 байт (0 слов) - 15:50, 15 мая 2019
- #перенаправление [[Временная и пространственная сложность алгоритмов/Машина Тьюринга. Количество./Решение Дербышев]]215 байт (0 слов) - 15:50, 15 мая 2019
- #перенаправление [[Временная и пространственная сложность алгоритмов/Машина Тьюринга. Количество./Решение Назарова Владимира]]234 байт (0 слов) - 15:50, 15 мая 2019
- #перенаправление [[Временная и пространственная сложность алгоритмов/Машина Тьюринга. Количество./Решение Ракутин]]213 байт (0 слов) - 15:50, 15 мая 2019
- ... desc
output=template
template=IncludeCardSolved
redirect=no
category=OptimizationProblems
category=Solved
ignore=Permission denied
ignore=Решенные бизнес задачи
silent=true
</templatedpagelist>302 байт (27 слов) - 12:29, 1 декабря 2022 
Файл:Решение задачи 1 2023-05-19 14-36-33 image0.png [[Category:Про]](480 × 300 (44 КБ)) - 11:36, 19 мая 2023- ==Идея==
Рассмотрим входную [[2SAT]]-формулу.
Во-первых, ясно, что можно быстро исключить все дизъюнкции, состоящие из одного терма — если это дизъюнкция типа <m>x_i</m>, то для выполнимости формулы ...61 КБ (3508 слов) - 09:55, 4 августа 2008 - Будем считать, что параметр <latex>k < n</latex>. По условию раунд выигрывает тот игрок, который выкинул орла. Считаем, что в раунде , если оба выкинули орла, то оба игрока выиграли в раунде.
Сначала ...2 КБ (99 слов) - 20:50, 20 мая 2020 - <math>\xi</math> - число “орлов” в серии из n испытаний Бернулли.
*<math>\xi\sim B \left(\ n, p \right)</math>
где <math>n=10, p=\frac{1}{2}</math>
a)
<math>P\left(\xi=k\right)=C_n^kp^k\left(1-p\ ...2 КБ (165 слов) - 20:50, 20 мая 2020 - 0 байт (0 слов) - 11:29, 18 декабря 2012
- <latex>
dfsdfsd
dfsdf
по-русски.
</latex>
Что-то пишем по русски
и формулы <m>$\frac12$</m>
*
*
*
[[File:Описание задачи.png]]180 байт (11 слов) - 14:45, 19 декабря 2012 
Файл:Решения задач Юрием Маркиным, 2011-12-07.pdf (595 × 841 (17 КБ)) - 03:26, 11 апреля 2013- Понятно, что можно пользоваться упрощенным определением вероятности: отношение успешных исходов к общему числу исходов.
1) Общее число исходов - число сочетаний из 52 по 2 и равно
<m>\ C_{52}^2</m>. ...2 КБ (67 слов) - 17:51, 30 июня 2013 - 1)Вероятность, что на первой кости выпадет что-то равна 1/6, вероятность того, что на второй кости выпадет то же самое равна 1/6, итого 1/36.
Всего на кубике 6 чисел, поэтому исходная вероятность ...1 КБ (1 слово) - 21:46, 30 июня 2013 -
Посчитаем сначала, сколькими способами проигравший мог выиграть ровно k раундов.
Известно, выигравший выиграл n раундов, и игра закончилась.
Значит, считая каждый из k выигрышей проигравшего ...2 КБ (74 слова) - 20:50, 20 мая 2020 - Алиса выбирает из двух кубиков в зависимости от выбора Боба и тем самым влияет на вероятность своей победы. <br/>
Если Боб выберет А, то Алисе надо выбирать В, так как вероятность ее выигрыша будет ...2 КБ (73 слова) - 20:50, 20 мая 2020 - #перенаправление [[Временная и пространственная сложность алгоритмов/Задачи/PSPACE in EXPTIME/Бойко Дмитрий, 175.]]193 байт (3 слова) - 23:30, 29 мая 2014
- Выберем произвольное ребро. Получим путь длины 1.
Покажем как можно увеличить путь на 1.
Пусть у нас имеется путь T из k < n вершин. Пусть последняя вершина пути «b», а первая — «a». Возьмем любую ...1 КБ (53 слова) - 20:50, 20 мая 2020 - '''Выпадут два одинаковых результата.'''
Рассмотрим все возможные исходы, удовлетворяющие условию и получим:
<math>P = \frac{6}{6^2}</math>
'''Число на первой кости больше, чем на второй.'''
...1 КБ (32 слова) - 14:56, 2 ноября 2016 - Не решено.
Странно. Если верный ответ 1, то
алгоритм который с вероятностью 3/4 отвечает 1, а иначе отвечает 1+e
или
алгоритм который с вероятностью 3/4 отвечает 1+e, а иначе отвечает 1+100e
...1 КБ (86 слов) - 12:59, 6 декабря 2016 - <latex>
\begin{itemize}
\item{Очевидно, что для любого языка, разрешимого за полиномиальное время, существует МТ, который разрешает его за недетерминированное полиномиальное время.
Поэтому $P\ ...1 КБ (53 слова) - 20:22, 10 декабря 2016 - <latex>
Для пары G, H выполним следующий алгоритм:
\begin{itemize}
\item{Если в G и H разное количество вершин, отвергаем эту пару}
\item{Недетерминированно получаем какую-либо перестановку ($\pi$) n ...912 байт (33 слова) - 21:34, 10 декабря 2016 - <latex>
Пусть $L$ - унарный NP-полный язык. Следовательно $SAT \leq_{p} L$L$. Пусть $A$ - соответствующая сводимость, работающая за время $p(n)$.
Приведем алгоритм, который решает SAT за ...0 вхождений (0 подкатегорий, 0 файлов) - 16:15, 14 декабря 2016 - <latex>
Пусть $L$ - унарный NP-полный язык. Следовательно $SAT \leq_{p} L$L$. Пусть $A$ - соответствующая сводимость, работающая за время $p(n)$.
Приведем алгоритм, который решает SAT за ...4 КБ (149 слов) - 18:34, 14 декабря 2016 
Файл:Решение на бумаге.png (960 × 480 (209 КБ)) - 20:15, 26 января 2017
Файл:Решение с вики-разметкой и кодом.png (913 × 627 (120 КБ)) - 20:23, 26 января 2017
Файл:Решение с LaTeX-разметкой.png (960 × 780 (421 КБ)) - 20:48, 26 января 2017- *[[Сильно связный граф NL-complete]]
Обозначим этот язык за M. проверим, что он в NL: Для этого нужно перебрать все пары вершин a, b (их хранение на рабочей ленте займет не более log(n)) памяти, где ...3 КБ (74 слова) - 23:53, 10 мая 2017 - *[[X-O в PSPACE]]
На рабочей ленте для каждой клетки игровой доски заведем свою ячейку. Используем рекурсивный алгоритм - ставим крестик/нолик и проверяем уже новый экземпляр на выигрышность. Позиция ...1 КБ (4 слова) - 00:53, 11 мая 2017 - в одной из задач было показано, что PH содержится в PSPACE. покажем, что это если PH = PSPACE, то полиномиальная иерархия схлопывается.
от противного. тогда PH = PSPACE. Известно, что в PSPACE есть ...994 байт (16 слов) - 13:22, 13 мая 2017 
Файл:Решение Кожевникова Романа 2019-04-16 18-46-08 image0.png (775 × 627 (155 КБ)) - 15:46, 16 апреля 2019
Файл:01 решение задачи SCCP методом улучшенной Лагранжевой релаксации 2017.pdf (При чтении оригинала учесть, что Cast -- заказ, состоит из нескольких плавок, Charge -- плавка, Job = Charge)
#Постановка.
Имеются некоторые заказы. Каждый заказ состоит из нескольких плавок.
...(595 × 793 (1 МБ)) - 16:10, 22 января 2023- ... новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами).
Этих ...15 КБ (513 слов) - 18:34, 30 марта 2024 
Файл:The-number-of-beautiful-subsets 2023-12-21 14-01-42 image0.png [[Category:На_проверку]] [[Category:Проблемы_в_решении]](524 × 182 (18 КБ)) - 11:01, 21 декабря 2023
Файл:Minimum Test Collection 2023-12-21 14-52-00 image0.png [[Category:На_проверку]] [[Category:Проблемы_в_решении]](1802 × 733 (70 КБ)) - 11:52, 21 декабря 2023- ... 22 €/день или увеличить каждую из существующих служб на два врача.
Определите, какое решение принять, с целью максимизации общего количества принятых пациентов.
{{reserve-task|[[Участник:Сергей ...2 КБ (20 слов) - 10:59, 27 декабря 2023 - ... типа C1
и 0,2 евро за кг для конфет типа C2.
Получите эффективные решения, которое
* максимизирует еженедельную выручку
* минимизирует количество сахара, используемого в неделю.
* минимизирует ...2 КБ (29 слов) - 17:51, 23 декабря 2023 - ... первого подхода к этому рынку и опасаясь потерять текущую клиентскую базу, руководство компании приняло решение ежедневно направлять не менее 75% общего объема производства на рынок «оригинального ...3 КБ (19 слов) - 22:21, 23 декабря 2023
Файл:Noncoprimes 2023-11-13 12-15-59 image0.png [[Category:На_проверку]] [[Category:Проблемы_в_решении]](1702 × 810 (151 КБ)) - 09:16, 13 ноября 2023- <!-- Probability and Computing -->
{{eupce-2-7}}
E[X | X ≤ Y] = ?
[[Категория:Теоретические задачи]]
[[Категория:Решенные задачи]]186 байт (11 слов) - 06:49, 18 декабря 2023 - ... случайным образом,
** подбрасываем ее
** выпала решка.
Какова вероятность, что мы выбрали фальшивую монету?
* [[Участник:Sanya/Решение задачи про монетки]]
[[Категория:Теоретические задачи]]674 байт (9 слов) - 06:41, 18 декабря 2023 - ... , если участник сменит выбранную на первом шаге коробку, увеличит ли это его шансы?
* [[Участник:Sanya/Решение Парадокс Монти Холла]]
[[Категория:Теоретические задачи]]1 КБ (9 слов) - 12:00, 15 декабря 2023 - ... (это может быть очень головоломно).
* Можно сделать и больше, такой же блок, может заменить решение задачи из [[Моделирование бизнес-задач]], если те почему-то не понравились.
* Может можно будет ...9 КБ (261 слово) - 15:10, 11 апреля 2024 - ... с одной стороны, а с другой, чтобы потери для торговой сети были минимальными.
Очевидно, что существует тривиальное допустимое решение~--- округлить цены всех товаров, но требуется найти именно ...2 КБ (10 слов) - 06:50, 4 мая 2023 - ... состоит не более чем из <m>|E|</m> ребер,
то данный алгоритм гарантированно даст 2-приближенное решение задачи MAX-CUT).
Разрезом называется разбиение <m>V</m> на два непересекающихся подмножества ...1 КБ (53 слова) - 06:50, 4 мая 2023 - ... алгоритма «alg-derand-max-sat» (кроме решения линейной релаксации) будет $O(mn)$.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]470 байт (10 слов) - 06:50, 4 мая 2023 - Есть оптимизационный алгоритм <tt>A</tt>, который для входа <tt>x</tt> находит оптимальное решение с вероятностью <tt>1/|x|</tt>.
Как сделать из него максимально эффективный алгоритм <tt>B</tt>, ...565 байт (24 слова) - 06:50, 4 мая 2023 - ... дешевые ребра к еще непосещенным вершинам, не гарантирует нахождение оптимального решения.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]625 байт (3 слова) - 06:50, 4 мая 2023 - ...
<latex>
\min l_j > OPT(x)/3
</latex>
этот алгоритм находит оптимальное решение.
(OPT(x) — значение этого оптимального решения).
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]861 байт (21 слово) - 06:50, 4 мая 2023 - ... оставшиеся вершины, к множеству, с которым у этой вершины меньше ребер-связей.
Прав ли студент?
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]673 байт (6 слов) - 06:50, 4 мая 2023 - ... ) паросочетания минимального размера.
Сложность алгоритма не больше $O( (n+m)^2 )$.
</latex>
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]507 байт (9 слов) - 06:50, 4 мая 2023 - ... совместной подсистемы системы линейных булевых уравнений (сложения и умножения по модулю 2).
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]586 байт (6 слов) - 06:50, 4 мая 2023 - ... - к разорению…
Обоснуйте.
Подсчитайте матожидание выигрыша для каждой из стратегий.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]3 КБ (23 слова) - 06:50, 4 мая 2023 - ... вероятности не больше ½
для проверки этой матрицы на вырожденность ($\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 - ... мультипликативной ошибки жадного алгоритма для задачи покрытия множеств достигается
по порядку.
<!--Вообще-то, решения уже есть-->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]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 - ... ]].
Придумайте приближенный алгоритм, основанный на линейной релаксации задачи линейного программирования, который находит
P-оптимальное решение, где <m>P=\max_i\sum_ja_{ij}</m>
[[Категория ...506 байт (16 слов) - 06:50, 4 мая 2023
Просмотреть (предыдущие 250 | следующие 250) (20 | 50 | 100 | 250 | 500)