Hardprob/Minimum Register Sufficiency

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

• Направленный ациклический граф
• Найти вычисление на G, которое использует k регистров, т.е.
  • порядок на вершинах V
  • последовательность подмножеств V, удовлетворяющих
    • — пустое
    • — содержит все вершины с нулевой входящей степенью в G
    • , , , и содержит все вершины u, для которых
• Минимизировать число регистров,т.е. k.

---

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

---

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

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

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

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