Правило Лаулера - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:31:12Z

rollbackEdits.php mass rollback

185.100.85.24 в 04:30, 1 сентября 2022

2022-09-01T04:30:45Z

Shersh: /* Доказательство */

2015-06-08T20:02:23Z

‎Доказательство

95.161.239.66: /* Формулировка */

2015-06-08T18:59:16Z

‎Формулировка

95.161.239.66 в 18:25, 8 июня 2015

2015-06-08T18:25:00Z

95.161.239.66: /* Источники информации */

2015-06-08T10:45:17Z

‎Источники информации

95.161.239.66 в 10:42, 8 июня 2015

2015-06-08T10:42:24Z

95.161.239.66 в 10:37, 8 июня 2015

2015-06-08T10:37:27Z

95.161.239.66: /* Реализация */

2015-06-07T13:16:33Z

‎Реализация

95.161.239.66 в 13:14, 7 июня 2015

2015-06-07T13:14:50Z

← Предыдущая		Версия 16:31, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	Рассмотрим задачу <tex>1 \mid prec \mid f_{max}</tex>.		Рассмотрим задачу <tex>1 \mid prec \mid f_{max}</tex>.
	{{Задача		{{Задача

← Предыдущая		Версия 04:30, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	Рассмотрим задачу <tex>1 \mid prec \mid f_{max}</tex>.		Рассмотрим задачу <tex>1 \mid prec \mid f_{max}</tex>.
	{{Задача		{{Задача

@@ Строка 38: / Строка 38: @@
 Вышеописанный алгоритм строит оптимальное расписание для задачи <tex>1 \mid prec \mid f_{max} </tex>.
 |proof=
-<wikitex>Пусть алгоритм построил расписание, в котором работы идут в порядке $1,2,\dots,n$. Также пусть $\sigma : \sigma(1), \dots, \sigma(n)$ {{---}} оптимальное расписание. Предположим, что $\sigma(i) = i$ для $i = n, n-1, \dots, r$ и $\sigma(r - 1) \ne r-1$, причем $r$ максимальное. Тогда имеем ситуацию, изображенную на рисунке.
+[[Файл:1.jpg]]
-[[Файл:1.jpg|right]]
 Мы можем поставить работу $r - 1$ сразу перед $r$ по построению. Поэтому $r - 1$ и $j$ не имеют наследников в множестве ${1,\dots,r-1}$. Пусть $p_{r-1}$ и $p_j$ есть времена, в которые выполняются работы $r-1$ и $j$. Теперь, если мы поменяем работы $r-1$ и $j$ местами, то ответ не ухудшится. Действительно, $f_j(p_{r-1}) \leqslant f_j(p_j)$ и $f_{r-1}(p_j) \leqslant f_j(p_j)$, а значения соответствующих функций для работ между $r-1$ и $j$ не изменятся, поэтому после перестановки ответ не ухудшится.
 </wikitex>

@@ Строка 7: / Строка 7: @@
 ==Правило Лаулера==
 ===Формулировка===
-<wikitex>Существует простой жадный алгоритм решения этой задачи, открытый Лаулером. Он заключается в том, чтобы строить расписание с конца.
+<wikitex>Существует простой [[Теорема Радо-Эдмондса (жадный алгоритм)| жадный алгоритм]] решения этой задачи, открытый Лаулером. Он заключается в том, чтобы строить расписание с конца.
 Пусть $N = \{1, \dots, n\}$ {{---}} множество работ, и $S \subseteq N$ {{---}} множество работ, которых ещё нет в расписании. Пусть также $p(S) = \sum\limits_{j \in S}{p_j}$. Тогда правило Лаулера можно сформулировать следующим образом: взять работу $j \in S$, у которой нет детей в графе зависимостей и имеющую минимальное значение $f_j(p(S))$, и сделать ее последней среди работ из $S$.

@@ Строка 1: / Строка 1: @@
 Рассмотрим задачу <tex>1 \mid prec \mid f_{max}</tex>.
 {{Задача
-|definition = <wikitex>Дано $n$ работ, которые надо выполнить на одной машине, причем $i$-ая работа выполняется $p_i$ времени. Для каждой работы задана монотонно неубывающая функция $f_i$. Также между работами заданы отношения в виде ориентированного графа без циклов: если существует ребро $a \to b$, то работа $a$ должна завершиться до начала выполнения работы $b$. Необходимо построить такое расписание, чтобы величина $f_{max} = \max\limits_{j=1}^{n}{f_j(C_j)}$, где $C_j$ {{---}} время окончания выполнения $j$-ой работы, была минимальна.</wikitex>
+|definition = <wikitex>Дано $n$ работ, которые надо выполнить на одной машине, причем $i$-ая работа выполняется $p_i$ времени. Для каждой работы задана монотонно неубывающая функция $f_i$. Также между работами заданы отношения в виде ориентированного графа без циклов: если существует ребро $a \to b$, то работа $a$ должна завершиться до начала выполнения работы $b$. Необходимо построить такое расписание, чтобы величина $f_{max} = \max\limits_{j=1..n}{f_j(C_j)}$, где $C_j$ {{---}} время окончания выполнения $j$-ой работы, была минимальна.</wikitex>
 }}
 <wikitex>Задача $1 \mid \mid f_{max}$ является частным случаем вышеописанной задачи. Здесь нет зависимостей между работами, то есть граф состоит из $n$ вершин и не содержит ребер. Очевидно, решив задачу в общем виде, мы также решим и эту.</wikitex>
@@ Строка 24: / Строка 24: @@
     find job j in S with N[j] == 0 and minimal f[j](P)-value
     S = S \ {j}
-    N[i] = <tex>\infty</tex>
+    N[j] = <tex>\infty</tex>
     schedule[k] = j
     P -= p[j]
@@ Строка 49: / Строка 49: @@
 ==Источники информации==
-* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 62 стр. {{---}} ISBN 978-3-540-69515-8
+* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 62-63 стр. {{---}} ISBN 978-3-540-69515-8
 [[Категория:Алгоритмы и структуры данных]]
 [[Категория: Теория расписаний]]

@@ Строка 1: / Строка 1: @@
 Рассмотрим задачу <tex>1 \mid prec \mid f_{max}</tex>.
 {{Задача
-|definition = <wikitex>Дано $n$ работ, которые надо выполнить на одной машине, причем $i$-ая работа выполняется $p_i$ времени. Для каждой работы задана монотонно неубывающая функция $f_i$. Также между работами заданы отношения в виде ориентированного графа без циклов: если существует ребро $a \to b$, то работа $a$ должна завершиться до начала выполнения работы $b$. Необходимо построить такое расписание, чтобы величина $f_{max} = \max^{n}_{j=1}{f_j(C_j)}$, где $C_j$ {{---}} время окончания выполнения $j$-ой работы, была минимальна.</wikitex>
+|definition = <wikitex>Дано $n$ работ, которые надо выполнить на одной машине, причем $i$-ая работа выполняется $p_i$ времени. Для каждой работы задана монотонно неубывающая функция $f_i$. Также между работами заданы отношения в виде ориентированного графа без циклов: если существует ребро $a \to b$, то работа $a$ должна завершиться до начала выполнения работы $b$. Необходимо построить такое расписание, чтобы величина $f_{max} = \max\limits_{j=1}^{n}{f_j(C_j)}$, где $C_j$ {{---}} время окончания выполнения $j$-ой работы, была минимальна.</wikitex>
 }}
 <wikitex>Задача $1 \mid \mid f_{max}$ является частным случаем вышеописанной задачи. Здесь нет зависимостей между работами, то есть граф состоит из $n$ вершин и не содержит ребер. Очевидно, решив задачу в общем виде, мы также решим и эту.</wikitex>
@@ Строка 10: / Строка 9: @@
 <wikitex>Существует простой жадный алгоритм решения этой задачи, открытый Лаулером. Он заключается в том, чтобы строить расписание с конца.
-Пусть $N = \{1, \dots, n\}$ {{---}} множество работ, и $S \subseteq N$ {{---}} множество работ, которых ещё нет в расписании. Пусть также $p(S) = \sum_{j \in S}{p_j}$. Тогда правило Лаулера можно сформулировать следующим образом: взять работу $j \in S$, у которой нет детей в графе зависимостей и имеющую минимальное значение $f_j(p(S))$, и сделать ее последней среди работ из $S$.
+Пусть $N = \{1, \dots, n\}$ {{---}} множество работ, и $S \subseteq N$ {{---}} множество работ, которых ещё нет в расписании. Пусть также $p(S) = \sum\limits_{j \in S}{p_j}$. Тогда правило Лаулера можно сформулировать следующим образом: взять работу $j \in S$, у которой нет детей в графе зависимостей и имеющую минимальное значение $f_j(p(S))$, и сделать ее последней среди работ из $S$.
 </wikitex>
 ===Реализация===
-<wikitex>Пусть граф задан матрицей смежности $A = (a_{ij})$, где $a_{ij} = 1$ тогда, и только тогда, когда существует ребро $i \to j$. За $N(i)$ обозначим число детей вершины $i$, а $schedule$ {{---}} расписание.
+*<tex>A = (a_{ij})</tex> {{---}} матрица смежности графа, где <tex>a_{ij} = 1</tex> тогда, и только тогда, когда существует ребро <tex>i \to j</tex>.
   '''for''' i = 1 '''to''' n
     '''for''' j = 1 '''to''' n
@@ Строка 21: / Строка 22: @@
   P = sum(p[i])
   '''for''' k = n '''downto''' 1
-    find job j in S with N[j] == 0 and minimal f[j](P)-value;
+    find job j in S with N[j] == 0 and minimal f[j](P)-value
     S = S \ {j}
     N[i] = <tex>\infty</tex>
@@ Строка 30: / Строка 31: @@
         N[i]--
-Сложность этого алгоритма $O(n^2)$.
+Сложность этого алгоритма <tex>O(n^2)</tex>.
 ===Доказательство===