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

Версия 17:25, 7 февраля 2023

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

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

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

Объявления

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

Программа курса

1. Алгебра логики. Функции алгебры логики, их представление таблицами истинности и формулами. Тождества. Существенность переменных. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Полиномы Жегалкина. Полнота в алгебре логики. Замкнутые классы. Предполные классы.

2. Графы. Графы, их простейшие свойства. Связность. Деревья, остовные деревья. Планарность графов. Раскраски графов.

3. Коды. Кодирование. Алфавитные коды, их свойства. Однозначность (разделимость) алфавитных кодов. Оптимальность алфавитных кодов. Коды, обнаруживающие и исправляющие ошибки. Коды Хэмминга. Линейные коды.

4. Конечные автоматы. Конечные автоматы-преобразователи и конечно-автоматные функции. Представления конечных автоматов и конечно-автоматных функций. Упрощение конечных автоматов.

5. Сложность. Схемы из функциональных элементов (СФЭ), представление функций алгебры логики ими. Сумматор, оценка его сложности в СФЭ. Вычитатель, оценка его сложности в СФЭ. Умножитель, оценка его сложности в СФЭ.

6. Многозначные логики. Функции многозначной логики, их представление нормальными формами и полиномами.

Литература

1. Конспекты лекций.
2. Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
3. Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс.
4. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
6. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.

Лекции

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

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

Лекция 2. Разложение функций по переменным. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Совершенная ДНФ и совершенная КНФ. Сокращенная ДНФ. Построение сокращенной ДНФ по КНФ.

Лекция 3. Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина.

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

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

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

Графы

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

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

Лекция 9. Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева.

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

Лекция 11. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.

Коды

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

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

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

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

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

Автоматы

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

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

Сложность

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

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

Многозначные логики

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

Семинары

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

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

Экзамен

Экзамен устный. В билете два теоретических вопроса и задача. Первый вопрос билета - из части А, второй вопрос билета - из части Б.