Институте Вычислительной Математики и Математической Геофизики со ран создается электронный учебник

Вид материала

Учебник

Содержание Описание работы с учебником Решение задач с объектами сетевой структуры

Подобный материал:

• Исследование и разработка моделей и методов оптимизации структур телекоммуникационных, 179.52kb.
• Программа, 247.1kb.
• Программа Российской научной конференции с участием зарубежных исследователей «Моделирование, 115.43kb.
• Численный алгоритм вариационной инициализации океанологических полей 05. 13. 18 Математическое, 202.48kb.
• Программы «Информационные технологии в делопроизводстве» Тематического планирования, 305.8kb.
• М. В. Ломоносова Факультет вычислительной математики и кибернетики Кафедра математической, 6.81kb.
• Программа по дисциплине вычислительная математика, 44.55kb.
• Совершенствование методов и механизмов формирования и использования Стабилизационного, 430.25kb.
• Обзор рекомендуемой литературы по дисциплине, 82.08kb.
• Программа подготовки 010400. 68. 03 Математическая физика, 230.29kb.

ПРИМЕНЕНИЕ ЭЛЕКТРОННОГО УЧЕБНИКА ПО ТЕОРИИ ГРАФОВ В УЧЕБНОМ ПРОЦЕССЕ

О.Д. Соколова

Институт Вычислительной Математики и Математической Геофизики СО РАН

E-mail: olga@rav.sscc.ru

Введение

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

В Институте Вычислительной Математики и Математической Геофизики СО РАН создается электронный учебник по теории графов. В учебнике собран большой лекционный материал по всем основным направлениям теории графов, приведены алгоритмы решения классических задач (поиск метрических характеристик графов, доминирующего и независимого множеств, раскраска вершин, задачи связности и др.) и многих прикладных задач, легко решаемых на графах и гиперсетях. Решение задач осуществляется на графическом редакторе, где студент (или любой другой пользователь) может сам построить нужный граф или гиперсеть и по разобранному алгоритму решить задачу. Весь пользовательский интерфейс редактора сделан в стиле Windows 95, и поэтому процесс редактирования и построения графа доступен всем, кто будет пользоваться этим электронным учебником. Для создания программы использовался объектно-ориентированный язык программирования Object Pascal, используемый для создания приложений для Windows в среде программирования Delphi 4.

Описание работы с учебником

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

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

Решение задач с объектами сетевой структуры

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

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

Рассматривая различные вопросы, возникающие при проектировании, можно выделить группы задач анализа структуры сети, легко решаемые с помощью теории графов:

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

Трудоемкость большинства алгоритмов решения оптимизационных задач сетей связи очень высока (как правило, задачи являются многокритериальными и NP-трудными). С другой стороны, существует много приближенных алгоритмов решения классических задач на графах и сетях с полиномиальной сложностью [1]. Поэтому основной проблемой для пользователя становится декомпозиция сложной задачи проектирования или анализа на частные подзадачи, сведение их к известным задачам теории графов и решение таких задач на конкретных примерах в графическом редакторе.

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

Заключение

Из всего описанного следует, что электронный учебник можно использовать в качестве обучающего инструмента, который позволяет:

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

Литература

1. Нечепуренко М. И., Попков В. К. и др. Алгоритмы и программы решения задач на графах и сетях. Новосибирск, Наука, Сибирское Отделение, 1990 г.