Дискретная математика (1-й поток) — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Подготовка к госэкзамену)
(Лекции)
 
(не показаны 102 промежуточных версий 1 участника)
Строка 5: Строка 5:
  
 
Лектор - [[Селезнева Светлана Николаевна]]
 
Лектор - [[Селезнева Светлана Николаевна]]
 +
<!---=='''Подготовка к госэкзамену''' (для студентов 4-го курса)==
  
=='''Подготовка к госэкзамену'''==
+
В этом разделе представлены ответы на некоторые вопросы госэкзамена. Эти вопросы читаются в курсах по дискретной математике (курсы "Дискретная математика" и "Дополнительные главы дискретной математики"). Вопросы госэкзамена всех потоков, основной и дополнительной частей.
  
 
1. Функции алгебры логики. Реализация их формулами. Совершенная  дизъюнктивная нормальная форма.  
 
1. Функции алгебры логики. Реализация их формулами. Совершенная  дизъюнктивная нормальная форма.  
Строка 20: Строка 21:
 
[[Media: dm-gos4-selezn.pdf | Ответ на вопрос 4]]
 
[[Media: dm-gos4-selezn.pdf | Ответ на вопрос 4]]
  
<!---5. Графы, деревья. Свойства деревьев. Алгоритм построения остовного дерева. Оценка числа деревьев.
+
5. Графы, деревья. Свойства деревьев. Алгоритм построения остовного дерева. Оценка числа деревьев.
 
[[Media: dm-gos5-selezn.pdf | Ответ на вопрос 5]]
 
[[Media: dm-gos5-selezn.pdf | Ответ на вопрос 5]]
  
Строка 28: Строка 29:
 
7. Схемы из функциональных элементов. N-разрядный сумматор, оценка сложности СФЭ для n-разрядного сумматора. N-разрядный вычитатель и оценка его сложности.
 
7. Схемы из функциональных элементов. N-разрядный сумматор, оценка сложности СФЭ для n-разрядного сумматора. N-разрядный вычитатель и оценка его сложности.
 
[[Media: dm-gos7-selezn.pdf | Ответ на вопрос 7]]--->
 
[[Media: dm-gos7-selezn.pdf | Ответ на вопрос 7]]--->
 +
<!---8. Сложность алгоpитмов. Классы P и NP. Теоpема об NP-полноте задачи о выполнимости КНФ.
 +
[[Media: dm-gos8-selezn.pdf | Ответ на вопрос 8]]--->
  
==Экзамен==
+
==Объявления==
  
<!---'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''.  
+
Вопросы по содержанию курса (и другие вопросы, относящиеся к курсу) можно задавать лектору Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru
  
Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами. Вопросы проясняют понимание студентом определения или теоремы. Они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи. Они показывают, может ли студент обосновывать утверждения и извлекать новые заключения из полученных знаний в курсе, оцениваются в 4 балла каждое. Эти задания могут состоять в доказательствах утверждений из части Б списка вопросов к экзамену.
+
==Программа курса==
  
Продолжительность написания работы - 2 ч (120 мин).
+
'''1. Алгебра логики'''. Функции алгебры логики, их представление таблицами истинности и формулами. Существенность  переменных. Тождества, эквивалентные преобразования формул. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Полиномы Жегалкина. Полнота в алгебре логики. Замкнутые классы. Предполные классы.  
  
[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]
+
'''2. Графы'''. Графы, их простейшие свойства. Связность. Деревья, остовные деревья. Планарность графов. Раскраски графов.
  
Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.
+
'''3. Коды'''. Кодирование. Алфавитные коды, их свойства. Однозначность (разделимость) алфавитных кодов. Оптимальность алфавитных кодов. Коды, обнаруживающие и исправляющие ошибки. Коды Хэмминга. Линейные коды.
  
Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.  
+
'''4. Конечные автоматы'''. Конечные автоматы-преобразователи и конечно-автоматные функции. Представления конечных автоматов и конечно-автоматных функций. Упрощение конечных автоматов.
  
'''Вопросы к экзамену''' можно посмотреть на странице [[Дискретная математика (1й курс)]]
+
'''5. Сложность'''. Схемы из функциональных элементов (СФЭ), представление функций алгебры логики ими. Сумматор, оценка его сложности в СФЭ. Вычитатель, оценка его сложности в СФЭ. Умножитель, оценка его сложности в СФЭ.
  
