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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Санкт-Петербургский государственный институт точной механики и оптики (технический университет) УТВЕРЖДАЮ Ректор СПбГИТМО(ТУ) _______________________В.Н.Васильев "_____"__________________200__ г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

Дискретная математика по направлению(ям) подготовки

Бизнес-информатика

Специальности(ям)

523100

Факультет(ы)

Информационных технологий и программирования

Председатель УМC университета

А.А.Шехонин

2

1. Цели и задачи дисциплины Цель курса – освоение обучаемым фундаментальных знаний в области дискретного анализа и выработка практических навыков применения этих знаний. Задачи курса – изложение основных положений дискретного анализа, их основных применений в современной математике и информатике, дать студенту ориентиры в дальнейшем углубленном изучении отдельных вопросов в специализированных курсах (представления данных, экстремальных задач, математической логики, теории вероятностей). 2. Требования к уровню освоения содержания дисциплины В результате изучения дисциплины студенты должны: - получить знания об основах теории множеств, теории отношений, комбинаторики, теории графов; - употреблять специальную математическую символику для выражения количественных и качественных отношений между объектами; - знать основные методы и алгоритмы теории графов, теории отношений, комбинаторики, теории нечетких множеств, связанные с моделированием и оптимизацией систем различной природы; - изучить основные приемы сведения прикладных задач автоматизированного проектирования к задачам дискретной математики; 3. Объем дисциплины и виды учебной работы Вид учебной работы Общая трудоемкость дисциплины Аудиторные занятия Лекции Практические занятия (ПЗ) Самостоятельная работы Вид итогового контроля (зачет, экзамен)

Семестры

Всего часов 189 108 36 72 81

1 90 54 18 36 36 зачет

Лекции 2 6

ПЗ 12

6

12

4 6 12

12 12 24

2 99 54 18 36 45 экзамен

4. Содержание дисциплины 4.1. Разделы дисциплин и виды занятий № п/п 1 2 3 4 5 6

Раздел дисциплины Введение Основные понятия теории множеств и нечетких множеств Отношения и функции. Нечеткие отношения Элементы общей алгебры Комбинаторика Основы теории графов

4.2. Содержание разделов дисциплины 4.2.1. Введение Место дискретной математики в системе математического образования. Использование элементов дискретной математики в решении прикладных задач автоматизированного

3

проектирования. Связь данной дисциплины с с общепрофессиональными и специальными дисциплинами. Организационно-методические указания по изучению дисциплины. 4.2.2. Основные понятия теории множеств и нечетких множеств Канторовское определение множества. Способы задания множеств. Конечные и бесконечные множества. Пустое и универсальное множества. Мощность множества. Семейство множества. Операции над множествами. Диаграммы Эйлера-Венна. Декартово произведение множеств. Покрытие и разбиение множеств. Основные тождества алгебры множеств. Понятие нечеткого множества. Функция принадлежности. Основные операции над нечеткими множествами и их свойства. Расстояние между нечеткими множествами, индексы нечеткости. Декомпозиция нечетких множеств. 4.2.3. Отношения и функции. Нечеткие отношения. Понятие отношения. Бинарные отношения и способы их задания. Операции над бинарными отношениями. Обратные отношения. Композиция бинарных отношений. Свойства бинарных отношений. Специальные бинарные отношения: порядок, эквивалентность. Представление бинарных отношений порядка с помощью диаграмм Хассе. Соответствия, отображения и функции. Свойства отображений. Композиция отображений. Понятие нечеткого отношения. Операции над нечеткими отношениями. Композиции нечетких отношений. Свойства нечетких отношений. Специальные типы нечетких отношений: предпорядок, порядок, подобие, различие, сходство. 4.2.4. Элементы общей алгебры Бинарные алгебраические операции и их свойства. Понятие алгебры. Основные алгебраические структуры: группоид, моноид, полугруппа, группа, кольцо, тело, поле. 4.2.5. Комбинаторика Классификация комбинаторных задач и характеристика их основных типов. Основные правила комбинаторики. Основные комбинаторные конфигурации: размещения, сочетания, перестановки. Урновые схемы. Разбиения. Бином Ньютона, биномиальные коэффициенты, треугольник Паскаля. Основные биномиальные тождества. Полиномиальная формула. Метод включений и исключений. 4.2.6. Основы теории графов Понятие графа. Псевдографы, мультирафы. Ориентированные и неориентированные графы. Подграфы. Способы представления графов. Матрицы смежности и инциндентности. Маршруты, цепи, пути, циклы в графах. Основные типы графов. Операции над графами. Изоморфизм и гомеоморфизм графов. Метрические характеристики графов. Определение центра, радиуса, диаметра, медианы графа. Достижимость и связность в графах. Алгоритмы определения компонент связности неорграфов и сильных компонент орграфов. Деревья. Понятие остова графа. Методы обхода графа (поиск в глубину и в ширину) и их использование для построения остовов. Алгоритмы Краскала и Прима построения кратчайшего остова взвешенного графа. Циклы и разрезы в графе. Цикломатическое и коцикломатическое числа графа. Построение матриц фундаментальных циклов и разрезов графа. Обходы графа. Эйлеровы графы, цепи, циклы. Теорема Эйлера. Метод Флери построения эйлерова цикла в графе. Гамильтоновы цепи, пути, циклы в графе. Алгоритм Робертса и Флореса построения гамильтонова цикла в графе. Независимость и покрытия. Независимые и доминирующие множества графа. Ядро графа. Паросочетания, покрытия, клики.

