Навигация
Алгоритмы сортировки, поиска длиннейшего пути во взвешенном графе и поиска покрытия, близкого к кратчайшему
32842
знака
5
таблиц
1
изображение
Введение
Теория алгоритмов и практика их построения и анализа является концептуальной основой разнообразных процессов обработки информации. В настоящее время теория алгоритмов образует теоретический фундамент вычислительных наук. Применение теории алгоритмов осуществляется как в использовании самих результатов (особенно это касается использования разработанных алгоритмов), так и в обнаружении новых понятий и уточнении старых. С ее помощью проясняются такие понятия как доказуемость, эффективность, разрешимость, перечислимость и другие.
Фактически, алгоритм – это точно определенная (однозначная) последовательность простых (элементарных) действий, обеспечивающих решение любой задачи из некоторого класса, т.е. такой набор инструкций, который можно реализовать чисто механически, вне зависимости от умственных способностей и возможностей исполнителя.
Как заметил Кнут: «Алгоритм должен быть определен настолько четко, чтобы его указаниям мог следовать даже компьютер».
Эффективность алгоритма определяется анализом, который должен дать четкое представление, во-первых, о емкостной и, во-вторых, о временной сложности процесса.
Речь идет о размерах памяти, в которой предстоит размещать все данные, участвующие в вычислительном процессе (естественно, к ним относятся входные наборы, промежуточная и выходная информация), а также физических ресурсах, затраченных исполнителем.
В курсовой работе представлены различные подходы и методы использования алгоритмов, приведены оценки сложностей алгоритмов, реализации математических задач с помощью алгоритмов. Проведена краткая характеристика используемых структур данных, эффективность их применения в данной задаче
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.
Похожие работы
... 6) + 1 =(509 mod 6) + 1 = 5 + 1=6; Алгоритм на графах: поиск кратчайшего пути. 3) (Y mod 5) + 1 =(509 mod 5) +1 =4 + 1 = 5; Алгоритм сортировки: сортировка-шейкер. 2 АЛГОРИТМ СОРТИРОВКИ: СОРТИРОВКА ШЕЙКЕР 2.1 Математическое описание задачи Сортировка – это перестановка элементов некоторого множества в заданном порядке при некоторой упорядочивающей функцию. Сортировка используется для ...
... распределения материальных благ и развития промышленного производства (сельского хозяйства, здравоохранения, связи и т. п.). Рис. 8.3. Структура системы управления общественным производством В реализации задачи инновационный менеджмент занимает специфическую и важную роль в установлении критериев и путей развития. 1 – Сбор данных и выделение ошибок. 2 – Анализ последствий ...
... телеги, микропроцессорные системы и т.д. В данном дипломном проекте поставлена задача оптимизировать сборку телеги, а также выявить экономический эффект за счет инноваций технологии и экономии ресурсов. Рассмотрим основные составляющие телеги: - Полка ТМ.201.01.03 – 24 шт. – Лист Б-О-ПН-2,0 ГОСТ 19903-74/12Х18Н10Т ГОСТ 5582-75; - Заглушка ТМ.201.01.09 – ...
... руководителя. Большое внимание следует уделять мотивации управленческого труда. 56. Организационно-распорядительные методы управления (Или административные). С их помощью осуществляются регулирующие функции гос-ва. Основаны на исполнении обязательных предписаний и рекомендаций, позволяют оперативно воздействовать на ход событий в процессе упр-я, ср-во волевого и конкретного воздействия ( ...
0 комментариев