МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

Государственный университет информатики и искусственного интеллекта

Д080403.1.01.03/056.НР

Кафедра программного обеспечения

интеллектуальных систем

ОТЧЕТ О НИРС

Тема: «Построение маршрута при групповой рассылке сетевых пакетов данных»

Руководитель:

___________ доц. А.И. Ольшевский

(дата, подпись)

Нормоконтроль:

___________ асс. Е.В. Курило

(дата, подпись)

Разработал:

___________ ст.гр. ПО-03м Л.В. Карпенко

(дата, подпись)

2008

РЕФЕРАТ

Отчет о НИРС: 39 с., 3 таблицы, 14 рисунков, 6 источников.

Объектом исследования является алгоритм построения оптимального маршрута при групповой рассылке данных.

Цель – разработка алгоритма построения маршрута для дальнейшего теоретического и практического его применения, а также написание программного продукта как реализации алгоритма.

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

В итоге были выбраны методы решения для каждого из этапов алгоритма и представлены схематические результаты построения.

Также были разработаны структуры для хранения и обработки данных алгоритма, предложены методы настройки параметров алгоритма.

СЕТЬ, РЕГИОНАЛЬНЫЕ ЦЕНТРЫ, ДЕРЕВЬЯ ШТЕЙНЕРА, ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ, СТРУКТУРЫ ДАННЫХ

ВВЕДЕНИЕ

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

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

В связи с этим одним из актуальных вопросов ДО стал поиск оптимального способа пересылки данных. Разрабатываются более дешевые и быстрые пути передачи информации.

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

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

Объектом исследования данной работы является алгоритм построения оптимального маршрута при групповой рассылке данных по сети. Основным критерием оптимальности является стоимость рассылки по построенному маршруту.

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

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

1 ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ

По своей сути сеть дистанционного обучения (СДО) представляет собой дерево с набором вершин и ребер. ............