47
правок
Изменения
м
Remove space in LaTeX token
{{ Определение
| definition =
Функция <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>
}}
Пусть <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> f(\min(a_1, a_2)) = \min(f(a_1), f(a_2)) = f(a_1) </tex>. Такие же рассуждения можно провести для случая <tex> a_2 < a_1 </tex>.
}}
== См. также ==*[[Сеть_Бетчера|Сеть Бетчера]]*[[Сортирующие_сети|Сортирующие сети]] == Источники информации ==*[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]*Дональд Кнут — {{---}} Искусство программирования — {{---}} Том 3 — {{---}} Глава 5.3.4 — {{---}} стр. 249
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Сортирующие сети]]
