Дискретная математика (3-й поток)
Дополнительная страница по курсу Дискретная математика (1-й курс).
Лектор - Ложкин Сергей Андреевич.
Информационные материалы (весенний семестр 2024-2025 учебного года).
Экзамен
Информация к экзамену 2025 года. Экзамен устный. В билете 2 вопроса (один из части А и один из части В) и задача по одной из 4 тем: алгебра логики, графы, коды, автоматы. Задачи решаются без конспектов и любых других материалов. После ответа на билет возможна прогонка по всему материалу без конспекта (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы.
Часть А
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
- Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
- Двойственность. Класс самодвойственных функций, его замкнутость.
- Лемма о нелинейной функции.
- Теорема Поста о полноте системы функций алгебры логики.
- Теорема о предполных классах.
- Деревья. Свойства деревьев.
- Алгоритм построения кратчайшего остовного дерева (с обоснованием).
- Теорема о раскраске планарных графов в 5 цветов.
- Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
- Теорема Маркова.
- Неравенство Макмиллана.
- Существование префиксного кода с заданными длинами кодовых слов.
- Теорема редукции.
- Коды с исправлением r ошибок. Оценка функции Mr(n).
- Коды Хэмминга. Оценка функции M1(n).
- Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
- Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
- Теорема Мура.
- Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
Часть В
Часть В – ответ без конспектов и других материалов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
- Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
- Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
- Полные системы. Примеры полных систем (с доказательством полноты).
- Теорема Жегалкина о представимости функции алгебры логики полиномом.
- Понятие замкнутого класса. Замкнутость классов T0, T1, L.
- Класс монотонных функций, его замкнутость.
- Лемма о несамодвойственной функции.
- Лемма о немонотонной функции.
- Теорема о максимальном числе функций в базисе в алгебре логики.
- Основные понятия теории графов. Изоморфизм графов. Связность.
- Корневые деревья. Верхняя оценка их числа.
- Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
- Планарные (плоские) графы. Формула Эйлера.
- Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
- Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
- Оптимальные коды, их свойства.
- Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
- Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
- Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
- Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
