Викиконспекты - Вклад участника [ru]

Об интеграле Фурье

2012-06-22T23:53:12Z

217.66.152.17: взята блокировка на статью :)

P2precpi1Lmax

2012-06-10T03:15:30Z

217.66.152.17:

==Описание алгоритма==
Полагаем, что ребра в графе ориентированы от работы, к работам, зависимым от нее.
Введем понятие ''вынужденного'' дедлайна <tex>d'_i</tex> {{---}} максмальное время, до которого необходимо выполнить <tex>i</tex>-ую работу, чтобы успеть
выполнить все работы из <tex>S(i)</tex>, где <tex>S(i)</tex> — множество работ, зависящих (не обязательно непосредственно) от <tex>i</tex>-ой работы.
Заметим, что эта величина может принимать отрицательные значения.
Обозначим через <tex>g(i, d)</tex> количество работ <tex>k</tex> из <tex>S(i)</tex>,
таких что <tex>d'_k \le d</tex>.

{{Утверждение
|statement=Пусть уже посчитаны работы для всех <tex>j \in S(i)</tex>. Тогда, если <tex>j \in S(i)</tex>, то <tex>i</tex>-ая работа
должна быть закончена до <tex>d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil</tex>.
|proof=Рассмотрим все работы <tex>k \in S(i)</tex>, для которых <tex>d'_k \le d'_j</tex>. Все эти работы будут выполнены после
окончания обработки детали с номером <tex>i</tex>. Для них <tex>d'_k \le d'_j</tex>. Пусть работу <tex>i</tex> закончили выполнять в
момент времени <tex>d</tex>. Нужно до момента времени <tex>d'_j</tex> выполнить ещё <tex>g(i, d'_j)</tex> работ.
Так как в нашем распоряжении находятся две машины, то время их выполнения будет не менее, чем <tex>\lceil \frac{g(i, d'_j)}{2} \rceil</tex>.
Поскольку необходимо выполнить все эти работы до <tex>d'_j</tex>, то <tex>i</tex>-ая работа должна быть закончена до момента времени
<tex>d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil</tex>.
}}

Тогда финально получаем формулу для вычисления «вынужденного» дедлайна для <tex>i</tex>-ой работы:
<tex>d'_i = \min\{d_i, \min\{d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil\}\}</tex>, где <tex>j \in S(i)</tex>.
Для вершин, исходящая степень которых равна нулю, по определению вынужденного дедлайна, считаем его равным обычному дедлайну.
Для подсчета вынужденных дедлайнов будем поддерживать список <tex>L</tex>, содержащий вершины, отсортированные в порядке
неубывания ''дедлайнов''. ''Дедлайн'' равен вынужденному дедлайну, если он уже посчитан, и обычному {{---}} в противном случае.
Будем рассматривать вершины в порядке, обратном топологической сортировке графа, то есть, начиная с вершин нулевой исходящей степени.
Пусть на текущем шаге мы рассматриваем работу с
номером <tex>i</tex>. Перебирая вершины из <tex>S(i)</tex> в порядке списка <tex>L</tex>, пересчитываем вынужденный дедлайн для
<tex>i</tex>-ой вершины по формуле, указанной выше, после чего обновляем дедлайн этой вершины в списке <tex>L</tex>.

После подсчета вынужденных дедлайнов, оптимальное расписание считается жадным алгоритмом.
На каждом шаге на для обработки на станках выбираются работы с минимальным вынужденным дедлайном, для которых все необходимые
работы уже выполнены. Одновременно с этим считается максимальное опоздание.

==Доказательство корректности==
{{Утверждение #1
|statement= В расписании с обычными дедлайнами нет опозданий тогда и только тогда, когда нет опозданий в расписании с
вынужденными дедлайнами.
|proof=
<tex>\Leftarrow</tex> Поскольку вынужденный дедлайн не нарушен, то, больший его обычный дедлайн, также не будет нарушен.

<tex>\Rightarrow</tex> По определению вынужденного дедлайна, <tex>d'_i</tex> {{---}} максимальное время окончания работы
<tex>i</tex>, при котором
ещё можно успеть выполнить все работы из <tex>S(i)</tex>. Значит, если для <tex>i</tex> был нарушен вынужденный дедлайн,
то не все работы из <tex>S(i)</tex> выполнены вовремя, то есть
был нарушен хотя бы один обычный дедлайн, что противоречит условию.

Более формально, пусть был нарушен вынужденный дедлайн. Найдём работу <tex>i</tex> с нарушенным вынужденным дедлайном,
такую, что <tex>\forall k \in S(i) : d'_k </tex> {{---}} не нарушено. Это всегда можно сделать в силу ацикличности графа.
Рассмотрим формулу для подсчёта вынужденного дедлайна:
<tex>d'_i = \min\{d_i, \min\{d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil\}\}</tex>, где <tex>j \in S(i)</tex>.

Минимум достигся либо на <tex>d_i</tex>, что невозможно в силу того, что обычные дедлайны не нарушены, либо на каком-то
<tex>j \in S(i)</tex>. В этом случае, <tex>d'_i = d'_j - \lceil\frac{g(i, d'_j)}{2}\rceil</tex>.
Значит, если <tex>d'_i</tex> нарушено, то будет также нарушен вынужденный дедлайн для какого-то <tex>k \in S(i)</tex>,
так как осталось меньше, чем <tex>d'_j - d'_i > \lceil \frac{g(i, d'_j)}{2} \rceil</tex> единиц времени. Это
противоречит условии выбора <tex>i</tex>.
}}

{{Утверждение #2
|statement= Если существует расписание без опоздание, то приведенный выше алгоритм найдет такое расписание.
|proof= Пусть <tex>x(1), x(2),...,x(n)</tex>~---расписание, построенное этим алгоритмом, где <tex>x(i)</tex>~--- время
начала обработки <tex>i</tex>-ой детали. Пусть в этом расписании существует работа, опаздывающая по обычным дедлайнам. Согласно
утверждению 1, в этом расписании также существует работа, опаздывающая по "вынужденным" дедлайнам. Пусть <tex>i</tex> работа с
минимальным временем начала, удолетворяющая следующему условию: <tex>d'_i < x(i) + 1</tex>. Следуя алгоритму, в каждый момент времени
<tex>t</tex>, такой что <tex>t < x(i)</tex>, хотя бы одна работа с номером <tex>j</tex>, такая что <tex>d'_j \le d'_i</tex> должна
быть выполнена.
Рассмотрим два случая.
Первый случай: в какой-то момент времени только одна работа с номером <tex>k</tex>, такая что <tex>d'_k \le d'_i</tex> выполнена.
Выберем максимальное время <tex>t</tex>, такое что <tex>t < x(i)</tex>, обладающее таким свойством. Тогда для всех работ c номером
<tex>j</tex>, которые выполнялись в момент времени с <tex>t+1</tex> до <tex>x(i)</tex> выполняется <tex>d'_j \le d'_i</tex>, кроме того
ни один станок не простаивал в течении этого периода.
}}

P2precpi1Lmax

2012-06-10T02:36:43Z

217.66.152.17:

==Описание алгоритма==
Полагаем, что ребра в графе ориентированы от работы, к работам, зависимым от нее.
Введем понятие ''вынужденного'' дедлайна <tex>d'_i</tex> — время, до которого необходимо выполнить <tex>i</tex>-ую работу, чтобы успеть
выполнить все работы из <tex>S(i)</tex>, где <tex>S(i)</tex> — множество работ, зависящих (не обязательно непосредственно) от <tex>i</tex>-ой работы.
Заметим, что эта величина может принимать отрицательные значения.
Обозначим через <tex>g(i, d)</tex> количество работ <tex>k</tex> из <tex>S(i)</tex>,
таких что <tex>d'_k \le d</tex>.

{{Утверждение
|statement=Пусть уже посчитаны работы для всех <tex>j \in S(i)</tex>. Тогда, если <tex>j \in S(i)</tex>, то <tex>i</tex>-ая работа
должна быть закончена до <tex>d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil</tex>.
|proof=Рассмотрим все работы <tex>k \in S(i)</tex>, для которых <tex>d'_k \le d'_j</tex>. Все эти работы будут выполнены после
окончания обработки детали с номером <tex>i</tex>. Для них <tex>d'_k \le d'_j</tex>. Пусть работу <tex>i</tex> закончили выполнять в
момент времени <tex>d</tex>. Нужно до момента времени <tex>d'_j</tex> выполнить ещё <tex>g(i, d'_j)</tex> работ.
Так как в нашем распоряжении находятся две машины, то время их выполнения будет не менее, чем <tex>\lceil \frac{g(i, d'_j)}{2} \rceil</tex>.
Поскольку необходимо выполнить все эти работы до <tex>d'_j</tex>, то <tex>i</tex>-ая работа должна быть закончена до момента времени
<tex>d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil</tex>.
}}

Тогда финально получаем формулу для вычисления «вынужденного» дедлайна для <tex>i</tex>-ой работы:
<tex>d'_i = \min\{d_i, \min\{d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil\}\}</tex>, где <tex>j \in S(i)</tex>.
Для вершин, исходящая степень которых равна нулю, по определению вынужденного дедлайна, считаем его равным обычному дедлайну.
Для подсчета вынужденных дедлайнов будем поддерживать список <tex>L</tex>, содержащий вершины, отсортированные в порядке
неубывания ''дедлайнов''. ''Дедлайн'' равен вынужденному дедлайну, если он уже посчитан, и обычному {{---}} в противном случае.
Будем рассматривать вершины в порядке, обратном топологической сортировке графа, то есть, начиная с вершин нулевой исходящей степени.
Пусть на текущем шаге мы рассматриваем работу с
номером <tex>i</tex>. Перебирая вершины из <tex>S(i)</tex> в порядке списка <tex>L</tex>, пересчитываем вынужденный дедлайн для
<tex>i</tex>-ой вершины по формуле, указанной выше, после чего обновляем дедлайн этой вершины в списке <tex>L</tex>.

После подсчета вынужденных дедлайнов, оптимальное расписание считается жадным алгоритмом.
На каждом шаге на для обработки на станках выбираются работы с минимальным вынужденным дедлайном, для которых все необходимые
работы уже выполнены. Одновременно с этим считается максимальное опоздание.

==Доказательство корректности==
{{Утверждение #1
|statement= В расписании с обычными дедлайнами нет опозданий тогда и только тогда, когда нет опозданий в расписании с
"вынужденными" дедлайнами.
|proof= <tex>\Leftarrow</tex> Так как "вынужденные" дедлайны меньше обычных, то в эту сторону утверждение очевидно.
<tex>\Rightarrow</tex> Напрямую следует из определения вынужденного дедлайна.
}}

{{Утверждение #2
|statement= Если существует расписание без опоздание, то приведенный выше алгоритм найдет такое расписание.
|proof= Пусть <tex>x(1), x(2),...,x(n)</tex>~---расписание, построенное этим алгоритмом, где <tex>x(i)</tex>~--- время
начала обработки <tex>i</tex>-ой детали. Пусть в этом расписании существует работа, опаздывающая по обычным дедлайнам. Согласно
утверждению 1, в этом расписании также существует работа, опаздывающая по "вынужденным" дедлайнам. Пусть <tex>i</tex> работа с
минимальным временем начала, удолетворяющая следующему условию: <tex>d'_i < x(i) + 1</tex>. Следуя алгоритму, в каждый момент времени
<tex>t</tex>, такой что <tex>t < x(i)</tex>, хотя бы одна работа с номером <tex>j</tex>, такая что <tex>d'_j \le d'_i</tex> должна
быть выполнена.
Рассмотрим два случая.
Первый случай: в какой-то момент времени только одна работа с номером <tex>k</tex>, такая что <tex>d'_k \le d'_i</tex> выполнена.
Выберем максимальное время <tex>t</tex>, такое что <tex>t < x(i)</tex>, обладающее таким свойством. Тогда для всех работ c номером
<tex>j</tex>, которые выполнялись в момент времени с <tex>t+1</tex> до <tex>x(i)</tex> выполняется <tex>d'_j \le d'_i</tex>, кроме того
ни один станок не простаивал в течении этого периода.
}}