Алгоритмы сортировки, поиска длиннейшего пути во взвешенном графе и поиска покрытия, близкого к кратчайшему

Введение

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

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

Как заметил Кнут: «Алгоритм должен быть определен настолько четко, чтобы его указаниям мог следовать даже компьютер».

Эффективность алгоритма определяется анализом, который должен дать четкое представление, во-первых, о емкостной и, во-вторых, о временной сложности процесса.

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

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

1. Выбор варианта задания

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

Y mod 4 + 1 - алгоритмы покрытия;

Y mod 6 + 1 - алгоритмы на графах;

Y mod 5 + 1 - алгоритмы сортировки.

Мой номер по журнальному списку равен 5, группа АЕ-035. Поэтому имеем Y=5+5*100=505. Получаем такие варианты:

А = 505 mod 4 +1 = 2;

B = 505 mod 6 +1 = 2;

C = 505 mod 5 +1 = 1.

Таким образом, имеем следующие алгоритмы: покрытия - по методу «построение одного кратчайшего покрытия», на графах - нахождение самого длинного пути, сортировки - простыми включениями.

Постановка задачи. Необходимо ввести таблицу покрытия. Алгоритм должен найти покрытие, близкое к кратчайшему.

2. Алгоритм сортировки

2.1 Математическое описание задачи и методов её решения

В общем смысле сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Её цель - облегчить последующий поиск элементов в таком отсортированном множестве.

Если у нас есть элементы а1, …, аn, то сортировка есть перестановка этих элементов в массив ак1, …, акn, где при некоторой упорядочивающей функции f выполняются отношения f(ak1)?f(ak2)?…?f(akn).

Метод сортировки называется устойчивым, если в её процессе относительное расположение элементов с равными ключами не изменяется.

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

2.2 Словесное описание алгоритма и его работы

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

Элементы мысленно делятся на уже «готовую» последовательность а1…а2 и исходную последовательность а1…аn. При каждом шаге, начиная с i=2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется в нужное место.

Словесное описание алгоритма сортировки простыми включениями:

0. В готовую подпоследовательность записывается а1, во входную - а2,….аn.

1. i = 2.

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

а) расширяем готовую подпоследовательность слева: а0 = х - барьер;

б) просматривая элементы готовой подпоследовательности слева направо, находим такой номер j что и ai <=x < ai+1;

в) если j=j-1, то переходим к пункту г), иначе расширяем готовую
подпоследовательность справа, сдвигая ее элементы, начиная с ai вправо;

г) ai+1 = x

д) i = i + 1. Если i <=n, то переходим к п. 2, иначе сортировка заканчивается.

Процесс может закончиться при двух различных условиях: 1) найден элемент с ключом, меньшим, чем ключ x; 2) достигнут конец готовой последовательности. Получается цикл с двумя условиями. Поэтому для некоторого улучшения быстродействия применяется барьер - a[0] присваивается значение ключа x.

Проанализируем этот алгоритм. Число сравнений (Сi) при i-м просеивании самое большее равно i-1, самое меньшее - 1; если предположить, что все перестановки из n ключей равновероятны, то среднее число сравнения - i/2. Число же пересылок (присваиваний элементов) Mi равно Сi+2 (включая барьер). Поэтому общее число сравнений и число пересылок таковы:

Сmin=n-1, Mmin=3*(n-1)

Cave=(n2+n-2)/4, Mave=(n2+*n-10)/4,

Cmax=(n2+n-4)/4, Mmax=(n2+3n-4)/2.

Минимальные оценки в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки - когда они первоначально расположены в обратном порядке. Очевидно, что приведенный алгоритм описывает метод устойчивой сортировки (см. [1]).

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

Словесное описание алгоритма сортировки с двоичным включением:

0. В готовую подпоследовательность записывается а1, во входную а2,….аn.

1. i = 2

2 Переносим элемент х=аi из входной подпоследовательности в готовую так, чтобы последняя осталась под сортированной. Для этого:

а) организуем бинарный поиск места включения х в готовую подпоследовательность: находим срединный элемент готовой подпоследовательности - am, где m =] i/2 (, и сравниваем его с х. Если am > х то ведем далее поиск в левой половине готовой подпоследовательности, т.е. опять находим срединный элемент и сравниваем его с х и т.д., пока не найдем номер j такой, что ai <=x < ai+1, иначе аналогично ведем поиск в правой половине готовой подпоследовательности;

б) если j=j-1, то переходим к пункту в), иначе расширяем готовую подпоследовательность справа, сдвигая ее элементы, начиная с ai вправо;

в) ai+1 = х

3. i=i+1. Если i <= n, то переходим к п. 2, иначе сортировка заканчивается.

Деление пополам производится i*log2i. Число сравнений практически не зависит от начального порядка элементов. В нижней части последовательности место включения отыскивается несколько быстрее, чем в верхней, поэтому предпочтительна ситуация, когда элементы немного упорядочены. Фактически, если элементы в обратном порядке, потребуется минимальное число сравнений, если уже упорядочены - максимальное:

C?n*log2(log2-log2e±0,5). Однако число пересылок так и остается порядка n2. И на самом деле сортировка уже упорядоченного массива потребует больше времени, чем метод с прямыми включениями (см. [1]).

2.3 Выбор структур данных

Алгоритмы сортировки очень сильно зависят от структуры данных, так что выделяют два класса: сортировку массивов и сортировку последовательностей (файлов). В данной работе рассматривается сортировка массивов. Тип данных «массив» удобен тем, что хранится во внутренней памяти и имеет случайный доступ к элементам, то есть более быстрый, чем у последовательности. Поэтому массивы целесообразно использовать для хранения небольших, часто используемых множеств.

Обычно упорядочивающая функция не вычисляется по какому-либо правилу, а хранится как явная компонента (поле) каждого элемента. Её значение называется ключом элемента. Поэтому для представления элемента хорошо подходит тип «запись», что на языке «Pascal» выглядит следующим образом:

TYPE item = RECORD key: INTEGER;

{здесь описаны другие компоненты}

END;

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

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

n - количество элементов массива;

A - сортируемый массив;

i - переменная цикла (по исходной последовательности);

j - переменная внутреннего цикла (по готовой последовательности);

x - i-й ключ (переносимый элемент).

Все переменные целого типа.

2.4 Описание схемы алгоритма

Блок-схема данного алгоритма изображена на рис. 2 в Приложении.

Алгоритм работает следующим образом. Сначала вводятся исходные данные: длина массива и его элементы (блоки 1, 2), затем организуется цикл по всей длине массива, во время которого ставится «барьер» (блок 3) и проводится сравнение i-го ключа с элементами готовой последовательности (стоящими раньше него). При этом все элементы, большие этого ключа (это условие проверяется в блоке 4), сдвигаются вправо (блок 5). Это происходит до тех пор, пока не встретится элемент меньший либо равный данному ключу (по крайней мере барьеру). Тогда i-й ключ вставляется в эту позицию (блок 6).

2.5 Контрольные примеры решения задачи с помощью алгоритма сортировки простыми включениями

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

Пусть задан такой массив из восьми элементов: (32,43,2,30,82,8,5,52) (см. Таб. 1).

Страницы: 1, 2, 3