Изменения
→Доказательство
|proof= Докажем по индукции по <tex>s</tex>, что если <tex>B(s) = O_{ij}</tex> и <tex>s > t</tex>, то <tex>A(s -1) = O_{i, j - 1}</tex>. Это, очевидно, верно при <tex>s = t+1</tex> так как если <tex>B(t+1) = O_{ij}</tex> и <tex>A(t)</tex> не соответствует задаче <tex>i</tex>, то <tex>B(t) = null</tex> означает что операция <tex>O_{ij}</tex> должна быть запланирована в расписании ранее.
Предположим теперь что лемма верна для всех <tex>v</tex> при <tex>t < v < s</tex> и <tex>B(s) = O_{ij}</tex> . Выберем максимальное <tex>l</tex>, такое что <tex>t < l < s</tex> и <tex>B(l) = null</tex>. По предположению индукции, <tex>A(v- −1)</tex> и <tex>B(v)</tex> соответствуют одной и той же задаче для <tex>v = l + 1,...,s —- 1</tex>. Пусть <tex>A(s - 1</tex>) не соответствует задаче <tex>i</tex>. Тогда для каждого <tex> v ∈ \in{l, l + 1, . . . , s - 1}</tex> операция <tex>A(v)</tex> не соответствует задаче <tex>i</tex>. Таким образом, <tex>O_{ij}</tex> может быть обработан в момент <tex>l</tex>, что противоречит тому факту, что <tex>Y</tex> является расписанием.
}}
