Программа экзамена. Программа экзамена по дисциплине Специальные разделы дискретной математики
 Скачать 24.45 Kb.
|
|
Программа экзамена по дисциплине «Специальные разделы дискретной математики» (зимняя сессия) Определение булевой функции. Лексикографический порядок, вес, несущественные переменные, индуктивное определение формулы над классом. Классы  и критерий Поста (доказательство).Определения ДНФ, КНФ, ранга элементарной конъюнкции и дизъюнкции, совершенной ДНФ. Импликанта и её свойства, Сокр.ДНФ, ТДНФ и МДНФ. Алгоритм Блейка построения Сокр.ДНФ, доказательство корректности. Построение МДНФ по Сокр.ДНФ. Группы инерции k-значных функций определения и свойства. Группы  диаграмма вложения. Функции с тривиальной группой инерции в афинной группе (с доказательством). Лемма Бернсайда (без доказательства).Псевдобулевы функции. Коэффициенты Фурье псевдобулевой функции, свойства. Коэффициенты Уолша-Адамара 2 рода, свойства. Тензорное произведение, основные свойства. Алгоритм быстрого преобразования Фурье-Адамара и его трудоёмкость (доказательство). Коэффициенты статистической структуры булевой функции и их свойства. Трансверсали. Критерий Ф. Холла с доказательством. Понятие мультимножества. Первичная спецификация. Метрика Хемминга для подстановок на  элементах (определение и простейшие свойства).Противоречивые подстановки. Латинские прямоугольники и квадраты. Теорема о пополнении латинского прямоугольника (доказательство). Ортогональные латинские квадраты, теорема о существовании (без доказательства). Перманенты, определения и основные свойства. Связь с трансверсалями. Формула Райзера (вывод).  -конфигурации, определения и основные свойства. Матрицы Адамара, определения и свойства. Вычисление коэффициентов статистической структуры булевой функции идея алгоритма и на чём он основан. Связь -конфигураций и кодов с матрицами Адамара (доказательство).9) Идеалы кольца. Многочлены от нескольких переменных над кольцом. Лексикографическое упорядочение. Базис Грёбнера, бриллиантовая лемма, алгоритм Бухбергера и его модификация в случае многочленов над конечным простым полем. Задачи Упрощение булевой функции от 5 переменных. Минимизация ДНФ функции от 4 переменных. Поиск групп инерции булевой функции от 4 переменных относительно групп  .Нахождение многочлена Жегалкина булевой функции от 4 переменных. Проверка существования и нахождение трансверсали семейства множеств. Построение латинских квадратов 12х12 из латинских прямоугольников меньших размерностей. Вычисление перманента заданной матрицы 6х6. Вычисление коэффициентов статистической структуры булевой функции от 4 переменных. Вычисление базиса Грёбнера над GF(2) для семейства из трёх многочленов. |