«УТВЕРЖДАЮ» Проректор по учебной работе

___________________

“___”___________ 2011 г.

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

"Теория конечных графов и ее приложения"

Направление подготовки 010300.62 «ФИИТ»

Профиль подготовки «Общий»

Квалификация (степень) выпускника Бакалавр________________

(бакалавр, магистр, дипломированный специалист)

Форма обучения_____________очная_______________________________

(очная, очно-заочная, заочная)

Семестр

Трудоем­кость (зач. ед, /час.)

Лек­ций, (час.)

Практ.

занятий,

(час.)

Лаборат.

работ,

(час.)

СРС,

(час.)

Форма

контроля

(экз./зачет)

5

3/108

17

17

17

57

Зачет

Итого

3/108

17

17

17

57

Владимир 2011

1.  ЦЕЛИ ОСВОЕНИЯ ДИСЦИПЛИНЫ

Дисциплина "Теория конечных графов и ее приложения" обеспечивает подготовку по следующим разделам. Графы ориентированные и неориентированные. Изоморфизм графов. Маршруты, цепи, циклы. Деревья. Помеченные графы. Плоские и планарные графы. Теоремы Эйлера и Понтрягина-Куратовского. Графы с весами. Задача о кратчайшем соединении. Алгоритмы Краскаля и Дейкстры.

Целями освоения дисциплины "Теория конечных графов и ее приложения" являются формирование навыков логического мышления; ознакомление с основами теоретических знаний по графам.

2. МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП ВПО

Дисциплина "Теория конечных графов и ее приложения" относится к дисциплинам естественно-научного цикла:

·  Код УЦ ООП учебного цикла основной образовательной программы (раздела) – Б2.2.1

НЕ нашли? Не то? Что вы ищете?

·   

Взаимосвязь с другими дисциплинами

Курс "Теория конечных графов и ее приложения" основывается на знании школьного курса математики.

Полученные знания могут быть использованы во всех без исключения общепрофессиональных дисциплинах, а также дисциплинах естественнонаучного цикла.

3.  КОМПЕТЕНЦИИ ОБУЧАЮЩЕГОСЯ, ФОРМИРУЕМЫЕ

В РЕЗУЛЬТАТЕ ОСВОЕНИЯ ДИСЦИПЛИНЫ

В результате освоения дисциплины обучающийся должен обладать следующими профессиональными компетенциями (ПК):

ПК-4

-- способность понимать и применять в исследовательской и прикладной деятельности современный мат. аппарат

В результате освоения дисциплины обучающийся должен:

Знать:

основы теории графов

Уметь:

- применять теоретические знания при решении задач с графами;

Владеть:

- основными приемами решения задач по теории графов

4.  СТРУКТУРА И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

4.1. ТЕОРЕТИЧЕСКИЙ КУРС

4.1.1 Графы ориентированные и неориентированные. Локальные характеристики графа. Теорема Эйлера о рукопожатиях

4.1.2 Изоморфизм графов. Геометрическая реализация графов. Подграфы. Операции над графами

4.1.3 Маршруты, цепи, циклы. Связность, сильная связность, компоненты.

4.1.4 Эйлеровы, квазиэйлеровы графы. Деревья.

4.1.5 Помеченные графы. Матрицы, ассоциированные с графами.

4.1.6 Плоские и планарные графы. Теоремы Эйлера и Понтрягина-Куратовского.

4.1.7 Графы с весами. Задача о кратчайшем соединении. Алгоритмы Краскаля и Дейкстры.

4.3. ТРУДОЕМКОСТЬ И ФОРМИРУЕМЫЕ КОМПЕТЕНЦИИ

Общая трудоемкость дисциплины составляет 3 зачетные единицы (108 часов): Дисциплина приходится на пятый семестр. Распределение трудоемкости по видам занятий представлено в табл. 1.

Таблица 1

В семестре выполняются контрольные работы

с оценками, учитываемыми в рейтинг контроле. Выдаются типовые расчеты

Неделя

семестра

Раздел дисциплины

Виды учебной работы и трудоемкость

(в часах)

Формы текущего контроля

успеваемости (по неделям)

Форма промежуточной

аттестации

Лек.

Прак.

Лаб.

СРС

1

4.1.1

2

2

2

2

4.1.1

2

4

3

4.1.1

2

2

2

4

4.1.2

2

4

5

4.1.2

2

2

2

Рейтинг контроль №1

6

4.1.2

2

4

7

4.1.3

2

2

2

8

4.1.3

2

4

9

4.1.3

2

2

2

10

4.1.4

2

4

Рейтинг контроль №2

11

4.1.4

2

2

4

12

4.1.4

2

4

13

4.1.5

2

2

4

14

4.1.5

2

4

15

4.1.6

2

2

2

16

4.1.7

2

6

17

4.1.7

2

2

4

Рейтинг контроль №3

Итого

18

16

18

58

ЗАЧЕТ

