МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Санкт-Петербургский государственный институт точной механики и оптики (тех...
22 downloads
266 Views
274KB 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
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Санкт-Петербургский государственный институт точной механики и оптики (технический университет) УТВЕРЖДАЮ Ректор СПбГИТМО(ТУ) _______________________В.Н.Васильев "_____"__________________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
Программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования и примерной программой дисциплины. Программу составили: кафедра компьютерных технологий старший преподаватель кафедры
Ищенко Алексей Петрович
Программа одобрена на заседании УМК факультета (или УМК цикла дисциплин) ___________________________________________________________________ _____________________________
___________________ (подпись) Ф.И.О.