Open Classic Hard Problems — различия между версиями

Версия 22:06, 5 апреля 2023 (просмотреть исходный код) StasFomin (обсуждение | вклад) ← Предыдущая правка		Версия 22:11, 5 апреля 2023 (просмотреть исходный код) StasFomin (обсуждение | вклад) Следующая правка →
Строка 2:		Строка 2:
	showtotal=yes		showtotal=yes
	namespace=Main		namespace=Main
−	limit=500	+	limit=5
	order=creation desc		order=creation desc
	output=template		output=template

---

Версия 22:11, 5 апреля 2023

Всего страниц найдено: 5.

---

Задача «Minimum Local Register Allocation»^©

---

• Набор инструкций, формирующих некий блок без переходов,
  • N доступных регистров,
  • стоимость чтения и записи в регистр i.
• Порядок резервирования регистров для этой последовательности инструкций.
• Минимизировать полную стоимость чтения-записи в регистры.

---

Задача в лаб22 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана

---

---

---

Задача «Minimum Register Sufficiency»^©

---

• Направленный ациклический граф G=(V,A)
• Найти вычисление на G, которое использует k регистров, т.е.
  • порядок v₁, …, v_n на вершинах V
  • последовательность S₀, …, S_n подмножеств V, удовлетворяющих
    • S₀ — пустое
    • S_n — содержит все вершины с нулевой входящей степенью в G
    • 1 ≤ i ≤ n, , , и содержит все вершины u, для которых
• Минимизировать число регистров,т.е. k.

---

Задача в лаб22 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана
• Код задачи в книге «ГД» → «PO1»

---

---

---

Задача «Minimum Permutation Group Base»^©

---

• Группа G перестановок из n символов.
• Найти базу для G, т.е. последовательность точек b₁, …, b_k, такой, что единственный элемент в G фиксирующий все эти b_i это идентичное преобразование.
• Минимизировать размер базы, т.е. k.

---

Задача в лаб22 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана

---

---

---

Задача «Minimum Locally Testable Automaton Order»^©

---

• Локально тестируемый язык L, т.е. некий язык L, такой, что положительное целое j, такое что входит или нет строка x в этот язык зависит от …
  • префикса и суффикса x длины j-1,
  • набора подстрок x длины j.
• Найти порядок j, т.е. положительное целое j, «свидетель» локальной тестируемости L.
• Минимизировать значение порядка, т.е. j.

---

Задача в лаб22 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана

---

---

---

Задача «Shortest Computation»^©

---

• Недетерминированная машина Тьюринга M, двоичная входная строка x.
• Найти недерминированную строку-догадку c, произведенную машиной M на входе x.
• Минимизировать длину кратчайшей из этих строк,т.е. .

---

Задача в лаб22 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана

---

---