19
правок
Изменения
м
Добавил англ. терминов; взял определение в шаблон; заменил дефисы на тире; правильно оформил источники информации.
{{Определение|definition='''Последовательность''' — (англ. ''sequence'') {{---}} это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества.}}
== Определения ==
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''неубывающей'''''(англ. ''nondecreasing''), если каждый элемент этой последовательности не превосходит следующего за ним.
<tex>\{x_n\}</tex> — '''''неубывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \leqslant x_{n+1}</tex>
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''невозрастающей'''''(англ. ''nonincreasing''), если каждый следующий элемент этой последовательности не превосходит предыдущего.
<tex>\{x_n\}</tex> — '''''невозрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \geqslant x_{n+1}</tex>
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''возрастающей'''''(англ. ''increasing''), если каждый следующий элемент этой последовательности превышает предыдущий.
<tex>\{x_n\}</tex> — '''''возрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n < x_{n+1}</tex>
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''убывающей'''''(англ. ''decreasing''), если каждый элемент этой последовательности превышает следующий за ним.
<tex>\{x_n\}</tex> — '''''убывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n > x_{n+1}</tex>
Последовательность называется '''монотонной'''(англ. ''monotonic''), если она является неубывающей, либо невозрастающей.
Последовательность называется '''строго монотонной'''(англ. ''strictly monotonic''), если она является возрастающей, либо убывающей.
Очевидно, что строго монотонная последовательность является монотонной.
|about=
|statement=
Пусть <tex>a</tex> {{- --}} перестановка чисел длины <tex>n, l</tex> {{--- }} длина наибольшей возрастающей подпоследовательности (НВП), <tex>k</tex> {{--- }} длина наибольшей убывающей подпоследовательности (НУП). Тогда <tex>l k \geqslant n</tex>.
|proof=
Рассмотрим два массива длины <tex>n : S </tex> и <tex> T </tex>, где <tex> S_i </tex> {{- --}} длина НВП, которая заканчивается на <tex>a_i</tex>, <tex> T_i </tex> {{--- }} длина НУП, которая начинается на <tex>a_i</tex>.
Докажем, что все пары <tex>(S_i, T_i)</tex> различны.
{{Утверждение
|statement=
Пусть <tex>n</tex> {{- --}} длина последовательности, тогда длина наибольшей монотонной подпоследовательности не меньше <tex>\sqrt{n}</tex>
}}
== Источники информации ==* [http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C#.D0.9D.D0.B5.D0.BA.D0.BE.D1.82.D0.BE.D1.80.D1.8B.D0.B5_.D0.B2.D0.B8.D0.B4.D1.8B_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B5.D0.B9 Wikipedia Википедия {{---}} Последовательность]
*[http://en.wikipedia.org/wiki/Longest_increasing_subsequence Wikipedia {{---}} Longest increasing subsequence - Wikipedia, the free encyclopedia]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]
