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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:06:01Z

rollbackEdits.php mass rollback

141.98.9.47 в 06:33, 1 сентября 2022

2022-09-01T06:33:38Z

Shersh: /* Время работы */

2016-06-07T19:23:18Z

‎Время работы

Shersh: /* Доказательство корректности алгоритма */

2016-06-07T19:22:50Z

‎Доказательство корректности алгоритма

Shersh: /* Псевдокод */

2016-06-07T19:22:07Z

‎Псевдокод

5.18.43.53: /* Псевдокод */

2016-06-07T19:20:22Z

‎Псевдокод

5.18.43.53 в 19:18, 7 июня 2016

2016-06-07T19:18:02Z

Внесённые изменения

5.18.43.53: /* Псевдокод */

2016-06-07T17:39:59Z

‎Псевдокод

Shersh: /* Описание алгоритма */

2016-06-07T17:07:20Z

‎Описание алгоритма

5.18.43.53: /* Доказательство корректности алгоритма */

2016-06-07T16:45:34Z

‎Доказательство корректности алгоритма

← Предыдущая		Версия 16:06, 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" >1 \mid\mid \sum w_i T_i</tex>		<tex dpi = "200" >1 \mid\mid \sum w_i T_i</tex>

← Предыдущая		Версия 06:33, 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" >1 \mid\mid \sum w_i T_i</tex>		<tex dpi = "200" >1 \mid\mid \sum w_i T_i</tex>

@@ Строка 96: / Строка 96: @@
 Пускай все времена выполнения работ различны. Тогда все множества работ, используемые в качестве аргументов рекурсивного вызова функции можно представить в виде <tex>\langle i, j, k \rangle : \{ v \mid i \leqslant v \leqslant j \wedge  p_v < p_k\}</tex>, <tex> i, j, k \in \{1, 2, \ldots, n\}</tex>.
-У нас максимум <tex> p = \sum\limits_{i=1}^n p_i</tex> различных значений <tex>t</tex>. Значит, мы вызовем <tex> \mathrm{sequence(t,I)}</tex> в худшем случае  <tex>\mathcal{O}(n^3p)</tex> раз. Более того, для фиксированного <tex>k</tex> все значения <tex>\max\{p_v \mid v \in I_{ijk}\}</tex> для  <tex>i, j = 1,\ldots, n,</tex>   <tex>i < j</tex> могут быть сосчитаны за <tex>\mathcal{O}(n^2)</tex>.
+У нас максимум <tex> p = \sum\limits_{i=1}^n p_i</tex> различных значений <tex>t</tex>. Значит, мы вызовем <tex> \mathrm{sequence}(t,I)</tex> в худшем случае  <tex>\mathcal{O}(n^3p)</tex> раз. Более того, для фиксированного <tex>k</tex> все значения <tex>\max\{p_v \mid v \in I_{ijk}\}</tex> для  <tex>i, j = 1,\ldots, n,</tex>   <tex>i < j</tex> могут быть сосчитаны за <tex>\mathcal{O}(n^2)</tex>.
 Таким образом, мы получаем алгоритм, работающий за <tex>\mathcal{O}(n^3p)</tex> или <tex>\mathcal{O}(n^4p_{max})</tex>, где <tex>p_{max} = \max\limits_{i=1}^n p_i</tex>.

@@ Строка 53: / Строка 53: @@
 Рассмотрим 2 случая:
-# '''<tex>C_j</tex> <tex>\leqslant d_j</tex>. '''
+# <tex>C_j</tex> <tex>\leqslant d_j</tex>.
 #:Тогда <tex>C_j = \min\{d_j, C_j\}  \leqslant d'_j  \leqslant \max\{d_j, C_j\} = d_j </tex>, из чего следует <tex> w_j\max\{0, C_j ~$-$~ d_j\} = w_j\max\{0, C_j ~$-$~ d'_j\} = 0.</tex>
 #:<tex>C_j  \leqslant d'_j  \leqslant d_j  </tex>, и, учитывая <tex>C'_j \leqslant d'_j,  d'_j  C'_j \leqslant d_j</tex> и <tex>d_j \leqslant C'_j,</tex> получаем, что <tex>w_j \max\{0, C'_j ~$-$~ d_j\} = w_j\max\{0, C'_j ~$-$~ d'_j\} - w_j \max\{0, \min\{C'_j, d'_j\} ~$-$~ d_j\}  </tex>.
 #:<tex>A_j = 0  </tex>,
 #:<tex>B_j = w_j \max\{0, \min\{C'_j, d_j \} ~$-$~d'_j\} </tex>;
-# '''<tex>C_j \geqslant d_j</tex>. '''
+# <tex>C_j \geqslant d_j</tex>
 #:Тогда <tex>d_j = \min\{d_j, C_j\}  \leqslant d'_j  \leqslant \max\{d_j, C_j\} = C_j </tex>, из чего следует <tex> w_j\max\{0, C_j ~$-$~ d_j\} = w_j\max\{0, C_j ~$-$~ d'_j\} + w_j(d'_j ~$-$~ d_j). </tex>
 #:<tex>d_j  \leqslant d'_j  \leqslant C_j</tex> , получаем, что <tex>w_j \max\{0, C'_j ~$-$~ d_j\} = w_j\max\{0, C'_j ~$-$~ d'_j\} + w_j \max\{0, \min\{C'_j, d'_j\} ~$-$~ d_j\} </tex>.

@@ Строка 19: / Строка 19: @@
 Приведенный ниже алгоритм вычисляет оптимальную последовательность работ <tex>\pi</tex> для множества работ <tex>I = \{i_1, i_2,\ldots, i_r\}</tex> в начальный момент времени <tex>t</tex>.
