F2Cmax - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:27:25Z

rollbackEdits.php mass rollback

91.212.153.123 в 04:52, 1 сентября 2022

2022-09-01T04:52:15Z

AMaltsev в 21:46, 6 июня 2016

2016-06-06T21:46:32Z

AMaltsev в 21:44, 6 июня 2016

2016-06-06T21:44:35Z

AMaltsev в 21:22, 6 июня 2016

2016-06-06T21:22:19Z

AMaltsev в 21:06, 6 июня 2016

2016-06-06T21:06:25Z

AMaltsev в 21:05, 6 июня 2016

2016-06-06T21:05:03Z

AMaltsev в 20:33, 6 июня 2016

2016-06-06T20:33:27Z

AMaltsev в 20:32, 6 июня 2016

2016-06-06T20:32:58Z

AMaltsev: убрал неоднозначность

2016-06-06T18:33:32Z

убрал неоднозначность

← Предыдущая		Версия 16:27, 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 dpi=200>F2 \mid\mid C_{max} </tex>		<tex dpi=200>F2 \mid\mid C_{max} </tex>
	{{Задача		{{Задача

← Предыдущая		Версия 04:52, 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 dpi=200>F2 \mid\mid C_{max} </tex>		<tex dpi=200>F2 \mid\mid C_{max} </tex>
	{{Задача		{{Задача

@@ Строка 52: / Строка 52: @@
 |statement= Пусть имеем произвольное расписание, в котором работа <tex> j </tex> идет сразу же после работы <tex> i </tex>. Тогда если <tex> \min(p_{j1}, p_{i2}) \leqslant   \min(p_{i1}, p_{j2}) </tex>, то можем поменять местами эти работы без ухудшения целевой функции.
 |proof=
-[[Файл:f2cmax_fixed.png|200px|thumb|right|Рис. 2 - Расположение последовательных работ]]
+[[Файл:f2cmax_fixed.png|200px|thumb|right|Рис. 2 {{---}} Расположение последовательных работ]]
 Пусть <tex> w_{ij} </tex> {{---}} время, прошедшее с начала выполнения работы <tex> i </tex> на первом станке до окончания работы <tex> j </tex> на втором станке.

@@ Строка 14: / Строка 14: @@
 <li> Пока множество <tex> X </tex> не пусто, распределяем работы по спискам следующим образом:
 <ul>
-<li> находим такие индексы <tex> i </tex> и <tex> j </tex>, что  <tex>p_{ij} = \min \{ p_{ij}  \mid i \in X; j = 1, 2\}</tex>, </li>
+<li> находим такие индексы <tex> i </tex> и <tex> j </tex>, что  <tex>p_{ij} = \min \{ p_{ij}  \mid i \in X \land j = 1, 2\}</tex>, </li>
 <li>если минимум достигается на первом станке (иными словами <tex> j = 1 </tex>), то поставим работу <tex> i </tex> в конец  списка <tex> L </tex>, иначе ставим в начало списка <tex> R </tex>,  </li>
 <li>удаляем работу <tex> i </tex> из множества <tex> X </tex>. </li>
 </ul>
 </li>
-<li> Рассмотрим список <tex> T = L + R</tex> - конкатенацию <tex> L</tex> и <tex>R</tex>. Утверждается, что этот список является оптимальной перестановкой работ как на первом, так и на втором станке. Далее расставляем подряд работы на первом станке согласно перестановке, после чего ставим в том же порядке работы на втором станке, при этом избегая одновременного выполнения одной и той же работы. </li>
+<li> Рассмотрим список <tex> T = L ~\texttt{++}~ R</tex> {{---}} конкатенацию <tex> L</tex> и <tex>R</tex>. Утверждается, что этот список является оптимальной перестановкой работ как на первом, так и на втором станке. Далее расставляем подряд работы на первом станке согласно перестановке, после чего ставим в том же порядке работы на втором станке, при этом избегая одновременного выполнения одной и той же работы. </li>
 </ol>
@@ Строка 31: / Строка 31: @@
 [[Файл:f2cmax_first_fixed.png|400px|thumb|right|Рис. 1]]
 Предположим обратное: что не существует оптимального расписания с одинаковыми перестановками работ на станках.
-Рассмотрим некоторое оптимальное расписание с максимальным по длине общим префиксом на станках. Пусть его длина равна <tex> k </tex>, где <tex> k < n </tex>. Пусть на <tex> k </tex> позиции на первом и втором станках стоит работа <tex> i </tex>, а на втором станке на позиции <tex> k + 1 </tex> стоит работа <tex> j </tex>. Тогда заметим, что если мы поставим работу <tex> j </tex> на первом станке сразу после работы <tex> i </tex>, то последовательные работы с <tex> h </tex> по <tex> m </tex> (см. Рис. 1) по-прежнему будут успевать выполниться, так как на втором станке они выполняются в текущем расписании после <tex> j </tex>. Таким образом нам удалось увеличить длину наибольшего общего префикса, а так как по нашему предположению она была максимальна, то наше предположение неверно, то искомое расписание с одинаковым порядком выполнения работ на обоих станках существует.
+Рассмотрим некоторое оптимальное расписание с максимальным по длине общим префиксом на станках. Пусть его длина равна <tex> k </tex>, где <tex> k < n </tex>. Пусть на <tex> k </tex> позиции на первом и втором станках стоит работа <tex> i </tex>, а на втором станке на позиции <tex> k + 1 </tex> стоит работа <tex> j </tex>. Тогда заметим, что если мы поставим работу <tex> j </tex> на первом станке сразу после работы <tex> i </tex>, то последовательные работы с <tex> h </tex> по <tex> m </tex> (см. рис. 1) по-прежнему будут успевать выполниться, так как на втором станке они выполняются в текущем расписании после <tex> j </tex>. Таким образом нам удалось увеличить длину наибольшего общего префикса, а так как по нашему предположению она была максимальна, то предположение неверно и искомое расписание с одинаковым порядком выполнения работ на обоих станках существует.
 }}
-Таким образом задача сводится к поиску этой искомой перестановки.  Докажем, что полученный приведенным выше алгоритмом список является оптимальной перестановкой работ.
+Таким образом задача сводится к поиску этой перестановки.  Докажем, что полученный приведенным выше алгоритмом список является оптимальной перестановкой работ.
 {{лемма
 |id=lemma1
 |about=1
-|statement= Если для каких-то работ <tex> i </tex> и <tex> j </tex> из списка <tex> T </tex> верно неравенство <tex> \min(p_{i1}, p_{j2}) <   \min(p_{j1}, p_{i2}) </tex>, то работа <tex> i </tex> встречается в списке <tex> T </tex> раньше, чем <tex> j </tex>.
+|statement= Если для каких-то работ <tex> i </tex> и <tex> j </tex> из списка <tex> T </tex> верно неравенство <tex> \min(p_{i1}, p_{j2}) < \min(p_{j1}, p_{i2}) </tex>, то работа <tex> i </tex> встречается в списке <tex> T </tex> раньше, чем <tex> j </tex>.
 |proof=
 Пусть <tex> p_{i1} < p_{j2} </tex>. Случай <tex> p_{i1} > p_{j2} </tex> рассматривается аналогично.
@@ Строка 101: / Строка 101: @@
 ==Псевдокод==
-    '''function''' F2Cmax(n: '''int''', p: '''int'''[n][2]): '''list'''
+    '''function''' F2Cmax(p: '''int'''[n][2]): '''list<int>'''
-       '''list''' L = <tex>\varnothing </tex>
+       '''list<int>''' L = <tex>\varnothing </tex>
-       '''list''' R = <tex>\varnothing </tex>
+       '''list<int>''' R = <tex>\varnothing </tex>
-       '''set''' X = <tex>\{1, \dots, n\}</tex>
+       '''set<int>''' X = <tex>\{1, \ldots, n\}</tex>
-       '''while'''  X <tex> \neq \varnothing</tex>
+       '''while''' X <tex>\neq \varnothing</tex>
-          Найти i  и j , такие что <tex>p_{ij} = \min \{ p_{ij}  \mid i \in X; j = 1, 2\}</tex>
+          Найти i и j, такие что <tex>p_{ij} = \min \{ p_{ij} \mid i \in X \land j = 1, 2\}</tex>
           '''if''' j == 1
              L.addLast(i)
@@ Строка 112: / Строка 112: @@
              R.addFirst(i)
           X.remove(i)
-       '''list''' T = L + R
+       '''list<int>''' T = L ++ R
        '''return''' T

@@ Строка 116: / Строка 116: @@
 ==Сложность алгоритма==
-Заметим, что на каждом шаге алгоритма мы выбираем минимум из оставшихся элементов за <tex>O(\log n)</tex> (либо предварительной [[Сортировка|сортировкой]], либо  с помощью любой структуры данных, поддерживающей нахождение минимума и удаление за <tex>O(\log n)</tex>, например [[Двоичная_куча|кучи]]). А так как мы делаем  это <tex> n </tex> раз, алгоритм работает за <tex>O(n\log n)</tex>.
+Заметим, что на каждом шаге алгоритма мы выбираем минимум из оставшихся элементов за <tex>O(\log n)</tex> (либо предварительной [[Сортировка|сортировкой]], либо  с помощью любой структуры данных, поддерживающей нахождение минимума и удаление за <tex>O(\log n)</tex>, например, [[Двоичная_куча|кучи]]). А так как мы делаем  это <tex> n </tex> раз, алгоритм работает за <tex>O(n\log n)</tex>.
 ==См. также==

@@ Строка 81: / Строка 81: @@
 Аналогично,  <tex> w_{ji} = \max (p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2},  \Delta + p_{i2} + p_{j2}) </tex>
-Так как <tex> \min(a, b) = - \max(-a, -b)</tex>, то из условия леммы имеем <tex> \max(-p_{i1}, -p_{j2}) \leqslant   \max(-p_{j1}, -p_{i2}) </tex>. Добавим <tex> p_{i1} + p_{i2} + p_{j1} + p_{j2} </tex> к обеим частям. Получим, что <tex> p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2} \leqslant p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2} </tex>, то есть <tex> w_{ji} \leqslant w_{ij} </tex> и при смене местами работ <tex> i </tex> и <tex> j </tex> ответ не ухудшается.
+Так как <tex> \min(a, b) = - \max(-a, -b)</tex>, то из условия леммы имеем <tex> \max(-p_{i1}, -p_{j2}) \leqslant   \max(-p_{j1}, -p_{i2}) </tex>. Добавив <tex> p_{i1} + p_{i2} + p_{j1} + p_{j2} </tex> к обеим частям, получим, что <tex> p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2} \leqslant p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2} </tex>, то есть <tex> w_{ji} \leqslant w_{ij} </tex> и при смене местами работ <tex> i </tex> и <tex> j </tex> ответ не ухудшается.
 }}

@@ Строка 14: / Строка 14: @@
 <li> Пока множество <tex> X </tex> не пусто, распределяем работы по спискам следующим образом:
 <ul>
-<li> Находим такие индексы <tex> i </tex> и <tex> j </tex>, что  <tex>p_{ij} = \min \{ p_{ij}  \mid i \in X; j = 1, 2\}</tex> </li>
+<li> находим такие индексы <tex> i </tex> и <tex> j </tex>, что  <tex>p_{ij} = \min \{ p_{ij}  \mid i \in X; j = 1, 2\}</tex>, </li>
-<li>Если минимум достигается на первом станке (иными словами <tex> j = 1 </tex>), то поставим работу <tex> i </tex> в конец  списка <tex> L </tex>, иначе ставим в начало списка <tex> R </tex>  </li>
+<li>если минимум достигается на первом станке (иными словами <tex> j = 1 </tex>), то поставим работу <tex> i </tex> в конец  списка <tex> L </tex>, иначе ставим в начало списка <tex> R </tex>,  </li>
-<li>Удаляем работу <tex> i </tex> из множества <tex> X </tex> </li>
+<li>удаляем работу <tex> i </tex> из множества <tex> X </tex>. </li>
 </ul>
 </li>
@@ Строка 59: / Строка 59: @@
 <li>Работа <tex> i </tex> начинается на втором станке сразу же после завершения ее на первом
 <ul>
-<li> Выполнение работы <tex> i </tex> на втором станке заканчивается позже, чем работы <tex> j </tex> на первом.  В этом случае  <tex> w_{ij} = p_{i1} + p_{i2} + p_{j2} </tex>.</li>
+* Выполнение работы <tex> i </tex> на втором станке заканчивается позже, чем работы <tex> j </tex> на первом.
-<li> Выполнение работы <tex> i </tex> на втором станке заканчивается раньше, чем работы <tex> j </tex> на первом.  В этом случае <tex> w_{ij} = p_{i1} + p_{j1} + p_{j2}  </tex>. </li>
+*: Тогда  <tex> w_{ij} = p_{i1} + p_{i2} + p_{j2} </tex>.
 </ul>
 </li>
 <li>Работа <tex> i </tex> не может  начаться на втором станке сразу же после завершения ее на первом
-<ul>
-<li> Выполнение работы <tex> i </tex> на втором станке заканчивается раньше, чем работы <tex> j </tex> на первом.  В этом случае  снова имеем <tex> w_{ij} = p_{i1} + p_{j1} + p_{j2}  </tex>.</li>
+* Выполнение работы <tex> i </tex> на втором станке заканчивается раньше, чем работы <tex> j </tex> на первом.
-<li> Выполнение работы <tex> i </tex> на втором станке заканчивается позже, чем работы <tex> j </tex> на первом.  Пусть <tex> delta </tex> {{---}} время прошедшее с начала выполнения работы <tex> i</tex> на первом станке и до начала ее выполнения на втором станке. Тогда имеем, что <tex> w_{ij} = delta + p_{i2} + p_{j2} </tex>. </li>
+*: Здесь снова имеем <tex> w_{ij} = p_{i1} + p_{j1} + p_{j2}  </tex>.
-</ul>
+* Выполнение работы <tex> i </tex> на втором станке заканчивается позже, чем работы <tex> j </tex> на первом.
 </li>
 </ol>
-Таким образом, <tex> w_{ij} = \max (p_{i1} + p_{j1} + p_{j2}, p_{i1} + p_{i2} + p_{j2}, delta + p_{i2} + p_{j2}) </tex>. Иначе говоря   <tex> w_{ij} = \max (p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2}, delta + p_{i2} + p_{j2}) </tex>.
+Таким образом, <tex> w_{ij} = \max (p_{i1} + p_{j1} + p_{j2}, p_{i1} + p_{i2} + p_{j2}, \Delta + p_{i2} + p_{j2}) </tex>.
-Аналогично имеем, что <tex> w_{ji} = \max (p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2},  delta + p_{i2} + p_{j2}) </tex>
+Аналогично,  <tex> w_{ji} = \max (p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2},  \Delta + p_{i2} + p_{j2}) </tex>
-Так как <tex> \min(a, b) = - \max(-a, -b)</tex>, то из условия леммы имеем <tex> \max(-p_{i1}, -p_{j2}) \leqslant   \max(-p_{j1}, -p_{i2}) </tex>, то добавим <tex> p_{i1} + p_{i2} + p_{j1} + p_{j2} </tex> к обеим частям. То получим, что <tex> p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2} \leqslant p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2} </tex>, то есть <tex> w_{ji} \leqslant w_{ij} </tex>, то при смене местами работ <tex> i </tex> и <tex> j </tex> ответ не ухудшается.
+Так как <tex> \min(a, b) = - \max(-a, -b)</tex>, то из условия леммы имеем <tex> \max(-p_{i1}, -p_{j2}) \leqslant   \max(-p_{j1}, -p_{i2}) </tex>. Добавим <tex> p_{i1} + p_{i2} + p_{j1} + p_{j2} </tex> к обеим частям. Получим, что <tex> p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2} \leqslant p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2} </tex>, то есть <tex> w_{ji} \leqslant w_{ij} </tex> и при смене местами работ <tex> i </tex> и <tex> j </tex> ответ не ухудшается.
 }}
