403
правки
Изменения
→Доказательство корректности
== Доказательство корректности ==
Покажем, что алгоритм строит корректное расписание. Если мы успеваем выполнить очередную работу, то, очевидно, от ее добавления, расписание не может стать некорректным. В противном случае мы пытаемся заменить одну работу из множества <tex> S </tex> на текущую. Но это так же не может сделать наше расписание некорректным. Это следует из того, что мы рассматриваем работы в порядке неуменьшениях их дедлайнов. Пусть мы заменяем работу <tex> k </tex> на работу <tex> i </tex>. Но <tex> d_{k} \leqslant d_{i} </tex>, и следовательно, если мы успевали выполнить работу <tex> k </tex>, то успеем выполнить и работу <tex> i </tex>.
Теперь докажем, что построенное данным алгоритмом расписание оптимально.
Пусть <tex> S^* </tex> множество непросроченных работ в оптимальном расписании. Так же пусть <tex> l </tex> {{---}} первая работа из множества <tex> S </tex>, которая не входит в <tex> S^* </tex>, а <tex> k </tex> {{---}} первая работа из <tex> S^* </tex> не содержащаяся в <tex> S </tex>. Мы можем предполагать существование этих работ, так как, <tex> S^* </tex> не может содержать <tex> S </tex> как подмножество, иначе это противоречило бы построению <tex> S </tex>. С другой стороны, если <tex> S^* \subseteq S </tex>, то <tex> S </tex> должно быть тоже оптимальным, и правильность алгоритма доказана.
== Время работы ==
