Исследование алгоритмов топологической сортировки
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Министерство образования и науки Российской Федерации
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОУ ВПО Северо-Кавказский государственный технический университет
Факультет информационных технологий и телекоммуникаций
Допустить к защите
Заведующий кафедрой ЗИ
А. Ф. Чипига
КУРСОВАЯ РАБОТА
НА ТЕМУ:
Исследование алгоритмов топологической сортировки
Автор дипломного проекта
Давлет-Кильдеева Екатерина Витальевна
Специальность
Комплексное обеспечение информационной безопасности автоматизированных систем
Группа БАС-081
Обозначение курсового проекта КР-СевКавГТУ-94374-11
Проектировал
Е.В.Давлет-Кильдеева
Руководитель работы
Р. А. Воронкин
Ставрополь, 2011
Содержание
ВВЕДЕНИЕ
. ОБЩИЕ ПРИНЦИПЫ ОРГАНИЗАЦИИ ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ
.1 Основные понятия
.2 Анализ структуры программы топологической сортировки
.3 Вывод
. СПОСОБЫ ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ
.1 Алгоритм Демукрона
.2 Метод топологической сортировки с помощью обхода в глубину
.3 Вывод
. РЕАЛИЗАЦИЯ ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ В ПРОГРАММНОЙ СРЕДЕ
.1 Программа, реализующая топологическую сортировку методом Демукрона
.2 Процедура топологической сортировки, реализующая метод обхода в глубину
.3 Вывод
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
Приложение 1
ВВЕДЕНИЕ
В словарях слово сортировка определяется как процесс разделения объектов по виду или сорту, но программисты традиционно используют его в гораздо более узком смысле, обозначая им такую перестановку предметов, при которой они располагаются в порядке возрастания или убывания. Хотя сортировка традиционно и большей частью использовалась для обработки коммерческих данных, в действительности она является инструментом, полезным в самых разных ситуациях, и поэтому о ней не следует забывать. Появление изощренных алгоритмов сортировки говорит о том, что она сама по себе очень интересна как объект исследования.
Среди всех широко известных методов упорядочивания элементов следует выделить алгоритмы сортировки на графах, а именно топологическую сортировку. Цель данной сортировки - преобразовать частичный порядок в линейный. Графически это означает расположение вершин графика в ряд так, чтобы все стрелки были направлены вправо.
Топологическая сортировка применяется в самых разных ситуациях, например при распараллеливании алгоритмов, когда по некоторому описанию алгоритма нужно составить граф зависимостей его операций и, отсортировав его типологически, определить, какие из операций являются независимыми и могут выполняться параллельно (одновременно). Формально топологическую сортировку можно реализовать по-разному. Примером использования может служить создание карты сайта, где имеет место древовидная система разделов.
Тема топологической сортировки слабо проработана в современной литературе: большинство авторов уделяют в основном внимание наиболее быстрым видам сортировок, а сортировки на графах практически не рассматриваются.
Итак, целью данной курсовой работы является - исследование методов топологической сортировки.
Поставленная цель раскрывается через следующие задачи:
Проанализировать общие принципы организации топологической сортировки;
Изучить способы топологической сортировки;
Исследовать реализацию топологической сортировки в программной среде;
Сделать выводы по исследованию.
1. ОБЩИЕ ПРИНЦИПЫ ОРГАНИЗАЦИИ ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ
1.1 Основные понятия
Множество M называется частично упорядоченным, если над его элементами определено отношение, которое мы назовем "x предшествует y" и обозначим x << y, удовлетворяющее следующим свойствам для любых элементов x, y и z из M:
.не x << x (антирефлексивность),
.если x <<y, то не y << x (антисимметричность),
.если x << y и y << z, то x << z (транзитивность).
Мы будем предполагать, что M - конечное множество.
Частичное упорядочение на конечном множестве всегда можно проиллюстрировать с помощью диаграммы некоторого графа, в которой элементы представляются вершинами графа, а отношения представляются дугами между этими вершинами; x << y означает, что от вершины, помеченной x, к вершине y существует путь, идущий вдоль дуг в соответствии с их направлением. Свойство частичного упорядочения означает, что в диаграмме графа нет замкнутых контуров.
Проблема топологической сортировки состоит в том, чтобы "перевести частичное упорядочение в линейное упорядочение", т.е. расположить элементы в такую последовательность a1,a2, ..., an, что если aj<<ak, то j<k [1, с.325]. Существование такого расположения не является непосредственно очевидным, однако оно заведомо невозможно, если имеется хотя бы один контур.
Чтобы найти одно из возможных линейных упорядочений начинаем с того, что выбираем какой-либо элемент, которому не предшествует никакой другой (хотя бы один такой элемент существует, иначе имелся бы цикл). Этот элемент помещается в начало списка и исключается из множества M. Оставшееся множество по-прежнему частично упорядочено; таким образом, можно вновь применить тот же самый алгоритм, пока множество не станет пустым. Этот алгоритм оказался бы непригодным в единственном случае, когда образовалось бы непустое частично упорядо?/p>