Hardprob/Minimum Register Sufficiency — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена \leq на ≤) |
StasFomin (обсуждение | вклад) (Массовая правка: замена <m>G=\left(V,A\right)</m> на <em>G=(V,A)</em>) |
||
| Строка 1: | Строка 1: | ||
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | ||
| − | * Направленный ациклический граф < | + | * Направленный ациклический граф <em>G=(V,A)</em> |
* Найти вычисление на <em>G</em>, которое использует <em>k</em> регистров, т.е. | * Найти вычисление на <em>G</em>, которое использует <em>k</em> регистров, т.е. | ||
** порядок <m>v_1, \ldots, v_n</m> на вершинах <em>V</em> | ** порядок <m>v_1, \ldots, v_n</m> на вершинах <em>V</em> | ||
Версия 21:33, 17 апреля 2023
- Направленный ациклический граф G=(V,A)
- Найти вычисление на G, которое использует k регистров, т.е.
- порядок на вершинах V
- последовательность подмножеств V, удовлетворяющих
- — пустое
- — содержит все вершины с нулевой входящей степенью в G
- , , , и содержит все вершины u, для которых
- Минимизировать число регистров,т.е. k.
Задача в лаб22 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «PO1»