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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Удаленное обучение)
(Экзамен)
(не показана 21 промежуточная версия 1 участника)
Строка 4: Строка 4:
  
 
Лектор - [[Селезнева Светлана Николаевна]]
 
Лектор - [[Селезнева Светлана Николаевна]]
 +
 +
==Экзамен==
 +
 +
'''Экзамен состоится 14 июня очно'''.
 +
 +
Экзамен письменный. Экзаменационная работа содержит восемь заданий по содержанию курса. Первые четыре задания - задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами. Вопросы проясняют понимание студентом определения или теоремы. Они оцениваются также в 3 балла каждое. Список вопросов и задач приведен на этой странице.
 +
 +
Продолжительность написания работы - 1 ч 30 мин (90 мин).
 +
 +
[[Media: example-dm-kf-exam.pdf | Примерный вариант экзаменационной работы]]
 +
 +
Экзамен проводится очно в аудитории. Работу следует написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются принимающему экзамен.
 +
 +
<!---Итоги экзамена появятся 18 июня в 14 ч (по московскому времени) (время появления итогов экзамена изменено). Затем до 15 ч (по московскому времени) 17 июня на почту dm1@cs.msu.ru можно прислать вопросы по оцениванию заданий в работах. После всех обсуждений оценки выставляются в ведомость.--->
 +
 +
'''Вопросы к экзамену'''
 +
 +
*Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества.
 +
*Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ.
 +
*Полнота в алгебре логики, полные системы. Полнота некоторых систем.
 +
*Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина.
 +
*Замыкание множества, замкнутые классы. Замкнутость классов T_0, T_1, L, S, M.
 +
*Леммы о несамодвойственной, немонотонной и нелинейной функциях.
 +
*Теорема Поста о полноте.
 +
*Базис в P_2. Теореме о числе функций в базисе P_2.
 +
*Предполные классы. Теорема о предполных классах в P_2.
 +
*Графы. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе.
 +
*Деревья. Теорема о равносильных определениях дерева.
 +
*Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.
 +
*Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева.
 +
*Геометрическое представление графов. Теорема о геометрическом представлении графов в трехмерном пространстве.
 +
*Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского.
 +
*Раскраски графов. Раскраски графов в два цвета.
 +
*Теорема о раскраске планарного графа.
 +
*Кодирование. Алфавитные коды. Проверка однозначности алфавитного кода. Теорема Маркова.
 +
*Неравенство Макмиллана.
 +
*Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов.
 +
*Оптимальные коды (коды с минимальной избыточностью). Свойства оптимальных кодов.
 +
*Теорема редукции. Метод Хаффмана построения оптимального кода.
 +
*Устойчивость кодов к ошибкам. Коды, обнаруживающие и исправляющие ошибки, их свойства.
 +
*Коды Хэмминга.
 +
*Конечные автоматы. Способы их представления.
 +
*Отличимость состояний конечного автомата. Теорема Мура. Упрощение автоматов.
 +
 +
'''Литература'''
 +
<ol>
 +
<li> Слайды к лекциям.
 +
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
 +
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс.
 +
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
 +
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
 +
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.
 +
</ol>
 +
 +
'''Задачи к экзамену'''
 +
 +
*Найти существенные и фиктивные переменные заданной функции алгебры логики.
 +
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
 +
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
 +
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
 +
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
 +
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
 +
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
 +
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
 +
*Проверить, является ли заданный граф планарным.
 +
*Проверить, найдется ли планарный граф с заданными свойствами.
 +
*Найти хроматическое число или хроматический индекс заданного графа.
 +
*Проверить разделимость заданного алфавитного кода (по алгоритму).
 +
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
 +
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
 +
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
 +
*Кодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
 +
*Найти диаграмму Мура автоматной функции, заданной описанием.
 +
*Найти диаграмму Мура, каноническую таблицу или канонические уравнения автоматной функции, заданной одним из перечисленных способов.
 +
*Построить диаграмму Мура, не содержащую недостижимых и неотличимых состояний, для заданной автоматной функции.
  
 
==Удаленное обучение==
 
==Удаленное обучение==
  
 
Вопросы по содержанию курса (и другие вопросы, относящиеся к курсу) можно задавать лектору Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru
 
Вопросы по содержанию курса (и другие вопросы, относящиеся к курсу) можно задавать лектору Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru
 
