Викиконспекты - Вклад участника [ru]

Дискретная математика

2021-06-15T20:52:39Z

91.108.2.123: /* Производящие функции */

[[Категория:Дискретная математика и алгоритмы]]
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].

Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.

[https://youtube.com/andrewzta видеолекции Андрея Станкевича]

== Отношения ==
*[[Определение отношения]]
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Транзитивное отношение]]
*[[Отношение порядка]]
*[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
*[[Отношение эквивалентности]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
*[[Транзитивный остов]]

== Булевы функции ==
*[[Определение булевой функции]]
*[[Побитовые операции]]<tex>^\star</tex>
*[[Суперпозиции]]
*[[ДНФ]]
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
*[[КНФ]]
*[[2-SAT]]
*[[XOR-SAT]]<tex>^\star</tex>
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
*[[Полные системы функций. Теорема Поста о полной системе функций]]
*[[Представление функции класса DM с помощью медианы]]
*[[Выражение функции XOR через медианы]]
*[[Пороговая функция]]
*[[Троичная логика]]<tex>^\star</tex>

== Схемы из функциональных элементов ==
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Простейшие методы синтеза схем из функциональных элементов]]
*[[Шифратор и дешифратор]]
*[[Мультиплексор и демультиплексор]]
*[[Метод Лупанова синтеза схем]]
*[[Представление булевых функций линейными программами]]
*[[Нижняя оценка размера схем из функциональных элементов]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Двоичный каскадный сумматор]]
*[[Троичный сумматор]]<tex>^\star</tex>
*[[Реализация вычитания сумматором]]
*[[Матричный умножитель]]
*[[Дерево Уоллеса]]
*[[Контактная схема]]
*[[Триггеры]]<tex>^\star</tex>
*[[Квантовые гейты]]<tex>^\star</tex>
*[[Квантовые алгоритмы]]<tex>^\star</tex>

== Представление информации ==
*[[Кодирование информации]]
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
*[[Представление вещественных чисел]]
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex>

== Алгоритмы сжатия ==
* [[Алгоритм Хаффмана]]
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]
* [[Алгоритм Хаффмана за O(n)]]
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
* [[Неравенство Крафта]]
* [[Неравенство Макмиллана]]
* [[Код Шеннона]]
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
* [[Алгоритмы LZ77 и LZ78]]
* [[Алгоритм LZW]]
* [[Алгоритм LZSS]]<tex>^\star</tex>
* [[Алгоритм LZMA]]<tex>^\star</tex>
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
* [[Преобразование MTF]]
* [[Расстояние Хэмминга]]
* [[Избыточное кодирование, код Хэмминга]]
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
* [[Арифметическое кодирование]]
* [[Контекстное моделирование]]

== Комбинаторика ==
=== Комбинаторные объекты ===
* [[Комбинаторные объекты]]
* [[Лексикографический порядок]]
* [[Коды Грея]]
* [[Коды Грея для перестановок]]
* [[Коды антигрея]]
* [[Монотонный код Грея]]
* [[Цепные коды]]
* [[Правильные скобочные последовательности]]

=== Генерация комбинаторных объектов ===
* [[Генерация комбинаторных объектов в лексикографическом порядке]]
* [[Получение номера по объекту]]
* [[Получение объекта по номеру]]
* [[Получение следующего объекта]]
* [[Получение предыдущего объекта]]<tex>^\star</tex>
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>
* [[Методы получения случайных комбинаторных объектов]]

=== Подсчёт числа объектов ===
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* [[Лемма Бёрнсайда и Теорема Пойа]]
* [[Задача об ожерельях]]
* [[Числа Стирлинга первого рода]]
* [[Числа Стирлинга второго рода]]
* [[Символ Похгаммера]]
* [[Числа Белла]]
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
* [[Числа Каталана]]
* [[Конструирование комбинаторных объектов и их подсчет]]
* [[Подсчет деревьев]]
* [[Метод производящих функций]]

=== Свойства комбинаторных объектов ===
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
* [[Таблица инверсий]]
* [[Теорема Кэли]]
* [[Матричное представление перестановок]]
* [[Задача о минимуме/максимуме скалярного произведения]]
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]

