Изменения

Перейти к: навигация, поиск

1pi1sumwu

3 байта убрано, 19:21, 18 июня 2013
м
Доказательство корректности
Покажем, что алгоритм строит корректное расписание.
Если мы успеваем выполнить очередную работу, то, очевидно, от ее добавления, расписание не может стать некорректным. В противном случае мы пытаемся заменить одну работу из множества <tex> S </tex> на текущую. Но это так же не может сделать наше расписание некорректным. Это следует из того, что мы рассматриваем работы в порядке неуменьшениях их дедлайнов. Пусть мы заменяем работу <tex> k </tex> на работу <tex> i </tex>. Но <tex> d_{k} \leqslant d_{i} </tex>, и следовательно, если мы успевали выполнить работу <tex> k </tex>, то успеем выполнить и работу <tex> i </tex>.
Теперь докажем, что построенное данным алгоритмом расписание оптимально.
403
правки

Навигация