23
правки
Изменения
→Алгоритмы сжатия: - добавлена ссылка на статью Контекстное моделирование
*[[Полные системы функций. Теорема Поста о полной системе функций]]
*[[Представление функции класса DM с помощью медианы]]
*[[Выражение функции XOR через медианы]]
*[[Пороговая функция]]
*[[Троичная логика]]<tex>^\star</tex>
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Простейшие методы синтеза схем из функциональных элементов]]
*[[Шифратор и дешифратор]]
*[[Мультиплексор и демультиплексор]]
*[[Метод Лупанова синтеза схем]]
*[[Cумматор]]
*[[Триггеры]]<tex>^\star</tex>
*[[Квантовые гейты]]<tex>^\star</tex>
*[[Квантовые алгоритмы]]<tex>^\star</tex>
== Представление информации ==
* [[Избыточное кодирование, код Хэмминга]]
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
* [[Арифметическое кодирование]]
* [[Контекстное моделирование]]
== Комбинаторика ==
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>
* [[Методы получения случайных комбинаторных объектов]]
=== Подсчёт числа объектов ===
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* [[Лемма Бёрнсайда и Теорема Пойа]]
* [[Задача об ожерельях]]
* [[Числа Стирлинга первого рода]]
* [[Числа Стирлинга второго рода]]
* [[Символ Похгаммера]]
* [[Числа Белла]]
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
* [[Числа Каталана]]
* [[Конструирование комбинаторных объектов и их подсчет]]
=== Свойства комбинаторных объектов ===
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
== [[Динамическое программированиеПроизводящая функция]] ===== Классические задачи динамического программирования ===*[[Кратчайший путь в ациклическом графеАрифметические действия с формальными степенными рядами]]*[[Задача Теорема о числе путей в ациклическом графесвязи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]]*[[Задача о расстановке знаков в выраженииИспользование производящих функций для доказательства тождеств]]*[[Задача о порядке перемножения матрицПроизводящие функции нескольких переменных]]*[[Задача о наибольшей общей подпоследовательностиРазложение рациональной функции в ряд]]*[[Задача о наибольшей возрастающей подпоследовательности]]*[[Быстрый поиск наибольшей возрастающей подпоследовательности]]**[[Задача коммивояжера, ДП по подмножествамПредставление производящей функций в виде непрерывных дробей]]*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишерасчастливых билетах]]*[[Задача о рюкзакеПроизведение Адамара рациональных производящих функций|Произведение Адамара]] === Способы оптимизации методов динамического программирования ===*[[Метод четырех русских для умножения матриц]]*[[Применение метода четырех русских в задачах ДП на примере задачи о НОПИнтегрирование/дифференцирование производящих функций]]<tex>^\star</tex>*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разрезаПроизводящая функция Дирихле]]*[[Meet-in-the-middleРешение рекуррентных соотношений]]<tex>^\star</tex>*[[Convex hull trickЯзык Дика]] === Другие задачи ===*[[Задача о расстоянии Дамерау-ЛевенштейнаУравнение Лагранжа и теорема Лагранжа]]<tex>^\star</tex>*[[Задача о выводе в контекстно-свободной грамматикеАсимптотика коэффициентов функций, алгоритм Кока-Янгера-Касами]]*[[Задача о наибольшей подпоследовательности-палиндроме]]*[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>*[[Динамическое программирование по профилю]]<tex>^\star</tex>*[[Динамика по поддеревьямсвязанных между собой уравнением Лагранжа]]