@@ Строка 95: / Строка 101: @@
 ==Псевдокод==
-    '''function''' F2Cmax(n: '''int''', p: '''int'''[i][2]):
+    '''function''' F2Cmax(n: '''int''', p: '''int'''[n][2]): '''list'''
-       L = <tex>\varnothing </tex>
+       '''list''' L = <tex>\varnothing </tex>
-       R = <tex>\varnothing </tex>
+       '''list''' R = <tex>\varnothing </tex>
-       X = <tex>\{1, \dots, n\}</tex>
+       '''set''' X = <tex>\{1, \dots, n\}</tex>
-       '''while'''  X <tex> \neq \varnothing</tex>:
+       '''while'''  X <tex> \neq \varnothing</tex>
           Найти i  и j , такие что <tex>p_{ij} = \min \{ p_{ij}  \mid i \in X; j = 1, 2\}</tex>
-          '''if''' j == 1:
+          '''if''' j == 1
              L.addLast(i)
-          '''else''':
+          '''else'''
              R.addFirst(i)
           X.remove(i)
-       T = L + R
+       '''list''' T = L + R
        '''return''' T
 ==Сложность алгоритма==
-Заметим, что на каждом шаге алгоритма мы выбираем минимум из оставшихся элементов за <tex>O(\log n)</tex> (либо предварительной сортировкой, либо любой структурой данных, поддерживающей нахождение минимума и удаление за <tex>O(\log n)</tex>). И делаем мы это <tex> n </tex> раз, следовательно алгоритм работает за <tex>O(n\log n)</tex>.
+Заметим, что на каждом шаге алгоритма мы выбираем минимум из оставшихся элементов за <tex>O(\log n)</tex> (либо предварительной [[Сортировка|сортировкой]], либо  с помощью любой структуры данных, поддерживающей нахождение минимума и удаление за <tex>O(\log n)</tex>, например [[Двоичная_куча|кучи]]). А так как мы делаем  это <tex> n </tex> раз, алгоритм работает за <tex>O(n\log n)</tex>.
-==Источники==
+==Источники информации==
 * Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 175 стр. {{---}} ISBN 978-3-540-69515-8
