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

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

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

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

==Экзамен==

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

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

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

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

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

Итоги экзамена появятся 17 июня в 10 ч (по московскому времени). Затем до 11 ч (по московскому времени) 17 июня на почту dm1@cs.msu.ru можно прислать вопросы по оцениванию заданий в работах. После всех обсуждений оценки выставляются в ведомость.

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

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

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

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

==Лекции==

'''Алгебра логики'''

[[Media: dm1-l1-selezn.pdf | Лекция 1]]. Двоичный куб. Наборы, вес набора. Слой n-мерного куба. Частичный порядок на n-мерном кубе. Соседние и противоположные наборы, расстояние между наборами. Лексико-графический порядок на n-мерном кубе.

[[Media: dm1-l2-selezn.pdf | Лекция 2]]. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества. Двойственность.

[[Media: dm1-l3-selezn.pdf | Лекция 3]]. Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. Полные системы. Полнота некоторых систем.

[[Media: dm1-l4-selezn.pdf | Лекция 4]]. Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина. Полные системы. Полнота некоторых систем. 

[[Media: dm1-l5-selezn.pdf | Лекция 5]]. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M. Леммы о несамодвойственной, немонотонной и нелинейной функциях.

[[Media: dm1-l6-selezn.pdf | Лекция 6]]. Полные системы. Теорема Поста о полноте. Базис в P_2. Теореме о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.

'''Графы'''

[[Media: dm1-l7-selezn.pdf | Лекция 7]]. Графы. Простейшие свойства графов. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе. Орграфы.

[[Media: dm1-l8-selezn.pdf | Лекция 8]]. Деревья. Теорема о равносильных определениях дерева. Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.

[[Media: dm1-l9-selezn.pdf | Лекция 9]]. Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева.

[[Media: dm1-l10-selezn.pdf | Лекция 10]]. Геометрическое представление графов. Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского. 

[[Media: dm1-l11-selezn.pdf | Лекция 11]]. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.

'''Коды'''

[[Media: dm1-kf-l12-selezn.pdf | Лекция 12]]. Кодирование. Алфавитные коды. Проверка однозначности алфавитного кода. Теорема Маркова. Неравенство Макмиллана. Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.

[[Media: dm1-kf-l13-selezn.pdf | Лекция 13]]. Алфавитные коды. Оптимальные коды (коды с минимальной избыточностью). Свойства оптимальных кодов. Теорема редукции. Метод Хаффмана построения оптимального кода.

[[Media: dm1-kf-l14-selezn.pdf | Лекция 14]]. Устойчивость кодов к ошибкам. Коды, обнаруживающие и исправляющие ошибки, их свойства. Коды Хэмминга.

'''Автоматы'''

[[Media: dm1-kf-l15-selezn.pdf | Лекция 15]]. Конечные автоматы. Способы их представления. Отличимость состояний конечного автомата. Теорема Мура. Упрощение автоматов.

===Литература===
<ol>
<li> Слайды к лекциям.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. 
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. 
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.
</ol>

==Семинары==

[[Media: dm1-kf-s.pdf | План семинарских занятий]]

[[Media: dm1-1-s-d.pdf | Дополнительные задачи к семинарским занятиям]]