Программа курса «Методы дискретной математики».
I. Организационно-методический раздел. 1.1 Данный курс реализуется в ра...
9 downloads
145 Views
131KB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
Программа курса «Методы дискретной математики».
I. Организационно-методический раздел. 1.1 Данный курс реализуется в рамках программы для бакалавров, обучающихся по направлению 552800 "Информатика и вычислительная техника" и относится к федеральной компоненте раздела «общие математические и естественно-научные дисциплины» государственного стандарта. 1.2 Дисциплина «Методы дискретной математики» предназначена для изучения основ дискретных математических дисциплин: комбинаторики, теории булевых функций, теории графов, теории автоматов, теории сложности. Основной целью освоения дисциплины является ознакомление с базовыми понятиями и теоретическими методами указанных разделов дискретной математики. Для достижения поставленной цели выделяются задачи курса Требования к уровню освоения содержания курса. По окончании изучения указанной дисциплины студент должен – иметь представление об области применимости методов дискретной математики – знать основные понятия дискретной математики и основные методы работы с дискретной информацией – уметь оценить возможности применения и применить методы комбинаторики, теории графов, теории булевых функций для решения конкретных прикладных задач 1.4. Формы контроля Итоговый контроль. Для контроля усвоения дисциплины учебным планом предусмотрен дифференцированный зачет в конце первого семестра курса и экзамен в конце второго семестра курса. Текущий контроль. В течение каждого (из двух) семестра курса выполняется 3 контрольные работы, принимается 2 задания. Выполнение указанных видов работ является обязательным для всех студентов, а результаты текущего контроля служат основанием для выставления оценок в ведомость контрольной недели на факультете. 2. Содержание дисциплины. 2.2.Тематический план курса (распределение часов). Количество Наименование разделов Лаборатори тем Лекции Семинары ные работы Комбинаторика 20 24 Теория булевых 14 14 функций Теория графов 16 16 Теория автоматов 10 6 Теория сложности 8 8 Итого по курсу: 68 68 2.3.Содержание отдельных разделов и тем. Комбинаторика.
часов Самостоятель- Всего ная работа часов 20 14
64 52
18 8 8 68
50 24 24 204
Простейшие комбинаторные задачи. Принцип Дирихле. Перестановки и сочетания. Формулы для их подсчета. Число отображений конечных множеств в конечные множества с различимыми элементами. Разбиения конечных множеств и числа Стирлинга. Формула включений и исключений. Задача о беспорядках. Производящие функции. Возвратные последовательности и рекуррентные соотношения. Решение линейных рекуррентных соотошений. Системы различных представителей. Теорема Холла. Алгоритм нахождения системы различных представителей. Теорема Кенига о (0,1)-матрицах. Теорема Рамсея. Блок-схемы, необходимые условия их существования. Латинские квадраты. Ортогональность латинских квадратов. Перманенты: свойства и приложения. Теория булевых функций. Булевы функции, таблицы истинности. Количество булевых функций от n переменных. Элементарные булевы функции. Формулы. Реализация булевых функций формулами. Дизъюнктивные нормальные формы и совершенные дизъюнктивные нормальные формы. Двойственность булевых функций. Представление булевых функций в виде полиномов Жегалкина. Замкнутость и полнота систем булевых функций. Основные замкнутые классы булевых функций. Самодвойственные, монотонные, линейные булевы функции. Леммы о замкнутых классах. Теорема Поста о полноте систем булевых функций. Реализации булевых функций формулами, контактными схемами и схемами из функциональных элементов. Сложность реализаций булевых функций. Реализации сумматора и линейной функции в классах контактных схем и схем из функциональных элементов. Теорема Шеннона о сложности реализации булевых функций в классе схем из функциональных элементов. Метод Шеннона синтеза схем из функциональных элементов. Теория графов. Основные понятия теории графов. Изоморфизм графов. Ориентированный граф. Деревья. Теорема о характеризации деревьев. Кодирование деревьев. Код Прюфера. Двудольные графы, критерий двудольности. Паросочетания в двудольных графах. Плоские графы. Формула Эйлера. Теорема Понтрягина - Куратовского. Алгоритм укладки графа на плоскости. Связность графов. Теорема Менгера. Эйлеровы обходы. Теорема Эйлера. Гамильтонов цикл. Теорема Дирака. Независимость и покрытия в графах. Паросочетания. Раскраски графов. Правильная вершинная раскраска графа. Оценки хроматического числа графов. Теорема о пяти красках и гипотеза четырех красок. Правильная реберная раскраска графа. Свод свойств "почти всех" графов. Теория автоматов. Автоматы как логические устройства с памятью. Схемы из функциональных элементов и задержек. Способы задания абстрактных автоматов. Представление событий в автоматах. Существование событий, не представимых в конечных автоматах. Регулярные события. Источники. Детерминированные источники. Теоремы синтеза и анализа автоматов. Теория сложности. Комбинаторные задачи распознавания свойств и языки. Детерминированные и недетерминированные машины Тьюринга. Распознавание языков детерминированными и недетерминированными машинами Тьюринга. Алгоритмы класса P и алгоритмы класса NP. Полиномиальная сводимость задач. NP-полные задачи. Теорема Кука. Проблема P≠NP и ее значение. 2.4.Примеры контрольных вопросов и заданий для самостоятельной работы. Выяснить, полна ли данная система функций. Для каждой функции проверить ее принадлежность каждому из пяти основных замкнутых классов. Установить, какие переменные данной булевой функции являются существенными, а какие –
фиктивными. Подсчитать количество вершин из n-мерного единичного куба, находящихся на расстояниях i и j соответственно от двух данных вершин. Вычислить количество булевых функций от n переменных, существенно зависящих от всех своих переменных. Найти производящую функцию данной последовательности. Найти частное решение данного рекуррентного соотношения с начальными условиями. Продемонстрировать работу алгоритма нахождения системы различных представителей на примере данных множеств. Доказать данное комбинаторное тождество. Указать бесконечные серии значений параметра n, при которых не могут существовать СТШ(n). Сколькими способами можно так переставить цифры числа 1223445566, чтобы никакие две одинаковые цифры не стояли рядом? Сколько имеется четырехзначных чисел, у которых каждая следующая цифра больше предыдущей? Колода состоит из 4n карт. Сколько возможно различных расположений карт в колоде, при которых i-я карта первой масти стоит на месте с меньшим номером, чем (i+1)-я карта этой масти (i=1,2,..,n-1)? В киоске продаются 15 видов открыток. Покупатель случайным образом выбирает 27 открыток. Какова вероятность, что у него будут все виды открыток? Какова степень вершины с номером k в помеченном дереве с n вершинами, 0
3. Учебно-методическое обеспечение дисциплины 3.2. Образцы вопросов для подготовки к экзамену. Простейшие принципы подсчета комбинаторных конфигураций: правило суммы, правило произведения и принцип Дирихле. Выборки: перестановки и сочетания. Формулы для их подсчета. Основные понятия теории графов. Способы задания графов. Булевы функции. Количество булевых функций, зависящих от n переменных. Формулы. Совершенные дизъюнктивные нормальные формы. Представимость булевой функции в виде СДНФ. Многочлены Жегалкина. Двойственность булевых функций. Принцип двойственности. Полнота систем булевых функций. Примеры полных систем. Замкнутость систем булевых функций. Основные замкнутые классы булевых функций. Леммы о замкнутых классах. Теорема Поста. Формулы, контактные схемы и схемы из функциональных элементов. Сложность реализаций булевых функций. Реализации сумматора и линейной функции в классах контактных схем и схем из функциональных элементов. Теорема Шеннона о сложности реализации булевых функций в классе схем из функциональных элементов. Метод Шеннона синтеза схем из функциональных элементов. Деревья. Теорема о характеризации деревьев. Кодирование деревьев. Код Прюфера. Остов графа. Алгоритмы Краскала и Прима.
Связность "почти всех" графов. Двудольные графы. Характеризация двудольных графов. Эйлеровы обходы. Теорема Эйлера. Алгоритм Флери. Гамильтонов цикл. Достаточные условия гамильтоновости графов. Независимость и покрытия. Паросочетания в двудольных графах. Связность графов. Свойства. Теорема Менгера. Плоские графы. Формула Эйлера. Теорема Понтрягина - Куратовского. Алгоритм укладки графа на плоскости. Раскраски графов. Алгоритм последовательной раскраски. Правильная вершинная раскраска графа. Оценки хроматического числа графов. Теорема о пяти красках и гипотеза четырех красок. Правильная реберная раскраска графа. Оценки реберного хроматического числа графов. Раскраска карт. Формула включений и исключений. Задача о беспорядках. Производящие функции. Производящая функция для числа сочетаний. Возвратные последовательности и рекуррентные соотношения. Решение рекуррентных соотношений. Числа Каталана. Плоские корневые деревья. Числа Стирлинга второго рода. Число отображений конечных множеств в конечные множества с различимыми элементами. Cистемы различных представителей. Теорема Холла. Теорема Кенига о (0,1)-матрицах. Теорема Рамсея. Вычисление R(3,3). Теорема Рамсея. Доказательство теоремы Рамсея для графов. Теорема о выпуклом многоугольнике на плоскости. Блок-схемы, соотношения между их параметрами. Симметричные блок-схемы. Их свойства. Конечные плоскости. Их свойства. Латинские квадраты. Их ортогональность. Перманенты. Их свойства. Применения перманентов в различных комбинаторных задачах. Конечные автоматы. Способы их задания. Автомат Мили и автомат Мура. Схемы из функциональных элементов и задержек. Функцонирование схем из функциональных элементов и задержек. Двоичный последовательный сумматор. Автоматные отображения. События. Распознавание событий автоматами. Существование событий, не распознаваемых конечным автоматом. Регулярные события. Их свойства. Источники. Представление регулярных событий в двухполюсных источниках. Теоремы синтеза и анализа автоматов. Задачи распознавания свойств. Детерминированные и недетерминированные машины Тьюринга. Алгоритмы класса P и алгоритмы класса NP. Проблема P=NP и ее значение. Полиномиальная сводимость задач. NP-полные задачи. Теорема Кука. Основные NP-полные задачи. 3.3. Список основной и дополнительной литературы Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. Емеличев В.А. и др. Лекции по теории графов. М.: Наука, 1990. Косточка А. В., Соловьева Ф. И. Дискретная математика: Учеб. пособие/ Новосиб. гос. ун-т, Мех.-мат. фак., Каф. теорет. кибернетики. - Новосибирск: НГУ, 2001. Косточка А. В. Дискретная математика: Учеб. пособие/ Новосиб. гос. ун-т, Мех.мат. фак., Каф. теорет. кибернетики. - Новосибирск: НГУ, 2001. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: 1980 (или позже). Нигматуллин Р.Г. Сложность булевых функций. Изд-во Казанского ун-та. - Казань, 1983. Новиков Ф.А. Дискретная математика для программистов. 2000-2001. Рыбников К.А.Введение в комбинаторный анализ. М.: Изд-во МГУ, 1985. Холл М. Комбинаторика. М.: Мир. 1970.
Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. М., "Наука", 1980. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1979.
Программу подготовила: к.ф.-м.н., доцент
Васильева А.Ю.
Программа утверждена на заседании Ученого совета факультета информационных технологий Новосибирского государственного университета 18 декабря 2003 г., протокол заседания №16. Декан ФИТ НГУ, д.ф.-м.н.
М.М.Лаврентьев