-[[Категория: Дискретная математика и алгоритмы]]
+[[Категория: Алгоритмы и структуры данных]]
 [[Категория: Теория расписаний]]

@@ Строка 1: / Строка 1: @@
 {{Задача
 |definition=Рассмотрим задачу:
-*Дано <tex>n</tex> работ и <tex>2</tex> станка.
+*дано <tex>n</tex> работ и <tex>2</tex> станка,
-*Для каждой работы известно её время выполнения на каждом станке <tex>p_{ij}</tex>.
+*для каждой работы известно её время выполнения на каждом станке <tex>p_{ij}</tex>,
-*Каждую работу необходимо выполнить сначала на первом станке, а потом на втором
+*каждую работу необходимо выполнить сначала на первом станке, а потом на втором.
 Требуется минимизировать время окончания выполнения всех работ. }}
@@ Строка 10: / Строка 11: @@
 Пусть <tex>p_{i1}</tex> {{---}} время выполнения <tex>i</tex>-ой работы на первом станке, а <tex>p_{i2}</tex> {{---}} на втором.<br/>
 <ol>
-<li>Будем в ходе нашего алгоритма строить два списка <tex> L </tex> и <tex>  R </tex>. Изначально оба списка пусты. И будем поддерживать множество еще не распределенных по спискам <tex> L </tex> и <tex>  R </tex> работ <tex>X = \{i \mid  i = 1, \dots, n\}</tex>  </li>
+<li>Алгоритм строит два списка <tex> L </tex> и <tex>  R </tex>. Изначально они пусты. Также поддерживается множество еще не распределенных по спискам <tex> L </tex> и <tex>  R </tex> работ <tex>X = \{i \mid  i = 1, \dots, n\}</tex>  </li>
-<li> Пока множество <tex> X </tex> не пусто, будем распределять работы по спискам следующим образом:
+<li> Пока множество <tex> X </tex> не пусто, распределяем работы по спискам следующим образом:
 <ul>
 <li> Находим такие индексы <tex> i </tex> и <tex> j </tex>, что  <tex>p_{ij} = \min \{ p_{ij}  \mid i \in X; j = 1, 2\}</tex> </li>
