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

• Полиномиальный в среднем алгоритм для задачи о рюкзаке/Задачи/Проблемы определения «в среднем»
  ... распределение: Вероятность появления каждой входной строки.
  ;<m>x_n</m>: вход длины n.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  680 байт (35 слов) - 06:50, 4 мая 2023
• Полиномиальный в среднем алгоритм для задачи упаковки/Задачи/ex-packing-average-bad-and-good-data
  ... для упаковки
  заставят его работать экспоненциально долго?
  * А какие — за <m>O(n^3)</m>?
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  451 байт (7 слов) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/ex-halt-empty-tape
  ... слове», т.е. для данной МТ <tt>T</tt> определить,
  остановится ли она на пустом слове.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  453 байт (7 слов) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/ex-lost
  ... 4815162342» встречается в десятичном разложении числа
  $\pi$ не менее чем $n$ раз подряд.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  463 байт (11 слов) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/ex-no-enumeration-of-cycled
  ... за
  другой все машины Тьюринга, которые не останавливаются, будучи
  запущенными на пустой ленте.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  465 байт (3 слова) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/ex-obfuscation-undecidable
  ... : попадет ли машина в это
  состояние хотя бы для одного входного слова <tt>x</tt>?
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  581 байт (14 слов) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/ex-turing-copy-lowerbound
  ... можно сказать про $T'(n)$,
  которое есть минимальное время ее работы на входах длины $n$?
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  815 байт (21 слово) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/ex-turing-max-time-grows
  ... любой вычислимой всюду
  определенной функции $b(n)$, то есть $\lim [T(n)/b(n)]=+\infty$.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  690 байт (20 слов) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/ex-union-decideable-decideable
  ... >
  Докажите, для разрешимых языков $L_1$ и $L_2$, язык $L=L_1 \cup L_2$ также разрешим.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  322 байт (11 слов) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/ex-unsolvable-exists
  ... существуют невычислимые по Тьюрингу
  функции <tt>y=f(x)</tt>, используя мощностные соображения.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  364 байт (8 слов) - 06:50, 4 мая 2023
• Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/random-walk-for-directed-graph
  Покажите, что метод случайного блуждания не работает для решения задачи связности на ориентированных графах.
  Представьте пример ориентированного графа c ''n'' вершинами, в котором даже есть путь из ...
  650 байт (11 слов) - 06:50, 4 мая 2023
• Приближенный алгоритм для метрической задачи коммивояжера/Задачи/nearest-neighbour-not-good-for-tsp
  ... и для любого n>3,
  существует экземпляр TSP с n-городами, на котором этот алгоритм будет находить решение, в С раз
  хуже (т.е. больше).
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  705 байт (15 слов) - 06:50, 4 мая 2023
• Приближенный алгоритм для метрической задачи коммивояжера/Задачи/nearest-neighbour-tsp-infty-bas-cases
  ... : для любого i>0, сконструируйте входную задачу, где NN-алгоритм будет находить решение, минимум в (i+2)/6 раз большее оптимального.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  792 байт (11 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/lpt-rule-for-scheduling-p-is-2
  ...
  \frac{M_{LPT}}{OPT(x)} = \frac{1}{3} ( 4 — \frac1p )
  </m>
  * OPT(x) — значение этого оптимального решения.
  * <m>M_{LPT}</m> — значение, найденное алгоритмом.
  См. также [[Жадный алгоритм в задачах ...
  1023 байт (30 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/lpt-rule-for-scheduling
  ... < \frac{1}{3} ( 4 — \frac1p )
  </m>
  * OPT(x) — значение этого оптимального решения.
  * <m>M_{LPT}</m> — значение, найденное алгоритмом
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  878 байт (28 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/fist-fit-for-vector-packing
  ... [https://en.wikipedia.org/wiki/Bin_packing_problem First Fit], обобщенный для многомерности,
  найдет (d+1)-оптимальное решение.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  1 КБ (33 слова) - 06:50, 4 мая 2023

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