Просмотр исходного текста страницы Дискретная математика (1й курс)

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф.  [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

==Экзамен (2021 г.)==

'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''. 

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

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

[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]

Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.

Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости. 

'''Стандартные задачи к экзамену'''

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

== Вопросы к экзамену по курсу «Дискретная математика», 2021 год.==

===Часть А=== 
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона) (вопрос № 1 только для студентов 2-3 потоков).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием). 
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами. 
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности (разделимости) алфавитного кодирования (с обоснованием). 
<li> Теорема Маркова о взаимной однозначности (разделимости) алфавитного кодирования.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки. 
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В === 
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о представлении k-значных функций 1-й формой.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка. 
</ol>

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
</ol>

[[Категория:Лекционные курсы кафедры МК]]