Hardprob/Minimum Register Sufficiency

Ссылки сюда (2) →

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

---

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

---

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.