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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Лекции)
(Экзамен)
(не показаны 11 промежуточные версии 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.
 +
*Проверить, является ли заданный граф планарным.
 +
*Проверить, найдется ли планарный граф с заданными свойствами.
 +
*Найти хроматическое число или хроматический индекс заданного графа.
 +
*Проверить разделимость заданного алфавитного кода (по алгоритму).
 +
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
 +
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
 +
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
 +
*Кодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
 +
*Найти диаграмму Мура автоматной функции, заданной описанием.
 +
*Найти диаграмму Мура, каноническую таблицу или канонические уравнения автоматной функции, заданной одним из перечисленных способов.
 +
*Построить диаграмму Мура, не содержащую недостижимых и неотличимых состояний, для заданной автоматной функции.
  
 
==Удаленное обучение==
 
==Удаленное обучение==
Строка 40: Строка 115:
  
 
[[Media: dm1-kf-l12-selezn.pdf | Лекция 12]]. Кодирование. Алфавитные коды. Проверка однозначности алфавитного кода. Теорема Маркова. Неравенство Макмиллана. Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.
 
[[Media: dm1-kf-l12-selezn.pdf | Лекция 12]]. Кодирование. Алфавитные коды. Проверка однозначности алфавитного кода. Теорема Маркова. Неравенство Макмиллана. Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.
<!---Лекция 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. Конечные автоматы. Отличимость состояний конечного автомата. Оценка длины слова, отличающего два отличимых состояния конечного автомата. Упрощение автоматов.--->
+
  
 
===Литература===
 
===Литература===

Версия 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.

Семинары

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

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