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

• PCP и аппроксимируемость/Задачи/TSP-approx
  ... алгоритм для задачи о коммивояжере на полном графе с положительными весами, где f любая функция, то P=NP.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  417 байт (6 слов) - 06:50, 4 мая 2023
• Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/ex-zpp-notnull
  ... для времени работы $T_M(x)$ машины M выполняется:
  \[
  \mathrm{E} T_M(x) \leq p(|x|).
  \]
  Докажите, что $ZPP_{NotNull}=ZPP$.
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  617 байт (24 слова) - 06:50, 4 мая 2023
• Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/Необратимое семейство перестановок
  ... <m>n</m> вероятность события <m>A(f_n(x))=x</m> меньше (случайно взятый <m>x</m> длины <m>n</m> и случайное бросание алгоритма).
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  769 байт (26 слов) - 06:50, 4 мая 2023
• Вероятность/Задачи/alice-bob-three-strange-dice
  ... первой кости Бобу.
  Покажите, что несмотря на это «благородство», что вероятность выигрыша Алисы больше ½.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  1 КБ (3 слова) - 06:50, 4 мая 2023
• Вероятность/Задачи/coin-game-n-k
  ... выиграет <tt>n</tt>-раз.
  Какова вероятность, что проигравший к концу игры выиграет <tt>k</tt>-раундов?
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  519 байт (9 слов) - 06:50, 4 мая 2023
• Вероятность/Задачи/coin-ten-times
  ... >0<i<6</tt>, <tt>i</tt>-й и <tt>11-i</tt>-й броски будут одинаковы.
  * Будет выброшено подряд четыре «орла».
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  551 байт (11 слов) - 06:50, 4 мая 2023
• Вероятность/Задачи/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

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