Дискретная математика (1-й поток) — различия между версиями

Версия 12:16, 6 мая 2020

Дополнительная страница по курсу Дискретная математика (1й курс).

Основной курс для студентов 1-го курса, читается во 2-м семестре. Лекции - 3 ч в неделю, семинары - 2 ч в неделю, отчетность - экзамен.

Лектор - Селезнева Светлана Николаевна

Удаленное обучение

Все лекции по курсу прочитаны.

Вопросы по содержанию курса (и другие вопросы, относящиеся к курсу) можно задавать лектору Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru

Экзамен

Вопросы к экзамену можно посмотреть на странице Дискретная математика (1й курс)

Типовые задачи к экзамену

• Найти существенные и фиктивные переменные заданной функции алгебры логики.
• Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
• Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
• Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
• Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
• Записать заданную k-значную функцию в 1-й или 2-й форме.
• Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
• Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
• Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
• Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
• Проверить, является ли заданный граф планарным.
• Проверить, найдется ли планарный граф с заданными свойствами.
• Найти хроматическое число или хроматический индекс заданного графа.
• Проверить разделимость заданного алфавитного кода (по алгоритму).
• Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
• Найти оптимальный алфавитный двоичный код по заданному набору частот.
• Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
• Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
• Найти кодовое расстояние заданного линейного кода.
• Найти диаграмму Мура автоматной функции, заданной описанием.
• Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
• Построить диаграмму Мура, не содержащую неотличимых состояний, для заданной автоматной функции.

Лекции

Алгебра логики

Лекция 1. Двоичный куб. Наборы, вес набора. Слой n-мерного куба. Частичный порядок на n-мерном кубе. Соседние и противоположные наборы, расстояние между наборами. Лексико-графический порядок на n-мерном кубе.

Лекция 2. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества. Двойственность.

Лекция 3. Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. Полиномы Жегалкина. Теорема Жегалкина. Быстрый способ построения полинома Жегалкина.

Лекция 4. Полные системы. Полнота некоторых систем. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M. Леммы о несамодвойственной, немонотонной и нелинейной функциях.

Лекция 5. Полные системы. Теорема Поста о полноте. Базис в P_2. Теореме о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.

Лекция 6. Функции k-значной логики. Таблицы значений. Представление функций k-значной логики в 1-й и 2-й формах. Представление функций k-значной логики полиномами по модулю k.

Графы

Лекция 7. Графы. Простейшие свойства графов. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе. Орграфы.

Лекция 8. Деревья. Теорема о равносильных определениях дерева. Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева. Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.

Лекция 9. Геометрическое представление графов. Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.

Коды

Лекция 10. Кодирование. Алфавитные коды. Теорема об однозначности равномерного кода. Теорема об однозначности префиксного кода. Алгоритм распознавания однозначности алфавитного кода. Теорема Маркова.

Лекция 11. Алфавитные коды. Неравенство Макмиллана. Теорема о существовании префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.

Лекция 12. Алфавитные коды. Оптимальные коды (коды с минимальной избыточностью). Свойства оптимальных кодов. Теорема редукции. Метод Хаффмана построения оптимального кода.

Лекция 13. Коды, обнаруживающие и исправляющие ошибки, их свойства. Мощность кода, исправляющего ошибки. Линейные коды и их свойства.

Лекция 14. Коды, исправляющие одну ошибку. Коды Хэмминга и их свойства. Мощность кода, исправляющего одну ошибку.

СФЭ

Лекция 15. Схемы из функциональных элементов (СФЭ). Схемы для сложения и вычитания, их сложность.

Лекция 16. Схема для умножения. Сложность схемы для умножения по методу Карацубы.

Автоматы

Лекция 17. Конечные автоматы. Способы их представления. Схемы из функциональных элементов с задержками (СФЭЗ) и представление конечных автоматов ими.

Лекция 18. Конечные автоматы. Отличимость состояний конечного автомата. Оценка длины слова, отличающего два отличимых состояния конечного автомата. Упрощение автоматов.

Алгоритмы

Семинары

План семинарских занятий

Дополнительные задачи к семинарским занятиям

Занятие 7. Деревья и их свойства. Корневые деревья. Остовные деревья. Поиск кратчайшего остовного дерева в графе.

Занятие 8. Планарность графов. Критерий планарности. Раскраски графов.

Занятие 9. Алфавитные коды. Однозначность алфавитного кода. Оптимальные коды. Метод Хаффмана построения оптимального кода.

Занятие 10. Коды, исправляющие ошибки. Линейные коды. Коды Хэмминга.

Занятие 11. Конечные автоматы и автоматные функции. Способы их представления: канонические уравнения и диаграммы Мура.

Занятие 12. Конечные автоматы и автоматные функции. Способы их представления: схемы из функциональных элементов с задержками (СФЭЗ). Упрощение конечных автоматов.