-   '''function''' <tex>\mathrm{sequence}</tex> (<tex>t</tex>: '''int''', <tex>I</tex>: '''int[]'''): '''int[]'''
+   '''function''' <tex>\mathrm{sequence}</tex>(<tex>t</tex>: '''int''', <tex>I</tex>: '''int[]'''): '''int[]'''
      '''if''' <tex>I = \varnothing</tex>
        '''return''' <tex>\varnothing</tex>

@@ Строка 17: / Строка 17: @@
 Приведенный ниже алгоритм вычисляет оптимальную последовательность работ <tex>\pi</tex> для множества работ <tex>I = \{i_1, i_2,\ldots, i_r\}</tex> в начальный момент времени <tex>t</tex>.
-   '''function''' sequence(t: '''int''', I: '''int[]'''): '''int[]'''
+   '''function''' <tex>\mathrm{sequence} </tex>(t: '''int''', I: '''int[]'''): '''int[]'''
      '''if''' <tex>I = \varnothing</tex>
        '''return''' <tex>\varnothing</tex>
@@ Строка 25: / Строка 25: @@
        <tex>I_1 = \{i_v \mid 1 \leqslant v  \leqslant j \wedge  v \ne k\}</tex>
        <tex>t_1 = t </tex>
-       <tex>\pi_1 = sequence (t_1 , I_1 )</tex>
+       <tex>\pi_1 = \mathrm{sequence} (t_1 , I_1 )</tex>
        <tex>I_2 = \{i_v \mid j <  v  \leqslant r\}</tex>
        <tex>t_2 = t + \sum\limits_{v=1}^j p_{i_v}</tex>
-       <tex>\pi_2 = sequence(t_2 , I_2 )</tex>
+       <tex>\pi_2 = \mathrm{sequence}(t_2 , I_2 )</tex>
-       <tex>\pi = \pi_1  \cup  \{i_k\}  \cup \pi2</tex>
+       <tex>\pi = \pi_1  \cup  \{i_k\}  \cup \pi_2</tex>
        '''if''' <tex>f(\pi, t) < f^*</tex>
          <tex>f^* = f(\pi, t)</tex>
-     '''return''' <tex>\pi^*</tex>
+     '''return''' <tex>\pi</tex>
 ===Доказательство корректности алгоритма===

@@ Строка 10: / Строка 10: @@
 ===Описание алгоритма===
 Упорядочим работы в порядке неубывания дедлайнов. Обозначим за <tex>k</tex> работу с максимальным <tex>p_i</tex>. <br>
-Будем делить имеющиеся у нас работы на множества <tex> I_1, I_2</tex> так, чтобы для любого <tex>j \geqslant k</tex> <tex>I_1 = \{1,\ldots, j\}\setminus\{k\}</tex>, <tex>I_2 = \{j+1,\ldots, n\}</tex>. Тогда в оптимальном расписании все работы из <tex>I_1</tex> окажутся до <tex>k</tex>, а работы из <tex>I_2</tex> будут расположены после <tex>k</tex>. Для работ из <tex> I_1</tex> оптимальное время начала выполнения <tex>t_1 = 0</tex>, для работ из <tex>I_2</tex> оптимальное начало <tex>t_2 = p = \sum\limits_{i=1}^j p_i</tex>. Таким образом, для любой <tex>j</tex> задача разбивается на 2 подзадачи. <br>
+Будем делить имеющиеся у нас работы на множества <tex> I_1, I_2</tex> так, чтобы для любого <tex>j \geqslant k</tex> <tex>I_1 = \{1,\ldots, j\}\setminus\{k\}</tex>, <tex>I_2 = \{j+1,\ldots, n\}</tex>. Тогда в оптимальном расписании все работы из <tex>I_1</tex> окажутся до <tex>k</tex>, а работы из <tex>I_2</tex> будут расположены после <tex>k</tex>. Для работ из <tex> I_1</tex> оптимальное время начала выполнения <tex>t_1 = 0</tex>, для работ из <tex>I_2</tex> оптимальное начало <tex>t_2 = p = \sum\limits_{i=1}^j p_i</tex>. Таким образом, для любой <tex>j</tex> задача разбивается на две подзадачи. <br>
 Алгоритм вычисляет оптимальное расписание для всех работ рекурсивно.

@@ Строка 40: / Строка 40: @@
 |statement=
 Пусть <tex> \pi -</tex> любая оптимальная последовательность работ для данных дедлайнов <tex>d_1, d_2,\ldots, d_n</tex>, <tex>C_j -</tex>  время завершения выполнения <tex>j</tex>-ой работы.
-Рассмотрим <tex>d'_j</tex> такие, что <tex>\min\{d_j, C_j\}  \leqslant d'_j  \leqslant \max\{d_j, C_j\}. </tex>Тогда любая оптимальная последовательность работ для <tex> d_j</tex> будет оптимальна и для <tex>d'_j</tex>
+Рассмотрим <tex>d'_j</tex> такие, что <tex>\min\{d_j, C_j\}  \leqslant d'_j  \leqslant \max\{d_j, C_j\}. </tex>Тогда любая оптимальная последовательность работ для <tex> d_j</tex> будет оптимальна и для <tex>d'_j</tex>.
 |proof=
 <tex>T( \pi) = T′(\pi) + \sum\limits_{i=1}^n A_j</tex>, <br>
 <tex>T( \pi′) = T ′(\pi′) + \sum\limits_{i=1}^n B_j</tex>, <br>