Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Учебно-методическое пособие'
Методические указания содержат основные требования по оформлению рефератов, курсовых и бакалаврских работ и рекомендации к их подготовке, написанию и...полностью>>
'Документ'
Приказ Министра обороны Российской Федерации «О порядке подготовки, оформления и государственной регистрации официальных документов Министерства оборо...полностью>>
'Документ'
1. Мы подтверждаем нашу приверженность наращиванию индивидуальных и совместных усилий с целью борьбы с интеллектуальным пиратством и распространением...полностью>>
'Документ'
Разрешите представиться – командир звездолёта «Безотказный», знаток удивительных тайн Космоса капитан Магеллан Христофорович Врунгель-второй. Недавно...полностью>>

Рабочая программа учебной дисциплины ен. Ф. 01. 03 Дискретная математика для специальности 230104 «Системы автоматизированного проектирования»

Главная > Рабочая программа
Сохрани ссылку в одной из сетей:

ГОУ ВПО

«Воронежский государственный технический университет»

«Утверждаю»

Декан ЕГФ

_____________С.М.Пасмурнов

РАБОЧАЯ ПРОГРАММА

УЧЕБНОЙ ДИСЦИПЛИНЫ

ЕН.Ф.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



Скачать документ

Похожие документы:

  1. Рабочая программа учебной дисциплины ф тпу 1- 21/01 федеральное агентство по образованию (5)

    Рабочая программа
    Цель: формирование знаний о математике, как особом способе познания мира и образе мышления, общности её понятий и представлений, дать опыт построения математических моделей и проводить необходимые расчёты в рамках построенных моделей;
  2. Рабочая программа по курсу математика для специальности 012500 -география Составитель А. И. Голиков, доцент кафедры математической экономики

    Рабочая программа
    Объем работы студента в часах из учебного плана специальности 012500 - «География», утвержденного Ученым Советом Биолого-географического факультета ЯГУ от «__» 2001г.
  3. Программа дисциплины «вычислительная математика» Индекс дисциплины по учебному плану: ен. Ф. 01. 4 Направление 230200 Информационные системы

    Программа дисциплины
    Программа курса разработана в соответствии с Государственным образовательным стан­дар­том выс­­шего профессионального образования по направлению 230200 «Информационные системы», по специальности 23201 «Информационные системы и технологии»,
  4. Учебная программа для высших учебных заведений по специальности i-54 01 04 Метрологическое обеспечение информационных систем и сетей Согласована с Учебно-методическим управл

    Программа
    С.В. Ляльков, доцент кафедры метрологии и стандартизации Учреждения образования «Белорусский государственный университет информатики и радиоэлектроники»,
  5. Рабочая программа по дисциплине «логика» для специальности 351400 Прикладная информатика (по областям) Форма обучения: очная

    Рабочая программа
    Рабочая программа составлена на основании ГОС ВПО специальности 351400 «Прикладная информатика (по областям)» (квалификация – информатик (квалификация в области ), утвержденного 14 марта 2 г.

Другие похожие документы..