Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 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 Майкл Наки].
 
|}
 
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=

Текущая версия на 19:12, 4 сентября 2022

Определение:
Последовательность (англ. sequence) — это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества.


Виды последовательностей

Определение:
Последовательность [math]\{x_n\}[/math] элементов множества [math]X[/math] называется неубывающей (англ. nondecreasing), если каждый элемент этой последовательности не превосходит следующего за ним. [math]\{x_n\}[/math]неубывающая [math]\Leftrightarrow\forall n \in \mathbb N: x_n \leqslant x_{n+1}[/math].


Определение:
Последовательность [math]\{x_n\}[/math] элементов множества [math]X[/math] называется невозрастающей (англ. nonincreasing), если каждый следующий элемент этой последовательности не превосходит предыдущего. [math]\{x_n\}[/math]невозрастающая [math]\Leftrightarrow\forall n \in \mathbb N: x_n \geqslant x_{n+1}[/math].


Определение:
Последовательность [math]\{x_n\}[/math] элементов множества [math]X[/math] называется возрастающей (англ. increasing), если каждый следующий элемент этой последовательности превышает предыдущий. [math]\{x_n\}[/math]возрастающая [math]\Leftrightarrow\forall n \in \mathbb N: x_n \lt x_{n+1}[/math].


Определение:
Последовательность [math]\{x_n\}[/math] элементов множества [math]X[/math] называется убывающей (англ. decreasing), если каждый элемент этой последовательности превышает следующий за ним. [math]\{x_n\}[/math]убывающая [math]\Leftrightarrow\forall n \in \mathbb N: x_n \gt x_{n+1}[/math].


Определение:
Последовательность называется монотонной (англ. monotonic), если она является неубывающей, либо невозрастающей.


Определение:
Последовательность называется строго монотонной (англ. strictly monotonic), если она является возрастающей, либо убывающей.


Очевидно, что строго монотонная последовательность является монотонной.

Теорема о связи длины НВП и НУП

Теорема:
Пусть [math]a[/math] — перестановка чисел длины [math]n, l[/math] — длина наибольшей возрастающей подпоследовательности (НВП), [math]k[/math] — длина наибольшей убывающей подпоследовательности (НУП). Тогда [math]l k \geqslant n[/math].
Доказательство:
[math]\triangleright[/math]

Рассмотрим два массива длины [math]n : S [/math] и [math] T [/math], где [math] S_i [/math] — длина НВП, которая заканчивается на [math]a_i[/math], [math] T_i [/math] — длина НУП, которая начинается на [math]a_i[/math].

Докажем, что все пары [math](S_i, T_i)[/math] различны. Пусть существуют такие [math]i \lt j[/math] , что [math] S_i [/math] = [math] S_j [/math] и [math] T_i [/math] = [math] T_j[/math]. Если [math]a_i \lt a_j[/math], тогда [math] a_j [/math] можно добавить к НВП, заканчивающейся на [math] a_i [/math], следовательно [math]S_j \geqslant S_i + 1[/math]. Если [math]a_i \gt a_j[/math], то по аналогии [math]T_i \geqslant T_j + 1[/math]. Противоречие! Следовательно все такие пары различны.

Заметим что [math]1 \leqslant S_i \leqslant l, 1 \leqslant T_i \leqslant k[/math], поэтому существуют [math]l k[/math] различных пар [math] (S_i, T_i) [/math]. Если [math]l k \lt n[/math] тогда среди [math] n [/math] пар найдутся две одинаковые. Такого быть не может по доказанному выше, т. е. [math]l k \geqslant n[/math], ч. т. д.
[math]\triangleleft[/math]

Следствие из теоремы

Утверждение:
Пусть [math]n[/math] — длина последовательности, тогда длина наибольшей монотонной подпоследовательности не меньше [math]\sqrt{n}[/math].

См. также

Источники информации