Матрица соотнесения разделов учебной дисциплины и формируемых в них профессиональных компетенций представлена в табл. 2

Таблица 2

Разделы

дисциплины

Колич. часов

(аудит.)

Компетенции

ПК-4

Общее

количество компетенций

4.1.1

4

+

1

4.1.2

4

+

1

4.1.3

4

+

1

4.1.4

4

+

1

4.1.5

4

+

1

4.1.6

4

+

1

4.1.7

4

+

1

5. ОБРАЗОВАТЕЛЬНЫЕ ТЕХНОЛОГИИ

5.1.  Активные и интерактивные формы обучения

С целью формирования и развития профессиональных навыков студентов в учебном процессе используются активные и интерактивные формы проведения занятий в сочетании с внеаудиторной работой: (контрольные аудиторные работы, индивидуальные домашние работы). Объем занятий, проводимых в интерактивных формах, составляет 4 часов консультационных занятий (вне расписания), контрольные работы 2 часов на практических занятиях.

5.2.  Самостоятельная работа студентов

Самостоятельная (внеаудиторная) работа студентов включает закрепление теоретического материала при подготовке к выполнению контрольных заданий, а также при выполнении индивидуальной домашней работы. Основа самостоятельной работы - изучение литературы по рекомендованным источникам и конспекту лекций, решение выданных преподавателем практики задач.

5.3.  Мультимедийные технологии обучения

Некоторые из лекционных и практических занятий проводятся в виде презентаций в мультимедийной аудитории с использованием компьютерного проектора.

Студентам предоставляется компьютерный курс лекций. Компьютерные технологии используются для оформления типовых расчетов.

5.4.  Лекции приглашенных специалистов

В рамках учебного курса «Фундаментальная и компьютерная алгебра» предусмотрены встречи с представителями российских и зарубежных университетов

5.5.  Рейтинговая система обучения

Рейтинг-контроль проводится три раза за семестр. Он предполагает оценку суммарных баллов по следующим составляющим: баллы на контрольных занятиях; качество выполнения домашних типовых заданий. Баллы рейтинговой системы аттестации студентов по семестрам приведены в табл. 3.

Таблица 3

Семестр 5

Вид занятий

Число

часов

Рейтинг

Баллы (макс.)

1

2

3

Контрольные

2

20

Лабораторные расчеты

18

40

Рейтинг-контроль

-

20

20

20

60

Зачет

-

-

-

-

40

Всего

100

6. ОЦЕНОЧНЫЕ СРЕДСТВА ДЛЯ ТЕКУЩЕГО КОНТРОЛЯ УСПЕВАЕ­МОСТИ, ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ ПО ИТОГАМ ОСВОЕНИЯ ДИСЦИПЛИНЫ

6.1 Экзаменационные билеты и задачи

1 Графы ориентированные и неориентированные. Локальные характеристики графа. Теорема Эйлера о рукопожатиях

2 Изоморфизм графов. Геометрическая реализация графов. Подграфы. Операции над графами

3 Маршруты, цепи, циклы. Связность, сильная связность, компоненты.

4 Эйлеровы, квазиэйлеровы графы. Деревья.

5 Помеченные графы. Матрицы, ассоциированные с графами.

6 Плоские и планарные графы. Теоремы Эйлера и Понтрягина-Куратовского.

7 Графы с весами. Задача о кратчайшем соединении. Алгоритмы Краскаля и Дейкстры.


6.2 Тесты для проверки остаточных знаний по дисциплине

-- см. приложение 1

7.УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

1.  Яблонский в дискретную математику. М.: Наука, 1986.

2.  Новиков математика для программистов. СПб, Питер, 2000 – 304 стр.

3.  Теория графовМ., Наука, 1980

4.  Дубровин. по алгебре. Владимирский политехнический институт (ВПИ). Кафедра высшей математики.— Владимир : ВПИ, 1997 .— 64 с..

5.  и др. Прикладные алгоритмы на графах. Учебное пособие, ВлГУ, 2005

8. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ

Материально-техническое обеспечение дисциплины включает:

·  кафедральные мультимедийные средства (ауд. 230-3);

·  электронные записи лекций;

·  оборудование специализированной лаборатории (230-3);

·  компьютеры со специализированным программным обеспечением виртуальных приборов.

Программа составлена в соответствии с требованиями ФГОС ВПО по направлению «Радиотехника» и профилям подготовки бакалавров «Радиотехника» и «Радиофизика».

Автор: доцент каф. АиГ _________________

Рецензент: _______________

Программа одобрена на заседании каф. АиГ

Протокол № ___________ От ___________________

Программа переутверждена:

на____________учебный год, протокол №__________от ______________

Зав. кафедрой ____________________________

на____________учебный год, протокол №__________от ______________

Зав. кафедрой ____________________________

на____________учебный год, протокол №__________от ______________

Зав. кафедрой ____________________________

на____________учебный год, протокол №__________от ______________

Зав. кафедрой ____________________________