[ Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
«Новосибирский государственный университет» (НГУ)
Факультет информационных технологий
Кафедра_Дискретного анализа и исследования операций
ПРОГРАММА
ДИСЦИПЛИНЫ _Дискретная математика
ЦИКЛ*_Общие математические и естественнонаучные дисциплины НАПРАВЛЕНИЕ ПОДГОТОВКИ БАКАЛАВРОВ 230100.62 «ИНФОРМАТИКА И
ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»
Автор _к.ф.-м.н. Пережогин А.Л._ (ФИО, ученая степень, ученое звание) Новосибирск 2009 * Наименование цикла дисциплин в соответствии с ГОС ВПО Программа дисциплины «Дискретная Математика» составлена в соответствии с требованиями к обязательному минимуму содержания и уровню подготовки бакалавра по циклу «Общих математических и естественнонаучных дисциплин» Федеральных государственных образовательных стандартов высшего профессионального образования по направлению 230100.62 «Информатика и вычислительная техника».1. Цели и задачи дисциплины (курса) 1.1 Дисциплина «Дискретная Математика» имеет своей целью ознакомление с базовыми понятиями и теоретическими основами и методами комбинаторики, теории булевых функций, теории графов, теории автоматов, теории сложности.
Для достижения поставленной цели выделяются задачи курса:
Познакомить с основными понятиями, методами и современными тенденциями в перечисленных разделах дискретной математики.
2. Требования к уровню освоения содержания дисциплины В результате освоения дисциплины студент должен:
Иметь представление о об области применимости методов дискретной математики Знать основные понятия дискретной математики и основные методы работы с дискретной информацией Уметь оценить возможности применения и применить методы комбинаторики, теории графов, теории булевых функций для решения конкретных прикладных задач 3. Объем дисциплины и виды учебной работы Вид учебной работы Всего часов Семестры 1 Общая трудоемкость дисциплины 204 108 Аудиторные занятия, в том числе: 136 72 Лекции 68 36 Семинары 68 36 Лабораторные работы Самостоятельная работа, в том 68 36 числе:
Курсовой проект Реферат Расчетные работы Другие виды самостоятельной 68 36 работы Вид текущего контроля 4 контрольные и 2 контрольные 2 и 1 контрольные самостоятельные самостоятельна и работы я работы самостоятель ная работы Вид промежуточного контроля дифф. зачет, дифф. зачет экзамен экзамен Общая трудоемкость дисциплины составляет зачетных единиц (если применяется на факультете/кафедре).
4. Содержание дисциплины 4.1. Новизна курса. Курс «Дискретная Математика» был в 2008 году переработан и дополнен после стажировки в 2007 году Пережогина А.Л. в Московском государственном университете на факультете вычислительной математики и кибернетики и на механикоматематическом факультете. При разработке новой версии курса использовались программы подобных дисциплин во многих ВУЗах России и за рубежом. В программу курса введены некоторые новые научные результаты в областях комбинаторики и теории графов.
4.2. Тематический план курса (распределение часов по видам учебной работы).
№ Наименование ВСЕГО Аудиторные занятия Самостоятел п/п тем и разделов (часов) (часов), в том числе ьная работа (часов) Лекции Семинары Лаб.
работы 1 Комбинаторика 36 10 14 2 Теория графов 87 30 28 3 Булевы функции, 81 28 26 схемы, автоматы ИТОГО: 204 68 68 4.3. Содержание разделов и тем курса.
КОМБИНАТОРИКА
Комбинаторные правила произведения и суммы. Выборки и перестановки. Формула включений и исключений. Задача о беспорядках. Функция Эйлера. Числа Стирлинга первого и второго рода. Числа Бела. Разбиения чисел. Диаграмма Ферре. Производящие функции и их свойства. Числа Каталана, формула для числа Каталана. Числа Фибоначчи Линейная однородная возвратная последовательность, ее производящая функция. Общее решение линейного однородного рекуррентного соотношения. Экспоненциальные производящие функции.
ТЕОРИЯ ГРАФОВ
Основные понятия теории графов. Изоморфизм графов, автоморфизм. Лемма о рукопожатиях. Ориентированный граф. Подграф, порожденный подграф, остовный подграф. Двудольность, критерий двудольности. Оценки числа ребер графа. Матрицы смежности, инцидентности, Кирхгофа графа, псевдографа, орграфа. Лес, дерево, характеризация деревьев. Остовное дерево, остов. Теорема Кирхгофа. Код Прюфера помеченного дерева. Теорема Кэли. Числа вершинной и реберной связности, их связь.Характеризация двусвязных графов. Блок, bc-дерево графа. Теорема Менгера.
Независимые множества и покрытия. Совершенное паросочетание. Терема Кенига о числе паросочетания для двудольных графов. Терема Холла о паросочетаниях. Теорема Фробениуса о свадьбах. Системы различных представителей, теорема Холла о СРП.
Теорема об увеличивающей цепи. Алгоритм построения наибольшего паросочетания в двудольном графе (венгерский метод). Эйлеров цикл, эйлеров граф. Теорема Эйлера.
Алгоритм Флёри. Гамильтонов цикл, гамильтонов граф. Теорема Оре. Теорема Дирака.
Гамильтоковость n-куба. Теорема о дополняемости любого совершенного паросочетания в n-кубе до гамильтонова цикла. Укладка графа в пространство. Планарный граф, плоский граф, укладка на сфере. Формула Эйлера. Алгоритм укладки графа на плоскость.
Правильная раскраска вершин графа. Хроматическое число. Теорема Брукса. Теорема Зыкова. Раскраски планарных графов. Теорема о четырех красках. Правильная раскраска ребер графа. Хроматический индекс. Теорема Кёнига о хроматическом индексе двудольных графов. Теорема Визинга. Теорема о хроматическом индексе полного графа.
Теорема Рамсея для графов.
БУЛЕВЫ ФУНКЦИИ, СХЕМЫ, АВТОМАТЫ
Булева функция. Формула. Теорема о разложении функций по переменным. Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма.Двойственная функция. Принцип двойственности. Замкнутое, полное множества булевых функций. Полином Жегалкина. Теорема Жегалкина. Три способа построения полинома Жегалкина. Основные замкнутые классы булевых функций. Предполные классы. Теорема Поста. Схема из функциональных элементов, ее сложность. Метод Лупанова синтеза схем из функциональных элементов. Мощностной метод получения нижней оценки функции Шеннона для СФЭ. Контактная схема, ее сложность. Функция Шеннона для контактных схем. Метод каскадов для контактных схем. Нижняя оценка функции Шеннона для контактных схем. Схема Кардо. Ограниченно-детерминированные функции. Способы их задания. Конечный детерминированный автомат с выходом. Автоматные функции, связь с ограниченно-детерминированными функциями. Схема из автоматных элементов. Теорема о не существовании конечных полных систем автоматных функций. Схемы из автоматных элементов с использованием операции обратной связи. Реализация произвольной автоматной функции. Конечные автоматы Мили и Мура, их эквивалентность. Конечный детерминированный инициальный автомат без выходов. Пример языка, не распознаваемого конечным автоматом. Конечные автоматы без выходов. Регулярные языки. Теорема анализа автоматов. Теорема синтеза автоматов.
4.4. Перечень примерных контрольных вопросов и заданий для самостоятельной работы.
Сколькими способами можно так переставить цифры числа 1223445566, чтобы никание две одинаковые цифры не стояли рядом? Сколько имеется четырехзначных чисел, у которых каждая следующая цифра больше предыдущей? Колода состоит из 4n карт.
Сколько возможно различных расположений карт в колоде, при которых i-я карта первой масти стоит на месте с меньшим номером, чем (i+1)-я карта этой масти (i=1,2,..,n-1)? В киоске продаются 15 видов открыток. Сколько вариантов купить случайным образом открыток. Найти производящую функцию данной последовательности. Найти частное решение данного рекуррентного соотношения с начальными условиями.
Продемонстрировать работу алгоритма нахождения системы различных представителей на примере данных множеств. Доказать данное комбинаторное тождество.
«