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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Экзамен (2021 г.))
(не показаны 84 промежуточных версий 5 участников)
Строка 1: Строка 1:
 
== Лекторы ==
 
== Лекторы ==
*[[Алексеев Валерий Борисович|В. Б. Алексеев]]
+
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*[[Марченков Сергей Серафимович|С. С. Марченков]]
+
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*[[Романов Дмитрий Сергеевич|Д. С. Романов]]
+
*проф.  [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]
== Вопросы к экзамену по курсу «Дискретная математика».==
+
  
В билете 2 вопроса (один из части А и один из части В) и задача.
+
==Экзамен 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.
 +
*Проверить, является ли заданный граф планарным.
 +
*Проверить, найдется ли планарный граф с заданными свойствами.
 +
*Найти хроматическое число или хроматический индекс заданного графа.
 +
*Проверить разделимость заданного алфавитного кода (по алгоритму).
 +
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
 +
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
 +
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
 +
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
 +
*Найти кодовое расстояние заданного линейного кода.
 +
*Найти диаграмму Мура автоматной функции, заданной описанием.
 +
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
 +
*Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.
 +
 
 +
== Экзамен 2022. Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год.==
 +
 
 +
Экзамен планируется устный. В билете 2 вопроса (один из части А и один из части В) и задача.
 +
 
 +
===Часть А===
 +
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки без конспектов.  
 
<ol>
 
<ol>
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
+
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона).
<li> Лемма о нелинейной функции.
+
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина по вектору значений булевой функции.
+
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Теорема Поста о полноте системы функций алгебры логики.
+
<li> Лемма о нелинейной функции.
<li> Теорема о предполных классах.
+
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Деревья. Свойства деревьев.
+
<li> Теорема о предполных классах.
<li> Теорема о раскраске планарных графов в 5 цветов.
+
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.  
<li> Алфавитное кодирование. Теорема Маркова о взаимной однозначности (разделимости) алфавитного кодирования.
+
<li> Деревья. Свойства деревьев.
<li> Неравенство Макмиллана.
+
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Существование префиксного кода с заданными длинами кодовых слов.
+
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Теорема редукции.
+
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
<li> Коды с исправлением r ошибок. Оценка функции M<sub>r</sub>(n).
+
<li> Теорема Маркова.
<li> Коды Хэмминга. Оценка функции M<sub>1</sub>(n).
+
<li> Неравенство Макмиллана.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
+
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
+
<li> Теорема редукции.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.  
+
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Теорема Мура.  
+
<li> Коды Хэмминга. Оценка функции M1(n).
 +
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
 +
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.  
 +
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
 +
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
 
</ol>
 
</ol>
  
=== Часть В ===  
+
=== Часть В ===
'''Ответ без конспектов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).'''
+
Часть В – ответ без конспектов и других материалов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).  
<ol start="18">
+
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
+
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
+
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
+
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.  
+
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T<sub>0</sub>, T<sub>1</sub> и L.
+
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
+
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
+
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
+
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
+
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
+
<li> k-значные функции. Теорема о существовании конечной полной системы в Pk.
<li> Корневые деревья. Верхняя оценка их числа.
+
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
+
<li> Корневые деревья. Верхняя оценка их числа.
<li> Планарные (плоские) графы. Формула Эйлера.
+
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Доказательство непланарности графов K<sub>5</sub> и K<sub>3,3</sub>. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
+
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Оптимальные коды, их свойства.
+
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
+
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
+
<li> Оптимальные коды, их свойства.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
+
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
 +
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
 +
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
 +
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.  
 
</ol>
 
</ol>
 +
Третьим пунктом в билете стоит задача по одной из 4 тем: алгебра логики, графы, коды, автоматы.
 +
Задачи решаются без конспектов и любых других материалов.
  
По результатам контрольных работ по каждой из четырех тем (алгебра логики, графы, коды, автоматы) у каждого студента должна стоять одна из трех оценок — 0, 1/2 или 1. Оценка 0 означает, что на экзамене студент должен решить дополнительную задачу по данной теме, оценка 1/2, — что студент решает задачу по данной теме только в случае, если она выпадает в билете. Оценка 1 означает, что на экзамене студент не должен решать по данной теме как дополнительные задачи, так и задачу из билета. Дополнительные задачи решаются до выбора билета. Студенты, не решившие достаточное количество дополнительных задач, удаляются с экзамена с оценкой «неудовлетворительно», количество решенных задач может ограничить сверху оценку, получаемую на экзамене.
+
После ответа на билет возможна прогонка по всему материалу без конспекта (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы.
  
Задачи решаются без конспектов.
+
===Литература===
 
+
<ol>
После ответа на билет возможна прогонка по всему материалу (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы (не путать с дополнительными!).
+
<li> Собственный конспект лекций.
 +
<li> Лекции (онлайн) Алексеева В.Б. по дискретной математике: https://www.youtube.com/watch?v=SAhzEOVDNEI&list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT
 +
<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))
 +
<li> Весь материал имеется также в книге: Алексеев В.Б. Дискретная математика : учебник. М.: Инфра-М, 2021 (доступна в электронной библиотечной системе (ЭБС) Znanium.com).
 +
</ol>
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

Версия 13:49, 22 мая 2022

Лекторы

Экзамен 2021 г.

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

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

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

Примерный вариант экзаменационной работы

Экзамен проводится очно в аудитории 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.
  • Проверить, является ли заданный граф планарным.
  • Проверить, найдется ли планарный граф с заданными свойствами.
  • Найти хроматическое число или хроматический индекс заданного графа.
  • Проверить разделимость заданного алфавитного кода (по алгоритму).
  • Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
  • Найти оптимальный алфавитный двоичный код по заданному набору частот.
  • Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
  • Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
  • Найти кодовое расстояние заданного линейного кода.
  • Найти диаграмму Мура автоматной функции, заданной описанием.
  • Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
  • Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.

Экзамен 2022. Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год.

Экзамен планируется устный. В билете 2 вопроса (один из части А и один из части В) и задача.

Часть А

Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.

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

Часть В

Часть В – ответ без конспектов и других материалов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).

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

Третьим пунктом в билете стоит задача по одной из 4 тем: алгебра логики, графы, коды, автоматы. Задачи решаются без конспектов и любых других материалов.

После ответа на билет возможна прогонка по всему материалу без конспекта (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы.

Литература

  1. Собственный конспект лекций.
  2. Лекции (онлайн) Алексеева В.Б. по дискретной математике: https://www.youtube.com/watch?v=SAhzEOVDNEI&list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT
  3. Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
  4. Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
  5. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
  6. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
  7. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
  8. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
  9. Весь материал имеется также в книге: Алексеев В.Б. Дискретная математика : учебник. М.: Инфра-М, 2021 (доступна в электронной библиотечной системе (ЭБС) Znanium.com).