Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП — различия между версиями
Da1s20 (обсуждение | вклад) |
Da1s20 (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
'''Последовательность''' — это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества. | '''Последовательность''' — это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества. | ||
Версия 23:19, 3 декабря 2010
Последовательность — это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества.
Определения
Последовательность элементов множества называется неубывающей, если каждый элемент этой последовательности не превосходит следующего за ним.
— неубывающая
Последовательность элементов множества называется невозрастающей, если каждый следующий элемент этой последовательности не превосходит предыдущего.
— невозрастающая
Последовательность элементов множества называется возрастающей, если каждый следующий элемент этой последовательности превышает предыдущий.
— возрастающая
Последовательность элементов множества называется убывающей, если каждый элемент этой последовательности превышает следующий за ним.
— убывающая
Последовательность называется монотонной, если она является неубывающей, либо невозрастающей.
Последовательность называется строго монотонной, если она является возрастающей, либо убывающей.
Очевидно, что строго монотонная последовательность является монотонной.
Теорема о связи длины НВП и НУП
Длина наибольшей возрастающей подпоследовательности(НВП) равна минимальному количеству наибольших убывающих подпоследовательностей(НУП) на которые её можно разбить.