@@ Строка 18: / Строка 19: @@
 </ul>
 </li>
-<li> Рассмотрим список <tex> T = L \circ R</tex>. Утверждается, что этот список является оптимальной перестановкой работ как на первом, так и на втором станке. Далее расставляем подряд работы на первом станке согласно перестановке, после чего ставим в том же порядке работы на втором станке, при этом избегая одновременного выполнения одной и той же работы. </li>
+<li> Рассмотрим список <tex> T = L + R</tex> - конкатенацию <tex> L</tex> и <tex>R</tex>. Утверждается, что этот список является оптимальной перестановкой работ как на первом, так и на втором станке. Далее расставляем подряд работы на первом станке согласно перестановке, после чего ставим в том же порядке работы на втором станке, при этом избегая одновременного выполнения одной и той же работы. </li>
 </ol>
@@ Строка 29: / Строка 30: @@
 |proof=
 [[Файл:f2cmax_first_fixed.png|400px|thumb|right|Рис. 1]]
-Предположим обратное: что не существует оптимального расписания с одинаковыми перестановками работ на станках. Рассмотрим некоторое оптимальное расписание с максимальным по длине общим префиксом на станках.
+Предположим обратное: что не существует оптимального расписания с одинаковыми перестановками работ на станках.
 Рассмотрим некоторое оптимальное расписание с максимальным по длине общим префиксом на станках. Пусть его длина равна <tex> k </tex>, где <tex> k < n </tex>. Пусть на <tex> k </tex> позиции на первом и втором станках стоит работа <tex> i </tex>, а на втором станке на позиции <tex> k + 1 </tex> стоит работа <tex> j </tex>. Тогда заметим, что если мы поставим работу <tex> j </tex> на первом станке сразу после работы <tex> i </tex>, то последовательные работы с <tex> h </tex> по <tex> m </tex> (см. Рис. 1) по-прежнему будут успевать выполниться, так как на втором станке они выполняются в текущем расписании после <tex> j </tex>. Таким образом нам удалось увеличить длину наибольшего общего префикса, а так как по нашему предположению она была максимальна, то наше предположение неверно, то искомое расписание с одинаковым порядком выполнения работ на обоих станках существует.
 }}
