Дискретная математика (КФ) — различия между версиями

Текущая версия на 22:35, 15 мая 2024

Курс для студентов 1-го курса Казахстанского филиала МГУ, читается во 2-м семестре. Лекции - 32 ч, семинары - 32 ч, отчетность - экзамен.

Лектор - Селезнева Светлана Николаевна

Экзамен

Экзамен состоится 14 июня очно.

Экзамен письменный. Экзаменационная работа содержит восемь заданий по содержанию курса. Первые четыре задания - задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами. Вопросы проясняют понимание студентом определения или теоремы. Они оцениваются также в 3 балла каждое. Список вопросов и задач приведен на этой странице.

Продолжительность написания работы - 1 ч 30 мин (90 мин).

Примерный вариант экзаменационной работы

Экзамен проводится очно в аудитории. Работу следует написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются принимающему экзамен.

Вопросы к экзамену

• Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества.
• Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ.
• Полнота в алгебре логики, полные системы. Полнота некоторых систем.
• Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина.
• Замыкание множества, замкнутые классы. Замкнутость классов T_0, T_1, L, S, M.
• Леммы о несамодвойственной, немонотонной и нелинейной функциях.
• Теорема Поста о полноте.
• Базис в P_2. Теореме о числе функций в базисе P_2.
• Предполные классы. Теорема о предполных классах в P_2.
• Графы. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе.
• Деревья. Теорема о равносильных определениях дерева.
• Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.
• Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева.
• Геометрическое представление графов. Теорема о геометрическом представлении графов в трехмерном пространстве.
• Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского.
• Раскраски графов. Раскраски графов в два цвета.
• Теорема о раскраске планарного графа.
• Кодирование. Алфавитные коды. Проверка однозначности алфавитного кода. Теорема Маркова.
• Неравенство Макмиллана.
• Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов.
• Оптимальные коды (коды с минимальной избыточностью). Свойства оптимальных кодов.
• Теорема редукции. Метод Хаффмана построения оптимального кода.
• Устойчивость кодов к ошибкам. Коды, обнаруживающие и исправляющие ошибки, их свойства.
• Коды Хэмминга.
• Конечные автоматы. Способы их представления.
• Отличимость состояний конечного автомата. Теорема Мура. Упрощение автоматов.

Литература

1. Слайды к лекциям.
2. Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
3. Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс.
4. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
6. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.

Задачи к экзамену

• Найти существенные и фиктивные переменные заданной функции алгебры логики.
• Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
• Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
• Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
• Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
• Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
• Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
• Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
• Проверить, является ли заданный граф планарным.
• Проверить, найдется ли планарный граф с заданными свойствами.
• Найти хроматическое число или хроматический индекс заданного графа.
• Проверить разделимость заданного алфавитного кода (по алгоритму).
• Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
• Найти оптимальный алфавитный двоичный код по заданному набору частот.
• Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
• Кодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
• Найти диаграмму Мура автоматной функции, заданной описанием.
• Найти диаграмму Мура, каноническую таблицу или канонические уравнения автоматной функции, заданной одним из перечисленных способов.
• Построить диаграмму Мура, не содержащую недостижимых и неотличимых состояний, для заданной автоматной функции.

Удаленное обучение

Вопросы по содержанию курса (и другие вопросы, относящиеся к курсу) можно задавать лектору Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru