V Международная студенческая научная конференция Студенческий научный форум - 2013

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

Раздел «Алгоритмы сортировки» является традиционным в курсах «Программирование», «Алгоритмы и структуры данных». Под сортировкой понимают процесс упорядочения данных по некоторому признаку. При изучении данного раздела студенты оттачивают свои навыки программирования, сортируя обычно массивы данных по убыванию или возрастанию, используя известные методы сортировки обменом, простым выбором, вставками, быстрые сортировки и т.п.

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

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

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

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

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

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

Метод топологической сортировки был впервые опубликован Каном (A.B.Kahn, 1962). Сам факт возможности топологической сортировки был доказан в статье Шпильрайна (E.Szpilrajn, 1930).

Рассмотрим пример с точками на плоскости, дающий удобную визуализацию задачи топологической сортировки.

Пусть дано конечное множество точек P_i с координатами (x_i, y_i). Введем для точек отношение

Код для цитирования: Скопировать