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