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

Введение

 

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

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

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

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

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

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

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.

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

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

 

 

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

 

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

 

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

Если у нас есть элементы а_1, …, а_n, то сортировка есть перестановка этих элементов в массив а_к1, …, а_кn, где при некоторой упорядочивающей функции f выполняются отношения f(a_k1)≤f(a_k2)≤…≤f(a_kn).

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

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

 

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

 

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

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

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

0. В готовую подпоследовательность записывается а₁, во входную – а₂,….а_n.

1. i = 2.

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

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

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

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

г) a_i+1 = x

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

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

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

 

С_min=n-1,                           M_min=3*(n-1)

C_ave=(n²+n-2)/4,                 M_ave=(n²+*n-10)/4,

C_max=(n²+n-4)/4,                M_max=(n²+3n-4)/2.

 

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

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

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

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

1. i = 2

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

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

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

в) a_i+1 = х

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

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

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

 

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

 

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

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

TYPE item = RECORD key: INTEGER;

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

END;

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

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

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

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

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

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

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

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