1pi=1wirisumwi(ci - pi -ri) - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:23:13Z

rollbackEdits.php mass rollback

185.220.101.186 в 05:06, 1 сентября 2022

2022-09-01T05:06:00Z

Dimitrova: Удалено содержимое страницы

2012-06-18T21:52:10Z

Удалено содержимое страницы

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

2012-06-18T19:27:25Z

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

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

2012-06-18T19:25:31Z

‎Псевдокод

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

2012-06-18T18:54:18Z

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

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

2012-06-18T18:53:08Z

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

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

2012-06-18T18:50:24Z

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

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

2012-06-18T18:49:58Z

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

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

2012-06-18T17:27:57Z

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

← Предыдущая		Версия 16:23, 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 Майкл Наки].
−	\|}

← Предыдущая	Версия 05:06, 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 Майкл Наки].
	+	\|}

← Предыдущая		Версия 21:52, 18 июня 2012
Строка 1:		Строка 1:
−	~~==Постановка задачи==~~
−	~~Рассмотрим задачу:~~
−	~~<ol>~~
−	~~<li>Дано <tex>n</tex> работ и один станок.</li>~~
−	<li>Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>.</li>
−	~~</ol>~~
−	~~Требуется выполнить все работы, чтобы значение <tex>\sum w_{i}(c_{i} - p_{i} - r_{i})</tex> было минимальным.~~

−	~~==Описание алгоритма==~~
−	~~Пусть <tex>time</tex> {{---}} текущий момент времени.<br/>~~
−	Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:
−	~~<ol>~~
−	<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li>
−	<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li>
−	~~<li> Увеличиваем <tex>time</tex> на один.</li>~~
−	~~</ol>~~
−
−	~~==Доказательство корректности алгоритма==~~
−	~~{{Теорема~~
−	~~\|statement=~~
−	~~Расписание, построенное данным алгоритмом, является корректным и оптимальным.~~
−	~~\|proof=~~
−	~~Доказательство будем вести от противного.<br/>~~
−	Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/>
−	Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/>
−	Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/>
−	Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/>
−	~~При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на~~
−	~~<ul><tex>(t_{1} - r_{2})w_{2} + (t_{2} - r_{1})w_{1} - ((t_{1} - r_{1})w_{1} + (t_{2} - r_{2})w_{2}) = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul>~~
−	Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/>
−	Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.
−	}}
−
−	~~==Псевдокод==~~
−	~~<tex> S \leftarrow \{1 \dots n\}</tex>~~
−	~~<tex> time \leftarrow 0</tex>~~
−	~~<tex> answer \leftarrow 0</tex>~~
−	~~while <tex> S \neq \varnothing </tex>~~
−	~~<tex> j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})</tex>~~
−	~~if <tex>j \neq null </tex>~~
−	~~<tex> S \leftarrow S \setminus j</tex>~~
−	~~<tex> Answer \leftarrow Answer + (time - r_{j})w_{j}</tex>~~
−	~~<tex> time++</tex>~~
−
−	~~==Сложность алгоритма==~~
−	Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex>

@@ Строка 9: / Строка 9: @@
 ==Описание алгоритма==
 Пусть <tex>time</tex> {{---}} текущий момент времени.<br/>
-Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последний работы, будем:
+Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:
 <ol>
-<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex> и значение <tex>w_{i}</tex> максимально.</li>
+<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li>
-<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex></li>
+<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li>
 <li> Увеличиваем <tex>time</tex> на один.</li>
 </ol>

← Предыдущая		Версия 19:25, 18 июня 2012
Строка 33:		Строка 33:

	==Псевдокод==		==Псевдокод==
		+	<tex> S \leftarrow \{1 \dots n\}</tex>
		+	<tex> time \leftarrow 0</tex>
		+	<tex> answer \leftarrow 0</tex>
		+	while <tex> S \neq \varnothing </tex>
		+	<tex> j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})</tex>
		+	if <tex>j \neq null </tex>
		+	<tex> S \leftarrow S \setminus j</tex>
		+	<tex> Answer \leftarrow Answer + (time - r_{j})w_{j}</tex>
		+	<tex> time++</tex>
		+
		+	==Сложность алгоритма==
		+	Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex>

← Предыдущая		Версия 18:54, 18 июня 2012
Строка 31:		Строка 31:
	Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.		Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.
	}}		}}
		+
		+	==Псевдокод==

@@ Строка 17: / Строка 17: @@
 ==Доказательство корректности алгоритма==
-Докажем, что алгоритм оптимален. Доказательство будем вести от противного.<br/>
+{{Теорема
 Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/>
 Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания  различаются. Пусть в этот момент времени  в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/>
@@ Строка 26: / Строка 30: @@
 Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/>
 Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.

← Предыдущая		Версия 18:49, 18 июня 2012
Строка 17:		Строка 17:

	==Доказательство корректности алгоритма==		==Доказательство корректности алгоритма==
		+	Докажем, что алгоритм оптимален. Доказательство будем вести от противного.<br/>
		+	Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/>
		+	Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/>
		+	Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/>
		+	Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/>
		+	При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на
		+	<ul><tex>(t_{1} - r_{2})w_{2} + (t_{2} - r_{1})w_{1} - ((t_{1} - r_{1})w_{1} + (t_{2} - r_{2})w_{2}) = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul>
		+	Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/>
		+	Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.

@@ Строка 12: / Строка 12: @@
 <ol>
 <li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex> и значение <tex>w_{i}(time - r_{i})</tex> максимально.</li>
-<li> Выполняем <tex>j</tex> в момент времени <tex>time</tex> и увеличиваем <tex>time</tex> на один.
+<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex></li>
 </ol>
 ==Доказательство корректности алгоритма==