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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:21:52Z

rollbackEdits.php mass rollback

194.26.192.187 в 05:23, 1 сентября 2022

2022-09-01T05:23:35Z

Анна: /* Псевдокод */

2016-05-07T14:55:20Z

‎Псевдокод

Анна в 14:47, 7 мая 2016

2016-05-07T14:47:21Z

Анна: /* Псевдокод */

2016-05-07T14:38:22Z

‎Псевдокод

Анна в 14:22, 7 мая 2016

2016-05-07T14:22:10Z

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

2016-05-07T14:20:02Z

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

Анна: /* Асимптотика */

2016-05-07T14:19:23Z

‎Асимптотика

Анна: /* Псевдокод */

2016-05-07T14:16:30Z

‎Псевдокод

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

2016-05-07T13:48:45Z

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

← Предыдущая		Версия 16:21, 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"> P \mid p_i=1 \mid \sum w_i U_i</tex>		<tex dpi = "200"> P \mid p_i=1 \mid \sum w_i U_i</tex>
	{{Задача		{{Задача

← Предыдущая		Версия 05:23, 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"> P \mid p_i=1 \mid \sum w_i U_i</tex>		<tex dpi = "200"> P \mid p_i=1 \mid \sum w_i U_i</tex>
	{{Задача		{{Задача

@@ Строка 9: / Строка 9: @@
 === Псевдокод ===
-Пусть есть работы <tex>1 \ldots n</tex> с временами окончания <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Будем называть ''простоем '' временной интервал, в который на машине ничего не обрабатывается. Для определения работ, не укладывающихся в срок, заведем счетчик времени <tex>t</tex>, который будем модифицировать так, как показано ниже. Тогда работа <tex>j</tex> опаздывает, если <tex>\left[ \dfrac{t}{m} \right] + p_j > d_j</tex>, где <tex>p_j = 1</tex>. Следующий алгоритм вычислит оптимальное множество <tex>S</tex>.
+Пусть есть работы <tex>1 \ldots n</tex> с временами окончания <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Будем называть ''простоем '' временной интервал, в который на машине ничего не обрабатывается. Для определения работ, не укладывающихся в срок, заведем счетчик времени <tex>t</tex>, который будем модифицировать так, как показано ниже. Тогда работа <tex>j</tex> опаздывает, если <tex>\left\lfloor \dfrac{t}{m} \right\rfloor + p_j > d_j</tex>, где <tex>p_j = 1</tex>. Следующий алгоритм вычислит оптимальное множество <tex>S</tex>.
     <tex>S = \varnothing</tex>

@@ Строка 35: / Строка 35: @@
 * <tex>l</tex> {{---}} первая работа в <tex>S</tex>: <tex>l \notin S^*</tex>
 * <tex>k</tex> {{---}} первая работа в <tex>S^*</tex>: <tex>k \notin S</tex>
-Покажем, что в <tex>S^*</tex> работа <tex>k</tex> может быть заменена работой <tex>l</tex> без увеличения значения целевой функции. Рассмотрим два случая:<br>
+Покажем, что в <tex>S^*</tex> работа <tex>k</tex> может быть заменена работой <tex>l</tex> без увеличения значения целевой функции. Рассмотрим два случая:
-# Пусть <tex>l < k</tex>.<br>
+# Пусть <tex>l < k</tex>.
-#:То, что <tex>k</tex> не принадлежит множеству <tex>S</tex>, значит, что либо на некотором шаге появилась опаздывающая работа <tex>j</tex>, которая заменила <tex>k</tex>, либо работа <tex>k</tex> опаздывала и <tex>w_k</tex> было меньше <tex>\min\limits_{i \in S}w_i</tex>, и поэтому она не была добавлена. В любом случае в это время работа <tex>l</tex> уже принадлежала <tex>S</tex>. Во втором случае очевидно, что <tex>w_k \leqslant w_l</tex>. То же неравенство выполняется и в первом случае, так как на этапе замены мы выбрали <tex>k</tex>, а не <tex>l</tex>. Следовательно, мы не ухудшим целевую функцию заменой <tex>k</tex> на <tex>l</tex>.<br>
+#:То, что <tex>k</tex> не принадлежит множеству <tex>S</tex>, значит, что либо на некотором шаге появилась опаздывающая работа <tex>j</tex>, которая заменила <tex>k</tex>, либо работа <tex>k</tex> опаздывала и <tex>w_k</tex> было меньше <tex>\min\limits_{i \in S}w_i</tex>, и поэтому она не была добавлена. В любом случае в это время работа <tex>l</tex> уже принадлежала <tex>S</tex>. Во втором случае очевидно, что <tex>w_k \leqslant w_l</tex>. То же неравенство выполняется и в первом случае, так как на этапе замены мы выбрали <tex>k</tex>, а не <tex>l</tex>. Следовательно, мы не ухудшим целевую функцию заменой <tex>k</tex> на <tex>l</tex>.
-# Пусть <tex>l > k</tex>.<br>
+# Пусть <tex>l > k</tex>.
-#:Замена работы <tex>k</tex> в <tex>S^*</tex> на работу <tex>l</tex> не противоречит условию, что за все работы в этом множестве штраф налагаться не будет, так как <tex>k</tex> выполнялась в срок, а <tex>d_k \leqslant d_l</tex> и все работы выполняются одинаковое количество времени. Следовательно, <tex>l</tex> так же будет выполнена в срок. Осталось доказать, что <tex>w_k \leqslant w_l</tex>. <br>
+#:Замена работы <tex>k</tex> в <tex>S^*</tex> на работу <tex>l</tex> не противоречит условию, что за все работы в этом множестве штраф налагаться не будет, так как <tex>k</tex> выполнялась в срок, а <tex>d_k \leqslant d_l</tex> и все работы выполняются одинаковое количество времени. Следовательно, <tex>l</tex> так же будет выполнена в срок. Осталось доказать, что <tex>w_k \leqslant w_l</tex>.
-#:Пусть работа <tex>k_{i_0} = k</tex> была заменена работой <tex>i_0</tex>, а так же <tex>k_{i_1} \ldots k_{i_r}</tex> {{---}} последовательность работ из <tex>S</tex>, каждая из которых была на некотором шаге заменена работой <tex>i_1 \ldots i_r</tex> соответственно. Тогда <tex>i_0 < i_1 < \ldots < i_r</tex>.<br>
+#:Пусть работа <tex>k_{i_0} = k</tex> была заменена работой <tex>i_0</tex>, а так же <tex>k_{i_1} \ldots k_{i_r}</tex> {{---}} последовательность работ из <tex>S</tex>, каждая из которых была на некотором шаге заменена работой <tex>i_1 \ldots i_r</tex> соответственно. Тогда <tex>i_0 < i_1 < \ldots < i_r</tex>.
 #:[[Файл:Sh.jpg|370px|thumb|right|Рис. 1. <tex>i_v</tex> превосходит <tex>i_u</tex>.]]
-#:Будем говорить <tex>i_v</tex> ''превосходит'' <tex>i_u</tex>, где <tex>u < v</tex>, если <tex>k_{i_v} \leqslant i_u</tex>. Тогда <tex>w_{k_{i_v}} \geqslant w_{k_{i_u}}</tex>, так как когда мы вставляли работу <tex>i_u</tex> мы выбрали для замены <tex>k_{i_u}</tex>, то есть ее вес был минимальным среди всех работ, находившихся на тот момент в <tex>S</tex>, включая <tex>k_{i_v}</tex>. Для большей ясности на рисунке 1 показано, в каком порядке располагаются эти работы относительно друг друга согласно их номерам.<br>
+#:Будем говорить <tex>i_v</tex> ''превосходит'' <tex>i_u</tex>, где <tex>u < v</tex>, если <tex>k_{i_v} \leqslant i_u</tex>. Тогда <tex>w_{k_{i_v}} \geqslant w_{k_{i_u}}</tex>, так как когда мы вставляли работу <tex>i_u</tex> мы выбрали для замены <tex>k_{i_u}</tex>, то есть ее вес был минимальным среди всех работ, находившихся на тот момент в <tex>S</tex>, включая <tex>k_{i_v}</tex>. Для большей ясности на рисунке 1 показано, в каком порядке располагаются эти работы относительно друг друга согласно их номерам.
 #:Если из последовательности <tex>i_0 < i_1 < \ldots < i_r</tex> можно выделить подпоследовательность <tex>j_0 = i_0 < j_1 < \ldots < j_s</tex> со свойствами:
 #:* <tex>j_{v + 1}</tex> превосходит <tex>j_v</tex>, где <tex>v \in [0 \ldots s - 1]</tex>
 #:* <tex>j_{s - 1} < l \leqslant j_s</tex> ,
-#:то <tex>w_l \geqslant w_{k_{j_s}} \geqslant \ldots \geqslant w_{k_{j_0}} = w_k</tex>, что доказывает теорему.<br>
+#:то <tex>w_l \geqslant w_{k_{j_s}} \geqslant \ldots \geqslant w_{k_{j_0}} = w_k</tex>, что доказывает теорему.
-#:В противном случае найдем такую работу <tex>i_t</tex> с наименьшим <tex>t</tex>, что никакая работа <tex>i_v</tex>, где <tex>v > t</tex>, не превосходит <tex>i_t</tex>, причем <tex>i_t < l</tex>. По определению это значит, что после того, как работа <tex>i_t</tex> будет добавлена в <tex>S</tex>, ни одна работа <tex>i \leqslant i_t</tex> не будет удалена из этого множества. Так как <tex>i_t < l</tex>, то по определению <tex>l</tex> все работы, которые на момент добавления <tex>i_t</tex> находятся в <tex>S</tex>, так же должны принадлежать <tex>S^*</tex>. Покажем, что это приведет нас к противоречию.<br>
+#:В противном случае найдем такую работу <tex>i_t</tex> с наименьшим <tex>t</tex>, что никакая работа <tex>i_v</tex>, где <tex>v > t</tex>, не превосходит <tex>i_t</tex>, причем <tex>i_t < l</tex>. По определению это значит, что после того, как работа <tex>i_t</tex> будет добавлена в <tex>S</tex>, ни одна работа <tex>i \leqslant i_t</tex> не будет удалена из этого множества. Так как <tex>i_t < l</tex>, то по определению <tex>l</tex> все работы, которые на момент добавления <tex>i_t</tex> находятся в <tex>S</tex>, так же должны принадлежать <tex>S^*</tex>. Покажем, что это приведет нас к противоречию.
-#:Пусть <tex>S_t</tex> {{---}} множество <tex>S</tex> после удаления <tex>k_{i_t}</tex> и добавления <tex>i_t</tex>. Рассмотрим два случая:<br>
+#:Пусть <tex>S_t</tex> {{---}} множество <tex>S</tex> после удаления <tex>k_{i_t}</tex> и добавления <tex>i_t</tex>. Рассмотрим два случая:
 #::<tex>(a)</tex> Если <tex>k^* = k_{i_t} > k</tex>, то есть <tex>d_{k^*} \geqslant d_k</tex>, то мы можем заменить <tex>k</tex> на <tex>k^*</tex> в <tex>S^*</tex>, сохранив условие, что <tex>S^*</tex> не содержит опаздывающих работ. Следовательно, множество <tex>S_t \cup \{k^*\}</tex> не содержит работ со штрафами, что противоречит построению <tex>S</tex>.
 #::<tex>(b)</tex> Пусть <tex>k^* < k</tex>. Тогда все работы из <tex>S_t \cup \{k\}</tex> могут быть выполнены в срок, так как <tex>S_t</tex> и <tex>k</tex> принадлежат <tex>S^*</tex>. Более того, все работы из множества <tex>\{j \in S_t \mid j < k\}</tex> могут быть выполнены без опозданий. Таким образом, мы снова приходим к тому, что множество <tex>S_t \cup \{k^*\}</tex> не содержит работ со штрафами, что является противоречием.

@@ Строка 9: / Строка 9: @@
 === Псевдокод ===
-Пусть есть работы <tex>1 \ldots n</tex> с временами окончания <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Будем называть ''простоем '' временной интервал, в который на машине ничего не обрабатывается. Тогда следующий алгоритм вычислит оптимальное множество <tex>S</tex>.
+Пусть есть работы <tex>1 \ldots n</tex> с временами окончания <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Будем называть ''простоем '' временной интервал, в который на машине ничего не обрабатывается. Для определения работ, не укладывающихся в срок, заведем счетчик времени <tex>t</tex>, который будем модифицировать так, как показано ниже. Тогда работа <tex>j</tex> опаздывает, если <tex>\left[ \dfrac{t}{m} \right] + p_j > d_j</tex>, где <tex>p_j = 1</tex>. Следующий алгоритм вычислит оптимальное множество <tex>S</tex>.
     <tex>S = \varnothing</tex>
     '''for''' <tex>j = 1</tex> '''to''' <tex>n</tex>
        '''if''' <tex>j</tex> опаздывает, и все более ранние простои заполнены
@@ Строка 18: / Строка 19: @@
              заменить <tex>i</tex> на <tex>j</tex> в <tex>S</tex>
        '''else'''
           добавить <tex>i</tex> в <tex>S</tex> и поставить <tex>i</tex> на место самого раннего простоя
 Таким образом, работы, не попавшие в <tex>S</tex>, будут иметь минимальное значение <tex>w_i</tex>.

@@ Строка 6: / Строка 6: @@
 == Описание алгоритма ==
 === Идея ===
-Оптимальное расписание для этой задачи будем задавать множеством работ <tex>S</tex>, которые будут выполнены в срок. Работы, которые не войдут в <tex>S</tex>, то есть завершатся с опозданием, могут быть выполнены в конце в любом порядке.<br>
+Оптимальное расписание для этой задачи будем задавать множеством работ <tex>S</tex>, которые будут выполнены в срок. Работы, которые не войдут в <tex>S</tex>, то есть завершатся с опозданием, могут быть выполнены в конце в любом порядке. Чтобы построить множество <tex>S</tex>, будем добавлять работы в порядке неуменьшения их времен окончания, и как только некоторая работа <tex>j</tex> опаздывает, удалим из <tex>S</tex> работу <tex>i</tex> с минимальным значением <tex>w_i</tex> и поставим <tex>j</tex> на ее место.
 === Псевдокод ===
@@ Строка 32: / Строка 31: @@
 |proof=
 Пусть <tex>S</tex> {{---}} множество работ, вычисленное с помощью алгоритма. Тогда все работы, находящиеся в этом множестве, будут выполнены в срок, то есть штраф за них налагаться не будет, так как если работа <tex>j</tex> заменила работу <tex>i</tex>, которая успевала выполниться до истечения <tex>d_i</tex>, то <tex>j</tex> так же успеет выполниться в срок, потому что <tex>d_i \leqslant d_j</tex>.<br>
-Пусть <tex>S^*</tex> {{---}} множество работ без штрафов в оптимальном расписании.<br>
+Пусть <tex>S^*</tex> {{---}} множество работ без штрафов в оптимальном расписании. Определим работы <tex>l</tex> и <tex>k</tex> следующим образом:
 * <tex>l</tex> {{---}} первая работа в <tex>S</tex>: <tex>l \notin S^*</tex>
 * <tex>k</tex> {{---}} первая работа в <tex>S^*</tex>: <tex>k \notin S</tex>

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