Исследование алгоритмов топологической сортировки - Программирование, компьютеры и кибернетика курсовая работа

Главная

Программирование, компьютеры и кибернетика
Исследование алгоритмов топологической сортировки

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

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

Министерство образования и науки Российской Федерации
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОУ ВПО «Северо-Кавказский государственный технический университет»
Факультет информационных технологий и телекоммуникаций
Исследование алгоритмов топологической сортировки
Давлет-Кильдеева Екатерина Витальевна
090105 «Комплексное обеспечение информационной безопасности автоматизированных систем»
Обозначение курсового проекта КР-СевКавГТУ-94374-11
- Изучить способы топологической сортировки;
- Исследовать реализацию топологической сортировки в программной среде;
2. если x < v } -- множество предшественников вершины v.
Уровень вершины сети можно интерпретировать как длину максимального пути от входов сети до этой вершины.
Порядковой функцией сети G = (V, Е) называют отображение ord: V > N, сопоставляющее каждой вершине сети номер ее уровня.
Во многих прикладных задачах возникает проблема такого упорядочения вершин сети, при котором вершины, принадлежащие одному уровню, располагаются друг под другом, а дуги ориентированного графа ведут в его изображении на плоскости от вершин с меньшим уровнем к вершинам с большим уровням слева направо. Подобного рода проблема называется проблемой топологической сортировки, поскольку необходимо расположить вершины графа на плоскости так, чтобы отчетливо было видно распределение вершин по уровням. Само расположение при этом может быть разным, лишь бы оно имело "слоистую" структуру, в которой каждый слой составляют вершины одного уровня (рисунок 2.1.2).
Топологическая сортировка применяется в самых разных ситуациях, например при распараллеливании алгоритмов, когда по некоторому описанию алгоритма нужно составить граф зависимостей его операций и, отсортировав его топологически, определить, какие из операций являются независимыми и могут выполняться параллельно (одновременно).
Рисунок 2.1.2. - Сеть и результат применения топологической сортировки сети.
Примером использования топологической сортировки может служить создание карты сайта, где имеет место древовидная система разделов.
Формально топологическую сортировку можно реализовать по-разному.
Один из методов вычислении порядковой функции сети - алгоритм Демукрона. Предполагается, что вершины сети пронумерованы от 1 до n.
Наглядно процесс определения уровней вершин можно представить следующим образом. Нулевой уровень образуют входы сети - вершины с полустепенью захода, равной 0. Удалив из сети все вершины нулевого уровня и исходящие из них дуги, вновь получим сеть, входами которой будут вершины первого уровня исходной сети. Указанный процесс "послойного" удаления вершин следует продолжать до тех пор, пока все вершины исходной сети не будут распределены по уровням.
Алгоритм Демукрона использует матрицу смежности вершин В типа n x n в качестве средства представления сети и основан непосредственно на определении уровня вершины и свойствах матрицы В. Можно увидеть, что сумма элементов k-го столбца матрицы В равна полустепени захода вершины Vk. Поэтому, просуммировав элементы матрицы по всем столбцам и выбрав вершины, соответствующие столбцам с нулевой суммой, получим множество вершин нулевого уровня - входы сети.
Безусловно, "физически" удалять вершины и дуги из сети и вычеркивать из матрицы В строки, соответствующие удаляемым вершинам, нет необходимости. Процесс вычисления порядковой функции можно организовать следующим образом. Запишем суммы элементов столбцов матрицы В в вектор М длины n. При этом элемент mk вектора М будет содержать полустепень захода вершины Vk. Пусть из сети удалена вершина Vi и все исходящие из нее дуги. Заметим, что элемент bik равен 1, если из вершины Vi идет дуга в вершину Vk, и равен 0 в противном случае. Поэтому, чтобы получить новую полустепень захода вершины Vk, необходимо из элемента mk вектора М вычесть элемент bik матрицы В. Чтобы пересчитать полустепени захода всех вершин сети, оставшихся в ней после удаления вершины Vi, надо из вектора М вычесть i-ю строку матрицы В.
Если на очередном шаге входами сети являются вершины Vi, … , Vir , то для определения следующего „слоя" вершин нужно из вектора М вычесть строки матрицы В с номерами i1, ... , ir и зафиксировать новые нулевые элементы вектора М, появившиеся после вычитания. Фиксировать следует именно новые нулевые элементы, поскольку элементы вектора М, соответствующие вершинам, лежащим на предыдущих уровнях, стали равными 0 на предыдущих шагах алгоритма.
Заметим, что порядковую функцию сети можно задать, указав множества вершин, принадлежащих каждому уровню, или сопоставив каждой вершине ее номер уровня. Первый способ более удобен при теоретических рассуждениях, второй - при вычислениях.
Алгоритм обрабатывает матрицу В смежности вершин графа порядка n. В результате работы алгоритма получаем массив Ord длины n, i-й элемент которого равен номеру уровня вершины Vi.
0. Сформировать множество V1 вершин сети. Значение счетчика уровней k положить равным 0. Найти суммы элементов по всем столбцам матрицы В (полустепени захода вершин) и заполнить ими массив М.
1. Бели множество V1 не пусто, перейти на шаг 2, если иначе, то перейти на шаг 3.
2. Определить множество I номеров всех новых нулевых элементов массива М, т.е. таких, что соответствующие этим номерам вершины принадлежат множеству V1.
3. Присвоить элементам массива Ord с номерами из множества I номер уровня k и удалить вершины с этими номерами из множества V1 ("замаскировать" вершины). Вычесть из массива М строки матрицы В, соответствующие вершинам с номерами из множества I (т.е. вершинам последнего вычисленного уровня).
4. Увеличить счетчик уровней на 1 (k = k + 1). Вернуться на шаг 1.
Пример. Применим алгоритм Демукрона к сети, представленной на рисунке 2.1.2. Матрица смежности вершин сети имеет следующий вид:
Рисунок 2.1.3. - Матрица смежности вершин сети.
Приведем последовательность значений массива М, соответствующую итерациям алгоритма и множества Ni вершин i-го уровня (рисунок 2.1.4). Прочерки соответствуют вершинам, не принадлежащим множеству V1 ("замаскированные" вершины) на соответствующем этапе алгоритма.
Рисунок 2.1.4. - Значения массива М.
Алгоритм Демукрона может быть модифицирован так, чтобы он останавливался, если ориентированный граф, поданный на вход, не является сетью, и сообщал об этом. Можно увидеть, что анализируемый граф не будет сетью тогда и только тогда, когда при очередном перевычислении массива М не появятся новые нули. [3, с.349]
1) Система отношений порядка имеет вид:
9>2, 3>7, 7>5, 5>8, 8>6, 4>6, 1>3, 7>4, 9>5, 2>8.
Программа топологической сортировки выдаст следующий результат:
2) Более содержательный пример использования программы топологической сортировки [4, с.261-262]:
Разнообразие вин, отражающих почтенную традицию и свидетельствующее об исключительном богатстве палитры французских виноделов, кажется, представляет бесконечные возможности для сервировки хорошего обеда. В действительности же имеются ограничения, выраженные следующими двумя общими правилами:
– не принято подавать за обедом более четырех вин, не считая шампанского;
– последовательность вин на столе подчиняется некоторым соотношениям порядка, признаваемым всеми знатоками.
белое (за исключением сладкого) < красное,
При этом знак < указывает, что вино, стоящее слева от него, должно быть подано прежде вина, которое стоит справа. Мы хотим отметить то, что эти соотношения вносят в любой винный погреб частичное упорядочение с точки зрения математика.
Закодируем сорта вин следующим образом:
Тогда система отношений порядка примет вид:
1<2, 2<3, 4<5, 1<4, 1<5, 2<4, 2<5, 4<3, 5<3,
а программа топологической сортировки выдаст следующий результат:
Hо так как не принято подавать за обедом более четырех вин, а шампанское в нашем перечне сортов вин отсутствует, то возможны лишь следующие варианты:
Цель топологической сортировки - преобразовать частичный порядок в
линейный. Графически это означает расположить вершины графа в ряд так, чтобы все стрелки были направлены вправо. Реализация в программной среде с++ алгоритма одного из возможных преобразований частичного порядка в линейный приведен в приложении 1.
— Топологическая сортировка применима в разных отраслях:
— Алгоритмы топологической сортировки достаточно просты и понятны, также легко реализуемы в программной среде.
1. Кнут Д. Искусство программирования Т. 1. Основные алгоритмы. - М.: Вильямс, 2000, - 736с.
2. Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1983,-406с.
3. Кофман А., Фор Р. Займемся исследованием операций. - М.: Мир, 1966, - 262с.
4. Кнут Д. Искусство программирования Т. 3. Сортировка и поиск. - М.: Вильямс, 2000.
5. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.:Вильямс, 2000 - 384 с.
6. Окулов С.М. Программирование в алгоритмах. М.: Лаборатория базовых знаний, 2002.-341 с.
7. Седжвик Р. Фундаментальные алгоритмы на С++/Алгоритмы на графах- К.:Диасофт, 2002. - 496 с.
8. Седжвик Р. Фундаментальные алгоритмы на С++/Анализ/Структуры данных/Сортировка/Поиск - К.:Диасофт, 2001. - 688с.
9. Бакнелл Дж. Фундаментальные алгоритмы и структуры данных в Delphi. - СПб.: Диасофт, 2003. - 560 с.
10. Белоусов А.И., Ткачев С.Б., Дискретная математика Москва, 2004 - 743с.
Алгоритмы сортировки методами простых вставок и пузырька. Зависимость среднего времени сортировки от числа сортируемых элементов. Функции, осуществляющие сортировку любого количества элементов методом простых вставок, на основе сортировки таблицы адресов. курсовая работа [557,1 K], добавлен 26.05.2010
Обработка массивов элементов любого типа как главное назначение алгоритмов сортировки. Анализ наиболее используемых алгоритмов сортировки: пузырьком, выбором, вставками, методом Шелла и быстрой сортировкой. Основные требования к алгоритмам сортировки. реферат [189,8 K], добавлен 06.12.2014
Разработка программы для осуществления сортировки данных методами "Выбора" с использованием языка C# и Visual Studio 2012. Плавный метод сортировки. Основные фазы сортировки во внутреннем представлении пирамиды. Программа сортировки методами выбора. курсовая работа [637,6 K], добавлен 29.11.2014
Изучение алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Отличительные черты сортировки включением, выбором, разделением, сортировки Шелла, обменной сортировки. Сравнение методов: плюсы и минусы. курсовая работа [203,8 K], добавлен 03.12.2010
Исследование основных особенностей алгоритмов быстрой и поразрядной сортировки данных. Построение графиков зависимости времени сортировки от количества элементов в файле и от степени перемешенности элементов. Описания сортировки чисел и строковых данных. лабораторная работа [1,2 M], добавлен 23.07.2012
Анализ основных алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Сортировка пузырьком, методами вставок, выбора, методом Шелла, быстрая сортировка. Операция разделения массива внутренней сортировки. курсовая работа [161,7 K], добавлен 17.12.2015
Методы реализации алгоритмов сортировки и алгоритмов поиска на языках программирования высокого уровня. Программирование алгоритмов сортировки и поиска в рамках создаваемого программного средства на языке Delphi. Создание руководства пользователя. курсовая работа [1,7 M], добавлен 16.04.2012
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Исследование алгоритмов топологической сортировки курсовая работа. Программирование, компьютеры и кибернетика.
Реферат по теме Діловий протокол
Реферат по теме Делегативная демократия
Дипломная работа по теме Разработка инвестиционного проекта (на примере ОАО 'Урейский угольный разрез')
Бюджетная Система Рф Эссе 2022 Скачать
Реферат: Внутрішнє та зовнішнє середовище організації
Дипломная Работа На Тему Анализ Использования Сырьевых Ресурсов И Пути Их Улучшения В Производстве Готовой Продукции (На Примере Цоф "Карагандинская")
Дипломная работа: Педагогическое значение памяти для процесса совершенствования лексических навыков диалогической речи 3
Контрольная работа по теме Расчет дымовой трубы
Реферат по теме Менеджмент моей фирмы
Анализ Почвы И Воды Практическая Работа
Дипломная работа по теме Основные направления развития физической культуры и спорта в субъектах Российской Федерации (на примере Новосибирской области)
Магистерская Диссертация Робототехника
Тема Эссе По Экономике Егэ
Аналитические Процедуры Маркетинговых Исследований Курсовая Работа
Контрольная работа по теме Термические методы и средства обезвреживания, переработки и утилизации нефтесодержащих отходов по технологии EX SITU
Курсовая работа по теме Социально-психологические особенности создания семьи в юношеском возрасте
Курсовая работа по теме Карелия – как природный территориальный комплекс
Реферат: The Father The Son And The Holy
Курсовая работа по теме Рыночный социализм Л. Абалкина
Реферат: Статистика цен 3
Демографическое положение Москвы - География и экономическая география презентация
Древний Рим - История и исторические личности презентация
Право "Европейского Союза" - Государство и право контрольная работа