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