Реферат: Дискретная математика

Дискретная математика


Кафедра систем телекоммуникаций, факультет физико-математических и естественных наук.

Обязательная дисциплина.

Объем учебной нагрузки: 72 час. – лекции, 90 час. – семинары
Цель курса
Целью курса является развитие логического мышления у студентов и изучение основ математической логики, а также обучение основным методам комбинаторики и теории графов. На протяжении годичного курса развиваются навыки формализации и описания дискретных математических объектов. Материал курса является базовым для учебных дисциплин, связанных с математическим моделированием, с анализом и принятием решений.
^ Содержание курса
3 семестр

Тема 1. Введение в алгебру логики.

Прямое произведение множеств. Соответствия и функции. Алгебры. Функции алгебры логики. Суперпозиции и формулы. Булева Алгебра. Принцип двойственности. Совершенная дизъюнктивная нормальная форма(СДНФ). Совершенная конъюнктивная нормальная форма(СКНФ). Разложение булевых функций по переменным. Построение СДНФ для функции, заданной таблично.

^ Тема 2. Минимизация булевых функций.

Проблема минимизации. Порождение простых импликантов. Алгоритм Куайна и Мак-Клоски. Таблицы простых импликантов.

Тема 3. Полнота и замкнутость систем логических функций.

Замкнутые классы. Класс логических функций, сохраняющий константы 0 и 1. Определение и доказательство замкнутости. Класс самодвойственных функций.

Определение и лемма о несамодвойственной функции. Класс монотонных функций. Определение и лемма о немонотонной функции. Класс линейных функций. Определение и лемма о нелинейной функции.

^ Тема 4. Исчисление высказываний и предикатов.

Общие принципы построения формальной теории. Интерпретация, общезначимость, противоречивость, логическое следствие. Метод резолюций для исчисления высказываний. Понятие предиката. Кванторы. Алфавит. Предваренная нормальная форма. Алгоритм преобразования формул в предваренную нормальную форму. Скулемовская стандартная форма. Подстановка и унификация. Алгоритм унификации. Метод резолюций в исчислении предикатов.
^ Темы контрольных работ 3 семестра
Промежуточный контроль знаний

Контрольная работа № 1. Булева алгебра.

Построение СДНФ, СКНФ, нахождение существенных и фиктивных переменных, построение полинома Жегалкина.

Представление функции булевой формулой.

Нахождение двойственной функции по правилу двойственности, по принципу двойственности и по таблице.

Проверка справедливости соотношения.

Контрольная работа № 2. Минимизация булевых функций и исчисление высказываний.

Построение минимального представления исходной функции с помощью алгоритма Куайна-МакКлоски и последующего выделения ядра.

Исследование истинности логического следствия.

Нахождение предваренной нормальной формы и скулемовской стандартной формы.

Исследование функции на линейность, самодвойственность и монотонность.


Итоговый контроль знаний.

Контрольная работа № 3. Применение булевой алгебры к исчислению высказываний и предикатов.

Теоретические вопросы по темам:

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

Минимизация булевых функций.

Полнота и замкнутость систем логических функций.

Исчисление высказываний и предикатов.


4 семестр

Тема 1. Элементы комбинаторики.

Основные принципы комбинаторики. Перестановки, размещения, сочетания. Свойства сочетаний. Перестановки с повторениями, размещения с повторениями, сочетания с повторениями. Бином Ньютона, следствия. Формула включений и исключений. Перечисление комбинаторных объектов и производящие функции. Разбиения множеств. Числа Стирлинга второго рода, рекуррентное соотношение для них. Логические методы комбинаторной математики. Числа Белла разбиений конечного множества на непересекающиеся подмножества, рекуррентное соотношение для чисел Белла. Прикладные модели и задачи, примеры применения комбинаторных методов.

^ Тема 2. Элементы теории графов.

Введение в теорию графов: основные понятия и определения. Матричные представления графов. Маршруты, цепи, циклы. Нахождение сильных компонент. Метрические характеристики графов. Подграфы. Операции над графами. Двудольные графы. Поиск в ширину. Деревья. Алгоритм Краскала. Эйлеровы графы. Гамильтоновы графы. Эйлеровы пути и циклы. Гамильтоновы пути и циклы. Алгоритм построения эйлеровых циклов. Связь между наличием в связном графе гамильтоновых циклов и длиной максимальных простых путей в нем. Нахождение кратчайших путей в ориентированном графе. Алгоритм построения кратчайшего пути от фиксированной вершины до всех остальных вершин в ориентированном графе (случай неотрицательных весов ребер).

^ Тема 3. Потоки в сетях.

Прикладные модели и задачи, примеры применения методов теории графов. Оценки структурных компонент графа. Задача о максимальном потоке и о минимальном разрезе в сети. Максимальный поток в транспортной сети. Задача на узкие места. Задача о потоке минимальной стоимости.
^ Темы контрольных работ 4 семестра
Промежуточный контроль знаний

Контрольная работа № 1. Комбинаторика и ее приложения.

Задача по комбинаторным методам.

Задача с числами Белла и числами Стирлинга.

Задача на производящую функцию.

Контрольная работа № 2. Прикладные модели и задачи на применение методов теории графов.

Задача на применение алгоритма Дейкстры или алгоритма Краскала.

Задача на применение алгоритма Уоршалла-Флойда.

Нахождение метрических характеристик графа.

Итоговый контроль знаний

Контрольная работа № 3. Прикладные модели и задачи на применение методов теории графов.

Теоретические вопросы по темам:

Комбинаторика.

Биномиальные и полиномиальные коэффициенты.

Числа Белла и числа Стирлинга.

Производящие функции.

Операции над графами.

Алгоритмы на графах.

Прикладные модели теории графов.
Литература
Обязательная

Гаврилов Г.П., Сапоженко А.А. «Задачи и упражнения по курсу дискретной математики».// М.: "Наука", 1992.

Иванов Б.Н. «Дискретная математика. Алгоритмы и программы». // М.: Изд-во «Лаборатория базовых знаний», 2003.

Грэхем Р., Кнут Д., Паташник О. «Конкретная математика». // М.: "Мир", 1998.

Холл М. «Комбинаторика». // М.: "Мир", 1970.
Дополнительная
Харари Ф. «Теория графов». // М.: "Мир", 1973.

Рыбников К.А. «Комбинаторный анализ. Задачи и упражнения». // М.: "Наука", 1982.

Ю.В. Гайдамака, К.Е. Самуйлов, Л.А. Севастьянов, С.С. Спесивов «Комбинаторика. Алгоритмы на графах». Учебно-методическое пособие. // М.: Изд-во РУДН, 2002.