Рабочая программа учебной дисциплины ен. Ф. 01. 03 Дискретная математика для специальности 230104 «Системы автоматизированного проектирования»
| Вид материала | Рабочая программа |
- Рабочая программа учебной дисциплины Операционные системы для специальности: 230104,, 227.9kb.
- Рабочая программа учебной дисциплины сд. 07 Автоматизация конструкторского и технологического, 280.56kb.
- Рабочая программа учебной дисциплины дс. 01 Моделирование систем Для специальности, 157.98kb.
- Рабочая программа учебной дисциплины сд. 08 Промышленная логистика Для специальности, 113.31kb.
- Рабочая программа учебной дисциплины ен. Р. 01 Оптимизация в сапр для специальности, 198.86kb.
- Рабочая программа учебной дисциплины сд. 05 Интеллектуальные подсистемы сапр для специальности, 198.1kb.
- Рабочая программа учебной дисциплины опд. Ф. 09 Организация ЭВМ и систем Для специальности, 240.03kb.
- Рабочая программа учебной дисциплины опд. Ф. 12 Сети ЭВМ и телекоммуникации Для специальности, 198.41kb.
- Рабочая программа учебной дисциплины ен. Ф. 01. 04 Математическая логика и теория алгоритмов, 259.76kb.
- Рабочая программа учебной дисциплины сд. 03 Модели и методы анализа проектных решений, 178.99kb.
ГОУ ВПО
«Воронежский государственный технический университет»
«Утверждаю»
Декан ЕГФ
_____________С.М.Пасмурнов
РАБОЧАЯ ПРОГРАММА
УЧЕБНОЙ ДИСЦИПЛИНЫ
ЕН.Ф.01.03 Дискретная математика
для специальности 230104 «Системы автоматизированного проектирования»
форма обучения очная
срок обучения нормативный
Воронеж 2007
Рабочая программа составлена в соответствии с государственным образовательным стандартом направления
230100 «Информатика и вычислительная техника» .
специальности 230104 «Системы автоматизированного проектирования»
на основании примерной программы дисциплины
__________________________________________________________________
утвержденной “_ 05” апреля_____________2000 г.
____по образованию в области машиностроения и приборостроения_______
(название УМО)
Составитель программы
доцент каф.САПРИС, к.т.н. С.Ю. Белецкая
Рабочая программа обсуждена на заседании кафедры «Системы автоматизированного проектирования и информационные системы» протокол №___ от «___»_____________ 200 г.
Зав. кафедрой Я.Е.Львович
Рабочая программа рассмотрена и одобрена методической комиссией ЕГФ «___»_____________ 200 г.
Председатель МК,
доцент, к.т.н. О.Г.Яскевич
С О Д Е Р Ж А Н И Е РАБОЧЕЙ ПРОГРАММЫ ПРЕПОДА-
ВАНИЯ ДИСЦИПЛИНЫ
Выписка из Государственного образовательного стандарта
высшего профессионального образования государственных требований к минимуму содержания уровню подготовки инженера
направления_ 230100 «Информатика и вычислительная техника»
по специальности_230104 «Системы автоматизированного проектирования»
(Текст из ГОС ВПО)
Дискретная математика: логические исчисления, графы, теория алгоритмов,
Языки и грамматики, автоматы, комбинаторика; логика высказываний, логическое следование, принцип дедукции; логика предикатов; синтаксис и семантика языка логики предикатов; принцип логического программирования; аксиоматические система, формальный вывод; метатеория формальных систем; понятие алгоритмической системы; рекурсивные функции; машина Тьюринга; алгоритмически неразрешимые проблемы; меры сложности алгоритмов; легко и трудноразрешимые задачи; основы нечеткой логики; элементы алгоритмической логики.
1. Цель и задачи дисциплины
Целью преподавания дисциплины является изучение теоретических и алгоритмических основ базовых разделов современной дискретной математики, формирование у студентов навыков описания дискретных объектов в прикладных задачах.
При изучении данной дисциплины необходимо знание студентами математики в объеме первого курса. Для выполнения курсовой работы необходимо знание алгоритмических языков и программирования
2.Требования к уровню освоения содержания дисциплины
В результате изучения дисциплины студенты должны:
- получить знания об основах теории множеств, теории отношений, комбинаторики, теории графов;
- употреблять специальную математическую символику для выражения количественных и качественных отношений между объектами;
- знать основные методы и алгоритмы теории графов, теории отношений, комбинаторики, теории нечетких множеств, связанные с моделированием и оптимизацией систем различной природы;
- изучить основные приемы сведения прикладных задач автоматизированного проектирования к задачам дискретной математики;
3. Объем дисциплины и виды учебной работы
Форма обучения_очная
Срок обучения нормативный
Курс 2
| Вид занятий | Всего часов | Семестры и Количество часов | | |
| Общая трудоемкость | 140 | 3 | 140 | |
| Аудиторные занятия | 68 | 3 | 68 | |
| Лекции | 34 | 3 | 34 | |
| Практические занятия | 34 | 3 | 34 | |
| Самостоятельная работа | 72 | 3 | 72 | |
| Работа над темами для Самостоятельного изучения | 72 | 3 | 72 | |
| Рубежи контроля знаний (экзамен, зачет) | экзамен | | Экзамен | |
4. Содержание дисциплины
4.1. Разделы дисциплины и виды занятий
| N n/ n | Разделы дисциплины | Лекции (час) | Практич занятия (час) |
| 1 | Введение.. Основные понятия теории множеств и нечетких множеств | 5 | 5 |
| 2 | Отношения и функции. Нечеткие отношения. | 6 | 4 |
| 3 | Элементы общей алгебры | 2 | 2 |
| 4 | Комбинаторика | 6 | 6 |
| 5 | Основы теории графов | 15 | 18 |
4.2..Содержание разделов дисциплины.
РАЗДЕЛ 1. Введение . Основные понятия теории множеств и нечетких множеств(5часов)
Лекция 1. Место дискретной математики в системе математического образования. Использование элементов дискретной математики в решении прикладных задач автоматизированного проектирования. Связь данной дисциплины с с общепрофессиональными и специальными дисциплинами. Организационно-методические указания по изучению дисциплины.
. Канторовское определение множества. Способы задания множеств. Конечные и бесконечные множества. Пустое и универсальное множества. Мощность множества. Семейство множества.
Лекции 2. Операции над множествами. Диаграммы Эйлера-Венна. Декартово произведение множеств. Покрытие и разбиение множеств. Основные тождества алгебры множеств.
Самостоятельное изучение. Понятие нечеткого множества. Функция принадлежности. Основные операции над нечеткими множествами и их свойства. Расстояние между нечеткими множествами, индексы нечеткости. Декомпозиция нечетких множеств.
РАЗДЕЛ 2. Отношения и функции. Нечеткие отношения.(6час)
Лекция 2. Понятие отношения. Бинарные отношения и способы их задания. Операции над бинарными отношениями. Обратные отношения.
Самостоятельное изучение. Композиция бинарных отношений.
Лекция 3. Свойства бинарных отношений. Специальные бинарные отношения: порядок, эквивалентность. Представление бинарных отношений порядка с помощью диаграмм Хассе.
. Соответствия, отображения и функции. Свойства отображений. Композиция отображений.
РАЗДЕЛ 3. Элементы общей алгебры (2час)
Лекция 4. Бинарные алгебраические операции и их свойства. Понятие алгебры. Основные алгебраические структуры: группоид, моноид, полугруппа, группа, кольцо, тело, поле.
РАЗДЕЛ 5.Комбинаторика (6час)
Лекция 5. Классификация комбинаторных задач и характеристика их основных типов.
Лекция 6. Основные правила комбинаторики. Основные комбинаторные конфигурации: размещения, сочетания, перестановки. Урновые схемы. Разбиения.
Лекция 7. Бином Ньютона, биномиальные коэффициенты, треугольник Паскаля. Основные биномиальные тождества. Полиномиальная формула.
. Метод включений и исключений.
РАЗДЕЛ 6. Основы теории графов (15час)
Лекция 8. Понятие графа. Псевдографы, мультирафы. Ориентированные и неориентированные графы. Подграфы. Способы представления графов. Матрицы смежности и инциндентности.
. Маршруты, цепи, пути, циклы в графах. Основные типы графов. Операции над графами.
Самостоятельное изучение. Изоморфизм и гомеоморфизм графов.
Лекция 9. Метрические характеристики графов. Определение центра, радиуса, диаметра, медианы графа.
Достижимость и связность в графах. Алгоритмы определения компонент связности неорграфов и сильных компонент орграфов.
Лекция 10. Деревья. Понятие остова графа. Методы обхода графа (поиск в глубину и в ширину) и их использование для построения остовов.
Самостоятельное изучение. Алгоритмы Краскала и Прима построения кратчайшего остова взвешенного графа.
Лекция 11. Циклы и разрезы в графе. Цикломатическое и коцикломатическое числа графа. Построение матриц фундаментальных циклов и разрезов графа.
Обходы графа. Эйлеровы графы, цепи, циклы. Теорема Эйлера.
Самостоятельное изучение. Метод Флери построения эйлерова цикла в графе.
Лекция 12. Гамильтоновы цепи, пути, циклы в графе. Алгоритм Робертса и Флореса построения гамильтонова цикла в графе.
Лекция 13. Независимость и покрытия. Независимые и доминирующие множества графа. Ядро графа. Паросочетания, покрытия, клики.
Реберная и вершинная раскраски графа. Хроматическое число.
Самостоятельное изучение. Эвристическая процедура раскраски графа.
Лекция 14. Определение кратчайших путей (маршрутов) в графах. Алгоритм определения пути с минимальным числом дуг.
Лекция 15. Алгоритмы Дейкстры и Форда определения кратчайшего пути между двумя фиксированными вершинами взвешенного графа.
Самостоятельное изучение . Алгоритм Форда определения кратчайших путей между всеми парами вершин графа.
Лекция 16. Потоки в транспортных сетях. Теорема о максимальном потоке и минимальном разрезе. Алгоритм Форда-Фалкерсона определения максимального потока в сети.
Самостоятельное изучение . Некоторые прикладные задачи теории графов. Использование алгоритмов теории графов в автоматизированном проектировании.
Лекция 17. Алгоритм Форда-Фалкерсона определения максимального потока в сети.
6. Учебно-методическое обеспечение дисциплины
6.1. Рекомендуемая литература
а)основная литература
1. Белецкая Светлана Юрьевна. Основы дискретной математики: Учеб. пособие / С.Ю.Белецкая. - Воронеж: Изд-во ВГТУ, 2001. - 106с.
2 Белецкая Светлана Юрьевна. Комбинаторика. Графы. Алгоритмы: Учеб. пособие / С.Ю.Белецкая. - Воронеж: ВГТУ, 2003. - 103с.
3. Новиков Ф.А. Дискретная математика для программистов: Учеб. пособие / Ф.А.Новиков. - СПб.: Питер
4. Белоусов Алексей Иванович. Дискретная математика: Учеб. пособие. Вып.XIX / А.И. Белоусов, С.Б. Ткачев; Под ред. В.С. Зарубина, А.П. Крищенко. - 2-е изд., стереотип. - М.: Изд-во МГТУ им.Н.Э.Баумана, 2002. - 743с
б)дополнительная литература
1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988. 480 с.
2. Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учебное пособие. М.: Изд-во МАИ, 1992. 264 с.
3. Лекции по теории графов / Емеличев В.А., Мельников О.И., М.: Наука, 1990. 384 с.
4. Кристофидес Н. Теория графов: алгоритмический подход. М.: Мир, 1978. 432 с.
в)методическая литература
1. Леденева Т.М. Специальные главы математики. Дискретная математика: Учеб. пособие. Воронеж. гос. техн. ун-т. Воронеж, 1997. 130 с.
2. Элементы теории графов: Методические указания к практическим и индивидуальным занятиям/ С.Ю.Белецкая, Л.Д.Кретова, Е.Н.Королев, Н.Б.Ускова. Воронеж.: ВГТУ, 1998. 38 с.
3. Алгоритмы теории графов: Методические указания к практическим и индивидуальным занятиям/ С.Ю.Белецкая, Л.Д.Кретова, Н.Б.Ускова. Воронеж.: ВГТУ, 2000. 30 с.
4. Леденева Т.М. Специальные главы математики. Прикладные дискретные модели: Учеб пособие. Воронеж: Изд-во ВГТУ, 2000. 98 с.
7. Материально-техническое обеспечение дисциплины.
Лаборатории «Информационных технологий» 217/3, 212/3
ЭВМ Pentium IV – 9шт.
8. Методические рекомендации по организации изучения дисциплины
8.1. Методические рекомендации для преподавателя
Работа преподавателя по организации изучению дисциплины заключается в чтении лекций в соответствии с рабочей программой, проведении лабораторных занятий и их прием у студентов, проведение промежуточных мероприятий по проверке знаний, проведение итогового контроля в виде экзамена и проведение контроля остаточных знаний. Самостоятельное изучение отдельных разделов дисциплины преподаватель должен организовать в соответствии с планом-графиком самостоятельной работы студентов. Основной учебный материал занесён в систему дистанционного обучения Афина.
8.2. Методические рекомендации для студентов
Студенты очной формы обучения нормативного срока обучения изучают дисциплину "Дискретная математика" в течение 3 семестра. Виды и объем учебных занятий, формы контроля знаний приведены в табл. 1. Темы и разделы рабочей программы, количество лекционных часов и количество часов самостоятельной работы студентов на каждую из тем приведены в табл. 2. В первой колонке этой таблицы указаны номера тем согласно разделу 4. Организация лабораторного практикума, порядок подготовки к лабораторным занятиям и методические указания к самостоятельной работе студентов, а также порядок допуска к лабораторным занятиям и отчетности по проделанным работам определены в методических указаниях по выполнению лабораторных работ. При самостоятельной работе студенты изучают методы и алгоритмы комбинаторики и теории графов, недостаточно подробно представленные в лекционном курсе. Рассматриваются вопросы программной реализации методов и алгоритмов, а также прикладные аспекты использования аппарата дискретной математики при автоматизированном проектировании. По результатам подготавливается индивидуальный отчет.
8.3. Содержание курсовой работы
Курсовая работа посвящена углубленному изучению теоретических и алгоритмических основ теории графов, формированию у студентов навыков анализа графовых структур и использования аппарата теории графов в прикладных задачах. Она заключается в разработке алгоритмического и программного обеспечения для решения графовых задач различных типов. Пояснительная записка объемом 20-30 страниц должна содержать: постановку задачи, описание используемого метода решения, схемы алгоритмов решения, описание разработанных программных средств и их характеристики, сравни-
тельный анализ реализованного алгоритма с другими методами решения данной задачи, прикладные аспекты метода и его использование в автоматизированном проектировании. В приложении приводятся листинги разработанных программных средств и контрольный пример.
9. Рекомендуемый перечень тем практических занятий
1. Операции над множествами. Диаграммы Эйлера-Венна. Упрощение выражений над множествами с использованием основных тождеств алгебры множеств.
2. Операции над нечеткими множествами и их свойства. Определение расстояний между нечеткими множествами, индексов нечеткости.
3. Бинарные отношения. Запись бинарных отношений с помощью специальной математической символики. Определение свойств бинарных отношений и их принадлежности к специальным типам бинарных отношений. Построение диаграмм Хассе.
4. Нечеткие отношения. Операции над нечеткими отношениями. Композиции нечетких отношений. Определение свойств нечетких отношений и их принадлежности к специальным нечетким отношениям.
5. Элементы общей алгебры. Определение принадлежности различных алгебр к основным типам.
6-8. Решение задач на использование основных комбинаторных формул.
9. Основные понятия теории графов. Типы графов. Подграфы. Матричное представление графов. Операции над графами. Построение графовых моделей электрических и коммутационных схем.
10. Метрические характеристики графа. Определение центра, радиуса, диаметра, медианы графа. Решение минимаксных и минисуммных задач размещения.
11. Достижимость и связность. Определение компонент связности неорграфов и сильных компонент орграфов.
12. Деревья: основные понятия. Построение остовных деревьев графа с использованием поиска в глубину и ширину. Алгоритмы Краскала и Прима построения кратчайшего остова взвешенного графа. Задачи определения кратчайших остовов в топологическом проектировании.
13. Построение матриц фундаментальных циклов и разрезов графа и их использование для составления систем уравнений Кирхгофа для токов и напряжений в электрических цепях.
14. Обходы графа. Определение эйлеровых и гамильтоновых циклов графа и использование данных задач в приложениях. Решение задачи коммивояжера и его прикладное значение.
15. Алгоритмы раскраски графа. Решение прикладных задач, сводящихся к задаче о раскраске.
16. Определение кратчайших путей в графах. Решение задач на использование алгоритмов Дейкстры, Форда и Флойда.
17. Алгоритм Форда-Фалкерсона определения максимального потока в транспортной сети.
Приложение1
4. КАЛЕНДАРНЫЙ ПЛАН ЧТЕНИЯ ЛЕКЦИЙ
| Номер и краткое название темы | Дата и N недель | Примечание |
| Лекция 1. Место дискретной математики в системе математического образования. Канторовское определение множества | 1 | |
| Лекции 2. Операции над множествами. Понятие отношения | 2 | |
| Лекция 3. Свойства бинарных отношений. Соответствия, отображения и функции | 3 | |
| Лекция 4. Бинарные алгебраические операции и их свойства | 4 | |
| Лекция 5. Классификация комбинаторных задач и характеристика их основных типов. | 5 | |
| Лекция 6. Основные правила комбинаторики. | 6 | |
| Лекция 7. Бином Ньютона. Метод включений и исключений. | 7 | |
| Лекция 8. Понятие графа Маршруты, цепи, пути, циклы в графах | 8 | |
| Лекция 9. Метрические характеристики графов Достижимость и связность в графах | 9 | |
| Лекция 10 Деревья. Понятие остова графа | 10 | |
| Лекция 11 Циклы и разрезы в графе. . Обходы графа | 11 | |
| Лекция 12. Гамильтоновы цепи, пути, циклы в графе | 12 | |
| Лекция 13. Независимость и покрытия Реберная и вершинная раскраски графа | 13 | |
| Лекция 14. Определение кратчайших путей (маршрутов) в графах | 14 | |
| Лекция 15. Алгоритмы Дейкстры и Форда определения кратчайшего пути между двумя фиксированными вершинами взвешенного графа | 15 | |
| Лекция 16. Потоки в транспортных сетях | 16 | |
| Лекция 17. Алгоритм Форда-Фалкерсона | 17 | |
| | | |
Приложение 2
План-график самостоятельной работы
| N недели | Вид работы | Нормотив час/задание | Объем (кол-во заданий) | Трудоемкость за неделю (час) |
| 3 | Понятие нечеткого множества. Функция принадлежности. Основные операции над нечеткими множествами и их свойства. | 2 | 4 | 8 |
| 4 | Композиция бинарных отношений. | 3 | 3 | 9 |
| 9 | Изоморфизм и гомеоморфизм графов | 3 | 2 | 6 |
| 11 | Алгоритмы Краскала и Прима построения кратчайшего остова взвешенного графа. | 5 | 2 | 10 |
| 12 | Метод Флери построения эйлерова цикла в графе. | 5 | 2 | 10 |
| 14 | . Эвристическая процедура раскраски графа | 4 | 2 | 8 |
| 15 | Алгоритм Форда определения кратчайших путей между всеми парами вершин графа. | 3 | 3 | 9 |
| 16 | Некоторые прикладные задачи теории графов | 6 | 2 | 12 |