1632
правки
Изменения
м
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]
== [[Динамическое программирование]] ===== Классические задачи динамического программирования ===*[[Кратчайший путь Разложение рациональной функции в ациклическом граферяд]]*[[Задача о числе путей Представление производящей функций в ациклическом графевиде непрерывных дробей]]*[[Задача о расстановке знаков в выражениисчастливых билетах]]*[[Задача о порядке перемножения матрицПроизведение Адамара рациональных производящих функций|Произведение Адамара]]*[[Задача о наибольшей общей подпоследовательностиИнтегрирование/дифференцирование производящих функций]]*[[Задача о наибольшей возрастающей подпоследовательностиПроизводящая функция Дирихле]]*[[Быстрый поиск наибольшей возрастающей подпоследовательностиРешение рекуррентных соотношений]]**[[Задача коммивояжера, ДП по подмножествамЯзык Дика]]*[[Задача о редакционном расстоянии, алгоритм Вагнера-ФишераУравнение Лагранжа и теорема Лагранжа]]*[[Задача о рюкзаке]] === Способы оптимизации методов динамического программирования ===*[[Метод четырех русских для умножения матриц]]*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<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>*[[Динамика по поддеревьямАвтокорреляционный многочлен]]
rollbackEdits.php mass rollback
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
[https://youtube.com/andrewzta видеолекции Андрея Станкевича]
== Отношения ==
*[[Множества]]
*[[Определение отношения]]
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
*[[Полные системы функций. Теорема Поста о полной системе функций]]
*[[Представление функции класса DM с помощью медианы]]
*[[Выражение функции XOR через медианы]]
*[[Пороговая функция]]
*[[Троичная логика]]<tex>^\star</tex>
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Простейшие методы синтеза схем из функциональных элементов]]
*[[Шифратор и дешифратор]]
*[[Мультиплексор и демультиплексор]]
*[[Метод Лупанова синтеза схем]]
*[[Представление булевых функций линейными программами]]
*[[Нижняя оценка размера схем из функциональных элементов]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Триггеры]]<tex>^\star</tex>
*[[Квантовые гейты]]<tex>^\star</tex>
*[[Квантовые алгоритмы]]<tex>^\star</tex>
== Представление информации ==
== Алгоритмы сжатия ==
* [[Алгоритм Хаффмана]]
* [[Алгоритм Хаффмана за O(n)]]
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
* [[Расстояние Хэмминга]]
* [[Избыточное кодирование, код Хэмминга]]
* [[Обнаружение и исправление ошибок кодирования]]
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
* [[Арифметическое кодирование]]
* [[Контекстное моделирование]]
== Комбинаторика ==
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>
* [[Методы получения случайных комбинаторных объектов]]
=== Подсчёт числа объектов ===
* [[Числа Стирлинга первого рода]]
* [[Числа Стирлинга второго рода]]
* [[Символ Похгаммера]]
* [[Числа Белла]]
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
* [[Числа Каталана]]
* [[Конструирование комбинаторных объектов и их подсчет]]
* [[Подсчет деревьев]]
* [[Метод производящих функций]]
=== Свойства комбинаторных объектов ===
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
== = Производящие функции ===* [[Производящая функция]] ==
* [[Арифметические действия с формальными степенными рядами]]
* [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]]
* [[Асимптотическое поведение последовательности, заданной рекуррентным соотношением]]
* [[Использование производящих функций для доказательства тождеств]]
* [[Производящие функции нескольких переменных]]
