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

Содержание

Введение

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

2 Алгоритм сортировки Шейкер

2.1 Математическое описание задачи

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

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

2.4 Контрольный пример

3 Алгоритм покрытия: построение одного кратчайшего покрытия

3.1 Математическое описание задачи

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

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

3.4 Контрольный пример

4 Алгоритм на графах: нахождение кратчайшего пути

4.1 Математическое описание задачи

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

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

4.4 Контрольный пример

Заключение

Перечень литературы

Введение

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

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

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

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

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

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

1 ВЫБОР ВАРИАНТА

Номер варианта определяется нахождением остатка от целочисленного деления числа У, которое является суммой числа Х и номера по списку в журнале. Номер по списку в журнале N=9. Таким образом:

X=Nгр*100=5*100=500;

Y=N+X=9+500=509.

По формулам нахожу соответствующие виды алгоритмов.

1) (Ymod 4) + 1 =(509 mod 4) + 1=1 + 1= 2; Алгоритм покрытия: построение одного кратчайшего покрытия.

2) (Ymod 6) + 1 =(509 mod 6) + 1 = 5 + 1=6; Алгоритм на графах: поиск кратчайшего пути.

3) (Ymod 5) + 1 =(509 mod 5) +1 =4 + 1 = 5; Алгоритм сортировки: сортировка-шейкер.

2 АЛГОРИТМ СОРТИРОВКИ: СОРТИРОВКА ШЕЙКЕР

2.1 Математическое описание задачи

Сортировка – это перестановка элементов некоторого множества в заданном порядке при некоторой упорядочивающей функцию.

Сортировка используется для облегчения поиска элемента в таком отсортированном множестве.

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

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

Сортировка Шейкер является усовершенствованной сортировкой методом пузырька. Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.(см. Таб. 1)

Таблица 1

i=1	2	3	4	5	6	7	8
44	06	06	06	06	06	06	06
55	44	12	12	12	12	12	12
12	55	44	18	18	18	18	18
42	12	55	44	42	42	42	42
94	42	18	55	44	44	44	44
18	94	42	42	55	55	55	55
06	18	94	94	67	67	67	67
67	67	67	67	94	94	94	94

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

Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать