Результаты поиска
Материал из DISCOPAL
Показаны 251-500 из 532 результатов запроса Решение, выполненного за 0.001 секунд. Статистика:
- ... ]].
Придумайте приближенный алгоритм, основанный на линейной релаксации задачи линейного программирования, который находит
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 - ... новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами).
Этих ...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 - ... _питон._С_машинным_кодом]]
* Бонусные задачи вполне решаются, если их не боятся → вот из последних решений → [[Участник:Mishaglik/Solutions/Spoj/FRQPRIME]]
[[File:2021-10-15 Practical Block_2021-11-03 ...4 КБ (116 слов) - 04:57, 3 мая 2024 - ... о рюкзаке:динамическое программирование|Алгоритмы динамического программирования для задачи]] о рюкзаке дают точное решение за время ''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
- ... эффективные алгоритмы построения асимптотически точных покрытий и упаковок, а также асимптотически точных решений задач целочисленного программирования. Одним из его важных научных достижений является ...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
- ... убрать красную фишку с доски. доски. В этом сценарии цель не ставится. Получение выполнимого решения будет означает, что красная фишка ушла с доски.
* Второй сценарий, как полная оптимизационная ...3 КБ (24 слова) - 11:59, 23 декабря 2023 - ... /advalg-2022-homeworks/?session=default advalg-2022-homeworks]»
* Учимся на готовых решениях коллег в соседних папках и решениях прошлых лет → [https://discopal-lab.0x1.tv/projects/3b41be68-a970-4f60 ...4 КБ (121 слово) - 12:05, 9 декабря 2022 - ... в его округе «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 - ... этой задачи, с ростом размера входных данных. Отсутствие же алгоритма субэкспоненциальной сложности для точного решения этой задачи следует из того, что эта задача является 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
- ... через
** PySAT
** Показанное сведение 3SAT → задача → Pyomo → ЦЛП-солвер.
** Сверять
*** если PySAT не нашел решения — то и вы не должны)
*** если нашел — то и у вас должно быть корректное ...946 байт (9 слов) - 12:30, 24 апреля 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 - ... %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 - Решения в бизнес-задачах, где высоковероятно ошибка (не совпадает с решением Стаса). Но может ошибки и нет. Если «перехватить чужое решение» и найти в нем ошибку — 5 бонусных баллов.5 вхождений (0 подкатегорий, 5 файлов) - 11:37, 11 декабря 2022
- {{проверено|[[Участник:StasFomin|StasFomin]] 09:42, 21 мая 2023 (UTC)}}
<!-- Probability and Computing -->
В графе может быть несколько одинаково минимальных разрезов.
Покажите, что их не больше n(n ...367 байт (10 слов) - 09:43, 21 мая 2023 - {{проверено|[[Участник:StasFomin|StasFomin]] 07:49, 24 мая 2023 (UTC)}}
<!-- Probability and Computing -->
Предположим, мы бросаем честный k-сторонний кубик с числами 1 через K на гранях.
Если x — ...436 байт (13 слов) - 07:49, 24 мая 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 - {{проверено|[[Участник: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 - Бонусная задача, решение ее закрывает квест по теоретическим задачам.128 байт (0 слов) - 15:24, 18 мая 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») задачи.1077 вхождений (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
- ...
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
- ... >U'⊆ U</em> переменных которых выставили в «истину», а остальные <em>U-U'</em> соответственно выставлены в «ложь». Значение решения <em>R</em> будет
** либо <em>B</em>, если <em>F</em> ложно
** либо ...1 КБ (104 слова) - 22:05, 17 апреля 2023 - Задачи с решениями на проверке.
__NOCATEGORYCOLUMNS__12 вхождений (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
Просмотреть (предыдущие 250 | следующие 250) (20 | 50 | 100 | 250 | 500)