689
правок
Изменения
→Decompose: +доказательство
4 вставить l в промежутки между блоками G, начиная с <tex> r_l </tex>
5 '''for''' B_j <tex> \in G </tex>:
6 ans = max(ans, Decompose(B<tex> B_j </tex>))
7 return ans
{{Теорема
|statement=
Расписание, построенное алгоритмом Decompose(), является корректным и оптимальным.
|proof=
Докажем сначала корректность.
Убедимся, что порядок выполнения работ, заданный графом зависимостей, не нарушается. Заметим, что в разбиении <tex> B \setminus l </tex> на блоки существует не более одного блока <tex> B_0 </tex>, расположенного до момента времени <tex> r_l </tex> — иначе после вставки <tex> l </tex> в промежутки между блоками, <tex> B </tex> выполнялся бы с прерываниями. Далее, заметим, что все интервалы времени, на которые назначается работа из блока <tex> B_j </tex>, находятся внутри интервала <tex> [s_j; e_j] </tex>; это относится и к блоку <tex> B_0 </tex>. Из этих двух наблюдений, а также того, что все работы со временами появления меньше, чем <tex> r_l </tex>, будут помещены в блок <tex> B_0 </tex>, следует, что порядок выполнения будет правильным.
Также для корректности требуется, чтобы работы выполнялись не раньше, чем они появляются. Так как время выполнения работы определяется только в строке 4 алгоритма, которая соответствует этому требованию, то условие выполняется.
Найдем теперь нижнюю оценку на <tex> f_{max} </tex>. Пусть <tex> f_{max}(J) </tex> — ответ для множества работ <tex> J </tex>.
Очевидно, для любой работы <tex> j \in J </tex> выполняется <tex> f_{max}(J) \ge f_{max}(J \ j) </tex>, значит, <tex> f_{max}(J) \ge \max\limits_{j \in J} f_{max}(J \ j) </tex>.
Также, так как в оптимальном решении какая-то работа без потомков обязательно заканчивается в блоке <tex> B </tex>, то <tex> f_{max}(J) \ge f_l(e) </tex>.
Отсюда следует <tex> f_{max}(J) \ge \max(f_l(e), \max\limits_{j \in J} f_{max}(J \ j)) </tex>. По псевдокоду алгоритма видно, что его ответ достигает этой нижней оценки.
}}
=== Общий алгоритм ===