4

Реберная и вершинная раскраски графа. Хроматическое число. Эвристическая процедура раскраски графа. Определение кратчайших путей (маршрутов( в графах. Алгоритм определения пути с минимальным числом дуг. Алгоритмы Дейкстры и Форда определения кратчайшего пути между двумя фиксированными вершинами взвешенного графа. Алгоритм Форда определения кратчайших путей между всеми парами вершин графа. Потоки в транспортных сетях. Теорема о максимальном потоке и минимальном разрезе. Алгоритм Форда-Фалкерсона определения максимального потока в сети. Некоторые прикладные задачи теории графов. Использование алгоритмов теории графов в автоматизированном проектировании. 5. Практические занятия и лабораторные работы 5.1. Практические занятия № п/п 1

№ раздела дисциплины 2

2

3

3

4

4

3

5

4

6

5

7

6

8

6

9

6

10

6

11

6

Наименование практических занятий Операции над множествами. Диаграммы Эйлера-Венна. Упрощение выражений над множествами с использованием основных тождеств алгебры множеств Операции над нечеткими множествами и их свойства. Определение расстояний между нечеткими множествами, индексов нечеткости Бинарные отношения. Запись бинарных отношений с помощью специальной математической символики. Определение свойств бинарных отношений и их принадлежности к специальным типам бинарных отношений. Построение диаграмм Хассе Нечеткие отношения. Операции над нечеткими отношениями. Композиции нечетких отношений. Определение свойств нечетких отношений и их принадлежности к специальным нечетким отношениям Элементы общей алгебры. Определение принадлежности различных алгебр к основным типам Решение задач на использование основных комбинаторных формул Основные понятия теории графов. Типы графов. Подграфы. Матричное представление графов. Операции над графами. Построение графовых моделей электрических и коммутационных схем Метрические характеристики графа. Определение центра, радиуса, диаметра, медианы графа. Решение минимаксных и минисуммных задач размещения Достижимость и связность. Определение компонент связности неорграфов и сильных компонент орграфов Деревья: основные понятия. Построение остовных деревьев графа с использованием поиска в глубину и ширину. Алгоритмы Краскала и Прима построения кратчайшего остова взвешенного графа. Задачи определения кратчайших остовов в топологическом проектировании Построение матриц фундаментальных циклов и разрезов графа и их использование для составления систем уравнений

5

12

6

13

6

14

6

15

6

Кирхгофа для токов и напряжений в электрических цепях Обходы графа. Определение эйлеровых и гамильтоновых циклов графа и использование данных задач в приложениях. Решение задачи коммивояжера и его прикладное значение Алгоритмы раскраски графа. Решение прикладных задач, сводящихся к задаче о раскраске Определение кратчайших путей в графах. Решение задач на использование алгоритмов Дейкстры, Форда и Флойда Алгоритм Форда-Фалкерсона определения максимального потока в транспортной сети

5.2. Лабораторные занятия не предусмотрены 6. Учебно-методическое обеспечение дисциплины Рекомендуемая литература а) основная литература 1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988. 480 с. 2. Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учебное пособие. М.: Издво МАИ, 1992. 264 с. 3. Лекции по теории графов / Емеличев В.А., Мельников О.И., М.: Наука, 1990. 384 с. 4. Кристофидес Н. Теория графов: алгоритмический подход. М.: Мир, 1978. 432 с. 5. Леденева Т.М. Специальные главы математики. Дискретная математика: Учеб. пособие. Воронеж. гос. техн. ун-т. Воронеж, 1997. 130 с. 6. Элементы теории графов: Методические указания к практическим и индивидуальным занятиям/ С.Ю.Белецкая, Л.Д.Кретова, Е.Н.Королев, Н.Б.Ускова. Воронеж.: ВГТУ, 1998. 38 с. 7. Алгоритмы теории графов: Методические указания к практическим и индивидуальным занятиям/ С.Ю.Белецкая, Л.Д.Кретова, Н.Б.Ускова. Воронеж.: ВГТУ, 2000. 30 с. б) дополнительная литература 1. Горбатов В.А. Основы дискретной математики. М.: Высшая школа, 1986. 310 с. 2. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1979. 272 с. 3. Кофман А. Введение в теорию нечетких множеств. М.: Радио и связь, 1982. 431 с. 4. Кофман А. Введение в прикладную комбинаторику. М.: Радио и связь, 1982. 431 с. 5. Свами А.А., Тхуласирман К. Графы, сети и алгоритмы. М.: Мир, 1984. 454 с. 6. Липский В. Комбинаторика для программистов: Пер. с польск. - М.: Мир, 1988. 213 с. 6.2. Средства обеспечения освоения дисциплины Установленные специализированные математические программные пакеты MatLab и MathCAD, а также систему компиляции одного из алгоритмических языков программирования. 7. Материально-техническое обеспечение дисциплины Для проведения практических занятий по дисциплине "Дискретная математика" необходим компьютерный класс с персональными компьютерами класса не ниже Pentium_II, ОЗУ не менее 64Мб и жесткими дисками не менее 1Гб.

6

Программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования и примерной программой дисциплины. Программу составили: кафедра компьютерных технологий старший преподаватель кафедры

Ищенко Алексей Петрович

Программа одобрена на заседании УМК факультета (или УМК цикла дисциплин) ___________________________________________________________________ _____________________________

___________________ (подпись) Ф.И.О.