http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=217.66.156.154&*
Викиконспекты - Вклад участника [ru]
2026-04-08T09:06:28Z
Вклад участника
MediaWiki 1.30.0
http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0&diff=64967
Дискретная математика
2018-04-17T20:21:48Z
<p>217.66.156.154: /* Производящая функция */</p>
<hr />
<div>[[Категория:Дискретная математика и алгоритмы]]<br />
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].<br />
<br />
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.<br />
<br />
== Отношения ==<br />
*[[Определение отношения]]<br />
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]<br />
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]<br />
*[[Симметричное отношение]]<br />
*[[Антисимметричное отношение]]<br />
*[[Транзитивное отношение]]<br />
*[[Отношение порядка]]<br />
*[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex><br />
*[[Отношение эквивалентности]]<br />
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]<br />
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]<br />
*[[Транзитивный остов]]<br />
<br />
== Булевы функции ==<br />
*[[Определение булевой функции]]<br />
*[[Побитовые операции]]<tex>^\star</tex><br />
*[[Суперпозиции]]<br />
*[[ДНФ]]<br />
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]<br />
*[[КНФ]]<br />
*[[2-SAT]]<br />
*[[XOR-SAT]]<tex>^\star</tex><br />
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]<br />
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]<br />
*[[Полные системы функций. Теорема Поста о полной системе функций]]<br />
*[[Представление функции класса DM с помощью медианы]]<br />
*[[Пороговая функция]]<br />
*[[Троичная логика]]<tex>^\star</tex><br />
<br />
== Схемы из функциональных элементов ==<br />
*[[Реализация булевой функции схемой из функциональных элементов]]<br />
*[[Простейшие методы синтеза схем из функциональных элементов]]<br />
*[[Метод Лупанова синтеза схем]]<br />
*[[Cумматор]]<br />
*[[Каскадный сумматор]]<br />
*[[Двоичный каскадный сумматор]]<br />
*[[Троичный сумматор]]<tex>^\star</tex><br />
*[[Реализация вычитания сумматором]]<br />
*[[Матричный умножитель]]<br />
*[[Дерево Уоллеса]]<br />
*[[Контактная схема]]<br />
*[[Триггеры]]<tex>^\star</tex><br />
*[[Квантовые гейты]]<tex>^\star</tex><br />
<br />
== Представление информации ==<br />
*[[Кодирование информации]]<br />
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]<br />
*[[Представление вещественных чисел]]<br />
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex><br />
<br />
== Алгоритмы сжатия ==<br />
* [[Алгоритм Хаффмана]]<br />
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]<br />
* [[Алгоритм Хаффмана за O(n)]]<br />
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex><br />
* [[Неравенство Крафта]]<br />
* [[Неравенство Макмиллана]]<br />
* [[Код Шеннона]]<br />
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex><br />
* [[Алгоритмы LZ77 и LZ78]]<br />
* [[Алгоритм LZW]]<br />
* [[Алгоритм LZSS]]<tex>^\star</tex><br />
* [[Алгоритм LZMA]]<tex>^\star</tex><br />
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]<br />
* [[Преобразование MTF]]<br />
* [[Расстояние Хэмминга]]<br />
* [[Избыточное кодирование, код Хэмминга]]<br />
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex><br />
<br />
== Комбинаторика ==<br />
=== Комбинаторные объекты ===<br />
* [[Комбинаторные объекты]]<br />
* [[Лексикографический порядок]]<br />
* [[Коды Грея]]<br />
* [[Коды Грея для перестановок]]<br />
* [[Коды антигрея]]<br />
* [[Монотонный код Грея]]<br />
* [[Цепные коды]]<br />
* [[Правильные скобочные последовательности]]<br />
<br />
=== Генерация комбинаторных объектов ===<br />
* [[Генерация комбинаторных объектов в лексикографическом порядке]]<br />
* [[Получение номера по объекту]]<br />
* [[Получение объекта по номеру]]<br />
* [[Получение следующего объекта]]<br />
* [[Получение предыдущего объекта]]<tex>^\star</tex> <br />
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]<br />
* [[Методы генерации случайного сочетания]]<tex>^\star</tex><br />
<br />
=== Подсчёт числа объектов ===<br />
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]<br />
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]<br />
* [[Лемма Бёрнсайда и Теорема Пойа]]<br />
* [[Задача об ожерельях]]<br />
* [[Числа Стирлинга первого рода]]<br />
* [[Числа Стирлинга второго рода]]<br />
* [[Символ Похгаммера]]<br />
* [[Числа Белла]]<br />
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex><br />
* [[Числа Каталана]]<br />
* [[Конструирование комбинаторных объектов и их подсчет]]<br />
<br />
=== Свойства комбинаторных объектов ===<br />
* [[Умножение перестановок, обратная перестановка, группа перестановок]]<br />
* [[Действие перестановки на набор из элементов, представление в виде циклов]]<br />
* [[Таблица инверсий]]<br />
* [[Теорема Кэли]]<br />
* [[Матричное представление перестановок]]<br />
* [[Задача о минимуме/максимуме скалярного произведения]]<br />
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]<br />
<br />
== [[Производящая функция]] ==<br />
* [[Арифметические действия с формальными степенными рядами]]<br />
* [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]]<br />
* [[Производящие функции нескольких переменных]]<br />
* [[Разложение рациональной функции в ряд]]<br />
* [[Представление производящей функций в виде непрерывных дробей]]<br />
* [[Задача о счастливых билетах]]<br />
* [[Произведение Адамара рациональных производящих функций|Произведение Адамара]]<br />
* [[Интегрирование/дифференцирование производящих функций]]<br />
* [[Производящая функция Дирихле]]<br />
* [[Решение рекуррентных соотношений]]</div>
217.66.156.154