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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:25:56Z

rollbackEdits.php mass rollback

103.251.167.21 в 05:01, 1 сентября 2022

2022-09-01T05:01:40Z

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

2012-06-20T22:22:22Z

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

217.66.152.134 в 22:18, 20 июня 2012

2012-06-20T22:18:29Z

217.66.152.134 в 22:06, 20 июня 2012

2012-06-20T22:06:36Z

Dimitrova: Новая страница: «==Постановка задачи== Рассмотрим задачу:

Дано n работ и один станок.

Для ка...»

2012-06-18T21:51:37Z

Новая страница: «==Постановка задачи== Рассмотрим задачу: <ol> <li>Дано <tex>n</tex> работ и один станок.</li> <li>Для ка...»

Новая страница

==Постановка задачи==
Рассмотрим задачу:
<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> {{---}} текущий момент времени. 
Для каждого очередного значения <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=
Доказательство будем вести от противного. 
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>. 
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>. 
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>. 
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>. 
При такой перестановке ответы на задачу для <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>. 
Итого имеем, что ответ для <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>

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

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

← Предыдущая		Версия 22:22, 20 июня 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}</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>
−
−	~~[[Категория: Дискретная математика и алгоритмы]]~~
−	~~[[Категория: Теория расписаний]]~~

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