Изменения

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

1pi1sumwu

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

Навигация