Дискретная математика (1й курс)
Содержание
Лекторы
- проф. Алексеев Валерий Борисович
- проф. Марченков Сергей Серафимович
- проф. Селезнева Светлана Николаевна
Экзамен (2020 г.)
Пересдача экзамена по дискретной математике (сентябрь, 2020 г.) будет проходить удаленно в той же форме, что и основной экзамен летом 2020 г. Схема экзамена описана ниже.
Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами. Вопросы проясняют понимание студентом определения или теоремы. Они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи. Они показывают, может ли студент обосновывать утверждения и извлекать новые заключения из полученных знаний в курсе, оцениваются в 4 балла каждое. Продолжительность написания работы - 2 ч (120 мин).
Работу нужно написать от руки на светлых листах контрастной ручкой. После выполнения работы ее нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png отправить на проверку (загрузить по определенной ссылке, ссылка будет разослана старостам групп). На сканирование или фотографирование работы и ее отправку отводится 15 мин. Если работа студента не получена через 2 ч 15 мин после начала экзамена, то считается, что студент работу не сдал.
Примерный вариант экзаменационной работы
Стандартные задачи к экзамену
- Найти существенные и фиктивные переменные заданной функции алгебры логики.
- Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
- Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
- Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
- Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
- Записать заданную k-значную функцию в 1-й или 2-й форме.
- Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
- Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
- Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
- Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
- Проверить, является ли заданный граф планарным.
- Проверить, найдется ли планарный граф с заданными свойствами.
- Найти хроматическое число или хроматический индекс заданного графа.
- Проверить разделимость заданного алфавитного кода (по алгоритму).
- Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
- Найти оптимальный алфавитный двоичный код по заданному набору частот.
- Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
- Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
- Найти кодовое расстояние заданного линейного кода.
- Найти диаграмму Мура автоматной функции, заданной описанием.
- Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
- Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.
Вопросы к экзамену по курсу «Дискретная математика», 2020 год.
Часть А
- Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона) (вопрос № 1 только для студентов 2-3 потоков).
- Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
- Двойственность. Класс самодвойственных функций, его замкнутость.
- Лемма о нелинейной функции.
- Теорема Поста о полноте системы функций алгебры логики.
- Теорема о предполных классах.
- Теоремы о представлении k-значных функций 2-й формой и полиномами.
- Деревья. Свойства деревьев.
- Алгоритм построения кратчайшего остовного дерева (с обоснованием).
- Теорема о раскраске планарных графов в 5 цветов.
- Алгоритм распознавания взаимной однозначности (разделимости) алфавитного кодирования (с обоснованием).
- Теорема Маркова о взаимной однозначности (разделимости) алфавитного кодирования.
- Неравенство Макмиллана.
- Существование префиксного кода с заданными длинами кодовых слов.
- Теорема редукции.
- Коды с исправлением r ошибок. Оценка функции Mr(n).
- Коды Хэмминга. Оценка функции M1(n).
- Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
- Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
- Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
- Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
Часть В
- Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
- Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
- Полные системы. Примеры полных систем (с доказательством полноты).
- Теорема Жегалкина о представимости функции алгебры логики полиномом.
- Понятие замкнутого класса. Замкнутость классов T0, T1, L.
- Класс монотонных функций, его замкнутость.
- Лемма о несамодвойственной функции.
- Лемма о немонотонной функции.
- Теорема о максимальном числе функций в базисе в алгебре логики.
- k-значные функции. Теорема о представлении k-значных функций 1-й формой.
- Основные понятия теории графов. Изоморфизм графов. Связность.
- Корневые деревья. Верхняя оценка их числа.
- Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
- Планарные (плоские) графы. Формула Эйлера.
- Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
- Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
- Оптимальные коды, их свойства.
- Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
- Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
- Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
- Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
Литература
- Собственный конспект лекций.
- Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
- Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
- Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
- Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
- Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
- Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))