Дискретная математика
Версия от 06:38, 1 сентября 2022; 217.79.179.7 (обсуждение)
| НЕТ ВОЙНЕ |
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Убедительная просьба читать правила оформления вики-конспектов.
Символом помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
Содержание
Отношения
- Множества
- Определение отношения
- Композиция отношений, степень отношения, обратное отношение
- Рефлексивное отношение. Антирефлексивное отношение.
- Симметричное отношение
- Антисимметричное отношение
- Транзитивное отношение
- Отношение порядка
- Изоморфизмы упорядоченных множеств
- Отношение эквивалентности
- Транзитивное замыкание отношения
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
- Транзитивный остов
Булевы функции
- Определение булевой функции
- Побитовые операции
- Суперпозиции
- ДНФ
- Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
- КНФ
- 2-SAT
- XOR-SAT
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
- Полином Жегалкина, преобразование Мёбиуса
- Полные системы функций. Теорема Поста о полной системе функций
- Представление функции класса DM с помощью медианы
- Выражение функции XOR через медианы
- Пороговая функция
- Троичная логика
Схемы из функциональных элементов
- Реализация булевой функции схемой из функциональных элементов
- Простейшие методы синтеза схем из функциональных элементов
- Шифратор и дешифратор
- Мультиплексор и демультиплексор
- Метод Лупанова синтеза схем
- Представление булевых функций линейными программами
- Нижняя оценка размера схем из функциональных элементов
- Cумматор
- Каскадный сумматор
- Двоичный каскадный сумматор
- Троичный сумматор
- Реализация вычитания сумматором
- Матричный умножитель
- Дерево Уоллеса
- Контактная схема
- Триггеры
- Квантовые гейты
- Квантовые алгоритмы
Представление информации
- Кодирование информации
- Представление целых чисел: прямой код, код со сдвигом, дополнительный код
- Представление вещественных чисел
- Представление символов, таблицы кодировок
Алгоритмы сжатия
- Алгоритм Хаффмана
- Алгоритм Хаффмана за O(n)
- Алгоритм Ху-Таккера
- Неравенство Крафта
- Неравенство Макмиллана
- Код Шеннона
- Оптимальный префиксный код с длиной кодового слова не более L бит
- Алгоритмы LZ77 и LZ78
- Алгоритм LZW
- Алгоритм LZSS
- Алгоритм LZMA
- Преобразование Барроуза-Уиллера и обратное ему
- Преобразование MTF
- Расстояние Хэмминга
- Избыточное кодирование, код Хэмминга
- Обнаружение и исправление ошибок кодирования
- Гамма-, дельта- и омега-код Элиаса
- Арифметическое кодирование
- Контекстное моделирование
Комбинаторика
Комбинаторные объекты
- Комбинаторные объекты
- Лексикографический порядок
- Коды Грея
- Коды Грея для перестановок
- Коды антигрея
- Монотонный код Грея
- Цепные коды
- Правильные скобочные последовательности
Генерация комбинаторных объектов
- Генерация комбинаторных объектов в лексикографическом порядке
- Получение номера по объекту
- Получение объекта по номеру
- Получение следующего объекта
- Получение предыдущего объекта
- Метод генерации случайной перестановки, алгоритм Фишера-Йетса
- Методы генерации случайного сочетания
- Методы получения случайных комбинаторных объектов
Подсчёт числа объектов
- Формула включения-исключения, подсчет числа беспорядков
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
- Числа Стирлинга первого рода
- Числа Стирлинга второго рода
- Символ Похгаммера
- Числа Белла
- Числа Эйлера первого и второго рода. Подъемы в перестановках
- Числа Каталана
- Конструирование комбинаторных объектов и их подсчет
- Подсчет деревьев
- Метод производящих функций
Свойства комбинаторных объектов
- Умножение перестановок, обратная перестановка, группа перестановок
- Действие перестановки на набор из элементов, представление в виде циклов
- Таблица инверсий
- Теорема Кэли
- Матричное представление перестановок
- Задача о минимуме/максимуме скалярного произведения
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
Производящие функции
- Производящая функция
- Арифметические действия с формальными степенными рядами
- Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности
- Асимптотическое поведение последовательности, заданной рекуррентным соотношением
- Использование производящих функций для доказательства тождеств
- Производящие функции нескольких переменных
- Разложение рациональной функции в ряд
- Представление производящей функций в виде непрерывных дробей
- Задача о счастливых билетах
- Произведение Адамара
- Интегрирование/дифференцирование производящих функций
- Производящая функция Дирихле
- Решение рекуррентных соотношений
- Язык Дика
- Уравнение Лагранжа и теорема Лагранжа
- Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа
- Обращение Лагранжа
- Автокорреляционный многочлен
