0-1 принцип — различия между версиями
Kamensky (обсуждение | вклад) м (Remove space in LaTeX token) |
|||
Строка 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> компараторов на то, что она сортирующая. | ||
Версия 07:08, 1 сентября 2022
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Есть два способа проверить сеть из
компараторов на то, что она сортирующая.Содержание
Первый способ
Первый, наивный способ — перебрать все перестановки из Сеть Бетчера). Таким образом, получаем асимптотику , и при проверить сеть очень проблематично.
элементов, пропустить их через сеть и проверить их на то, что они отсортированы. Этот подход потребует действий, где — количество компараторов в сети из элементов. Это количество можно оценить как (Второй способ
Второй способ основывается на предположении, что если сеть сортирует все последовательности из нулей и единиц, то сеть является сортирующей. Если мы докажем это, то сможем проверять сеть за
, что намного быстрее.Доказательство 0-1 принципа
Определение: |
Функция | называется монотонной (англ. monotonous), если
Лемма: |
Пусть — монотонная. Тогда . |
Доказательство: |
Не теряя общности, предположим что . Тогда . Также, по монотонности, . Тогда . То есть, . Такие же рассуждения можно провести для случая . |
Определение: |
Рассмотрим отображение | и последовательность . Определим как последовательность , то есть
Лемма: |
Пусть — монотонная, а — сеть компараторов.
Тогда и коммутируют, то есть . Другими словами, неважно, применить сначала к и пропустить через сеть , или пропустить через сеть последовательность , а потом применить монотонную функцию . |
Доказательство: |
Рассмотрим произвольный компаратор , сортирующий элементы и . Применим его к последовательности и рассмотрим элемент с индексом .Тогда
|
Теорема (0-1 принцип): |
Если сеть компараторов сортирует все последовательности из нулей и единиц, то она сортирующая |
Доказательство: |
Рассмотрим сеть , сортирующую в возрастающем порядке: .Предположим, что есть последовательность Рассмотрим функцию , которую сеть не сортирует. Тогда после пропуска через сеть , получим последовательность , в которой найдется индекс такой, что . . Очевидно, она монотонная. Заметим, что , а , то есть , или — не отсортирована. Так как и коммутируют, — также не отсортирована. Но по предположению теоремы, все последовательности из нулей и единиц сеть сортировать умеет, то есть такой последовательности не найдется, то есть сеть компараторов является сортирующей. |
См. также
Источники информации
- Bachelor-Studiengang Angewandte Informatik — Sorting networks
- Wikipedia — Sorting networks
- Дональд Кнут — Искусство программирования — Том 3 — Глава 5.3.4 — стр. 249