Результаты поиска
Материал из DISCOPAL
Показаны 1-500 из 531 результатов запроса Решение, выполненного за 0.001 секунд. Статистика:
- решен найдено 6178 раз в 2217 документах
Файл:Эксперимент — улучшаем старые решения 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 
Файл:Minimum Test Collection 2023-12-21 14-52-00 image0.png [[Category:На_проверку]] [[Category:Проблемы_в_решении]](1802 × 733 (70 КБ)) - 11:52, 21 декабря 2023
Файл:The-number-of-beautiful-subsets 2023-12-21 14-01-42 image0.png [[Category:На_проверку]] [[Category:Проблемы_в_решении]](524 × 182 (18 КБ)) - 11:01, 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 - ... -03-01-p116 -->
Опишите алгоритм локального поиска для MAX-SAT, покажите, что он находит решение не хуже половины от оптимума.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]342 байт (6 слов) - 06:50, 4 мая 2023 - ... алгоритм [[Greedy algorithm for SAT]] находит 2-приближенное решение для MAX SAT (т.е. не хуже оптимального больше чем в два раза).
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]378 байт (12 слов) - 06:50, 4 мая 2023 - <latex>
Доказать, что следующая проблема принятия решения NP-полная. Пусть есть $n$ рыцарей, и множество пар рыцарей, являющихся врагами. Возможно ли рассадить (расположить) рыцарей у ...557 байт (5 слов) - 06:50, 4 мая 2023 - ... дизъюнкций)
\item где функция $g_i: \{0,1\}^3 \rightarrow \{0,1\}$
\item y_{i,j} \in \{x_1, \ldots, x_m\}
\end{itemize}
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]570 байт (38 слов) - 12:14, 26 декабря 2023 
Файл:Find-all-people-with-secret 2022-12-21 19-56-58 image0.png [[Category:Проблемы_в_решении]](429 × 130 (9 КБ)) - 18:37, 1 марта 2023
Файл:Планирование задач с приоритетом и временами перенастройки 2022-12-23 04-08-31 image0.png [[Category:Возможно_ошибка]] [[Category:Проблемы_в_решении]](368 × 405 (40 КБ)) - 18:37, 1 марта 2023
Файл:Планирование задач с приоритетом и временами перенастройки 2022-12-23 04-09-02 image0.png [[Category:Возможно_ошибка]] [[Category:Проблемы_в_решении]](438 × 483 (37 КБ)) - 18:37, 1 марта 2023
Файл:Планирование задач с приоритетом и временами перенастройки 2022-12-23 04-11-15 image0.png [[Category:Возможно_ошибка]] [[Category:Проблемы_в_решении]](927 × 655 (195 КБ)) - 18:37, 1 марта 2023
Файл:Планирование задач с приоритетом и временами перенастройки 2022-12-23 04-17-24 image0.png [[Category:Возможно_ошибка]] [[Category:Проблемы_в_решении]](1271 × 745 (1,22 МБ)) - 18:37, 1 марта 2023- ... зарождения ребра — ½.
;Hint: Сначала надо правильно решить [[MAX-CUT: вероятностное округление/Задачи/Матожидание разреза]].
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]589 байт (8 слов) - 06:50, 4 мая 2023 - ... ($p=1/2$) приписать к~множеству $T$ или $S$.
Докажите, что этот вероятностный алгоритм является $0.5$-приближенным.
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]582 байт (6 слов) - 06:50, 4 мая 2023 - ... 3--5
}
</neato>
----
Доказать, что вероятностный алгоритм вычисляет минимальный разрез с вероятностью <m>P \ge \frac{2}{n(n-1)}</m>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]2 КБ (92 слова) - 06:50, 4 мая 2023 - ... формулу матожидания средней величины разреза по всем таким случайным графам из <tt>n</tt>-вершин.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]499 байт (7 слов) - 06:50, 4 мая 2023 - ... «MAX-SAT», только в КНФ в каждой скобке ровно три литерала.
Предложите вероятностный алгоритм с точностью <m>\frac{7}{8}</m>.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]382 байт (6 слов) - 06:50, 4 мая 2023 - ... ), для которой на любом наборе переменных выполнено не более половины скобок.
* А менее половины скобок?
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]515 байт (1 слово) - 06:50, 4 мая 2023 - ... путем дерандомизации построения
<m>\frac{3}{4}</m>-приближенного детерминированного полиномиального алгоритма для задачи MAX-SAT?
[[Category:Решенные задачи]]
[[Категория:Теоретические задачи]]366 байт (6 слов) - 06:50, 4 мая 2023 - ... алгоритм для задачи о коммивояжере на полном графе с положительными весами, где f любая функция, то P=NP.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]417 байт (6 слов) - 06:50, 4 мая 2023 - ... для времени работы $T_M(x)$ машины M выполняется:
\[
\mathrm{E} T_M(x) \leq p(|x|).
\]
Докажите, что $ZPP_{NotNull}=ZPP$.
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]617 байт (24 слова) - 06:50, 4 мая 2023 - ... <m>n</m> вероятность события <m>A(f_n(x))=x</m> меньше (случайно взятый <m>x</m> длины <m>n</m> и случайное бросание алгоритма).
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]769 байт (26 слов) - 06:50, 4 мая 2023 - ... первой кости Бобу.
Покажите, что несмотря на это «благородство», что вероятность выигрыша Алисы больше ½.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]1 КБ (3 слова) - 06:50, 4 мая 2023 - ... выиграет <tt>n</tt>-раз.
Какова вероятность, что проигравший к концу игры выиграет <tt>k</tt>-раундов?
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]519 байт (9 слов) - 06:50, 4 мая 2023 - ... >0<i<6</tt>, <tt>i</tt>-й и <tt>11-i</tt>-й броски будут одинаковы.
* Будет выброшено подряд четыре «орла».
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]551 байт (11 слов) - 06:50, 4 мая 2023 - ... некоторое число <m>\kappa</m> экспериментов и взяв среднее значение. Оценить сверху <m>\kappa</m> как функцию от <m>\delta</m>.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]665 байт (20 слов) - 06:50, 4 мая 2023 - ... <tt>n</tt>-ходов, число существ типа A будет равновероятно распределено между <tt>1</tt> и <tt>n+1</tt>.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]706 байт (14 слов) - 06:50, 4 мая 2023 - ... , чем на второй.
* Сумма обоих результатов — четная.
* Произведение результатов — квадрат какого-то целого числа.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]685 байт (1 слово) - 06:50, 4 мая 2023 - Придумайте входные наборы для алгоритма Немхаузера-Ульмана, на которых он будет работать экспоненциальное время.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]326 байт (1 слово) - 06:50, 4 мая 2023 - ... алгоритм построения дерева ключей, минимизирующего суммарную стоимость доступа ко всем элементам (частоты доступа $p_i$).
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]856 байт (17 слов) - 06:50, 4 мая 2023 - Предложите детерминированный приближенный алгоритм для [[Minimum Hitting Set]] и оцените его точность.
{{needjupyternotebook}}
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]313 байт (4 слова) - 06:50, 4 мая 2023 - ... образующих цикл, в ориентированном подграфе.
И сделайте это за линейное время от размера графа.
</latex>
{{Needjupyternotebook}}
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]522 байт (4 слова) - 06:50, 4 мая 2023 - ... ,
когда известно, что в исходных данных, каждый элемент покрывается не более, чем <tt>k</tt> подмножествами.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]446 байт (7 слов) - 06:50, 4 мая 2023 - ... асимптотическую оценку $\sim \log {_2} n$ для чисел вида $n=2^k+2^{k-1}+2^{k-2}+\ldots+2^{k-tk-t}$?
Для произвольных чисел?
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]733 байт (18 слов) - 06:50, 4 мая 2023 - Почему в алгоритме Люби построенное множество:
* а) является независимым
* б) максимальным по включению
[[Category:Решенные задачи]]
[[Категория:Теоретические задачи]]296 байт (1 слово) - 06:50, 4 мая 2023 - ... конечных множеств и натуральное <m>k</m>. Существует ли подсемейство, состоящее из <m>k</m> попарно непересекающихся множеств?
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]476 байт (7 слов) - 06:50, 4 мая 2023 - Покажите, что метрическая задача коммивояжера NP-полна.
[[Category:Решенные задачи]]
[[Категория:Теоретические задачи]]208 байт (2 слова) - 06:50, 4 мая 2023 - Придумайте пример, входной метрический граф, на котором алгоритм Кристофидеса дает наихудшую точность, т.е. 3/2.
[[Category:Решенные задачи]]
[[Категория:Теоретические задачи]]310 байт (1 слово) - 06:50, 4 мая 2023 - <latex>
Почему множество всех вершин нечетной степени в остовном дереве $T$ четно?
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]268 байт (3 слова) - 06:50, 4 мая 2023 - ... связный ненаправленный граф с ребрами попарно различной длины имеет только одно минимальное остовное дерево.
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]362 байт (2 слова) - 06:50, 4 мая 2023 - ... выписывает одну за
другой все машины Тьюринга, которые останавливаются, будучи
запущенными на пустой ленте?
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]374 байт (0 слов) - 06:50, 4 мая 2023 - Докажите
<m>
NP \cup coNP \subseteq P^{NP}
</m>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]172 байт (8 слов) - 06:50, 4 мая 2023 - Докажите <m>P^{SAT}=P^{NP}</m>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]155 байт (6 слов) - 06:50, 4 мая 2023 - Докажите
<m>NP^{SAT}=\Sigma^p_2</m>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]160 байт (6 слов) - 06:50, 4 мая 2023 - ... любого натурального $k, \ k \geq 0$, верно соотношение
$$
L \in \Sigma^p_k \ \iff \ \{0,1\}^*\setminus L \in \Pi^p_k \ .
$$
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]324 байт (17 слов) - 06:47, 18 декабря 2023 - Докажите, что
<m>PH\subseteq PSPACE</m>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]168 байт (5 слов) - 06:50, 4 мая 2023 - ... $ существует полный язык относительно полиномиальной сводимости по Карпу,
то для некоторого $k$ $\Sigma^p_k=PH$.
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]340 байт (8 слов) - 06:50, 4 мая 2023 - Показать, что <m>P/poly</m> содержит некоторые невычислимые функции.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]232 байт (4 слова) - 06:50, 4 мая 2023 - ... не выиграет определенную сумму <math>n \geq k</math>. Какова вероятность, что игрок проиграет все деньги?
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]670 байт (6 слов) - 06:50, 4 мая 2023 - ... с номерами $n$ и $f(n)$ на одном и том же входе либо дают одинаковый ответ, либо оба зацикливаются.
</latex>
[[Category:Решенные задачи]]
[[Категория:Теоретические задачи]]536 байт (8 слов) - 06:50, 4 мая 2023 - Докажите корректность алгоритма Прима построения минимального остовного дерева взвешенного связного неориентированного графа.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]355 байт (0 слов) - 06:50, 4 мая 2023 - Доказать, что NP ≠ coNP, если P ≠ NP
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]172 байт (4 слова) - 06:50, 4 мая 2023 - ... каждому отрезку принадлежит хотя бы она точка. Предложить эффективный жадный алгоритм, оценить сложность.
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]551 байт (3 слова) - 06:50, 4 мая 2023 - ... Sigma =\{a_0,...,a_n\}$, есть множество состояний $S=\{s_0,...,s_m\}$. Сколько существует машин Тьюринга для данных множеств?
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]365 байт (10 слов) - 06:50, 4 мая 2023 - ... на x за конечное число шагов.
Является ли HALT:
* NP-полным
* NP-трудным
* PSPACE-полным
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]383 байт (10 слов) - 06:50, 4 мая 2023 - ... [[3SAT]] и [[TAUTOLOGY]] полиномиально сводятся к друг другу по Карпу, то
[[NP]] = [[CoNP]].
<!-- P1401 -->
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]301 байт (7 слов) - 06:50, 4 мая 2023 - ... нулей.
Покажите, что если существует один из таких языков <m>L_{0}</m>, что <m>L_{0} \in NPC</m>,
то <m>P=NP</m>.
[[Категория:Решенные задачи]]
[[Категория:P1401]]
[[Категория:Теоретические задачи]]456 байт (14 слов) - 06:50, 4 мая 2023 - ... из таких 3КНФ, которые
* выполнимы
* и в этом выполняющем наборе, в каждой скобке ровно один истинный литерал.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]429 байт (2 слова) - 06:56, 4 мая 2023 - ... -программу, которая по входу (a,b), где a,b > 1, вычисляет a<sup>b</sup>. Время работы программы должно быть ''О''(log ''b'')
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]516 байт (15 слов) - 06:50, 4 мая 2023 - ... сфере плотностью бросают $N$~точек.
Найти медиану расстояния от центра сферы до ближайшей точки.
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]505 байт (4 слова) - 06:50, 4 мая 2023 - ... . Является ли разрешимой их конкатенация? То есть $L_1L_2 = \{ab \;|\; a \in L_1, b \in L_2\}$
\newline\newline
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]344 байт (16 слов) - 06:50, 4 мая 2023 - ... mod\, d\,\}\, \text{принадлежит}\,P
2. Укажите два слова, принадлежащие языку, и два слова, не принадлежащие языку.
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]453 байт (16 слов) - 06:50, 4 мая 2023 - ... или матрицей смежности)}.
Покажите, что L_{planar} ∈co−NP .
Подсказка: посмотри Th. Понтрягина — Куратовского
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]499 байт (11 слов) - 06:50, 4 мая 2023 - ... определить, что граф гамильтонов, но и найти в нем какой-нибудь гамильтонов цикл (если он существует).
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]463 байт (2 слова) - 06:50, 4 мая 2023 - ... . Удивительным кажется то, что для этой задачи построен
детерминированный o( $n^2$ )-алгоритм. Он очень хитрый.
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]1 КБ (9 слов) - 06:50, 4 мая 2023 - ... >
Пусть $L_1,L_2 \in P$. Принадлежит ли $P$ их конкатенация? То есть $L_1L_2 = \{ab \;|\; a \in L_1, b \in L_2\} \in P$?
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]290 байт (18 слов) - 06:50, 4 мая 2023 - ... одна ниточка, а суммарная длина всех ниточек была минимальна.
Построить полиномиальный от N алгоритм решающий задачу.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]687 байт (2 слова) - 06:50, 4 мая 2023 - ... на ленте не считается.
(можно представить многоленточную машину, в которой первая лента не считается).
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]465 байт (8 слов) - 06:50, 4 мая 2023 - ... ) ''first fit'' и ''best fit''.
Найдите примеры входных данных, когда first fit лучше best fit.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]425 байт (24 слова) - 06:50, 4 мая 2023 - ... в один из m, контейнеров, выкидываем этот предмет.
Докажите, что этот алгоритм упакует как минимум n/2 предметов.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]1 КБ (25 слов) - 06:50, 4 мая 2023 - ... {itemize}
\item $\chi(G)$ --- хроматическое число графа $G$,
\item $G^c$ --- дополнение графа $G$.
\end{itemize}
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]447 байт (30 слов) - 06:50, 4 мая 2023 - ... для его раскраски (раскраска графа --- чтобы смежные вершины не были одного цвета).
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]494 байт (9 слов) - 06:50, 4 мая 2023 - ... в три цвета граф из ''n'' вершин, для которого алгоритм [[Smallest Last]] будет использовать <m>\Omega(n)</m> цветов.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]453 байт (13 слов) - 06:50, 4 мая 2023 - ... вершин, а делить вершины надо на две одинаковые команды.
Придумайте полиномиальный алгоритм для этой задачи.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]496 байт (6 слов) - 06:50, 4 мая 2023 - ... ''k''-оптимальный полиномиальный алгоритм.
;Hint: [[Minimum Hitting Set]] является обобщением минимального вершинного покрытия.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]530 байт (15 слов) - 06:50, 4 мая 2023 - ... -ex-02-19-p99 -->
Придумайте алгоритм динамического программирования для [[Maximum Integer d-dimentional Knapsack]].
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]295 байт (9 слов) - 06:50, 4 мая 2023 - ... -greedy-sat-is-2-approx]], только покажите, что 2-приближенность сохранится, если будет [[MAX-SAT-Weighted]]
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]332 байт (9 слов) - 06:50, 4 мая 2023 - ... элементов линейного пространства, на произвольное множество.} для доказательства оптимальности алгоритма?
\end{enumerate}
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]1 КБ (16 слов) - 06:50, 4 мая 2023 - ... {A}(x)=\mathcal{B}(f(x))$.
Считайте, что предикат $a \le b$ и функции $a + b$ и $a^2$ от целых чисел вычисляются за $O(1)$.
</latex>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]2 КБ (73 слова) - 06:50, 4 мая 2023 - ... «?», при том есть хотя бы один путь к «0».
Покажите, что <m>L \in NP \cap \overline{NP}</m>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]808 байт (24 слова) - 06:50, 4 мая 2023 - Покажите, что [[3ESAT]] — NP-полная задача.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]185 байт (2 слова) - 06:50, 4 мая 2023 - ... ) DLOGSPACE] ≠ P
* PSPACE ≠ P
* Заметим, что если у вас вряд ли получится доказать эти неравенства по отдельности.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]522 байт (11 слов) - 06:50, 4 мая 2023 - Покажите, что если [https://en.wikipedia.org/wiki/L_(complexity) DLOGSPACE] = P, то PSPACE = EXPTIME.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]235 байт (11 слов) - 06:50, 4 мая 2023 - ... , что если <m>L \in NP</m>, а KOD — какая-то кодировка над алфавитом L, то <m>KOD(L) \in NP</m>
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]408 байт (17 слов) - 06:50, 4 мая 2023 - K(L) — [[кодировка]].
Докажите, что класс P замкнут относительно кодировок тогда и только тогда, если P=NP.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]301 байт (5 слов) - 06:50, 4 мая 2023 - Докажите, что если каждый [[унарный язык]] из NP также лежит в P, то EXPTIME=NEXP.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]246 байт (4 слова) - 06:53, 18 декабря 2023 - ... ли
* а). перечислимым
* б). ко-перечислимым множество описаний машин Тюринга, останавливающихся на пустом входе?
Ответ обосновать.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]373 байт (1 слово) - 06:50, 4 мая 2023 - ... . Доказать, что если его слова можно лексикографически упорядочить, то <latex> L </latex> тогда является и разрешимым.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]383 байт (7 слов) - 06:50, 4 мая 2023 - ... задача отыскания раскраски графа в три цвета сводится по Куку к задаче проверки три-раскрашиваемости графа
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]447 байт (8 слов) - 06:50, 4 мая 2023 - ... SAT, для которых есть по крайней мере два выполняющих набора.
Покажите, что <m>L \in NPC</m>.
[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]312 байт (7 слов) - 06:50, 4 мая 2023 
Файл:Производство штучных изделий 2022-12-09 16-45-10 image0.png [[Category:Проблемы_в_решении]](932 × 273 (47 КБ)) - 13:45, 9 декабря 2022
Файл:Resetmtrx.png [[Category:Возможно_ошибка]] [[Category:Проблемы_в_решении]](417 × 563 (19 КБ)) - 07:28, 23 декабря 2022- {{проверено|[[Участник:StasFomin|StasFomin]] 06:51, 18 декабря 2023 (UTC)}}
<!-- Probability and Computing -->
{{eupce-2-7}}
E[max(X, Y)] = ?
[[Категория:Теоретические задачи]]231 байт (14 слов) - 06:51, 18 декабря 2023 - {{проверено|[[Участник:StasFomin|StasFomin]] 12:29, 26 декабря 2023 (UTC)}}
<!-- Probability and Computing -->
Пытаемся передать один бит (0 или 1) через «n» промежуточных узлов, каждый из которых ...614 байт (23 слова) - 12:29, 26 декабря 2023 - ...
template=IncludeCard2
redirect=no
category=Теоретические_задачи
notcategory=Solved
notcategory=Решенные_задачи
notcategory=OptimizationProblems
ignore=Permission denied
ignore=A
ignore=Open_Exercises ...421 байт (32 слова) - 23:31, 23 декабря 2023 - ... , что даже сам Голдратт, пропустил оптимальное решение.
В [http://lib.custis.ru/Toc- ... докладе Стас Фомина] была приведена модель на MathML и решение на GLPK (увы, вроде остались только слайды и видео ...3 КБ (259 слов) - 11:59, 23 декабря 2023 - ... N задач из M разных разделов.
* Либо одну бонусную задачу — считаем, что ее решение закрывает квест.
* Выбирайте задачи из [[Open Exercises]], переходите к редактированию по «Беру…»
** помечайте ...2 КБ (14 слов) - 12:15, 19 мая 2023 - ... -2023]», заведите там подпапку по вашему логину, желательно без пробелов.
* Учимся на готовых решениях коллег - [[Решенные бизнес задачи]], ну и в папке «[https://xn--17-6kce2c.xn--80apqgfe.xn--p1ai ...3 КБ (116 слов) - 16:23, 30 ноября 2023 - ... _питон._С_машинным_кодом]]
* Бонусные задачи вполне решаются, если их не боятся → вот из последних решений → [[Участник:Mishaglik/Solutions/Spoj/FRQPRIME]]
[[File:2021-10-15 Practical Block_2021-11-03 ...4 КБ (116 слов) - 04:57, 3 мая 2024 - ... новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами).
Этих ...20 КБ (494 слова) - 05:44, 3 февраля 2024 - ... ==
<graph>
digraph G{
node [shape=note]
"Нерешенные задачи" -> "Решения в подстраницах"
"Решения в подстраницах" -> "На проверку"
"Решения" [style=filled fillcolor=lightblue shape=box3d]
"На ...7 КБ (490 слов) - 22:53, 26 января 2017 - ... ==
<graph>
digraph G{
node [shape=note]
"Нерешенные задачи" -> "Решения в подстраницах"
"Решения в подстраницах" -> "На проверку"
"Решения" [style=filled fillcolor=lightblue shape=box3d]
"На ...5 КБ (306 слов) - 06:44, 9 марта 2017 - ... о рюкзаке:динамическое программирование|Алгоритмы динамического программирования для задачи]] о рюкзаке дают точное решение за время ''O(nf<sup>*</sup>)'' или ''O(nB)''. Если величины ''f<sup>*</sup ...10 КБ (509 слов) - 16:48, 23 октября 2008
- ... , что предложенная схема сотрудничества с двумя политиками лучше, чем структура DRL с одной политикой, в решении различных NP-трудных проблем маршрутизации, включая TSP, TSP с получением призов (PCTSP ...3 КБ (29 слов) - 12:23, 9 декабря 2021
- ... в его округе «j».
Надо минимизировать разницу между «Y_j», соблюдая вышеуказанные регуляции.
{{@|Не готово, проблемы с решением}}
{{enddiv}}
{{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}}21 КБ (3349 слов) - 11:59, 23 декабря 2023 - ... %D0%B8%D0%B4%D0%BA%D0%B0%D0%BC%D0%B8.ipynb?session=default Решение]
[[Участник:StasFomin|StasFomin]] 01:14, 28 ноября 2022 (UTC): Надо сделать модификацию задачи (генератор?), тут ...2 КБ (136 слов) - 11:59, 23 декабря 2023 - ... убрать красную фишку с доски. доски. В этом сценарии цель не ставится. Получение выполнимого решения будет означает, что красная фишка ушла с доски.
* Второй сценарий, как полная оптимизационная ...3 КБ (24 слова) - 11:59, 23 декабря 2023 - ... эффективные алгоритмы построения асимптотически точных покрытий и упаковок, а также асимптотически точных решений задач целочисленного программирования. Одним из его важных научных достижений является ...9 КБ (35 слов) - 13:40, 11 февраля 2020
- ... как в едином гибридном генетическом поиске (UHGS) приводит к значительным повышение точности решения. Находятся новые лучшие решения для на удивление небольшие экземпляры всего с 256 клиентами. Эти ...3 КБ (20 слов) - 22:12, 9 декабря 2021
- ... случая без нарушений, в то время как в случае с нарушениями,
мы можем скорректировать решение с помощью простого алгоритма восстановления, который в нашем случае заключается в удалении элементов из ...3 КБ (24 слова) - 15:07, 23 ноября 2021 - Arxiv/Vehicle Routing Problem with Time Windows — A Deterministic Annealing approach 2016 1604.03590... с помощью настраиваемого параметра, что позволяет нам генерировать качественно хорошие решения.
Эти решения различаются степенью пересечения маршрутов, обоснование пунктов передачи, в которых можно ...2 КБ (24 слова) - 12:55, 9 декабря 2021 - ... . Правило оценки (GSA) для DS-VRPTW, и мы сравниваем его с существующими правила принятия решений, такие как MSA. В частности, мы показываем, что GSA полностью интегрирует ограничения непредвиденности ...2 КБ (24 слова) - 17:40, 9 декабря 2021
- ... Routing Problems 2021 2109.08345|
Подходы глубокого обучения показали многообещающие результаты в решении проблем маршрутизации. проблемы. Однако по-прежнему существует значительный разрыв в качестве ...3 КБ (22 слова) - 20:25, 9 декабря 2021 - ... поверхность значений) над пространство поиска; затем эта сеть ценностей используется для проверки решений, чтобы помочь агент оптимизации черного ящика для инициализации или перезапуска для навигации ...2 КБ (17 слов) - 21:35, 9 декабря 2021
- ... глубокую архитектуру, основанную на самовнимании, как сеть политик для руководства выбором следующего решения. Мы применяем наш метод к две важные проблемы маршрутизации, то есть проблема коммивояжера ...2 КБ (14 слов) - 21:56, 9 декабря 2021
- ... /advalg-2022-homeworks/?session=default advalg-2022-homeworks]»
* Учимся на готовых решениях коллег в соседних папках и решениях прошлых лет → [https://discopal-lab.0x1.tv/projects/3b41be68-a970-4f60 ...4 КБ (121 слово) - 12:05, 9 декабря 2022 - ... этой задачи, с ростом размера входных данных. Отсутствие же алгоритма субэкспоненциальной сложности для точного решения этой задачи следует из того, что эта задача является NP-полной, и общепринятой ...6 КБ (326 слов) - 17:52, 30 ноября 2011
- ... [student]: но разным весом, но оба допустимых
[13:46:25] Фаворская Алена [student]: оба равноценные решения?
[13:46:25] Суворикова Александра [student]: вот, это то о чем я говорила же
[13:46:38 ...16 КБ (250 слов) - 18:34, 17 октября 2011 - ... /~gohlke/pythonlibs/#cvxopt
* Придется вкурить документацию к CVXOPT (крутой оптимизационный пакет, очень полезно).
Собственно решение релаксации будет давать верхнюю оценку для MAX-CUT.
<blockquote ...893 байт (25 слов) - 07:38, 30 мая 2012 - ... -12-16_16-54-15_image0.png||400px]]
** Иногда это может быть сложно — понять длинное решение на C или Rust
*** Но в целом, полезный навык
*** по 2 балла за задачу
*** Таких много, несколько десятков ...1 КБ (55 слов) - 15:40, 16 декабря 2020 - ... «поиска кукушки» (CS) с улучшенным алгоритмом «перетасованного лягушачьего прыжка» (ISFLA) для решения
0-1 ранцевой задачи. Прежде всего, в рамках SFLA разработан улучшенный оператор «прыжка лягушки ...2 КБ (33 слова) - 06:38, 17 марта 2022 - ... длительного или общего времени в пути транспортного средства (транспортных средств) во флоте. Для решения этих проблем мы предлагаем метод DRL, основанный на механизм внимания с декодером выбора ...3 КБ (26 слов) - 20:09, 9 декабря 2021
- ... улучшения VRP, потому что его метод позиционного кодирования (PE) не подходит для представления решений VRP. В этой статье представлен новый Dual-Aspect Collaborative Transformer (DACT) для изучения ...2 КБ (35 слов) - 20:23, 9 декабря 2021
- ... 2021 2105.02730|
Для NP-сложных задач комбинаторной оптимизации обычно сложно находить качественные решения за полиномиальное время. Дизайн либо точный алгоритм или приближенный алгоритм для этих ...3 КБ (24 слова) - 20:58, 9 декабря 2021 - ... которые в основном вращаются вокруг использование различных эвристик. Глубокое обучение может предоставить решения, которые менее затратный по времени и более качественный в больших масштабах, как это ...2 КБ (14 слов) - 21:31, 9 декабря 2021
- ... %D1%80%D1%83%D0%BA%D1%82%D0%BE%D0%B2.ipynb?session=default Решение]
{{enddiv}}
{{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}}2 КБ (69 слов) - 11:59, 23 декабря 2023 - ... :GeraskinDA/Капитальные инвестиции]]
* [[Blog:Advanced_Algorithms/2022-11-27_Разбор_задачи_«Капитальные_инвестиции»_и_решения_студента]]
{{enddiv}}
{{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}}2 КБ (55 слов) - 11:59, 23 декабря 2023 - ... * [[Blog:Advanced_Algorithms/Хорошие_практики_компактных_Pyomo-формулировок_на_примере_решения_«Задачи_о_станках»]]
* [[Участник:Cherniavskii/BusinessProblems/Покупка_станков]]
{{enddiv}}
{{Cat4Term2 ...1 КБ (40 слов) - 11:59, 23 декабря 2023 - ... .tv/projects/3b41be68-a970-4f60-9138-1aa73f8ee1fa/files/advalg-2022-homeworks/Cherniavskii/business_problem_1.ipynb Решение]
{{enddiv}}
{{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}}2 КБ (51 слово) - 11:59, 23 декабря 2023 - ... через
** PySAT
** Показанное сведение 3SAT → задача → Pyomo → ЦЛП-солвер.
** Сверять
*** если PySAT не нашел решения — то и вы не должны)
*** если нашел — то и у вас должно быть корректное ...946 байт (9 слов) - 12:30, 24 апреля 2023 - {{проверено|[[Участник:StasFomin|StasFomin]] 07:49, 24 мая 2023 (UTC)}}
<!-- Probability and Computing -->
Предположим, мы бросаем честный k-сторонний кубик с числами 1 через K на гранях.
Если x — ...436 байт (13 слов) - 07:49, 24 мая 2023 - {{проверено|[[Участник:StasFomin|StasFomin]] 07:51, 24 мая 2023 (UTC)}}
<!-- Probability and Computing -->
Мы берем карты равномерно случайным образом с из колоды из n карт, выбранную карту добавляют ...821 байт (11 слов) - 07:51, 24 мая 2023 - {{проверено|[[Участник:StasFomin|StasFomin]] 07:50, 24 мая 2023 (UTC)}}
Покажите, что в графе с n вершинами и m ребрами, существует разрез, размера как минимум mn/(2n-1).
[[Категория:Теоретические ...323 байт (7 слов) - 07:50, 24 мая 2023 - {{проверено|[[Участник:StasFomin|StasFomin]] 09:42, 21 мая 2023 (UTC)}}
<!-- Probability and Computing -->
В графе может быть несколько одинаково минимальных разрезов.
Покажите, что их не больше n(n ...367 байт (10 слов) - 09:43, 21 мая 2023 - {{проверено|[[Участник:StasFomin|StasFomin]] 09:45, 21 мая 2023 (UTC)}}
<!-- Probability and Computing -->
Обезьяна печатает на клавиатуре из 26 букв, которая содержит только строчные латинские буквы ...590 байт (9 слов) - 09:45, 21 мая 2023 - {{проверено|[[Участник:StasFomin|StasFomin]] 09:48, 21 мая 2023 (UTC)}}
<!-- Probability and Computing -->
Предположим, что Алиса и Боб решили продолжать заводить детей, пока у них не родится девочка ...533 байт (8 слов) - 09:48, 21 мая 2023 - Бонусная задача, решение ее закрывает квест по теоретическим задачам.128 байт (0 слов) - 15:24, 18 мая 2023
- ... на вес), и набивать рюкзак наиболее «удельно дорогими» предметами, пока они влезают. Пусть стоимость этого решения ''C<sub>greedy</sub>''
* В зависимости от того, что больше, ''C<sub>max</sub>'' или ...3 КБ (163 слова) - 09:55, 4 августа 2008 - ... новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами).
Этих ...16 КБ (531 слово) - 13:43, 18 апреля 2024 - ... большого числа) допустимых неравенств, введенных Вулси (''Wolsey''), что дает очень мощный способ решения этих проблем.
Для задачи «Min Knapsack» мы доказываем, что даже после непостоянного ...3 КБ (47 слов) - 15:32, 23 ноября 2021 - ... во временных окнах, минимизировать общее расстояние путешествовал, и предоставить быстрое решение, удовлетворив дополнительное ограничение что у каждого агента есть ограниченное количество топлива ...3 КБ (19 слов) - 12:50, 9 декабря 2021
- ... счет пропуска бесполезных деталей.
Мы покажем, как вычислить ожидаемая стоимость априорных решений в псевдополиномиальное время для этого стратегия обращения. Мы представляем новую метаэвристику под ...3 КБ (29 слов) - 12:52, 9 декабря 2021 - ... , чем точные формулы и современные технологии метаэвристика, достаточно близкая к оптимальной с точки зрения решения качество. Мы описываем эксперименты как в статическом случае (когда все покупатели ...2 КБ (26 слов) - 21:06, 9 декабря 2021
- ... через сети политик и показали многообещающие характеристики. Существующие работы сосредоточены на решении (транспортное средство) проблемы с маршрутизацией, поскольку в них есть хороший баланс между ...3 КБ (20 слов) - 21:12, 9 декабря 2021
- ... the Capacitated Vehicle Routing Problem 2020 2012.11021|
Метаэвристика широко используется для решения сложных задач оптимизации, таких как задачи маршрутизации транспортных средств (VRP), для которых ...2 КБ (31 слово) - 21:22, 9 декабря 2021 - ... широкому кругу проблем с CO. Он предназначен для использования симметрии в представлении решения CO. ПОМО использует модифицированный Алгоритм REINFORCE, который заставляет разнообразные развертывания ...3 КБ (31 слово) - 21:27, 9 декабря 2021
- ... создали проект с [http://github.com/iedmrc/binary-cws-mcs открытым исходным кодом] для решения CVRP методом Монте-Карло на основе эвристические методы.
}}
{{enddiv}}
[[Категория:ArxivArticles]]2 КБ (25 слов) - 21:44, 9 декабря 2021 - Решения в бизнес-задачах, где высоковероятно ошибка (не совпадает с решением Стаса). Но может ошибки и нет. Если «перехватить чужое решение» и найти в нем ошибку — 5 бонусных баллов.5 вхождений (0 подкатегорий, 5 файлов) - 11:37, 11 декабря 2022
- ...
redirect=no
category=Теоретические задачи
notcategory=Reserved
notcategory=Solved
notcategory=Решенные задачи
ignore=Permission denied
ignore=Открытые теоретические задачи
</templatedpagelist>369 байт (26 слов) - 06:54, 4 мая 2023 - Теоретические задачи для решения239 вхождений (0 подкатегорий, 1 файл) - 06:54, 4 мая 2023
- Решенные и нерешенные задачи, для тренировки.
Предназначены для коллаборативного решения.2 вхождения (2 подкатегории, 0 файлов) - 04:50, 26 октября 2012 - ... алгоритмов. Предложен генетический алгоритм для решения этой задачи и проведено исследование его ... новая модель программ, предназначенная для решения задач проверки эквивалентности программ и проведения ...11 КБ (95 слов) - 14:58, 21 июня 2011
- ... алгоритмов. Предложен генетический алгоритм для решения этой задачи и проведено исследование его ... новая модель программ, предназначенная для решения задач проверки эквивалентности программ и ...10 КБ (71 слово) - 19:09, 25 ноября 2010
- ... n] \ -n^2 \leq a_i \leq n^2 $ и~число~$B$.
\item Найти ответ на <<Существует ли решение в~0--1 переменных $(x_1, \ldots, x_n)$ уравнения $\sum_{i=1}^n a_i x_i=B$B$?>>.
\end{itemize}
Существует ли ...761 байт (40 слов) - 22:00, 4 октября 2020 - ... экспоненциально) длину входных данных.
Например, следующий алгоритм использует хранение наилучших частичных решений-наборов, в хэш-таблице, т. е. для каждого веса, если существует набор с таким весом ...3 КБ (127 слов) - 09:55, 4 августа 2008 - ... :48:19] Максим Р [student]: 4 снизу
[14:49:01] Фаворская Алена [student]: а здесь нет других решений
[14:49:04] Фаворская Алена [student]: или я ошибаюсь?
[14:50:34] Фаворская Алена [student]: я верю ...24 КБ (303 слова) - 18:03, 17 октября 2011 - Временная категория для статей, которых потом перенесу в [[:Категория:Решения]]
Т.е. если вы видите решение в этой категории — оно зачтено. Возможно там пометки и правки, которых вам полезно увидеть.15 вхождений (0 подкатегорий, 0 файлов) - 18:38, 15 мая 2019 - Решенные (до уровня «есть решение на Python, укладывающееся в TL») задачи.1045 вхождений (0 подкатегорий, 0 файлов) - 14:20, 28 октября 2021
- ... этой статье мы предлагаем первый эволюционный подход к повторному связыванию путей (EPR) для приближенного решения QMKP.
Этот подход сочетает в себе расширенные функции как из пути метод повторного ...2 КБ (25 слов) - 09:22, 23 ноября 2021 - ... метода дают по крайней мере 30%-ное сокращение ожидаемого разрыва между значением решения и мощностью по сравнению с базовой политикой.
<p>
Аналогичные результаты показаны для задачи о ранце.
</html ...2 КБ (25 слов) - 14:45, 23 ноября 2021 - ... результат о трудности, мы представляем алгоритм, который за полиномиальное время дает 3-аппроксимируемое решение, такое, что одно ранцевое ограничение удовлетворяется, а остальные могут быть нарушены ...3 КБ (21 слово) - 15:23, 23 ноября 2021
- ... ), что позволяет использовать более широкий класс приложений, требующих большего, чем просто решение задач минимизации.
В этой работе мы рассматриваем недавно предложенную настройку PFL с целевой ...3 КБ (29 слов) - 07:05, 24 марта 2022 - ... задачу динамической оптимизации маршрута как долгосрочную последовательную задачу принятия решений. Для решения этой проблемы предлагается структура обучения с подкреплением путем интеграции механизма ...2 КБ (17 слов) - 11:00, 9 декабря 2021
- ... алгоритм Variable Neighborhood Search Branch (VNSB) также предназначен для определение качественных решений за разумное время вычислений.
Числовой результаты, полученные на некоторых тестовых ...3 КБ (29 слов) - 13:00, 9 декабря 2021 - ... окна.
Предлагаем интеграцию нечеткой и муравьиной колонии. системный эволюционный алгоритм для решения проблемы с сохранением ограничения. Результаты расчетов для некоторых задач тестов, имеющих ...1 КБ (20 слов) - 19:47, 9 декабря 2021 - ... кратчайшего времени прохождения между любой парой вершин с произвольное время отправления. Для решения MPISP мы предлагаем несколько локальных операторы поиска адаптированы из классических операторов ...3 КБ (24 слова) - 19:51, 9 декабря 2021
- ... по маршрутизации. Это мотивирует нас изучать неявные предпочтения из прошлых решений и включение этих усвоенных предпочтения в процессе оптимизации. Эти предпочтения представлены в виде вероятности ...3 КБ (19 слов) - 20:31, 9 декабря 2021
- ... быстрые алгоритмы для CVRG, способные Вычислительные решения высокого качества для сотен регионов.
Наши алгоритмические решение гарантированно будет оптимальным, когда клиентские регионы ...2 КБ (20 слов) - 20:35, 9 декабря 2021 - ... ультрасовременная производительность для политики авторегрессии, которая последовательно вставьте узлы для построения решений на CVRP.
Кроме того, мы первые решить MDVRP с помощью методов машинного ...1 КБ (17 слов) - 21:02, 9 декабря 2021 - ... решить.
Мы обсуждаем новый способ решения упомянутой проблемы с использованием рекурсивного подход ... эти методы вместе, чтобы получить ближайшее решение оптимального маршрута, так как исследования и ...2 КБ (17 слов) - 06:36, 17 марта 2022 - ... интерес не только к многоцелевые модели, но также и в специализированных многоцелевых метаэвристиках для решения этих моделей. Широкий спектр методов, например NSGA-II, SPEA, IBEA, Таким образом ...3 КБ (33 слова) - 22:16, 9 декабря 2021
- ... >U'⊆ U</em> переменных которых выставили в «истину», а остальные <em>U-U'</em> соответственно выставлены в «ложь». Значение решения <em>R</em> будет
** либо <em>B</em>, если <em>F</em> ложно
** либо ...1 КБ (104 слова) - 22:05, 17 апреля 2023 - Задачи с решениями на проверке.
__NOCATEGORYCOLUMNS__48 вхождений (0 подкатегорий, 4 файла) - 18:02, 3 ноября 2021 - Надо разбираться, не осилил решение.2 вхождения (0 подкатегорий, 0 файлов) - 00:31, 13 декабря 2011
- ... статьи в этой категории — задачи, которые можно пытаться решать.
Любая активность, даже попытки решения — хорошо. После того, как задача решена, она перейдет в архив. Т.е. в некотором смысле задачи ...22 вхождения (0 подкатегорий, 0 файлов) - 13:58, 8 апреля 2020 - Задачи, предложенные студентами.
Смело создавайте здесь статьи-задачи, и подстатьи-решения.
__NOCATEGORYCOLUMNS__55 вхождений (0 подкатегорий, 0 файлов) - 10:31, 20 мая 2015 - ... дизъюнкции имеют не более чем два терма.
Эта задача полиномиально разрешима (т.е. лежит в классе [[P]]) алгоритмом [[2SAT:Решение]].
[[Category:Задачи]]
{{replicate-from-custiswiki-to-lib}}422 байт (7 слов) - 09:55, 4 августа 2008 - ... алгоритма для рассматриваемой задачи, работающего в режиме on-line и гарантирующего нахождение решения, отличающегося от оптимального не более, чем в константу раз.
В статье Н.Н. Кузюрина ...10 КБ (95 слов) - 19:15, 25 ноября 2010 
Файл:Ex-fast-power.pdf Попытка решения задачи http://discopal.ispras.ru/index.php?title=Несложно_о_сложности._Примеры_алгоритмов/Задачи/ex-fast-power(612 × 792 (65 КБ)) - 03:25, 11 апреля 2013- ... X размерности n в SeDumi
% в качестве положительно-полуопределенной
K.s = [n];
% Запуск SeDumi для решения задачи SDP
[X, Y, INFO] = sedumi(A, b, c, K);
% Преобразование столбца в матрицу
Xmatrix ...2 КБ (106 слов) - 10:05, 21 июня 2012 - ... right)^{{{2}\over{3}}}+
\left(2\,x^3+4\,x+5\right)\,\left(x^4+1\right)^{{{1}\over{3}}}
}\over{x^4+1}}
</m>
==Решение полиномов==
Нахождение нулей у полиномов от одной переменной — задача известная ...26 КБ (1478 слов) - 16:47, 23 октября 2008 - ... под ''машинами'' традиционно понимают ''single-purpose machines''), т. е. машины, созданные для решения какой-либо одной фиксированной задачи, а в терминах программиста это скорее программы).
RAM ...14 КБ (698 слов) - 16:47, 23 октября 2008 - ... »} или «веса»;
\item[{$B \in N$}]~--- {«размер рюкзака»}.
\end{description}
Cуществует ли решение уравнения:
\[
\sum_{i=1}^n a_i x_i = B, \ \ \ x_ix_i \in \{0,1\}.
\]
\end{problem}
</latex>438 байт (38 слов) - 01:18, 17 декабря 2010 - Алгоритм Дейкстры (Dijkstra) предназначен для решения задачи [[Поиск кратчайших путей в графе]].
Важным фактом, позволяющим исключить перебор, является то, что если у нас ...53 КБ (2994 слова) - 16:47, 23 октября 2008 - Алгоритм Кристофидеса предназначен для решения [[Задача коммивояжера#метрическая задача коммивояжера|метрической версии задачи о коммивояжере]].
Пусть на входе мы имеем ''m x n'' матрицу ...2 КБ (65 слов) - 16:47, 23 октября 2008 - Алгоритм Прима предназначен для решения задачи
[[Минимальное остовное дерево]].
В этом алгоритме минимальный остов строится постепенно: сначала выбирается произвольная
вершина, которая ...7 КБ (414 слов) - 16:47, 23 октября 2008 - Алгоритм Флойда-Уоршолла (Floyd-Warshall) предназначен для решения задачи
[[Поиск кратчайших путей в графе]]. В отличие от [[алгоритм Дейкстры|алгоритма Дейкстры]], он находит все кратчайшие ...8 КБ (644 слова) - 10:04, 27 марта 2009 - ... этом, чтобы выполнение алгоритма было
замедлено не больше, чем в $O(p(|x|))$ раз.
</latex>
[[Category:Задачи]]
<!--Вообще-то, решения уже есть-->570 байт (18 слов) - 01:57, 26 декабря 2013 - ... ,
* а оставшееся объявить вершинным покрытием.
Прав ли он? Докажите или опровергните.
[[Category:Проблемные задачи]]
<!--Вообще-то, решения уже есть-->568 байт (6 слов) - 17:13, 19 мая 2015 - ... . По этой причине
трудно надеяться на существование полиномиального алгоритма
ее решения.
Поэтому, можно рассматривать приближенные алгоритмы:
* [[Задача о покрытии:Жадный алгоритм]]
[[Category ...1 КБ (45 слов) - 16:48, 23 октября 2008 - ... Фомин]]
== Замечания Стаса Фомина ==
* Нужно описание проекта
* Желательно здесь
* С недружелюбием вопрос будет решен до 18.05
* Нужна ссылка на исходные данные по → я думаю, вполне можно выложить на ...1 КБ (29 слов) - 16:23, 20 мая 2012 - ... алгоритмические аспекты теории решеток и их применение в криптографии, в частности, сложность решения систем линейных диофантовых уравнений, сложность нахождения кратчайшего ненулевого вектора решетки ...7 КБ (363 слова) - 11:43, 21 марта 2023
- ... иначе организовать цилк
[22.09.2011 16:53:44] Фаворская Алена [student]: но наверное предложенное решение оптимально
[22.09.2011 16:56:39] Фаворская Алена [student]: сам
[22.09.2011 16 ...20 КБ (281 слово) - 18:23, 17 октября 2011 - ... Pavlov [student]: это пример использования
[2011-09-25 19:18:44] Kirill Pavlov [student]: где решение SAT применяется.
[2011-09-25 19:19:54] Фаворская Алена [student]: отвалились?
[2011-09-25 ...22 КБ (1075 слов) - 18:29, 17 октября 2011 - ...
[15:55:54] Alexander (Suslik) [student]: фектически мы подогнали условие таким образом, чтобы наше решение для него подошло?
[15:56:17] Фаворская Алена [student]: ну... оно ж достаточно общий случай ...9 КБ (244 слова) - 18:36, 17 октября 2011 - ... е. по всем
множествам ''T'' из ''(n-1)'' дуг, связывающим все ''n'' вершин в единую сеть.
Для решения этой задачи можно применять:
* [[алгоритм Прима]] ;
* алгоритм Краскала (Kruskal).
[[Category ...1 КБ (66 слов) - 16:48, 23 октября 2008 - ... длины, но нет циклов отрицательного веса (если такие циклы есть — то оптимального решения очевидно не существует), то можно использовать [[алгоритм Флойда-Уоршолла]].
[[Category:Задачи]]
{{replicate ...1 КБ (39 слов) - 16:48, 23 октября 2008 - Алгоритм Флойда-Уоршолла (Floyd-Warshall) предназначен для решения задачи поиска кратчайших путей в графе — ''Shortest Path Problem''. В отличие от [[Поиск кратчайших путей:алгоритм Дейкстры| ...5 КБ (331 слово) - 21:12, 20 июня 2006
- ... выполняющих наборов переменных для 3SAT задачи, равнялось бы шестикратному количеству раскрасок в три цвета.
<!--Вообще-то, решения уже есть-->
[[Категория:Проблемные задачи]]467 байт (7 слов) - 09:50, 20 декабря 2016 - ... <m>\varepsilon</m>
выступает в качестве нового параметра, и алгоритм находит
<m>\varepsilon</m>-оптимальное решение за время, ограниченное полиномом от
длины входа и величины <m>\frac{1}{\varepsilon ...745 байт (20 слов) - 16:48, 23 октября 2008 - * Собственно реализовать алгоритм вероятностного округления.
* Но требуется решение [[../Релаксация MAX-CUT]]190 байт (1 слово) - 07:37, 30 мая 2012 - ... /ru/map.php
* Сбор у комнаты 301, а там видно будет.
<!--
Дистанционная активность — замечания к слайдам и книге,
решение опубликованных задач — обязательно учитывается. -->801 байт (12 слов) - 19:10, 8 января 2011 - ... произведением, поскольку события независимы.
P.S. Но я так понимаю что задачу нужно было решить без параметра Т, потому решение наверное не то что нужно. но я старался)1 КБ (24 слова) - 08:56, 21 мая 2013 
Файл:Ex-halt-empty-tape.jpg пробное_решение_ИванМ(745 × 233 (13 КБ)) - 08:37, 10 марта 2016- ... -- cabook-ex-02-20-p100 -->
Придумайте алгоритм динамического программирования, находящий оптимальное решение задачи [[Maximum Integer k-choice Knapsack]].
[[Категория:Нерешенные задачи]]
[[Категория ...358 байт (9 слов) - 06:51, 4 мая 2023 - ... приближенные полиномиальные алгоримтмы из алгоритмов динамического программирования, ищущих точное решение.
Это обобщение процедуры скейлинга коэффициентов входной задачи, рассмотренной в разделе ...1 КБ (14 слов) - 14:59, 9 декабря 2017 - ... фокус. [[Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ)#Фокус]]
* Новые квесты → [[LeetCoding]] и [[SpojCoding]]. Можно питонизировать решенное!676 байт (30 слов) - 07:14, 11 марта 2021 - Задачи с сервиса Spoj
Возможно проблемны для решения питоном (не настроены TL) — сервис относительно заброшенный, что конечно жаль.242 вхождения (0 подкатегорий, 0 файлов) - 14:17, 28 октября 2021
Просмотреть (предыдущие 500 | следующие 500) (20 | 50 | 100 | 250 | 500)