Hardprob/Minimum Register Sufficiency — различия между версиями

Текущая версия на 23:44, 17 апреля 2023

@@ Строка 2: / Строка 2: @@
 * Направленный ациклический граф <em>G=(V,A)</em>
 * Найти вычисление на <em>G</em>, которое использует <em>k</em> регистров, т.е.
-** порядок <m>v_1, \ldots, v_n</m> на вершинах <em>V</em>
+** порядок <em>v<sub>1</sub>, …, v<sub>n</sub></em> на вершинах <em>V</em>
-** последовательность <m>S_0, \ldots, S_n</m> подмножеств <em>V</em>, удовлетворяющих
+** последовательность <em>S<sub>0</sub>, …, S<sub>n</sub></em> подмножеств <em>V</em>, удовлетворяющих
 ***  <m>\vert S_i\vert ≤ k</m>
 ***  <em>S<sub>0</sub></em> — пустое
 ***  <em>S<sub>n</sub></em> — содержит все вершины с нулевой входящей степенью в <em>G</em>
-***  <m>1 ≤ i ≤ n</m>, <m>v_i ∈ S_i</m>, <m>S_i - \{v_i\} ⊆ S_{i-1}</m>, и <m>S_{i-1}</m> содержит все вершины <em>u</em>, для которых <m>(v_i,u) ∈  A</m>
+***  <em>1 ≤ i ≤ n</em>, <m>v_i ∈ S_i</m>, <m>S_i - \{v_i\} ⊆ S_{i-1}</m>, и <m>S_{i-1}</m> содержит все вершины <em>u</em>, для которых <m>(v_i,u) ∈  A</m>
 * Минимизировать число регистров,т.е. <em>k</em>.