Результаты поиска

• Вероятность/Задачи/estimate-probability
  ... некоторое число <m>\kappa</m> экспериментов и взяв среднее значение. Оценить сверху <m>\kappa</m> как функцию от <m>\delta</m>.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  665 байт (20 слов) - 06:50, 4 мая 2023
• Вероятность/Задачи/random-cloning-n-times
  ... <tt>n</tt>-ходов, число существ типа A будет равновероятно распределено между <tt>1</tt> и <tt>n+1</tt>.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  706 байт (14 слов) - 06:50, 4 мая 2023
• Вероятность/Задачи/roll-two-dice
  ... , чем на второй.
  * Сумма обоих результатов — четная.
  * Произведение результатов — квадрат какого-то целого числа.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  685 байт (1 слово) - 06:50, 4 мая 2023
• Динамическое программирование для задачи о рюкзаке/Задачи/Худший случай для алгоритма Немхаузера Ульмана
  Придумайте входные наборы для алгоритма Немхаузера-Ульмана, на которых он будет работать экспоненциальное время.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  326 байт (1 слово) - 06:50, 4 мая 2023
• Динамическое программирование для задачи о рюкзаке/Задачи/Задача о построении дерева
  ... алгоритм построения дерева ключей, минимизирующего суммарную стоимость доступа ко всем элементам (частоты доступа $p_i$).
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  856 байт (17 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set
  Предложите детерминированный приближенный алгоритм для [[Minimum Hitting Set]] и оцените его точность.
  {{needjupyternotebook}}
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  313 байт (4 слова) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/ex-acyclic-subgraph-1-2
  ... образующих цикл, в ориентированном подграфе.
  И сделайте это за линейное время от размера графа.
  </latex>
  {{Needjupyternotebook}}
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  522 байт (4 слова) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/k-cover
  ... ,
  когда известно, что в исходных данных, каждый элемент покрывается не более, чем <tt>k</tt> подмножествами.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  446 байт (7 слов) - 06:50, 4 мая 2023
• Несложно о сложности. Примеры алгоритмов/Задачи/ex-fast-power
  ... асимптотическую оценку $\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
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/k-подсемейство множеств - NPC
  ... конечных множеств и натуральное <m>k</m>. Существует ли подсемейство, состоящее из <m>k</m> попарно непересекающихся множеств?
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  476 байт (7 слов) - 06:50, 4 мая 2023
• Приближенный алгоритм для метрической задачи коммивояжера/Задачи/MTSP NP-полна
  Покажите, что метрическая задача коммивояжера NP-полна.
  [[Category:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  208 байт (2 слова) - 06:50, 4 мая 2023
• Приближенный алгоритм для метрической задачи коммивояжера/Задачи/Плохой пример
  Придумайте пример, входной метрический граф, на котором алгоритм Кристофидеса дает наихудшую точность, т.е. 3/2.
  [[Category:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  310 байт (1 слово) - 06:50, 4 мая 2023
• Приближенный алгоритм для метрической задачи коммивояжера/Задачи/Четность вершин нечетной степени в MST
  <latex>
  Почему множество всех вершин нечетной степени в остовном дереве $T$ четно?
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  268 байт (3 слова) - 06:50, 4 мая 2023
• Уникальность минимального остовного дерева
  ... связный ненаправленный граф с ребрами попарно различной длины имеет только одно минимальное остовное дерево.
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  362 байт (2 слова) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/ex-exists-enumeration-of-halts
  ... выписывает одну за
  другой все машины Тьюринга, которые останавливаются, будучи
  запущенными на пустой ленте?
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  374 байт (0 слов) - 06:50, 4 мая 2023
• Полиномиальная иерархия/Задачи/NP \cup co-NP \subseteq P^NP
  Докажите
  <m>
  NP \cup coNP \subseteq P^{NP}
  </m>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  172 байт (8 слов) - 06:50, 4 мая 2023
• Полиномиальная иерархия/Задачи/P^SAT=P^NP
  Докажите <m>P^{SAT}=P^{NP}</m>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  155 байт (6 слов) - 06:50, 4 мая 2023
• Полиномиальная иерархия/Задачи/NP^SAT=\Sigma^p 2
  Докажите
  <m>NP^{SAT}=\Sigma^p_2</m>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  160 байт (6 слов) - 06:50, 4 мая 2023

Просмотреть (предыдущие 20 | следующие 20) (20 | 50 | 100 | 250 | 500)