Дискретная математика (1й курс) — различия между версиями
(→Часть В) |
(→Экзамен (2021 г.)) |
||
(не показаны 46 промежуточные версии 3 участников) | |||
Строка 1: | Строка 1: | ||
== Лекторы == | == Лекторы == | ||
− | *проф. [[Алексеев Валерий Борисович| | + | *проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]] |
− | *проф. [[Марченков Сергей Серафимович| | + | *проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]] |
− | * | + | *проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]] |
− | == | + | ==Экзамен (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. | ||
+ | *Проверить, является ли заданный граф планарным. | ||
+ | *Проверить, найдется ли планарный граф с заданными свойствами. | ||
+ | *Найти хроматическое число или хроматический индекс заданного графа. | ||
+ | *Проверить разделимость заданного алфавитного кода (по алгоритму). | ||
+ | *Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов. | ||
+ | *Найти оптимальный алфавитный двоичный код по заданному набору частот. | ||
+ | *Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код. | ||
+ | *Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга. | ||
+ | *Найти кодовое расстояние заданного линейного кода. | ||
+ | *Найти диаграмму Мура автоматной функции, заданной описанием. | ||
+ | *Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов. | ||
+ | *Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции. | ||
+ | |||
+ | == Вопросы к экзамену по курсу «Дискретная математика», 2021 год.== | ||
===Часть А=== | ===Часть А=== | ||
− | |||
<ol> | <ol> | ||
− | <li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона). | + | <li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона) (вопрос № 1 только для студентов 2-3 потоков). |
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием). | <li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием). | ||
<li> Двойственность. Класс самодвойственных функций, его замкнутость. | <li> Двойственность. Класс самодвойственных функций, его замкнутость. | ||
Строка 35: | Строка 71: | ||
=== Часть В === | === Часть В === | ||
− | |||
<ol start="22"> | <ol start="22"> | ||
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций. | <li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций. | ||
Строка 46: | Строка 81: | ||
<li> Лемма о немонотонной функции. | <li> Лемма о немонотонной функции. | ||
<li> Теорема о максимальном числе функций в базисе в алгебре логики. | <li> Теорема о максимальном числе функций в базисе в алгебре логики. | ||
− | <li> k-значные функции. Теорема о | + | <li> k-значные функции. Теорема о представлении k-значных функций 1-й формой. |
<li> Основные понятия теории графов. Изоморфизм графов. Связность. | <li> Основные понятия теории графов. Изоморфизм графов. Связность. | ||
<li> Корневые деревья. Верхняя оценка их числа. | <li> Корневые деревья. Верхняя оценка их числа. | ||
Строка 58: | Строка 93: | ||
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель. | <li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель. | ||
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка. | <li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка. | ||
− | |||
</ol> | </ol> | ||
Строка 69: | Строка 103: | ||
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7)) | <li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7)) | ||
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9) | <li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9) | ||
− | |||
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237)) | <li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237)) | ||
</ol> | </ol> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
[[Категория:Лекционные курсы кафедры МК]] | [[Категория:Лекционные курсы кафедры МК]] |
Версия 16:00, 16 сентября 2021
Содержание
Лекторы
- проф. Алексеев Валерий Борисович
- проф. Марченков Сергей Серафимович
- проф. Селезнева Светлана Николаевна
Экзамен (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.
- Проверить, является ли заданный граф планарным.
- Проверить, найдется ли планарный граф с заданными свойствами.
- Найти хроматическое число или хроматический индекс заданного графа.
- Проверить разделимость заданного алфавитного кода (по алгоритму).
- Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
- Найти оптимальный алфавитный двоичный код по заданному набору частот.
- Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
- Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
- Найти кодовое расстояние заданного линейного кода.
- Найти диаграмму Мура автоматной функции, заданной описанием.
- Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
- Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.
Вопросы к экзамену по курсу «Дискретная математика», 2021 год.
Часть А
- Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона) (вопрос № 1 только для студентов 2-3 потоков).
- Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
- Двойственность. Класс самодвойственных функций, его замкнутость.
- Лемма о нелинейной функции.
- Теорема Поста о полноте системы функций алгебры логики.
- Теорема о предполных классах.
- Теоремы о представлении k-значных функций 2-й формой и полиномами.
- Деревья. Свойства деревьев.
- Алгоритм построения кратчайшего остовного дерева (с обоснованием).
- Теорема о раскраске планарных графов в 5 цветов.
- Алгоритм распознавания взаимной однозначности (разделимости) алфавитного кодирования (с обоснованием).
- Теорема Маркова о взаимной однозначности (разделимости) алфавитного кодирования.
- Неравенство Макмиллана.
- Существование префиксного кода с заданными длинами кодовых слов.
- Теорема редукции.
- Коды с исправлением r ошибок. Оценка функции Mr(n).
- Коды Хэмминга. Оценка функции M1(n).
- Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
- Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
- Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
- Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
Часть В
- Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
- Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
- Полные системы. Примеры полных систем (с доказательством полноты).
- Теорема Жегалкина о представимости функции алгебры логики полиномом.
- Понятие замкнутого класса. Замкнутость классов T0, T1, L.
- Класс монотонных функций, его замкнутость.
- Лемма о несамодвойственной функции.
- Лемма о немонотонной функции.
- Теорема о максимальном числе функций в базисе в алгебре логики.
- k-значные функции. Теорема о представлении k-значных функций 1-й формой.
- Основные понятия теории графов. Изоморфизм графов. Связность.
- Корневые деревья. Верхняя оценка их числа.
- Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
- Планарные (плоские) графы. Формула Эйлера.
- Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
- Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
- Оптимальные коды, их свойства.
- Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
- Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
- Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
- Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
Литература
- Собственный конспект лекций.
- Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
- Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
- Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
- Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
- Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
- Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))