Практикум по дискретной математике в среде виртуальной лаборатории системы ДО ИТМО (стр. 1 )

Санкт-Петербургский государственный университет

информационных технологий, механики и оптики

(СПбГУ ИТМО)

Кафедра «Компьютерные образовательные технологии»

,

Практикум по дискретной математике

в среде виртуальной лаборатории системы ДО ИТМО

Учебно-методическое пособие

Санкт-Петербург

2004

УДК 681.3

, Лисицына по дискретной математике.

Учебно-методическое пособие. – СПб., 20с.

Рецензенты: , д. т.н., профессор, декан ЕНФ СПбГУ ИТМО,

, к. т.н., доцент каф. СУиИ СПбГУ ИТМО

Учебно-методическое пособие подготовлено на кафедре «Компьютерные образовательные технологии» (КОТ) факультета ИТиП и предназначено для студентов специальностей 073700 – «Информационные технологии в образовании» и 071900 – «Информационные системы и технологии», изучающих курс «Дискретная математика». Пособие служит для поддержки практических занятий и аттестаций в среде виртуальной лаборатории по данному курсу в системе дистанционного обучения (ДО) ИТМО.

Печатается по решению УМС факультета ИТиП СПбГУ ИТМО.

© Санкт-Петербургский государственный

институт точной механики и оптики

(технический университет), 2003

ОГЛАВЛЕНИЕ

Введение.

1.  План занятий и форма отчетности в среде виртуальной лаборатории по «Дискретной математике» системы ДО ИТМО.

2.  Методические указания по темам практических занятий.

2.1.  Тема № 1 «Связность в графе». Волновой метод поиска минимального маршрута в связном графе.

2.2.  Тема № 2 «Циклы в графе». Циклы Гамильтона и задача коммивояжера.

2.2.1.  Метод Робертса и Флореса.

2.2.2.  Метод ветвей и границ.

2.2.3.  Эвристические методы.

2.3.  Тема № 3 «Деревья в графе». Минимальные остовные деревья во взвешенном графе.

2.3.1.  Метод Прима.

2.3.2.  Метод Краскала.

2.4.  Тема № 4 «Внутренняя и внешняя устойчивость в графе».

2.4.1.  Метод Магу-Вейсмана для поиска НВУП.

2.4.2.  Метод Брона-Кербоша для поиска НВУП.

2.4.3.  Метод разборки графа для поиска НПП.

2.5.  Тема № 5 «Операции над графами». Минимальная раскраска.

2.5.1.  Алгоритм раскраски на основе метода Магу-Вейсмана.

2.5.2.  Алгоритм раскраски А1.

2.5.3.  Алгоритм раскраски А2.

2.6.  Тема № 6 «Изоморфизм графов». Метод на основе обобщения локальных характеристик вершин.

2.7.  Тема № 7 «Транспортная задача».

2.7.1.  Метод «северо-западного угла».

2.7.2.  Метод минимальной стоимости.

2.7.3.  Метод потенциалов.

2.8.  Тема № 8 « Задача линейного назначения».

2.8.1.  Венгерский алгоритм.

2.8.2.  Метод на основе принципа максимина.

2.8.3.  Метод на основе принципа минимального риска.

3.  Методические указания для подготовки к аттестующим тестам.

3.1. Тест № 1 «Экстремальные числа графа».

3.2. Тест № 2 «Сети Петри».

Литература.

ВВЕДЕНИЕ

Целью данного пособия является:

·  методическая поддержка практических занятий по курсу «Дискретная математика», проводимых в среде виртуальной лаборатории системы ДО ИТМО,

·  методическая поддержка подготовки к аттестующим тестам по лекционному курсу «Дискретная математика».

Виртуальная лаборатория по «Дискретной математике» представляет собой комплекс программ, моделирующих работу ряда изучаемых методов курса с целью проверки правильности решения задач. Результаты проверки заносятся в электронный журнал системы ДО ИТМО и являются основанием для зачета по данной теме занятий. При этом, система ДО ИТМО позволяет отслеживать студенту, преподавателю и деканату текущую успеваемость по предмету.

Тестирование по лекционному курсу «Дискретная математика» проводится в системе ДО ИТМО в рамках расписания практических занятий. Студенты должны пройти тестирование по двум темам: «Экстремальные числа графа» и «Сети Петри». Оба теста – с оценкой.

Аттестация по курсу «Дискретная математика» включает в себя:

·  для студентов по специальности 071900 в форме зачета, который определяется на основании всех сданных зачетов по темам практикума и аттестующих тестов,

·  для студентов по специальности 071900 в форме экзамена, допуском к которому является зачет по практическим занятиям и положительные оценки по аттестующим тестам.

1.  План занятий и форма отчетности в среде виртуальной лаборатории по «Дискретной математике» системы ДО ИТМО

№ задания	Тема занятия	вариант	Форма отчетности
073700	071900
	«Связность в графе»
1	Волновой метод поиска минимального маршрута в связном графе.	*		зачет
	«Циклы в графе»
2	Метод Робертса и Флореса.	*		зачет
3	Метод ветвей и границ.	*	*	зачет
4	Эвристические методы.	**		зачет
	«Деревья в графе»
5	Метод Прима.	*	*	зачет
6	Метод Краскала.	**	*	зачет
	«Внутренняя и внешняя устойчивость в графе»
7	Метод Магу-Вейсмана для поиска НВУП.	*	*	зачет
8	Метод Брона-Кербоша для поиска НВУП.	**		зачет
9	Метод разборки графа для поиска НПП.	*		зачет
	«Операции над графами»
10	Алгоритм раскраски на основе метода Магу-Вейсмана.	**		зачет
11	Алгоритм раскраски А1.	**		зачет
12	Алгоритм раскраски А2.	**		зачет
	«Изоморфизм графов»
13	Метод на основе обобщения локальных характеристик вершин графов.	*		зачет
14	Тест № 1 «Экстремальные числа графа»	*	*	оценка
	«Транспортная задача»
15	Метод «северо-западного угла».	*		зачет
16	Метод минимальной стоимости.	**		зачет
17	Метод потенциалов.	*		зачет
	«Задача линейного назначения»
18	Венгерский алгоритм.	*	*	зачет
19	Метод на основе принципа максимина.	**		зачет
20	Метод на основе принципа минимального риска.	**		зачет
21	Тест № 2 «Сети Петри»	*	*	оценка

В приведенной выше таблице представлен план проведения практических занятий в 2-ух вариантах: 32 часа занятий - для студентов специальности 073700 и 16 часов – для студентов специальности 071900. Символом «*» отмечены обязательные темы для изучения и зачета, а символами «**» - темы для самостоятельного изучения и зачета.