Экзаменационные вопросы по дискретной математике II семестр
Описание файла
Документ из архива "Экзаменационные вопросы по дискретной математике II семестр", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 2 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "Экзаменационные вопросы по дискретной математике II семестр"
Текст из документа "Экзаменационные вопросы по дискретной математике II семестр"
Вопросы к экзамену по курсу «Дискретная математика»
Лекторы: В. Б. Алексеев, С. С. Марченков, Д.С.Романов;
весна 2012 года.
В билете 2 вопроса (один из части А и один из части В) и задача.
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
-
Двойственность. Класс самодвойственных функций, его замкнутость.
-
Лемма о нелинейной функции.
-
Теорема Поста о полноте системы функций алгебры логики.
-
Теорема о предполных классах.
-
Деревья. Свойства деревьев.
-
Теорема о раскраске планарных графов в 5 цветов.
-
Алгоритм распознавания взаимной однозначности алфавитного кодирования. Теорема Маркова.
-
Неравенство Макмиллана.
-
Существование префиксного кода с заданными длинами кодовых слов.
-
Теорема редукции.
-
Коды с исправлением r ошибок. Оценка функции .
-
Коды Хэмминга. Оценка функции .
-
Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
-
Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
-
Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
-
Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
Часть В – ответ без конспектов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
-
Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
-
Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
-
Полные системы. Примеры полных систем (с доказательством полноты).
-
Теорема Жегалкина о представимости функции алгебры логики полиномом.
-
Понятие замкнутого класса. Замкнутость классов
-
Класс монотонных функций, его замкнутость.
-
Лемма о несамодвойственной функции.
-
Лемма о немонотонной функции.
-
Теорема о максимальном числе функций в базисе в алгебре логики.
-
Основные понятия теории графов. Изоморфизм графов. Связность.
-
Корневые деревья. Верхняя оценка их числа.
-
Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
-
Планарные (плоские) графы. Формула Эйлера.
-
Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
-
Оптимальные коды, их свойства.
-
Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
-
Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
-
Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
По результатам контрольных работ по каждой из четырех тем (алгебра логики, графы, коды, автоматы) у каждого студента должна стоять одна из трех оценок — 0, 1/2 или 1. Оценка 0 означает, что на экзамене студент должен решить дополнительную задачу по данной теме, оценка 1/2, — что студент решает задачу по данной теме только в случае, если она выпадает в билете. Оценка 1 означает, что на экзамене студент не должен решать по данной теме как дополнительные задачи, так и задачу из билета. Дополнительные задачи решаются до выбора билета. Студенты, не решившие достаточное количество дополнительных задач, удаляются с экзамена с оценкой «неудовлетворительно», количество решенных задач может ограничить сверху оценку, получаемую на экзамене.
Задачи решаются без конспектов.
После ответа на билет возможна прогонка по всему материалу (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы (не путать с дополнительными!).