Тема: Алгоритмы поиска и сортировки. Учебная работа № 430439

Учебная работа № 430439. Тема: Алгоритмы поиска и сортировки

Выдержка из похожей работы

…….

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

…..го класса, т.е. такой набор
инструкций, который можно реализовать чисто механически, вне зависимости от
умственных способностей и возможностей исполнителя.

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

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

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

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

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 Переносим элемент х = а из входной
подпоследовательности в готовую так, чтобы готова…