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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема о связи длины НВП и НУП)
Строка 31: Строка 31:
 
== Теорема о связи длины НВП и НУП ==
 
== Теорема о связи длины НВП и НУП ==
  
Длина наибольшей возрастающей подпоследовательности(НВП) равна минимальному количеству наибольших убывающих подпоследовательностей(НУП) на которые её можно разбить.  
+
{{
 +
Теорема
 +
|author=
 +
|about=
 +
|statement=
 +
Произведение длин наибольшей возрастающей и наибольшей убывающей подпоследовательностей больше либо равно длине последовательности.
  
 +
|proof=
 +
Пусть есть стока <tex> a </tex>. Рассмотрим наибольшую возрастающую подпоследовательность
 +
<tex> a[i_1] < a[i_2] < \dots < a[i_k] </tex> и наибольшую убывающую подпоследовательность <tex> x[j_1] > x[j_2] < \dots > x[j_l] </tex> строки <tex> a </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://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 Последовательность]

Версия 22:46, 16 декабря 2010

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

Определения

Последовательность [math]\{x_n\}[/math] элементов множества [math]X[/math] называется неубывающей, если каждый элемент этой последовательности не превосходит следующего за ним.

[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] называется невозрастающей, если каждый следующий элемент этой последовательности не превосходит предыдущего.

[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] называется возрастающей, если каждый следующий элемент этой последовательности превышает предыдущий.

[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] называется убывающей, если каждый элемент этой последовательности превышает следующий за ним.

[math]\{x_n\}[/math]убывающая [math]\Leftrightarrow\forall n \in \mathbb N: x_n \gt x_{n+1}[/math]


Последовательность называется монотонной, если она является неубывающей, либо невозрастающей.

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

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

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

Теорема:
Произведение длин наибольшей возрастающей и наибольшей убывающей подпоследовательностей больше либо равно длине последовательности.
Доказательство:
[math]\triangleright[/math]

Пусть есть стока [math] a [/math]. Рассмотрим наибольшую возрастающую подпоследовательность

[math] a[i_1] \lt a[i_2] \lt \dots \lt a[i_k] [/math] и наибольшую убывающую подпоследовательность [math] x[j_1] \gt x[j_2] \lt \dots \gt x[j_l] [/math] строки [math] a [/math].
[math]\triangleleft[/math]

Источники