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

• Временная и пространственная сложность алгоритмов/Задачи/замки и ключи
  ... . Удивительным кажется то, что для этой задачи построен
  детерминированный o( $n^2$ )-алгоритм. Он очень хитрый.
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  1 КБ (9 слов) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/Конкатенция P
  ... >
  Пусть $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
• Временная и пространственная сложность алгоритмов/Задачи/SAT-in-LOGSPACE
  ... на ленте не считается.
  (можно представить многоленточную машину, в которой первая лента не считается).
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  465 байт (8 слов) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/bin packing problem-first-fit-sometimes-better-than-best-fit
  ... ) ''first fit'' и ''best fit''.
  Найдите примеры входных данных, когда first fit лучше best fit.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  425 байт (24 слова) - 06:50, 4 мая 2023
• Жадный алгоритм в задачах о покрытии/Задачи/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

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