Изменения

Перейти к: навигация, поиск
Изменения в "см. также"
{{В разработке}}Определение|definition='''Последовательность''' (англ. ''sequence'') {{---}} это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества.}}
== Определения Виды последовательностей =={{Определение|definition = Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''неубывающей''''' (англ. ''nondecreasing''), если каждый элемент этой последовательности не превосходит следующего за ним. <tex>\{x_n\}</tex> &mdash; '''''неубывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \leqslant x_{n+1}</tex>.}}
{{Определение|definition = Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''неубывающейневозрастающей'''''(англ. ''nonincreasing''), если каждый следующий элемент этой последовательности не превосходит следующего за нимпредыдущего.<tex>\{x_n\}</tex> &mdash; '''''невозрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \geqslant x_{n+1}</tex>.}}
{{Определение|definition = Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''возрастающей''''' (англ. ''increasing''), если каждый следующий элемент этой последовательности превышает предыдущий. <tex>\{x_n\}</tex> &mdash; '''''неубывающаявозрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \leqslant < x_{n+1}</tex>.}}
{{Определение
|definition =
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''убывающей''''' (англ. ''decreasing''), если каждый элемент этой последовательности превышает следующий за ним. <tex>\{x_n\}</tex> &mdash; '''''убывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n > x_{n+1}</tex>.
}}
{{Определение|definition = Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''монотонной''невозрастающей'(англ. ''monotonic''), если каждый следующий элемент этой последовательности не превосходит предыдущегоона является неубывающей, либо невозрастающей.}}
<tex>\{x_n\}</tex> &mdash; {Определение|definition = Последовательность называется '''строго монотонной''невозрастающая'(англ. ''strictly monotonic'' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \geqslant x_{n+1), если она является возрастающей, либо убывающей.}}</tex>
Очевидно, что строго монотонная последовательность является монотонной.
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''возрастающей''''', если каждый следующий элемент этой последовательности превышает предыдущий. <tex>\{x_n\}</tex> &mdash; '''''возрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n < x_{n+1}</tex>== Теорема о связи длины НВП и НУП ==
Последовательность {{Теорема|author=|about=|statement=Пусть <tex>a</tex>\{x_n\{---}}перестановка чисел длины <tex>n, l</tex> элементов множества {{---}} длина наибольшей возрастающей подпоследовательности ([[Задача о наибольшей возрастающей подпоследовательности|НВП]]), <tex>Xk</tex> называется '''''{{---}} длина наибольшей убывающей''''', если каждый элемент этой последовательности превышает следующий за нимподпоследовательности (НУП). Тогда <tex>l k \geqslant n</tex>.
|proof=Рассмотрим два массива длины <tex>\n : S </tex> и <tex> T </tex>, где <tex> S_i </tex> {x_n\{---}} длина НВП, которая заканчивается на <tex>a_i</tex> &mdash; '''''убывающая''''' , <tex>\Leftrightarrow\forall n \in \mathbb N: x_n T_i </tex> x_{n+1{---}}длина НУП, которая начинается на <tex>a_i</tex>.
Докажем, что все пары <tex>(S_i, T_i)</tex> различны.
Пусть существуют такие <tex>i < j</tex> , что <tex> S_i </tex> = <tex> S_j </tex> и <tex> T_i </tex> = <tex> T_j</tex>. Если <tex>a_i < a_j</tex>, тогда <tex> a_j </tex> можно добавить к НВП, заканчивающейся на <tex> a_i </tex>, следовательно <tex>S_j \geqslant S_i + 1</tex>. Если <tex>a_i > a_j</tex>, то по аналогии <tex>T_i \geqslant T_j + 1</tex>. Противоречие! Следовательно все такие пары различны.
Последовательность называется '''монотонной'''Заметим что <tex>1 \leqslant S_i \leqslant l, если она является неубывающей1 \leqslant T_i \leqslant k</tex>, либо невозрастающейпоэтому существуют <tex>l k</tex> различных пар <tex> (S_i, T_i) </tex>. Если <tex>l k < n</tex> тогда среди <tex> n </tex> пар найдутся две одинаковые. Такого быть не может по доказанному выше, т. е. <tex>l k \geqslant n</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 Википедия {{---}} Последовательность]
*[http://en.wikipedia.org/wiki/Longest_increasing_subsequence Wikipedia {{---}} Longest increasing subsequence]
== Источники ==[[Категория: Дискретная математика и алгоритмы]][[Категория: Комбинаторика]]* [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 ПоследовательностьСвойства комбинаторных объектов]]
17
правок

Навигация