<!---Записи лекций можно найти по ссылке [https://m.cs.msu.ru/index.php/s/N6FkcmFbxQkS8z9] в разделе '''СелезневаСН'''.--->
 
  
 
==Лекции==
 
==Лекции==
Строка 15: Строка 88:
 
'''Алгебра логики'''
 
'''Алгебра логики'''
  
Лекция 1. Двоичный куб. Наборы, вес набора. Слой n-мерного куба. Частичный порядок на n-мерном кубе. Соседние и противоположные наборы, расстояние между наборами. Лексико-графический порядок на n-мерном кубе.
+
[[Media: dm1-l1-selezn.pdf | Лекция 1]]. Двоичный куб. Наборы, вес набора. Слой n-мерного куба. Частичный порядок на n-мерном кубе. Соседние и противоположные наборы, расстояние между наборами. Лексико-графический порядок на n-мерном кубе.
  
Лекция 2. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества. Двойственность.
+
[[Media: dm1-l2-selezn.pdf | Лекция 2]]. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества. Двойственность.
  
Лекция 3. Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. Полные системы. Полнота некоторых систем.
+
[[Media: dm1-l3-selezn.pdf | Лекция 3]]. Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. Полные системы. Полнота некоторых систем.
  
Лекция 4. Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина. Полные системы. Полнота некоторых систем.  
+
[[Media: dm1-l4-selezn.pdf | Лекция 4]]. Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина. Полные системы. Полнота некоторых систем.  
  
Лекция 5. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M. Леммы о несамодвойственной, немонотонной и нелинейной функциях.
+
[[Media: dm1-l5-selezn.pdf | Лекция 5]]. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M. Леммы о несамодвойственной, немонотонной и нелинейной функциях.
  
Лекция 6. Полные системы. Теорема Поста о полноте. Базис в P_2. Теореме о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.
+
[[Media: dm1-l6-selezn.pdf | Лекция 6]]. Полные системы. Теорема Поста о полноте. Базис в P_2. Теореме о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.
  
 
'''Графы'''
 
'''Графы'''
  
Лекция 7. Графы. Простейшие свойства графов. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе. Орграфы.
+
[[Media: dm1-l7-selezn.pdf | Лекция 7]]. Графы. Простейшие свойства графов. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе. Орграфы.
  
Лекция 8. Деревья. Теорема о равносильных определениях дерева. Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.
+
[[Media: dm1-l8-selezn.pdf | Лекция 8]]. Деревья. Теорема о равносильных определениях дерева. Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.
  
Лекция 9. Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева.
+
[[Media: dm1-l9-selezn.pdf | Лекция 9]]. Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева.
  
Лекция 10. Геометрическое представление графов. Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского.  
+
[[Media: dm1-l10-selezn.pdf | Лекция 10]]. Геометрическое представление графов. Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского.  
  
Лекция 11. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.
+
[[Media: dm1-l11-selezn.pdf | Лекция 11]]. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.
  
 
'''Коды'''
 
'''Коды'''
  
Лекция 12. Кодирование. Алфавитные коды. Теорема об однозначности равномерного кода. Теорема об однозначности префиксного кода. Алгоритм распознавания однозначности алфавитного кода. Теорема Маркова.
+
[[Media: dm1-kf-l12-selezn.pdf | Лекция 12]]. Кодирование. Алфавитные коды. Проверка однозначности алфавитного кода. Теорема Маркова. Неравенство Макмиллана. Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.
 
+
Лекция 13. Алфавитные коды. Неравенство Макмиллана. Теорема о существовании префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.
+
 
+
Лекция 14. Алфавитные коды. Оптимальные коды (коды с минимальной избыточностью). Свойства оптимальных кодов. Теорема редукции. Метод Хаффмана построения оптимального кода.
+
  
Лекция 15. Коды, обнаруживающие и исправляющие ошибки, их свойства. Мощность кода, исправляющего ошибки. Линейные коды и их свойства.
+
[[Media: dm1-kf-l13-selezn.pdf | Лекция 13]]. Алфавитные коды. Оптимальные коды (коды с минимальной избыточностью). Свойства оптимальных кодов. Теорема редукции. Метод Хаффмана построения оптимального кода.
  
Лекция 16. Коды, исправляющие одну ошибку. Коды Хэмминга и их свойства. Мощность кода, исправляющего одну ошибку.
+
[[Media: dm1-kf-l14-selezn.pdf | Лекция 14]]. Устойчивость кодов к ошибкам. Коды, обнаруживающие и исправляющие ошибки, их свойства. Коды Хэмминга.
  
 
'''Автоматы'''
 
'''Автоматы'''
  
Лекция 17. Конечные автоматы. Способы их представления. Схемы из функциональных элементов с задержками (СФЭЗ) и представление конечных автоматов ими.
+
[[Media: dm1-kf-l15-selezn.pdf | Лекция 15]]. Конечные автоматы. Способы их представления. Отличимость состояний конечного автомата. Теорема Мура. Упрощение автоматов.
  
Лекция 18. Конечные автоматы. Отличимость состояний конечного автомата. Оценка длины слова, отличающего два отличимых состояния конечного автомата. Упрощение автоматов.
+
===Литература===
 +
<ol>
 +
<li> Слайды к лекциям.
 +
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
 +
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс.
 +
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
 +
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
 +
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.
 +
</ol>
  
 
==Семинары==
 
==Семинары==

Версия 09:38, 17 июня 2022


Курс для студентов 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

Лекции

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

Лекция 1. Двоичный куб. Наборы, вес набора. Слой n-мерного куба. Частичный порядок на n-мерном кубе. Соседние и противоположные наборы, расстояние между наборами. Лексико-графический порядок на n-мерном кубе.

Лекция 2. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества. Двойственность.

Лекция 3. Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. Полные системы. Полнота некоторых систем.

Лекция 4. Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина. Полные системы. Полнота некоторых систем.

Лекция 5. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M. Леммы о несамодвойственной, немонотонной и нелинейной функциях.

Лекция 6. Полные системы. Теорема Поста о полноте. Базис в P_2. Теореме о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.

Графы

Лекция 7. Графы. Простейшие свойства графов. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе. Орграфы.

Лекция 8. Деревья. Теорема о равносильных определениях дерева. Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.

Лекция 9. Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева.

Лекция 10. Геометрическое представление графов. Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского.

Лекция 11. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.

Коды

Лекция 12. Кодирование. Алфавитные коды. Проверка однозначности алфавитного кода. Теорема Маркова. Неравенство Макмиллана. Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.

Лекция 13. Алфавитные коды. Оптимальные коды (коды с минимальной избыточностью). Свойства оптимальных кодов. Теорема редукции. Метод Хаффмана построения оптимального кода.

Лекция 14. Устойчивость кодов к ошибкам. Коды, обнаруживающие и исправляющие ошибки, их свойства. Коды Хэмминга.

Автоматы

Лекция 15. Конечные автоматы. Способы их представления. Отличимость состояний конечного автомата. Теорема Мура. Упрощение автоматов.

Литература

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

Семинары

План семинарских занятий

Дополнительные задачи к семинарским занятиям