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

Убедительная просьба читать правила оформления вики-конспектов.

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

видеолекции Андрея Станкевича

Отношения

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

Булевы функции

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

Схемы из функциональных элементов

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

Представление информации

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

Алгоритмы сжатия

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

Комбинаторика

Комбинаторные объекты

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

Генерация комбинаторных объектов

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

Подсчёт числа объектов

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

Свойства комбинаторных объектов

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

Производящие функции

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