Дискретная математика (1й курс)

Лекторы

• проф. Алексеев Валерий Борисович
• проф. Марченков Сергей Серафимович
• проф. Селезнева Светлана Николаевна

Экзамен (2020 г.)

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

Работу нужно написать от руки на светлых листах контрастной ручкой. После выполнения работы ее нужно сфотографировать или отсканировать. Затем фотографии или сканы работы в формате jpg, png или pdf отправить на проверку (загрузить по определенной ссылке, ссылка будет разослана старостам групп). На фотографирование или сканирование работы и ее отправку отводится 15 мин. Если работа студента не получена через 1 ч 45 мин (105 мин) после начала экзамена, то считается, что студент работу не сдал.

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

Вопросы к экзамену по курсу «Дискретная математика», 2020 год.

Часть А

1. Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона) (вопрос № 1 только для студентов 2-3 потоков).
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. Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.

Часть В

22. Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
23. Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
24. Полные системы. Примеры полных систем (с доказательством полноты).
25. Теорема Жегалкина о представимости функции алгебры логики полиномом.
26. Понятие замкнутого класса. Замкнутость классов T0, T1, L.
27. Класс монотонных функций, его замкнутость.
28. Лемма о несамодвойственной функции.
29. Лемма о немонотонной функции.
30. Теорема о максимальном числе функций в базисе в алгебре логики.
31. k-значные функции. Теорема о представлении k-значных функций 1-й формой.
32. Основные понятия теории графов. Изоморфизм графов. Связность.
33. Корневые деревья. Верхняя оценка их числа.
34. Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
35. Планарные (плоские) графы. Формула Эйлера.
36. Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
37. Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
38. Оптимальные коды, их свойства.
39. Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
40. Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
41. Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
42. Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.

Литература

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