'''Стандартные задачи к экзамену'''
+
'''6. Многозначные логики'''. Функции многозначной логики, их представление нормальными формами и полиномами.
  
*Найти существенные и фиктивные переменные заданной функции алгебры логики.
+
'''Литература'''
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
+
<ol>
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
+
<li> Конспекты лекций.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
+
<li> Слайды к лекциям
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
+
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
*Записать заданную k-значную функцию в 1-й или 2-й форме.
+
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс.  
*Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.  
+
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.  
+
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.  
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
+
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
+
</ol>
*Проверить, является ли заданный граф планарным.
+
*Проверить, найдется ли планарный граф с заданными свойствами.
+
*Найти хроматическое число или хроматический индекс заданного графа.
+
*Проверить разделимость заданного алфавитного кода (по алгоритму).
+
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
+
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
+
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
+
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
+
*Найти кодовое расстояние заданного линейного кода.
+
*Найти диаграмму Мура автоматной функции, заданной описанием.
+
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
+
*Построить диаграмму Мура, не содержащую неотличимых состояний, для заданной автоматной функции.--->
+
  
==Удаленное обучение==
+
==Лекции==
  
Вопросы по содержанию курса (и другие вопросы, относящиеся к курсу) можно задавать лектору Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru
+
Слайды к лекциям можно найти по прямой ссылке [https://m.cs.msu.ru/s/yN44Ca7d9aXmFE4 '''Дискретная математика, 1 поток''']
  
Записи лекций можно найти по ссылке [https://m.cs.msu.ru/index.php/s/N6FkcmFbxQkS8z9] в разделе '''СелезневаСН''' или по прямой ссылке [https://m.cs.msu.ru/s/zKAxX54jJ9ZB3MA].
+
1. '''Алгебра логики'''
  
==Лекции==
+
Лекция 1. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества.
  
'''Алгебра логики'''
+
Лекция 2. Разложение функций по переменным. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Совершенная ДНФ и совершенная КНФ.
 +
<!---[[Media: dm1-1-selezn-l3.pdf | Лекция 3]]. Сокращенная ДНФ. Построение сокращенной ДНФ по КНФ.--->
  
[[Media: dm1-l1-selezn.pdf | Лекция 1]]. Двоичный куб. Наборы, вес набора. Слой n-мерного куба. Частичный порядок на n-мерном кубе. Соседние и противоположные наборы, расстояние между наборами. Лексико-графический порядок на n-мерном кубе.
+
Лекция 3. Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина.
  
[[Media: dm1-l2-selezn.pdf | Лекция 2]]. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества. Двойственность.
+
Лекция 4. Полные системы, полнота некоторых систем. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M.  
  
[[Media: dm1-l3-selezn.pdf | Лекция 3]]. Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. Полные системы. Полнота некоторых систем.
+
Лекция 5. Леммы о несамодвойственной, немонотонной и нелинейной функциях. Полнота. Теорема Поста о полноте.  
  
[[Media: dm1-l4-selezn.pdf | Лекция 4]]. Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина. Полные системы. Полнота некоторых систем.  
+
Лекция 6. Базисы в P_2. Теорема о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.
  
[[Media: dm1-l5-selezn.pdf | Лекция 5]]. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M. Леммы о несамодвойственной, немонотонной и нелинейной функциях.
+
2. '''Графы'''
  
[[Media: dm1-l6-selezn.pdf | Лекция 6]]. Полные системы. Теорема Поста о полноте. Базис в P_2. Теореме о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.
+
Лекция 7. Графы. Простейшие свойства графов. Пути и цепи. Циклы и связность. Удаление и добавление ребер в связных графах. Соотношение между числом вершин, числом ребер и числом компонент связности в графе. Орграфы.
  
'''Графы'''
+
Лекция 8. Деревья. Теорема о равносильных определениях дерева. Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.
  
[[Media: dm1-l7-selezn.pdf | Лекция 7]]. Графы. Простейшие свойства графов. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе. Орграфы.
+
Лекция 9. Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева.  
  
[[Media: dm1-l8-selezn.pdf | Лекция 8]]. Деревья. Теорема о равносильных определениях дерева. Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.
+
Лекция 10. Геометрическое представление графов. Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского.  
  
[[Media: dm1-l9-selezn.pdf | Лекция 9]]. Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева.  
+
Лекция 11. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.
  
[[Media: dm1-l10-selezn.pdf | Лекция 10]]. Геометрическое представление графов. Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского.  
+
3. '''Коды'''
 +
<!---[[Media: dm1-1-selezn-l12.pdf | Лекция 12]]. Кодирование. Алфавитные коды. Теорема об однозначности равномерного кода. Теорема об однозначности префиксного кода. Алгоритм распознавания однозначности алфавитного кода. Теорема Маркова.
  
[[Media: dm1-l11-selezn.pdf | Лекция 11]]. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.
+
[[Media: dm1-1-selezn-l13.pdf | Лекция 13]]. Алфавитные коды. Неравенство Макмиллана. Теорема о существовании префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.
  
'''Коды'''
+
[[Media: dm1-1-selezn-l14.pdf | Лекция 14]]. Алфавитные коды. Оптимальные коды (коды с минимальной избыточностью). Свойства оптимальных кодов. Теорема редукции. Метод Хаффмана построения оптимального кода.
  
[[Media: dm1-l12-selezn.pdf | Лекция 12]]. Кодирование. Алфавитные коды. Теорема об однозначности равномерного кода. Теорема об однозначности префиксного кода. Алгоритм распознавания однозначности алфавитного кода. Теорема Маркова.
+
[[Media: dm1-1-selezn-l15.pdf | Лекция 15]]. Коды, обнаруживающие и исправляющие ошибки, их свойства. Мощность кода, исправляющего ошибки. Линейные коды и их свойства.
  
[[Media: dm1-l13-selezn.pdf | Лекция 13]]. Алфавитные коды. Неравенство Макмиллана. Теорема о существовании префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.
+
[[Media: dm1-1-selezn-l16.pdf | Лекция 16]]. Коды, исправляющие одну ошибку. Коды Хэмминга и их свойства. Мощность кода, исправляющего одну ошибку.--->
  
[[Media: dm1-l14-selezn.pdf | Лекция 14]]. Алфавитные коды. Оптимальные коды (коды с минимальной избыточностью). Свойства оптимальных кодов. Теорема редукции. Метод Хаффмана построения оптимального кода.
+
4. '''Автоматы'''
 +
<!---[[Media: dm1-1-selezn-l17.pdf | Лекция 17]]. Конечные автоматы. Способы их представления. Схемы из функциональных элементов с задержками (СФЭЗ) и представление конечных автоматов ими.
  
[[Media: dm1-l15-selezn.pdf | Лекция 15]]. Коды, обнаруживающие и исправляющие ошибки, их свойства. Мощность кода, исправляющего ошибки. Линейные коды и их свойства.
+
[[Media: dm1-1-selezn-l18.pdf | Лекция 18]]. Конечные автоматы. Отличимость состояний конечного автомата. Оценка длины слова, отличающего два отличимых состояния конечного автомата. Упрощение автоматов.--->
  
[[Media: dm1-l16-selezn.pdf | Лекция 16]]. Коды, исправляющие одну ошибку. Коды Хэмминга и их свойства. Мощность кода, исправляющего одну ошибку.
+
5. '''Сложность'''
 +
<!---[[Media: dm1-1-selezn-l19.pdf | Лекция 19]]. Схемы из функциональных элементов (СФЭ). Схемы для сложения и вычитания, их сложность.
  
'''Автоматы'''
+
[[Media: dm1-1-selezn-l20.pdf | Лекция 20]]. Схема для умножения. Сложность схемы для умножения по методу Карацубы.--->
  
[[Media: dm1-l17-selezn.pdf | Лекция 17]]. Конечные автоматы. Способы их представления. Схемы из функциональных элементов с задержками (СФЭЗ) и представление конечных автоматов ими.
+
6. '''Многозначные логики'''
 +
<!---[[Media: dm1-1-selezn-l21.pdf | Лекция 21]]. Функции k-значной логики. Таблицы значений. Представление функций k-значной логики в 1-й и 2-й формах. Представление функций k-значной логики полиномами по модулю k.--->
  
[[Media: dm1-l18-selezn.pdf | Лекция 18]]. Конечные автоматы. Отличимость состояний конечного автомата. Оценка длины слова, отличающего два отличимых состояния конечного автомата. Упрощение автоматов.
+
==Семинары==
  
'''СФЭ'''
+
[[Media: dm1-1-s.pdf | План семинарских занятий]]
  
[[Media: dm1-l19-selezn.pdf | Лекция 19]]. Схемы из функциональных элементов (СФЭ). Схемы для сложения и вычитания, их сложность.
+
[[Media: dm1-1-s-d.pdf | Дополнительные задачи к семинарским занятиям]]
  
[[Media: dm1-l20-selezn.pdf | Лекция 20]]. Схема для умножения. Сложность схемы для умножения по методу Карацубы.
+
==Записи лекций==
  
'''Многозначные логики'''
+
Записи лекций Селезневой С.Н., прочитанных в 2021 г., можно найти по прямой ссылке [https://m.cs.msu.ru/s/6JnNMf5AXwYT7JF '''Записи лекций''']
  
[[Media: dm1-l21-selezn.pdf | Лекция 21]]. Функции k-значной логики. Таблицы значений. Представление функций k-значной логики в 1-й и 2-й формах. Представление функций k-значной логики полиномами по модулю k.
+
==Экзамен==
  
==Семинары==
+
Экзамен устный. В билете два теоретических вопроса и задача. Первый вопрос билета - из части А, второй вопрос билета - из части Б.
  
[[Media: dm1-1-s.pdf | План семинарских занятий]]
+
'''Вопросы к экзамену'''
  
[[Media: dm1-1-s-d.pdf | Дополнительные задачи к семинарским занятиям]]
+
'''Часть А'''.
 +
Ответ без подготовки, но с возможностью смотреть любые бумажные источники (конспекты лекций, распечатки слайдов, учебники, пр.). Пользоваться любыми электронными средствами (телефонами, планшетами, ноутбуками, пр.) не разрешается. Проверяется понимание материала и умение пояснить переходы в доказательствах утверждений. Важно: все определения и теоремы вопроса следует сформулировать без источников (до того, как материалы будут открыты).
 +
 
 +
<ol>
 +
<li> Функции алгебры логики. Полиномы Жегалкина. Быстрый алгоритм построения полинома Жегалкина функции алгебры логики (с обоснованием).
 +
<li> Функции алгебры логики. Двойственность. Самодвойственные функции. Замкнутость класса самодвойственных функций.
 +
<li> Функции алгебры логики. Линейные функции. Лемма о нелинейной функции.
 +
<li> Функции алгебры логики. Полнота. Теорема Поста о полноте системы функций алгебры логики.
 +
<li> Функции алгебры логики. Предполные классы. Теорема о предполных классах.
 +
<li> Функции k-значной логики. Теоремы о представлении функций k-значной логики во 2-й форме и полиномами по модулю k.
 +
<li> Деревья. Теорема о равносильных определениях дерева.
 +
<li> Остовные деревья. Алгоритм построения кратчайшего остовного дерева в связном графе (с обоснованием).
 +
<li> Раскраски вершин графов. Теорема о раскраске вершин планарных графов в 5 цветов.
 +
<li> Алфавитные коды. Однозначность (разделимость) алфавитного кода. Алгоритм распознавания однозначности алфавитного кода (с обоснованием).
 +
<li> Алфавитные коды. Теорема Маркова об алфавитных кодах.
 +
<li> Алфавитные коды. Неравенство Макмиллана.
 +
<li> Алфавитные коды. Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов.
 +
<li> Оптимальные коды (коды с минимальной избыточностью). Теорема редукции.
 +
<li> Коды, обнаруживающие и исправляющие ошибки. Критерии кодов, обнаруживающих и исправляющих t ошибок замещения. Функция Mt(n), ее оценки.
 +
<li> Коды, исправляющие одну ошибку. Коды Хэмминга. Оценка функции M1(n).
 +
<li> Схемы из функциональных элементов и элементов задержки (СФЭЗ). Автоматность осуществляемых ими отображений.
 +
<li> Схемы из функциональных элементов и элементов задержки (СФЭЗ). Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
 +
<li> Конечные автоматы. Отличимость состояний конечного автомата. Теорема Мура. Достижимость оценки теоремы Мура.
 +
<li> Схемы из функциональных элементов (СФЭ). Умножитель. Метод Карацубы построения умножителя, верхняя оценка его сложности.
 +
</ol>
 +
 
 +
'''Часть Б'''.
 +
Ответ почти без подготовки и без возможности пользоваться источниками.
 +
 
 +
<ol start="21">
 +
<li> Функции алгебры логики. Существенность переменных. Формулы. Тождества.
 +
<li> Функции алгебры логики. Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме (ДНФ). Теорема о совершенной конъюнктивной нормальной форме (КНФ).
 +
<li> Функции алгебры логики. Полные системы. Примеры полных систем (с доказательством полноты).
 +
<li> Функции алгебры логики. Теорема Жегалкина о представимости функции алгебры логики полиномом Жегалкина.
 +
<li> Функции алгебры логики. Замыкание, замкнутый класс. Функции, сохраняющие константу, и линейные функции. Замкнутость классов функций, сохраняющих константу, и линейных функций.
 +
<li> Функции алгебры логики. Монотонные функции. Замкнутость класса монотонных функций.
 +
<li> Функции алгебры логики. Самодвойственные функции. Лемма о несамодвойственной функции.
 +
<li> Функции алгебры логики. Монотонные функции. Лемма о немонотонной функции.
 +
<li> Функции алгебры логики. Базис. Теорема о числе функций в базисе в алгебре логики.
 +
<li> Функции k-значной логики. Теорема о представлении функций k-значной логики в 1-й форме.
 +
<li> Графы. Изоморфизм графов. Связность. Простейшие свойства графов. Теорема о числе вершин, ребер и компонент связности в графе.
 +
<li> Деревья. Корневые деревья, упорядоченные корневые деревья. Верхняя оценка числа деревьев с заданным числом ребер.
 +
<li> Геометрическое представление графов. Теорема о геометрическом представлении графов в трехмерном пространстве.
 +
<li> Планарные графы. Формула Эйлера для планарных графов. Теорема о наибольшем числе ребер в планарном графе.
 +
<li> Графы K5 и K3,3. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
 +
<li> Раскраски вершин графов. Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
 +
<li> Оптимальные коды (коды с минимальной избыточностью). Леммы о свойствах оптимальных кодов.
 +
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
 +
<li> Схемы из функциональных элементов. Сумматор, верхняя оценка его сложности. Вычитатель, верхняя оценка его сложности.
 +
<li> Конечные автоматы. Функционирование конечного автомата. Автоматные функции. Канонические уравнения и диаграмма Мура конечного автомата. Единичная задержка, ее автоматность.
 +
</ol>
 +
 
 +
'''Литература'''
 +
<ol>
 +
<li> Слайды к лекциям.
 +
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
 +
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс.
 +
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
 +
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
 +
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.
 +
</ol>
 +
 
 +
'''Задачи к экзамену'''
 +
 
 +
*Найти существенные и фиктивные переменные заданной функции алгебры логики.
 +
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
 +
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
 +
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
 +
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
 +
*Записать заданную функцию k-значной логики в 1-й или 2-й форме.
 +
*Найти полином по модулю k заданной функции k-значной логики при заданном простом числе k или проверить, можно ли представить заданную функцию k-значной логики полиномом по модулю k при заданном составном числе k.
 +
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
 +
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
 +
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
 +
*Проверить, является ли заданный граф планарным.
 +
*Проверить, найдется ли планарный граф с заданными свойствами.
 +
*Найти хроматическое число или хроматический индекс заданного графа.
 +
*Проверить разделимость заданного алфавитного кода (по алгоритму).
 +
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
 +
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
 +
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
 +
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
 +
*Найти кодовое расстояние заданного линейного кода.
 +
*Найти диаграмму Мура автоматной функции, заданной описанием.
 +
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
 +
*Построить диаграмму Мура, не содержащую недостижимых и неотличимых состояний, для заданной автоматной функции.
 
<!---[[Media: dm1-s1-selezn.pdf | Занятие 1]]. Функции алгебры логики. Формулы. Тождества. Существенность переменных.
 
<!---[[Media: dm1-s1-selezn.pdf | Занятие 1]]. Функции алгебры логики. Формулы. Тождества. Существенность переменных.
  
Строка 151: Строка 232:
 
[[Media: dm1-s11-selezn.pdf | Занятие 11]]. Конечные автоматы и автоматные функции. Способы их представления: канонические уравнения и диаграммы Мура.
 
[[Media: dm1-s11-selezn.pdf | Занятие 11]]. Конечные автоматы и автоматные функции. Способы их представления: канонические уравнения и диаграммы Мура.
  
[[Media: dm1-s12-selezn.pdf | Занятие 12]]. Конечные автоматы и автоматные функции. Способы их представления: схемы из функциональных элементов с задержками (СФЭЗ). Упрощение конечных автоматов.--->
+
[[Media: dm1-s12-selezn.pdf | Занятие 12]]. Конечные автоматы и автоматные функции. Способы их представления: схемы из функциональных элементов с задержками (СФЭЗ). Упрощение конечных автоматов.
 +
 
 +
<!---'''Вторая пересдача экзамена состоится 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 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.--->

Текущая версия на 17:06, 18 марта 2024

Дополнительная страница по курсу Дискретная математика (1й курс).

Основной курс для студентов 1-го курса, читается во 2-м семестре. Лекции - 3 ч в неделю, семинары - 2 ч в неделю, отчетность - экзамен.

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

Объявления

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

Программа курса

1. Алгебра логики. Функции алгебры логики, их представление таблицами истинности и формулами. Существенность переменных. Тождества, эквивалентные преобразования формул. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Полиномы Жегалкина. Полнота в алгебре логики. Замкнутые классы. Предполные классы.

2. Графы. Графы, их простейшие свойства. Связность. Деревья, остовные деревья. Планарность графов. Раскраски графов.

3. Коды. Кодирование. Алфавитные коды, их свойства. Однозначность (разделимость) алфавитных кодов. Оптимальность алфавитных кодов. Коды, обнаруживающие и исправляющие ошибки. Коды Хэмминга. Линейные коды.

4. Конечные автоматы. Конечные автоматы-преобразователи и конечно-автоматные функции. Представления конечных автоматов и конечно-автоматных функций. Упрощение конечных автоматов.

5. Сложность. Схемы из функциональных элементов (СФЭ), представление функций алгебры логики ими. Сумматор, оценка его сложности в СФЭ. Вычитатель, оценка его сложности в СФЭ. Умножитель, оценка его сложности в СФЭ.

6. Многозначные логики. Функции многозначной логики, их представление нормальными формами и полиномами.

Литература

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

Лекции

Слайды к лекциям можно найти по прямой ссылке Дискретная математика, 1 поток

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

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

Лекция 2. Разложение функций по переменным. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Совершенная ДНФ и совершенная КНФ.

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

Лекция 4. Полные системы, полнота некоторых систем. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M.

Лекция 5. Леммы о несамодвойственной, немонотонной и нелинейной функциях. Полнота. Теорема Поста о полноте.

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

2. Графы

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

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

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

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

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

3. Коды

4. Автоматы

5. Сложность

6. Многозначные логики

Семинары

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

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

Записи лекций

Записи лекций Селезневой С.Н., прочитанных в 2021 г., можно найти по прямой ссылке Записи лекций

Экзамен

Экзамен устный. В билете два теоретических вопроса и задача. Первый вопрос билета - из части А, второй вопрос билета - из части Б.

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

Часть А. Ответ без подготовки, но с возможностью смотреть любые бумажные источники (конспекты лекций, распечатки слайдов, учебники, пр.). Пользоваться любыми электронными средствами (телефонами, планшетами, ноутбуками, пр.) не разрешается. Проверяется понимание материала и умение пояснить переходы в доказательствах утверждений. Важно: все определения и теоремы вопроса следует сформулировать без источников (до того, как материалы будут открыты).

  1. Функции алгебры логики. Полиномы Жегалкина. Быстрый алгоритм построения полинома Жегалкина функции алгебры логики (с обоснованием).
  2. Функции алгебры логики. Двойственность. Самодвойственные функции. Замкнутость класса самодвойственных функций.
  3. Функции алгебры логики. Линейные функции. Лемма о нелинейной функции.
  4. Функции алгебры логики. Полнота. Теорема Поста о полноте системы функций алгебры логики.
  5. Функции алгебры логики. Предполные классы. Теорема о предполных классах.
  6. Функции k-значной логики. Теоремы о представлении функций k-значной логики во 2-й форме и полиномами по модулю k.
  7. Деревья. Теорема о равносильных определениях дерева.
  8. Остовные деревья. Алгоритм построения кратчайшего остовного дерева в связном графе (с обоснованием).
  9. Раскраски вершин графов. Теорема о раскраске вершин планарных графов в 5 цветов.
  10. Алфавитные коды. Однозначность (разделимость) алфавитного кода. Алгоритм распознавания однозначности алфавитного кода (с обоснованием).
  11. Алфавитные коды. Теорема Маркова об алфавитных кодах.
  12. Алфавитные коды. Неравенство Макмиллана.
  13. Алфавитные коды. Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов.
  14. Оптимальные коды (коды с минимальной избыточностью). Теорема редукции.
  15. Коды, обнаруживающие и исправляющие ошибки. Критерии кодов, обнаруживающих и исправляющих t ошибок замещения. Функция Mt(n), ее оценки.
  16. Коды, исправляющие одну ошибку. Коды Хэмминга. Оценка функции M1(n).
  17. Схемы из функциональных элементов и элементов задержки (СФЭЗ). Автоматность осуществляемых ими отображений.
  18. Схемы из функциональных элементов и элементов задержки (СФЭЗ). Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
  19. Конечные автоматы. Отличимость состояний конечного автомата. Теорема Мура. Достижимость оценки теоремы Мура.
  20. Схемы из функциональных элементов (СФЭ). Умножитель. Метод Карацубы построения умножителя, верхняя оценка его сложности.

Часть Б. Ответ почти без подготовки и без возможности пользоваться источниками.

  1. Функции алгебры логики. Существенность переменных. Формулы. Тождества.
  2. Функции алгебры логики. Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме (ДНФ). Теорема о совершенной конъюнктивной нормальной форме (КНФ).
  3. Функции алгебры логики. Полные системы. Примеры полных систем (с доказательством полноты).
  4. Функции алгебры логики. Теорема Жегалкина о представимости функции алгебры логики полиномом Жегалкина.
  5. Функции алгебры логики. Замыкание, замкнутый класс. Функции, сохраняющие константу, и линейные функции. Замкнутость классов функций, сохраняющих константу, и линейных функций.
  6. Функции алгебры логики. Монотонные функции. Замкнутость класса монотонных функций.
  7. Функции алгебры логики. Самодвойственные функции. Лемма о несамодвойственной функции.
  8. Функции алгебры логики. Монотонные функции. Лемма о немонотонной функции.
  9. Функции алгебры логики. Базис. Теорема о числе функций в базисе в алгебре логики.
  10. Функции k-значной логики. Теорема о представлении функций k-значной логики в 1-й форме.
  11. Графы. Изоморфизм графов. Связность. Простейшие свойства графов. Теорема о числе вершин, ребер и компонент связности в графе.
  12. Деревья. Корневые деревья, упорядоченные корневые деревья. Верхняя оценка числа деревьев с заданным числом ребер.
  13. Геометрическое представление графов. Теорема о геометрическом представлении графов в трехмерном пространстве.
  14. Планарные графы. Формула Эйлера для планарных графов. Теорема о наибольшем числе ребер в планарном графе.
  15. Графы K5 и K3,3. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
  16. Раскраски вершин графов. Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
  17. Оптимальные коды (коды с минимальной избыточностью). Леммы о свойствах оптимальных кодов.
  18. Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
  19. Схемы из функциональных элементов. Сумматор, верхняя оценка его сложности. Вычитатель, верхняя оценка его сложности.
  20. Конечные автоматы. Функционирование конечного автомата. Автоматные функции. Канонические уравнения и диаграмма Мура конечного автомата. Единичная задержка, ее автоматность.

Литература

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

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

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