Дискретная математика и алгоритмы

Отношения

• Определение отношения
• Степень отношений
• Рефлексивное отношение. Антирефлексивное отношение.
• Симметричное отношение
• Антисимметричное отношение
• Композиция отношений. Обратное отношение
• Транзитивное отношение
• Транзитивное замыкание отношения
• Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения

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

• Определение булевой функции
• Примеры булевых функций: все функции от нуля, одной и двух переменных
• Подстановка одной функции в другую, отождествление переменных
• Представление функции формулой, полные системы функций
• СДНФ
• СКНФ
• Полином Жегалкина
• Теорема Поста о полной системе функций
• Сокращенная и минимальная ДНФ
• Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно
• Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
• Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина

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

• Реализация булевой функции схемой из функциональных элементов
• Изменение размера оптимальной схемы при переходе к другому базису
• Каскадный сумматор
• Двоичный каскадный сумматор
• Матричный умножитель
• Дерево Уоллеса

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

• Кодирование информации
• Представление целых чисел: прямой код, код со сдвигом, дополнительный код

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

• Алгоритм LZW
• Алгоритмы LZ77 и LZ78
• Преобразование Барроуза-Уиллера
• Преобразование MTF