[ Программа курса
«Методы дискретной математики».
I. Организационно-методический раздел.
1.1 Данный курс реализуется в рамках программы для бакалавров, обучающихся по
направлению 552800 "Информатика и вычислительная техника" и относится к
федеральной компоненте раздела «общие математические и естественно-научные
дисциплины» государственного стандарта.
1.2 Дисциплина «Методы дискретной математики» предназначена для изучения основ дискретных математических дисциплин: комбинаторики, теории булевых функций, теории графов, теории автоматов, теории сложности.
Основной целью освоения дисциплины является ознакомление с базовыми понятиями и теоретическими методами указанных разделов дискретной математики.
Для достижения поставленной цели выделяются задачи курса Требования к уровню освоения содержания курса.
По окончании изучения указанной дисциплины студент должен – иметь представление об области применимости методов дискретной математики – знать основные понятия дискретной математики и основные методы работы с дискретной информацией – уметь оценить возможности применения и применить методы комбинаторики, теории графов, теории булевых функций для решения конкретных прикладных задач 1.4. Формы контроля Итоговый контроль. Для контроля усвоения дисциплины учебным планом предусмотрен дифференцированный зачет в конце первого семестра курса и экзамен в конце второго семестра курса.
Текущий контроль. В течение каждого (из двух) семестра курса выполняется контрольные работы, принимается 2 задания. Выполнение указанных видов работ является обязательным для всех студентов, а результаты текущего контроля служат основанием для выставления оценок в ведомость контрольной недели на факультете.
2. Содержание дисциплины.
2.2.Тематический план курса (распределение часов).
Количество часов Наименование разделов Лаборатор- Самостоятель- Всего и тем Лекции Семинары ные ная работа часов работы Комбинаторика 20 24 20 Теория булевых 14 14 14 функций Теория графов 16 16 18 Теория автоматов 10 6 8 Теория сложности 8 8 8 Итого по курсу: 68 68 68 2.3.Содержание отдельных разделов и тем.
Комбинаторика.
Простейшие комбинаторные задачи. Принцип Дирихле. Перестановки и сочетания.
Формулы для их подсчета. Число отображений конечных множеств в конечные множества с различимыми элементами. Разбиения конечных множеств и числа Стирлинга. Формула включений и исключений. Задача о беспорядках.
Производящие функции. Возвратные последовательности и рекуррентные соотношения. Решение линейных рекуррентных соотошений. Системы различных представителей. Теорема Холла. Алгоритм нахождения системы различных представителей. Теорема Кенига о (0,1)-матрицах. Теорема Рамсея. Блок-схемы, необходимые условия их существования. Латинские квадраты. Ортогональность латинских квадратов. Перманенты: свойства и приложения.
Теория булевых функций.
Булевы функции, таблицы истинности. Количество булевых функций от n переменных. Элементарные булевы функции. Формулы. Реализация булевых функций формулами. Дизъюнктивные нормальные формы и совершенные дизъюнктивные нормальные формы. Двойственность булевых функций.
Представление булевых функций в виде полиномов Жегалкина. Замкнутость и полнота систем булевых функций. Основные замкнутые классы булевых функций.
Самодвойственные, монотонные, линейные булевы функции. Леммы о замкнутых классах. Теорема Поста о полноте систем булевых функций. Реализации булевых функций формулами, контактными схемами и схемами из функциональных элементов. Сложность реализаций булевых функций. Реализации сумматора и линейной функции в классах контактных схем и схем из функциональных элементов. Теорема Шеннона о сложности реализации булевых функций в классе схем из функциональных элементов. Метод Шеннона синтеза схем из функциональных элементов.
Теория графов.
Основные понятия теории графов. Изоморфизм графов. Ориентированный граф.
Деревья. Теорема о характеризации деревьев. Кодирование деревьев. Код Прюфера.
Двудольные графы, критерий двудольности. Паросочетания в двудольных графах.
Плоские графы. Формула Эйлера. Теорема Понтрягина - Куратовского. Алгоритм укладки графа на плоскости. Связность графов. Теорема Менгера. Эйлеровы обходы. Теорема Эйлера. Гамильтонов цикл. Теорема Дирака. Независимость и покрытия в графах. Паросочетания. Раскраски графов. Правильная вершинная раскраска графа. Оценки хроматического числа графов. Теорема о пяти красках и гипотеза четырех красок. Правильная реберная раскраска графа. Свод свойств "почти всех" графов.
Теория автоматов.
Автоматы как логические устройства с памятью. Схемы из функциональных элементов и задержек. Способы задания абстрактных автоматов. Представление событий в автоматах. Существование событий, не представимых в конечных автоматах. Регулярные события. Источники. Детерминированные источники.
Теоремы синтеза и анализа автоматов.
Теория сложности.
Комбинаторные задачи распознавания свойств и языки. Детерминированные и недетерминированные машины Тьюринга. Распознавание языков детерминированными и недетерминированными машинами Тьюринга. Алгоритмы класса P и алгоритмы класса NP. Полиномиальная сводимость задач. NP-полные задачи. Теорема Кука. Проблема PNP и ее значение.
2.4.Примеры контрольных вопросов и заданий для самостоятельной работы.
Выяснить, полна ли данная система функций. Для каждой функции проверить ее принадлежность каждому из пяти основных замкнутых классов. Установить, какие переменные данной булевой функции являются существенными, а какие – фиктивными. Подсчитать количество вершин из n-мерного единичного куба, находящихся на расстояниях i и j соответственно от двух данных вершин.
Вычислить количество булевых функций от n переменных, существенно зависящих от всех своих переменных.
Найти производящую функцию данной последовательности. Найти частное решение данного рекуррентного соотношения с начальными условиями.
Продемонстрировать работу алгоритма нахождения системы различных представителей на примере данных множеств. Доказать данное комбинаторное тождество. Указать бесконечные серии значений параметра n, при которых не могут существовать СТШ(n). Сколькими способами можно так переставить цифры числа 1223445566, чтобы никакие две одинаковые цифры не стояли рядом?
Сколько имеется четырехзначных чисел, у которых каждая следующая цифра больше предыдущей? Колода состоит из 4n карт. Сколько возможно различных расположений карт в колоде, при которых i-я карта первой масти стоит на месте с меньшим номером, чем (i+1)-я карта этой масти (i=1,2,..,n-1)? В киоске продаются 15 видов открыток. Покупатель случайным образом выбирает открыток. Какова вероятность, что у него будут все виды открыток?
«