=== Производящие функции ===
* [[Производящая функция]]
* [[Арифметические действия с формальными степенными рядами]]
* [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]]
* [[Асимптотическое поведение последовательности, заданной рекуррентным соотношением]]
* [[Использование производящих функций для доказательства тождеств]]
* [[Производящие функции нескольких переменных]]
* [[Разложение рациональной функции в ряд]]
* [[Представление производящей функций в виде непрерывных дробей]]
* [[Задача о счастливых билетах]]
* [[Произведение Адамара рациональных производящих функций|Произведение Адамара]]
* [[Интегрирование/дифференцирование производящих функций]]
* [[Производящая функция Дирихле]]
* [[Решение рекуррентных соотношений]]
* [[Язык Дика]]
* [[Уравнение Лагранжа и теорема Лагранжа]]
*[[Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа]]
* [[Обращение Лагранжа]]
* [[Автокорреляционный многочлен]]

Асимптотическое поведение последовательности, заданной рекуррентным соотношением

2021-06-15T20:51:23Z

91.108.2.123: Новая страница: «== Нахождение асимптотики рекуррентной последовательности == Здесь будет рассмотрен мет…»

== Нахождение асимптотики рекуррентной последовательности ==
Здесь будет рассмотрен метод поиска функции, которая имеет одинаковую асимптотику<ref>[https://ru.wikipedia.org/wiki/%D0%90%D1%81%D0%B8%D0%BC%D0%BF%D1%82%D0%BE%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE Асимптотическое равенство]</ref> с <tex>a_n</tex>, то есть при <tex>n \rightarrow \infty</tex> будет отличаться от <tex>a_n</tex> в константу раз. Из [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности | теоремы о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]] известно, что последовательность, заданная рекуррентным соотношением, представима в виде дробно-рациональной производящей функции в следующем виде: <tex>A(t)=\dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_s \cdot t^s</tex>, <tex>deg(P) < s</tex>, тогда <tex>Q(t)</tex> — многочлен конечной степени, следовательно, он имеет <tex>s</tex> корней <tex>t_i\in \mathbb{C}</tex>, каждый из которых имеет некоторую кратность <tex>f_i</tex>.

'''Идея'''

Дробно-рациональную производящую функцию можно представить в виде <tex>A(t)=\dfrac{P(t)}{Q(t)}=\dfrac{c_1}{(1-r_1 t)^{f_1}} + \dfrac{c_2}{(1-r_2 t)^{f_2}} + \ldots + \dfrac{c_s}{(1-r_s t)^{f_s}}</tex>, а из [[Произведение Адамара рациональных производящих функций#lemma1 | леммы о представлении коэффициента последовательности, заданной рациональной ПФ, в форме квазимногочлена]] мы знаем, чему равен <tex>n</tex>-й коэффициент последовательности, которую задает каждая дробь, тогда <tex>n</tex>-й коэффициент
<tex>A(t)</tex> будет равен <tex>c_1 \begin{pmatrix} f_1 - 1 + n \\ f_1 - 1 \end{pmatrix} r_1^{n} + c_2 \begin{pmatrix} f_2 - 1 + n \\ f_2 - 1 \end{pmatrix} r_2^{n}+\ldots+
c_s \begin{pmatrix} f_s - 1 + n \\ f_s - 1 \end{pmatrix} r_s^{n}</tex>. Очевидно, наибольший вклад в поведение <tex>a_n</tex> вносит наибольший по модулю <tex>r_i</tex> с наибольшей кратностью <tex>f_i</tex>.

Зная, что <tex>\begin{pmatrix} f_i - 1 + n \\ f_i - 1 \end{pmatrix} = \dfrac{(n + 1)(n + 2)\ldots(n + f_i - 1)}{(f_i - 1)!}</tex>, и, пренебрегая константой, получаем, что <tex>a_n \sim n^{f_i - 1} \cdot r_i^{n}</tex>.

'''Алгоритм'''

Найдем обратные корни к <tex>t_i</tex>, то есть <tex>r_i = \dfrac{1}{t_i}</tex>.
Тогда имеем набор <tex>r_1, r_2, \,\dots, r_s</tex> обратных корней <tex>Q(t)</tex> с кратностью соответственно <tex>f_1, f_2, \,\dots, f_s</tex>:

# Существует единственный максимальный по модулю обратный корень: <tex>\exists i: \: \forall j \neq i \; |r_i| > |r_j|</tex>.<br/> Тогда <tex>r_i \in \mathbb{R}</tex>, в этом случае <tex>a_n \sim n^{f_i - 1} \cdot r_{i}^{n}</tex>.
# Существует несколько максимальных по модулю обратных корней:<br/> Найдем коэффициенты корней <tex>c_i</tex>, которые получаются разложением <tex>A(t)</tex> на сумму простых дробей в вида <tex>\dfrac{c_i}{(1 - r_i t)^{f_i}}</tex>. <br/> Возьмем те обратные корни, кратность которых максимальна, тогда имеем набор <tex>r_1, r_2, \,\dots, r_l</tex>, в котором каждый обратный корень имеет максимальную кратность <tex>f</tex>. Тогда <tex>\forall j \in 1 \,\dots\, l :\; r_j = z e^{i \phi_j}</tex>, где <tex>z</tex> — модуль каждого из корней. <br/>Значит <tex>\displaystyle a_n \sim n^{f - 1} \sum_{j = 1}^{l} {c_j \cdot r_j^n} = n^{f - 1} \sum_{j = 1}^{l} {c_j \cdot (z\cdot e^{i \phi_j})^{n}} = n^{f - 1} z^n \sum_{j = 1}^{l} {c_j \cdot e^{i \phi_j n}}</tex>, где <tex>c_j</tex> — коэффициенты, полученные при разбиении дробно-рациональной функции на простые дроби.

== Примеры задач ==
{{Задача
|definition = Оцените асимптотическое поведение коэффициента <tex>a_n</tex> производящей функции <tex>A(t)=\dfrac{t^2}{1 - 2t - t^2 + 2t^3}</tex> при <tex>n \rightarrow \infty</tex>.
}}
Найдем корни знаменателя производящей функции: <tex>Q(t) = 1 - 2t - t^2 + 2t^3 = (1 - 2t)(1 - t)(1 + t)</tex>, тогда обратные корни: <tex>r_1 = 2,\,f_1 = 1;\; r_2 = 1,\, f_2 = 1;\; r_3 = -1,\, f_3 = 1</tex>.

Выберем максимальный по модулю <tex>r_1 = 2</tex>, тогда <tex>a_n \sim n^{f_1 - 1} \cdot r_{1}^{n} = 2^n</tex>.
{{Задача
|definition = Оцените асимптотическое поведение коэффициента <tex>a_n</tex> производящей функции <tex>A(t)=\dfrac{1}{(1 - 2t)(1 + 4t^2)}</tex> при <tex>n \rightarrow \infty</tex>.
}}
Найдем корни знаменателя производящей функции: <tex>Q(t) = (1 - 2t)(1 + 4t^2)</tex>: <tex>t_1 = \dfrac{1}{2},\, t_2 = \dfrac{1}{2i},\, t_3 = -\dfrac{1}{2i}</tex>, тогда обратные корни: <tex>r_1 = 2,\,f_1 = 1;\; r_2 = 2i,\, f_2 = 1;\; r_3 = -2i,\, f_3 = 1</tex>.
Все три обратных корня имеют одинаковый модуль <tex>z = 2</tex> и кратность <tex>f = 1</tex>.

Для определения доминирующего коэффициента разложим производящую функцию на простые дроби, например, с помощью метода неопределенных коэффициентов, так мы найдем <tex>c_i:</tex>

<tex>A(t) = \dfrac{\frac{1}{4}}{\frac{1}{2} - t} + \dfrac{\frac{1 - i}{4}}{t + \frac{1}{2i}} + \dfrac{\frac{1 + i}{4}}{t - \frac{1}{2i}},\; c_1 = \dfrac{1}{4},\, c_2 = \dfrac{1 - i}{4},\,
c_3 = \dfrac{1 + i}{4}</tex>

<tex>\displaystyle a_n \sim n^{f - 1} \sum_{i = 1}^{3} {c_i \cdot r_i^{n}} = n^{1 - 1} \cdot \left(\dfrac{1}{4} \cdot 2^n + \dfrac{1 - i}{4} \cdot (2i)^n + \dfrac{1 + i}{4} \cdot (-2i)^n \right) =
2^{n - 2}\cdot (1 + (1 - i)\cdot i^n + (1 + i) \cdot (-i)^n)</tex>.

В этом примере оценка включает в себя все обратные корни с их коэффициентами, поэтому она является представлением коэффициента производящей функции в форме квазимногочлена<ref>[[Произведение Адамара рациональных производящих функций#lemma1 | Лемма о представлении коэффициента рациональной производящей функции в форме квазимногочлена]]</ref>. Это значит, что вместо знака <tex>\sim</tex> можно поставить знак равенства.

== См. также ==
* [[Производящая функция]]
* [[Произведение Адамара рациональных производящих функций]]

==Примечания==

<references />

== Источники информации ==
* ''Graham R.L., Knuth D.E., and Patashnik O.'' (1994) Concrete Mathematics. Second edition. Massachusetts: Addison-Weasley Publishing Company, Inc. P.340-347.
* [https://en.wikipedia.org/wiki/Generating_function#Asymptotic_growth_of_a_sequence Wikipedia {{---}} Asymptotic growth of a sequence]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Производящие функции]]