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

• Жадный алгоритм в задачах о покрытии/Задачи/bin packing problem-maximize
  ... в один из m, контейнеров, выкидываем этот предмет.
  Докажите, что этот алгоритм упакует как минимум n/2 предметов.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  1 КБ (25 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/chromatic-numbers-for-graphs
  ... {itemize}
  \item $\chi(G)$ --- хроматическое число графа $G$,
  \item $G^c$ --- дополнение графа $G$.
  \end{itemize}
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  447 байт (30 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/chromatic-numbers-for-graph-with-degree
  ... для его раскраски (раскраска графа --- чтобы смежные вершины не были одного цвета).
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  494 байт (9 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/graph-coloring-smallest-last-not-good
  ... в три цвета граф из ''n'' вершин, для которого алгоритм [[Smallest Last]] будет использовать <m>\Omega(n)</m> цветов.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  453 байт (13 слов) - 06:50, 4 мая 2023
• MAX-CUT: вероятностное округление/Задачи/max-cut-equal-partition-polinomial-local-search
  ... вершин, а делить вершины надо на две одинаковые команды.
  Придумайте полиномиальный алгоритм для этой задачи.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  496 байт (6 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/minimum-hitting-set-k
  ... ''k''-оптимальный полиномиальный алгоритм.
  ;Hint: [[Minimum Hitting Set]] является обобщением минимального вершинного покрытия.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  530 байт (15 слов) - 06:50, 4 мая 2023
• Динамическое программирование для задачи о рюкзаке/Задачи/multidimentional-knapsack-dynamic-programming
  ... -ex-02-19-p99 -->
  Придумайте алгоритм динамического программирования для [[Maximum Integer d-dimentional Knapsack]].
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  295 байт (9 слов) - 06:50, 4 мая 2023
• Полиномиальный в среднем алгоритм для SAT/Задачи/ex-greedy-sat-is-2-approx-weighted
  ... -greedy-sat-is-2-approx]], только покажите, что 2-приближенность сохранится, если будет [[MAX-SAT-Weighted]]
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  332 байт (9 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/internal-cover
  ... элементов линейного пространства, на произвольное множество.} для доказательства оптимальности алгоритма?
  \end{enumerate}
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  1 КБ (16 слов) - 06:50, 4 мая 2023
• Сортировка/Задачи/sorting-convex-hull
  ... {A}(x)=\mathcal{B}(f(x))$.
  Считайте, что предикат $a \le b$ и функции $a + b$ и $a^2$ от целых чисел вычисляются за $O(1)$.
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  2 КБ (73 слова) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/strong-nmt-good-characterization
  ... «?», при том есть хотя бы один путь к «0».
  Покажите, что <m>L \in NP \cap \overline{NP}</m>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  808 байт (24 слова) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3ESAT-NPC
  Покажите, что [[3ESAT]] — NP-полная задача.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  185 байт (2 слова) - 06:50, 4 мая 2023
• Временная и пространственная сложность алгоритмов/Задачи/dlogspace-pspace-gap
  ... ) DLOGSPACE] ≠ P
  * PSPACE ≠ P
  * Заметим, что если у вас вряд ли получится доказать эти неравенства по отдельности.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  522 байт (11 слов) - 06:50, 4 мая 2023
• Временная и пространственная сложность алгоритмов/Задачи/l-eq-p-then-pspace-eq-exptime
  Покажите, что если [https://en.wikipedia.org/wiki/L_(complexity) DLOGSPACE] = P, то PSPACE = EXPTIME.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  235 байт (11 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/np-closed-under-coding
  ... , что если <m>L \in NP</m>, а KOD — какая-то кодировка над алфавитом L, то <m>KOD(L) \in NP</m>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  408 байт (17 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/p-looks-unclosed-under-coding
  K(L) — [[кодировка]].
  Докажите, что класс P замкнут относительно кодировок тогда и только тогда, если P=NP.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  301 байт (5 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/unary-in-p-then-exptime-nexp
  Докажите, что если каждый [[унарный язык]] из NP также лежит в P, то EXPTIME=NEXP.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  246 байт (4 слова) - 06:53, 18 декабря 2023

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