Дискретный анализ
Название спецкурса на английском языке
Discrete analysis
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2026/27
Список тем
Функции алгебры логики. Операция суперпозиции и оператор замыкания. Примеры полных систем
Теорема Поста о полноте
Теорема Поста о замкнутых классах.
Преобразование Уолша-Адамара и его связь с корреляцией функций
Матрица корреляции для композиции булевых операторов
Функции k-значной логики
Теоремы Янова и Мучника
Задача выполнения ограничений
Полиномиальная полнота квазигрупповых операций
Постановка задачи минимизации д.н.ф.
Функция Шеннона и ее значение
Геометрическая постановка задачи минимизации д.н.ф. Простые импликанты и максимальные грани. Сокращенная д.н.ф. Теорема о получении минимальной д.н.ф. удалением слагаемых в сокращенной д.н.ф.
Определение схемы из функциональных элементов
Сложность и глубина схемы
Понятие соединения
Нижняя оценка функции Шеннона сложности схем
Метод синтеза Шеннона
Метод синтеза Лупанова
Алфавитное кодирование
Префиксное кодирование
Однозначность декодирования префиксных и суффиксных кодов
Неравенство Макмиллана
Достаточность справедливости неравенства Макмиллана для существования префиксного кода с заданными длинами кодовых слов
Критерий Маркова однозначности декодирования
Графовый критерий однозначности декодирования
Коды Хафмана
Помехоустойчивое кодирование
Коды Хэмминга с исправлением одной ошибки
Геометрическая постановка задачи построения помехоустойчивого кода
Понятие графа и помеченного графа
Теорема Поста о полноте
Теорема Поста о замкнутых классах.
Преобразование Уолша-Адамара и его связь с корреляцией функций
Матрица корреляции для композиции булевых операторов
Функции k-значной логики
Теоремы Янова и Мучника
Задача выполнения ограничений
Полиномиальная полнота квазигрупповых операций
Постановка задачи минимизации д.н.ф.
Функция Шеннона и ее значение
Геометрическая постановка задачи минимизации д.н.ф. Простые импликанты и максимальные грани. Сокращенная д.н.ф. Теорема о получении минимальной д.н.ф. удалением слагаемых в сокращенной д.н.ф.
Определение схемы из функциональных элементов
Сложность и глубина схемы
Понятие соединения
Нижняя оценка функции Шеннона сложности схем
Метод синтеза Шеннона
Метод синтеза Лупанова
Алфавитное кодирование
Префиксное кодирование
Однозначность декодирования префиксных и суффиксных кодов
Неравенство Макмиллана
Достаточность справедливости неравенства Макмиллана для существования префиксного кода с заданными длинами кодовых слов
Критерий Маркова однозначности декодирования
Графовый критерий однозначности декодирования
Коды Хафмана
Помехоустойчивое кодирование
Коды Хэмминга с исправлением одной ошибки
Геометрическая постановка задачи построения помехоустойчивого кода
Понятие графа и помеченного графа
Список источников
Яблонский С.В. Введение в дискретную математику, Высшая школа, 2010
Кудрявцев В.Б., Блохина Г.Н., Кнап Ж., Кудрявцев В.В. Алгебра логики, Изд-во мех-мат МГУ Москва-Любляна, 2006
Гашков С., Гринчук М., Сергеев И. О построении схем сумматоров малой глубины, Дискретный анализ и исследование операций, Серия 1, Т. 14, 1, 2007, стр. 27-44
Галатенко А.В., Панкратьев А.Е. О сложности проверки полиномиальной полноты конечных квазигрупп, Дискрет. матем., 30, 4 (2018), 3-11.
Zhuk D., A Proof of the CSP Dichotomy Conjecture, Journal of the ACM, 67, 5 (2020), 1-78
Кудрявцев В.Б., Блохина Г.Н., Кнап Ж., Кудрявцев В.В. Алгебра логики, Изд-во мех-мат МГУ Москва-Любляна, 2006
Гашков С., Гринчук М., Сергеев И. О построении схем сумматоров малой глубины, Дискретный анализ и исследование операций, Серия 1, Т. 14, 1, 2007, стр. 27-44
Галатенко А.В., Панкратьев А.Е. О сложности проверки полиномиальной полноты конечных квазигрупп, Дискрет. матем., 30, 4 (2018), 3-11.
Zhuk D., A Proof of the CSP Dichotomy Conjecture, Journal of the ACM, 67, 5 (2020), 1-78
День недели
четверг
Время
16:45-18:20
Аудитория
1226б
Дата первого занятия
Аудитория первого занятия
1226б
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.