Дискретная математика (КФ) — различия между версиями
(→Экзамен) |
|||
| Строка 18: | Строка 18: | ||
Итоги экзамена появятся 17 июня в 10 ч (по московскому времени). Затем до 11 ч (по московскому времени) 17 июня на почту dm1@cs.msu.ru можно прислать вопросы по оцениванию заданий в работах. После всех обсуждений оценки выставляются в ведомость. | Итоги экзамена появятся 17 июня в 10 ч (по московскому времени). Затем до 11 ч (по московскому времени) 17 июня на почту dm1@cs.msu.ru можно прислать вопросы по оцениванию заданий в работах. После всех обсуждений оценки выставляются в ведомость. | ||
| + | |||
| + | '''Вопросы к экзамену''' | ||
| + | |||
| + | *Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества. | ||
| + | *Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. | ||
| + | *Полнота в алгебре логики, полные системы. Полнота некоторых систем. | ||
| + | *Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина. | ||
| + | *Замыкание множества, замкнутые классы. Замкнутость классов T_0, T_1, L, S, M. | ||
| + | *Леммы о несамодвойственной, немонотонной и нелинейной функциях. | ||
| + | *Теорема Поста о полноте. | ||
| + | *Базис в P_2. Теореме о числе функций в базисе P_2. | ||
| + | *Предполные классы. Теорема о предполных классах в P_2. | ||
| + | *Простейшие свойства графов. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе. | ||
| + | *Деревья. Теорема о равносильных определениях дерева. | ||
| + | *Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами. | ||
| + | *Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева. | ||
| + | *Геометрическое представление графов. Теорема о геометрическом представлении графов в трехмерном пространстве. | ||
| + | *Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского. | ||
| + | *Раскраски графов. Раскраски графов в два цвета. | ||
| + | *Теорема о раскраске планарного графа. | ||
| + | *Кодирование. Алфавитные коды. Проверка однозначности алфавитного кода. Теорема Маркова. | ||
| + | *Неравенство Макмиллана. | ||
| + | *Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов. | ||
| + | *Оптимальные коды (коды с минимальной избыточностью). Свойства оптимальных кодов. | ||
| + | *Теорема редукции. Метод Хаффмана построения оптимального кода. | ||
| + | *Устойчивость кодов к ошибкам. Коды, обнаруживающие и исправляющие ошибки, их свойства. | ||
| + | *Коды Хэмминга. | ||
| + | *Конечные автоматы. Способы их представления. | ||
| + | *Отличимость состояний конечного автомата. Теорема Мура. Упрощение автоматов. | ||
==Удаленное обучение== | ==Удаленное обучение== | ||
Версия 10:46, 11 июня 2022
Курс для студентов 1-го курса Казахстанского филиала МГУ, читается во 2-м семестре. Лекции - 32 ч, семинары - 32 ч, отчетность - экзамен.
Лектор - Селезнева Светлана Николаевна
Экзамен
Экзамен состоится 14 июня очно.
Экзамен письменный. Экзаменационная работа содержит восемь заданий по содержанию курса. Первые четыре задания - задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами. Вопросы проясняют понимание студентом определения или теоремы. Они оцениваются также в 3 балла каждое. Список вопросов и задач приведен на этой странице.
Продолжительность написания работы - 1 ч 30 мин (90 мин).
Примерный вариант экзаменационной работы
Экзамен проводится очно в аудитории. Работу следует написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются принимающему экзамен.
Итоги экзамена появятся 17 июня в 10 ч (по московскому времени). Затем до 11 ч (по московскому времени) 17 июня на почту dm1@cs.msu.ru можно прислать вопросы по оцениванию заданий в работах. После всех обсуждений оценки выставляются в ведомость.
Вопросы к экзамену
- Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества.
- Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ.
- Полнота в алгебре логики, полные системы. Полнота некоторых систем.
- Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина.
- Замыкание множества, замкнутые классы. Замкнутость классов T_0, T_1, L, S, M.
- Леммы о несамодвойственной, немонотонной и нелинейной функциях.
- Теорема Поста о полноте.
- Базис в P_2. Теореме о числе функций в базисе P_2.
- Предполные классы. Теорема о предполных классах в P_2.
- Простейшие свойства графов. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе.
- Деревья. Теорема о равносильных определениях дерева.
- Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.
- Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева.
- Геометрическое представление графов. Теорема о геометрическом представлении графов в трехмерном пространстве.
- Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского.
- Раскраски графов. Раскраски графов в два цвета.
- Теорема о раскраске планарного графа.
- Кодирование. Алфавитные коды. Проверка однозначности алфавитного кода. Теорема Маркова.
- Неравенство Макмиллана.
- Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов.
- Оптимальные коды (коды с минимальной избыточностью). Свойства оптимальных кодов.
- Теорема редукции. Метод Хаффмана построения оптимального кода.
- Устойчивость кодов к ошибкам. Коды, обнаруживающие и исправляющие ошибки, их свойства.
- Коды Хэмминга.
- Конечные автоматы. Способы их представления.
- Отличимость состояний конечного автомата. Теорема Мура. Упрощение автоматов.
Удаленное обучение
Вопросы по содержанию курса (и другие вопросы, относящиеся к курсу) можно задавать лектору Селезневой Светлане Николаевне по эл. почте 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. Конечные автоматы. Способы их представления. Отличимость состояний конечного автомата. Теорема Мура. Упрощение автоматов.
Литература
- Слайды к лекциям.
- Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
- Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс.
- Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
- Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
- Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.
