0-1 принцип - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:35:32Z

rollbackEdits.php mass rollback

185.220.100.254 в 04:08, 1 сентября 2022

2022-09-01T04:08:36Z

Kamensky: Remove space in LaTeX token

2017-05-22T05:29:22Z

Remove space in LaTeX token

217.66.156.118 в 05:28, 8 июня 2015

2015-06-08T05:28:04Z

217.66.156.118: /* Источники */

2015-06-08T05:24:15Z

‎Источники

217.66.156.118: /* Доказательство 0-1 принципа */

2015-06-08T05:21:19Z

‎Доказательство 0-1 принципа

217.66.156.118: /* Доказательство 0-1 принципа */

2015-06-08T05:20:09Z

‎Доказательство 0-1 принципа

217.66.156.118: /* Первый способ */

2015-06-08T05:17:38Z

‎Первый способ

77.241.45.30 в 13:29, 7 июня 2012

2012-06-07T13:29:00Z

77.241.45.30: /* Доказательство 0-1 принципа */

2012-05-31T19:51:04Z

‎Доказательство 0-1 принципа

← Предыдущая		Версия 16:35, 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>n</tex> компараторов на то, что она сортирующая.		Есть два способа проверить сеть из <tex>n</tex> компараторов на то, что она сортирующая.

← Предыдущая		Версия 04:08, 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>n</tex> компараторов на то, что она сортирующая.		Есть два способа проверить сеть из <tex>n</tex> компараторов на то, что она сортирующая.

@@ Строка 19: / Строка 19: @@
 Пусть <tex> f: A \rightarrow B </tex> — монотонная. Тогда <tex> \forall a_1, a_2 \in A: f(\min(a_1, a_2)) = \min(f(a_1), f(a_2)) </tex>.
 | proof =
-Не теряя общности, предположим что <tex> a_1 \ leqslant a_2 </tex>. Тогда <tex> f(\min(a_1, a_2)) = f(a_1) </tex>. Также, по монотонности, <tex> f(a_1) \leqslant f(a_2) </tex>. Тогда <tex> \min(f(a_1), f(a_2)) = f(a_1) </tex>. То есть,
+Не теряя общности, предположим что <tex> a_1 \leqslant a_2 </tex>. Тогда <tex> f(\min(a_1, a_2)) = f(a_1) </tex>. Также, по монотонности, <tex> f(a_1) \leqslant f(a_2) </tex>. Тогда <tex> \min(f(a_1), f(a_2)) = f(a_1) </tex>. То есть,
 <tex> f(\min(a_1, a_2)) = \min(f(a_1), f(a_2)) = f(a_1) </tex>. Такие же рассуждения можно провести для случая <tex> a_2 < a_1 </tex>.

@@ Строка 60: / Строка 60: @@
 }}
-== Источники информации==
+== См. также ==
 *[http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/networks/indexen.htm Bachelor-Studiengang Angewandte Informatik {{---}} Sorting networks]
 *[http://en.wikipedia.org/wiki/Sorting_network Wikipedia {{---}} Sorting networks]

@@ Строка 60: / Строка 60: @@
 }}
-== Источники ==
+== Источники информации==
-*[http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/networks/indexen.htm Sorting networks]
+*[http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/networks/indexen.htm Bachelor-Studiengang Angewandte Informatik {{---}} Sorting networks]
-*[http://en.wikipedia.org/wiki/Sorting_network Wikipedia — Sorting networks]
+*[http://en.wikipedia.org/wiki/Sorting_network Wikipedia {{---}} Sorting networks]
-*Дональд Кнут — Искусство программирования — Том 3 — Глава 5.3.4 — стр. 249
+*Дональд Кнут {{---}} Искусство программирования {{---}} Том 3 {{---}} Глава 5.3.4 {{---}} стр. 249
 [[Категория:Дискретная математика и алгоритмы]]
 [[Категория:Сортирующие сети]]

@@ Строка 12: / Строка 12: @@
 {{ Определение
 | definition =
-Функция <tex> f: A \rightarrow B </tex> называется '''монотонной''', если <tex> \forall a_1, a_2 \in A : a_1 \leqslant a_2 \Rightarrow f(a_1) \leqslant f(a_2) </tex>
+Функция <tex> f: A \rightarrow B </tex> называется '''монотонной''' (англ. ''monotonous''), если <tex> \forall a_1, a_2 \in A : a_1 \leqslant a_2 \Rightarrow f(a_1) \leqslant f(a_2) </tex>
 }}

@@ Строка 4: / Строка 4: @@
 == Первый способ ==
-Первый, наивный способ — перебрать все перестановки из <tex> n </tex> элементов, пропустить их через сеть и проверить их на то, что они отсортированы. Этот подход потребует <tex> O(n! \cdot Comp(n)) </tex> действий, где <tex> Comp(n) </tex> — количество компараторов в сети из <tex>n</tex> элементов. Обычно это количество можно оценить как <tex> n \log^2n </tex> ([[Сеть_Бетчера|Сеть Бетчера]]). Таким образом, получаем асимптотику <tex> O(n!n \log^2n) </tex>, и при <tex>n = 10</tex> проверить сеть очень проблематично.
+Первый, наивный способ — перебрать все перестановки из <tex> n </tex> элементов, пропустить их через сеть и проверить их на то, что они отсортированы. Этот подход потребует <tex> O(n! \cdot Comp(n)) </tex> действий, где <tex> Comp(n) </tex> — количество компараторов в сети из <tex>n</tex> элементов. Это количество можно оценить как <tex> n \log^2n </tex> ([[Сеть_Бетчера|Сеть Бетчера]]). Таким образом, получаем асимптотику <tex> O(n!n \log^2n) </tex>, и при <tex>n = 10</tex> проверить сеть очень проблематично.
 == Второй способ ==

← Предыдущая		Версия 13:29, 7 июня 2012
Строка 1:		Строка 1:
−	Есть два способа проверить сеть из n компараторов на то, что она сортирующая.	+	Есть два способа проверить сеть из <tex>n</tex> компараторов на то, что она сортирующая.

	__TOC__		__TOC__