-Таким образом задача сводится к поиску этой искомой перестановки.  Докажем, что полученный нашим алгоритмом список является оптимальной перестановкой работ.
+Таким образом задача сводится к поиску этой искомой перестановки.  Докажем, что полученный приведенным выше алгоритмом список является оптимальной перестановкой работ.
 {{лемма
 |id=lemma1
 |about=1
-|statement= Если для каких-то работ <tex> i </tex> и <tex> j </tex> из списка <tex> T </tex> верно неравенство <tex> \min(p_{i1}, p_{j2}) <   \min(p_{j1}, p_{i2}) </tex>, то работа <tex> i </tex> встречается в списке <tex> T </tex> раньше, чем <tex> j </tex>
+|statement= Если для каких-то работ <tex> i </tex> и <tex> j </tex> из списка <tex> T </tex> верно неравенство <tex> \min(p_{i1}, p_{j2}) <   \min(p_{j1}, p_{i2}) </tex>, то работа <tex> i </tex> встречается в списке <tex> T </tex> раньше, чем <tex> j </tex>.
 |proof=
 Пусть <tex> p_{i1} < p_{j2} </tex>. Случай <tex> p_{i1} > p_{j2} </tex> рассматривается аналогично.
-То есть имеем, что <tex> p_{i1} < \min(p_{j1}, p_{i2}) </tex>. Так как <tex> p_{i1} < \min(p_{j1}, p_{i2}) \leqslant p_{i2} </tex>, то работа <tex> i \in L </tex>. Работа <tex> j </tex> либо стоит в <tex> R </tex>, либо она стоит в <tex> L </tex> и при этом <tex> p_{i1} < p_{j1} </tex>. Заметим, что в обоих случаях она расположена позже (в силу нашего построения), чем работа <tex> i </tex>, то лемма доказана.
+Так как <tex> p_{i1} < \min(p_{j1}, p_{i2}) \leqslant p_{i2} </tex>, то работа <tex> i \in L </tex>. Работа <tex> j </tex> либо стоит в <tex> R </tex>, либо она стоит в <tex> L </tex> и при этом <tex> p_{i1} < p_{j1} </tex>. Заметим, что в обоих случаях она расположена позже (в силу нашего построения), чем работа <tex> i </tex>.
 }}