Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП — различия между версиями
Da1s20 (обсуждение | вклад) (→Теорема о связи длины НВП и НУП) |
м (rollbackEdits.php mass rollback) |
||
(не показано 13 промежуточных версий 6 участников) | |||
Строка 1: | Строка 1: | ||
− | '''Последовательность''' | + | {{Определение |
+ | |definition= | ||
+ | '''Последовательность''' (англ. ''sequence'') {{---}} это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества. | ||
+ | }} | ||
− | == | + | ==Виды последовательностей == |
+ | {{Определение | ||
+ | |definition = | ||
+ | Последовательность <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> называется ''''' | + | {{Определение |
+ | |definition = | ||
+ | Последовательность <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> — ''''' | + | {{Определение |
+ | |definition = | ||
+ | Последовательность <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>. | ||
+ | }} | ||
+ | {{Определение | ||
+ | |definition = | ||
+ | Последовательность <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>. | ||
+ | }} | ||
− | Последовательность | + | {{Определение |
+ | |definition = | ||
+ | Последовательность называется '''монотонной''' (англ. ''monotonic''), если она является неубывающей, либо невозрастающей. | ||
+ | }} | ||
− | + | {{Определение | |
− | + | |definition = | |
− | + | Последовательность называется '''строго монотонной''' (англ. ''strictly monotonic''), если она является возрастающей, либо убывающей. | |
− | + | }} | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | Последовательность называется '''монотонной''' | ||
− | |||
− | |||
Очевидно, что строго монотонная последовательность является монотонной. | Очевидно, что строго монотонная последовательность является монотонной. | ||
Строка 36: | Строка 44: | ||
|about= | |about= | ||
|statement= | |statement= | ||
− | + | Пусть <tex>a</tex> {{---}} перестановка чисел длины <tex>n, l</tex> {{---}} длина наибольшей возрастающей подпоследовательности ([[Задача о наибольшей возрастающей подпоследовательности|НВП]]), <tex>k</tex> {{---}} длина наибольшей убывающей подпоследовательности (НУП). Тогда <tex>l k \geqslant n</tex>. | |
|proof= | |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> | + | |
+ | Докажем, что все пары <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 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 Википедия {{---}} Последовательность] | ||
+ | |||
+ | *[http://en.wikipedia.org/wiki/Longest_increasing_subsequence Wikipedia {{---}} Longest increasing subsequence] | ||
+ | |||
+ | [[Категория: Дискретная математика и алгоритмы]] | ||
+ | [[Категория: Комбинаторика]] | ||
+ | [[Категория: Свойства комбинаторных объектов]] |
Текущая версия на 19:12, 4 сентября 2022
Определение: |
Последовательность (англ. sequence) — это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества. |
Содержание
Виды последовательностей
Определение: |
Последовательность | элементов множества называется неубывающей (англ. nondecreasing), если каждый элемент этой последовательности не превосходит следующего за ним. — неубывающая .
Определение: |
Последовательность | элементов множества называется невозрастающей (англ. nonincreasing), если каждый следующий элемент этой последовательности не превосходит предыдущего. — невозрастающая .
Определение: |
Последовательность | элементов множества называется возрастающей (англ. increasing), если каждый следующий элемент этой последовательности превышает предыдущий. — возрастающая .
Определение: |
Последовательность | элементов множества называется убывающей (англ. decreasing), если каждый элемент этой последовательности превышает следующий за ним. — убывающая .
Определение: |
Последовательность называется монотонной (англ. monotonic), если она является неубывающей, либо невозрастающей. |
Определение: |
Последовательность называется строго монотонной (англ. strictly monotonic), если она является возрастающей, либо убывающей. |
Очевидно, что строго монотонная последовательность является монотонной.
Теорема о связи длины НВП и НУП
Теорема: |
Пусть НВП), — длина наибольшей убывающей подпоследовательности (НУП). Тогда . — перестановка чисел длины — длина наибольшей возрастающей подпоследовательности ( |
Доказательство: |
Рассмотрим два массива длины и , где — длина НВП, которая заканчивается на , — длина НУП, которая начинается на .Докажем, что все пары Заметим что различны. Пусть существуют такие , что = и = . Если , тогда можно добавить к НВП, заканчивающейся на , следовательно . Если , то по аналогии . Противоречие! Следовательно все такие пары различны. , поэтому существуют различных пар . Если тогда среди пар найдутся две одинаковые. Такого быть не может по доказанному выше, т. е. , ч. т. д. |
Следствие из теоремы
Утверждение: |
Пусть — длина последовательности, тогда длина наибольшей монотонной подпоследовательности не меньше . |
См. также
- Задача о минимуме/максимуме скалярного произведения
- Теорема Кэли
- Матричное представление перестановок