Методические указания по выполнению курсовых работ по курсу (стр. 1 из 6)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

«Нижегородский государственный университет им. Н. И. Лобачевского»

Факультет вычислительной математики и кибернетики

Кафедра информатики и автоматизации

научных исследований

Методические указания по выполнению
курсовых работ по курсу

«Управление информационными ресурсами»

специальность «Прикладная информатика»

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

Рекомендовано методической комиссией факультета вычислительной математики и кибернентики для студентов ННГУ, обучающихся по направлению подготовки 080800 «Прикладная информатика» и специальности 080801 «Прикладная информатика»

Н.Новгород, 2010

Методические указания по выполнению курсовых работ по курсу «Управление информационными ресурсами» для студентов факультета ВМК специальности «Прикладная информатика./ Нижегородский государственный университет, 2010, 22 c.

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

Методическое пособие подготовлено к.т.н. Неймарк Е.А.

Рецензент д.т.н., проф. Турлапов В.Е.

Введение

Данная часть курса является продолжением изучения объектно-ориентированного подхода в программировании и основ алгоритмизации.

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

В результате выполнения курсовой работы каждая задача должна иметь два режима выполнения: демонстрационный и обучающий. Демонстрационный режим пошагово отображает процесс построения решения задачи. Обучающий режим направлен на обучение пользователя решению задачи при помощи данного метода. Этот режим предполагает интерактивное участие пользователя, выбор параметров, а также выбор ребра или вершины для следующего шага алгоритма. Программа должна проверить правильность выбора и в случае неправильного выбора уведомить пользователя об этом.

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

Целью данной работы является обучение использованию объектно-ориентированного подхода в программировании, построению графического интерактивного интерфейса. Кроме того, важной частью работы является ознакомление с различными задачами на графах и методами их решения, а также перевод алгоритмов решения задачи в программную реализацию.

Общие методические указания к выполнению работы

В интерфейсе демонстрационной части программы необходимо наличие следующих блоков:

1. Панель с демонстрацией текущего решения (отображение графа)

2. Кнопка начала демонстрации и(или) кнопка пошагового выполнения алгоритма

3. Выделение цветом параметров, измененных на текущем шаге алгоритма (веса, вершины, ребра)

4. Области для ввода параметров задачи

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

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

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

1. Построение минимального остова графа

Постановка задачи

В рамках данного курса мы будем рассматривать только связные графы.

Рассмотрим граф G(V, E), V – это множество вершин графа G, E – множество ребер. Остовом графа G(V, E), является дерево

, . Минимальный остов это остов графа, имеющий минимальный суммарный вес входящих ребер.

Методы решения

Предлагаемые алгоритмы построения минимального остова относятся к жадным методам поиска решения.

- Алгоритм Краскала

Более подробно с данным подходом можно ознакомиться в работе [2].

Шаг 1. Граф Т является вполне несвязным графом, содержащим n вершин исходного графа G (Т – пустой граф).

Шаг 2. Упорядочиваем ребра графа G в порядке неубывания весов.

Шаг 3. Начав с первого ребра в списке ребер, добавлять ребра в Т таким образом, чтобы добавление ребра не приводило к появлению цикла.

Шаг 4. Повторять шаг 3 до тех пор, пока число ребер в графе Т не станет равным n-1. Полученное дерево является минимальным остовом графа G(V, E).

Указания по отображению процесса поиска решения:

Режим демонстрации:

Для каждого ребра отображать его вес. Добавляемое на текущем шаге в дерево ребро, выделять цветом. Отображать текущий вес остова.

Режим обучения:

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

- Алгоритм Прима

Более подробно с данным методом можно ознакомиться в работе [2].

Здесь и далее

обозначает множество вершин, смежных с .

Шаг 1. Произвольно выбираем вершину

, - множество вершин в строящемся остове .

Шаг 2. Для каждой вершины

находим вершину такую, что и приписываем вершине пометку [ ], если такой вершины нет, то есть , приписываем вершине метку [0, ].

Шаг 3. Выбрать такую вершину

, для которой . Добавляем ее в дерево { .

Если |

, то остановиться, полученное дерево – минимальный остов.

Шаг 4. Для всех

, для которых обновить метки.

Если

, то , . Вернуться к шагу 3.

Иначе вернуться к шагу 3.

Указания по отображению процесса поиска решения:

Режим демонстрации:

Для каждой вершины

отображать пометку [ ]. Добавляемое в остов на текущем шаге ребро , выделять цветом. Отображать текущий вес остова.