|
|
| Строка 4: |
Строка 4: |
| | *проф. [[Селезнева Светлана Николаевна| С.Н. Селезнева]] | | *проф. [[Селезнева Светлана Николаевна| С.Н. Селезнева]] |
| | | | |
| − | == Вопросы к экзамену по курсу «Дискретная математика», 2019 год.== | + | == Вопросы к экзамену по курсу «Дискретная математика», 2020 год.== |
| | | | |
| − | В билете 2 вопроса (один из части А и один из части В) и задача.
| + | Скоро здесь появится список вопросов к экзамену. |
| − | | + | |
| − | ===Часть А===
| + | |
| − | '''Ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки — без конспектов.'''
| + | |
| − | <ol>
| + | |
| − | <li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона).
| + | |
| − | <li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
| + | |
| − | <li> Двойственность. Класс самодвойственных функций, его замкнутость.
| + | |
| − | <li> Лемма о нелинейной функции.
| + | |
| − | <li> Теорема Поста о полноте системы функций алгебры логики.
| + | |
| − | <li> Теорема о предполных классах.
| + | |
| − | <li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
| + | |
| − | <li> Деревья. Свойства деревьев.
| + | |
| − | <li> Алгоритм построения кратчайшего остовного дерева (с обоснованием) (вопрос № 9 только для студентов 2-го и 3-го потоков).
| + | |
| − | <li> Теорема о раскраске планарных графов в 5 цветов.
| + | |
| − | <li> Алгоритм распознавания взаимной однозначности (разделимости) алфавитного кодирования (с обоснованием).
| + | |
| − | <li> Теорема Маркова о взаимной однозначности (разделимости) алфавитного кодирования.
| + | |
| − | <li> Неравенство Макмиллана.
| + | |
| − | <li> Существование префиксного кода с заданными длинами кодовых слов.
| + | |
| − | <li> Теорема редукции.
| + | |
| − | <li> Коды с исправлением r ошибок. Оценка функции Mr(n).
| + | |
| − | <li> Коды Хэмминга. Оценка функции M1(n).
| + | |
| − | <li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
| + | |
| − | <li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
| + | |
| − | <li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
| + | |
| − | <li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
| + | |
| − | </ol>
| + | |
| − | | + | |
| − | === Часть В ===
| + | |
| − | '''Ответ без конспектов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).'''
| + | |
| − | <ol start="22">
| + | |
| − | <li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
| + | |
| − | <li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
| + | |
| − | <li> Полные системы. Примеры полных систем (с доказательством полноты).
| + | |
| − | <li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
| + | |
| − | <li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
| + | |
| − | <li> Класс монотонных функций, его замкнутость.
| + | |
| − | <li> Лемма о несамодвойственной функции.
| + | |
| − | <li> Лемма о немонотонной функции.
| + | |
| − | <li> Теорема о максимальном числе функций в базисе в алгебре логики.
| + | |
| − | <li> k-значные функции. Теорема о существовании конечной полной системы в Pk.
| + | |
| − | <li> Основные понятия теории графов. Изоморфизм графов. Связность.
| + | |
| − | <li> Корневые деревья. Верхняя оценка их числа.
| + | |
| − | <li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
| + | |
| − | <li> Планарные (плоские) графы. Формула Эйлера.
| + | |
| − | <li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
| + | |
| − | <li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
| + | |
| − | <li> Оптимальные коды, их свойства.
| + | |
| − | <li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов (вопрос № 39 только для студентов 2-го и 3-го потоков).
| + | |
| − | <li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
| + | |
| − | <li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
| + | |
| − | <li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
| + | |
| − | </ol>
| + | |
| | | | |
| | ===Литература=== | | ===Литература=== |
| Строка 70: |
Строка 18: |
| | <li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237)) | | <li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237)) |
| | </ol> | | </ol> |
| − |
| |
| − | ===Задачи на экзамене===
| |
| − |
| |
| − | В билете кроме двух теоретических вопросов указана тема задачи. Всего тем четыре: алгебра логики, графы, коды, автоматы.
| |
| − |
| |
| − | По итогам контрольных работ каждый студент по каждой из этих четырех тем получает одну из трех оценок - 1; 0,5 или 0.
| |
| − |
| |
| − | Оценка 1 по определенной теме означает освобождение от задачи по этой теме, если она попадается в билете. Оценка 0 означает дополнительную задачу по этой теме на экзамене. Все дополнительные задачи (по одной задаче по каждой теме, за которую 0) решаются студентом до выбора билета. Если студент не решил достаточного числа дополнительных задач, то ему может быть поставлена оценка неуд (без возможности выбрать билет). Если студент решил не все дополнительные задачи и тянет билет, то ему снижается оценка с учетом числа нерешенных дополнительных задач.
| |
| − |
| |
| − | Задачи решаются без конспектов.
| |
| − |
| |
| − | После ответа на билет экзаменатор может опрашивать студента по всему материалу (определения, формулировки теорем, идеи доказательств). Кроме того, экзаменатор может предлагать студенту решить задачи по любым темам из курса (в том числе, по которым у студента 1).
| |
| − |
| |
| − | На пересдаче нет освобождения от задач и дополнительных задач: студент отвечает на два теоретических вопроса в билете и решает задачу из билета.
| |
| | | | |
| | | | |
| | [[Категория:Лекционные курсы кафедры МК]] | | [[Категория:Лекционные курсы кафедры МК]] |
