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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Литература)
 
(не показаны 90 промежуточные версии 5 участников)
Строка 1: Строка 1:
−
== Вопросы к экзамену по курсу «Дискретная математика».==
+
== Лекторы ==
−
Лекторы: В. Б. Алексеев, С. С. Марченков, Д. С. Романов
+
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
 +
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
 +
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]
  
−
В билете 2 вопроса (один из части А и один из части В) и задача.
+
== Экзамен 2024. Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2024 год.==
  
−
=== Часть А ===  
+
Экзамен планируется устный. В билете 2 вопроса (один из части А и один из части В) и задача.
−
'''Ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определение и формулировки — без конспектов.'''
+
 
 +
===Часть А===
 +
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.  
 
<ol>
 
<ol>
−
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
+
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
−
<li> Лемма о нелинейной функции.
+
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
−
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина по вектору значений булевой функции.
+
<li> Лемма о нелинейной функции.
−
<li> Теорема Поста о полноте системы функций алгебры логики.
+
<li> Теорема Поста о полноте системы функций алгебры логики.
−
<li> Теорема о предполных классах.
+
<li> Теорема о предполных классах.
−
<li> Деревья. Свойства деревьев.
+
<li> Деревья. Свойства деревьев.
−
<li> Теорема о раскраске планарных графов в 5 цветов.
+
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
−
<li> Алфавитное кодирование. Теорема Маркова о взаимной однозначности (разделимости) алфавитного кодирования.
+
<li> Теорема о раскраске планарных графов в 5 цветов.
−
<li> Неравенство Макмиллана.
+
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
−
<li> Существование префиксного кода с заданными длинами кодовых слов.
+
<li> Теорема Маркова.
−
<li> Теорема редукции.
+
<li> Неравенство Макмиллана.
−
<li> Коды с исправлением r ошибок. Оценка функции M<sub>r</sub>(n).
+
<li> Существование префиксного кода с заданными длинами кодовых слов.
−
<li> Коды Хэмминга. Оценка функции M<sub>1</sub>(n).
+
<li> Теорема редукции.
−
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
+
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
−
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
+
<li> Коды Хэмминга. Оценка функции M1(n).
−
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.  
+
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
−
<li> Теорема Мура.  
+
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.  
 +
<li> Теорема Мура.
 +
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
 
</ol>
 
</ol>
  
−
=== Часть В ===  
+
=== Часть В ===
−
'''Ответ без конспектов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).'''
+
Часть В – ответ без конспектов и других материалов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).  
−
<ol start="18">
+
<ol start="20">
−
<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> Основные понятия теории графов. Изоморфизм графов. Связность.
−
<li> Корневые деревья. Верхняя оценка их числа.
+
<li> Корневые деревья. Верхняя оценка их числа.
−
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
+
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
−
<li> Планарные (плоские) графы. Формула Эйлера.
+
<li> Планарные (плоские) графы. Формула Эйлера.
−
<li> Доказательство непланарности графов K<sub>5</sub> и K<sub>3,3</sub>. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
+
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
−
<li> Оптимальные коды, их свойства.
+
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
−
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
+
<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. (Вопросы 2-6, 8-33, 35, 37-39)
 +
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 2-6, 8-33, 35, 37-39)
 +
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 2-5, 10-12, 20-28)
 +
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 1 (стр. 53-56) и вопрос 36 (задача 4.9 из главы 7))
 +
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 7)
 +
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 34 (стр. 36-37 и 237))
 +
<li> Весь материал имеется также в книге: Алексеев В.Б. Дискретная математика : учебник. М.: Инфра-М, 2021 (доступна в электронной библиотечной системе (ЭБС) Znanium.com).
 +
</ol>
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

Текущая версия на 12:35, 29 мая 2024

Лекторы

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

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

Часть А

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

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

Часть В

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

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

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

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

Литература

  1. Собственный конспект лекций.
  2. Лекции (онлайн) Алексеева В.Б. по дискретной математике: https://www.youtube.com/watch?v=SAhzEOVDNEI&list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT
  3. Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 2-6, 8-33, 35, 37-39)
  4. Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс. (Вопросы 2-6, 8-33, 35, 37-39)
  5. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 2-5, 10-12, 20-28)
  6. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 1 (стр. 53-56) и вопрос 36 (задача 4.9 из главы 7))
  7. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 7)
  8. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 34 (стр. 36-37 и 237))
  9. Весь материал имеется также в книге: Алексеев В.Б. Дискретная математика : учебник. М.: Инфра-М, 2021 (доступна в электронной библиотечной системе (ЭБС) Znanium.com).
Источник — «https://mk.cs.msu.ru/index.php?title=Дискретная_математика_(1й_курс)&oldid=11192»