Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования(Понятие и свойства алгоритма).pdf

Введение

Для решения многих задач и достижения целей мы составляем «план действий». Разбивая выполнение задания на этапы, мы оптимизируем наше время и силы, начинаем лучше понимать, чего мы хотим сделать и каким образом мы должны это сделать. Конечно, этот «план» должен быть записан на понятном для исполнителя языке.

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

Цель курсовой работы – сравнить основные структуры алгоритмов и определить сферу их применения.

Исходя из цели, можно выделить следующие задачи:

• Раскрыть понятие алгоритма
• Выделить свойства алгоритма
• Определить основные структуры алгоритмов, провести их сравнительный анализ
• Выяснить сферу и способ применения основных структур алгоритмов для решения различных задач в программировании

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

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

В своей работе я использовал учебно-методические материалы таких авторов, как М.П. Белов (СЗТУ), И.А. Селиванова (УралГАХА), А.А. Ключарев (СПбГУАП). В них подробно и понятно раскрывается понятие алгоритма, его основные свойства, приводятся примеры структур алгоритмов и анализ их эффективности.

Глава 1. Понятие и свойства алгоритма

---

Термин алгоритм происходит от имени узбекского ученого IX века Аль-Хорезми, который в своем труде «Арифметический трактат», переведенном в XII веке с арабского на латынь, изложил правила арифметических действий над числами в позиционной десятичной системе счисления. Эти правила назывались алгоритмами.

Многие правила, инструкции, записанные в различных документах и представляющие собой подробнейшие указания, годные во всевозможных ситуациях, также можно отнести к алгоритмам.^[1]

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

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

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

Итак, алгоритм – это понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение указанной цели или на решение поставленной задачи.^[2]

В соответствии с определением можно выделить следующие свойства алгоритма, отличающие его от любых предписаний и обеспечивающих автоматическое выполнение:

• Понятность для исполнителя – содержание предписания о выполнении только таких действий, которые входят в систему команд исполнителя, т.е. алгоритм должен быть задан с помощью таких указаний, которые исполнитель может воспринимать и выполнять по ним требуемые действия (операции).
• Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное исполнение простых (или ранее определенных) шагов (этапов). Ими могут служить пункты инструкции, ввод различных типов данных с устройств ввода – текстовых, графических, аудиовизуальных, операторы языков программирования.
• Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Это свойство обеспечивает выполнение алгоритма механически, не требуя никаких дополнительных указаний или сведений о решаемой задаче.
• Результативность – алгоритм должен приводить к решению задачи за конечное число шагов. При этом в некоторых случаях число шагов устанавливается вручную и влияет на точность результата, а иногда число шагов заранее неизвестно, например, при выполнении алгоритма до остановки пользователем по достижении требуемого результата. В остальных случаях алгоритм может производить вывод о невозможности продолжения решения задачи по какой-либо из причин, что тоже является результатом.
• Массовость – алгоритм решения задачи производится в общем виде, т.е. его можно будет применять дня некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.^[3]

---

Для решения любой задачи нам понадобятся начальные (входные) и конечные (выходные, результативные) данные. Они могут быть отнесены к одному из двух типов: основному (простому), форма представления которого определяется архитектурой ЭВМ, или сложному, конструируемому пользователем для решения конкретных задач.

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

Для записи алгоритмов применяются следующие способы записи:

• Словесный – в виде, например, нумерованного списка, на языке, понятном исполнителю.
• Графический (Блок-схема) – это вариант графической записи алгоритма, применяемый на этапе алгоритмизации задачи, выполняемой на программируемом вычислительном устройстве.
• Псевдокоды
• Программный^[4]

Основным способом записи алгоритмов в программировании является блок-схема. В ней каждому типу действий соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий. Для начертания этих схем используется набор символов, определяемых ГОСТ 19.701-90 (ИСО 5807-85) «Единая система программной документации». Наиболее часто употребляемые символы приведены в таблице 1. ^[5]

Таблица 1

Название символа	Обозначение	Пояснение
Процесс		Вычислительное действие или последовательность вычислительных действий
Решение	Условие нет да	Проверка условий
Модификация	i = 1, 20, 2	Начало цикла
Предопределенный процесс		Вычисления по подпрограмме, стандартной подпрограмме
Документ	Печать x,y	Вывод, печать результатов на бумаге
Ввод-вывод	Ввод переменных	Ввод-вывод данных в общем виде
Соединитель	или	Разрыв линий потока
Пуск, остановка		Начало, конец, остановка, вход и выход в подпрограммах
Комментарий	Текст комментария	Пояснения, содержание подпрограмм, формулы[6]

---

Существует три основных структуры алгоритмов:

• Линейная структура - предполагает выполнение действий последовательно. Алгоритм с такой структурой не зависит от условий и происходит единожды.
• Разветвляющаяся структура – имеет логическое условие, от которого зависит, по какой ветви будет происходить в дальнейшем вычислительный процесс. Структура ветвление существует в четырех основных вариантах: если – то; если – то – иначе; выбор; выбор – иначе. Оператор выбора используется в тех случаях, когда возникает необходимость выбора альтернативы из трех возможностей и более.
• Циклическая структура – содержит многократно выполняемые участки, называемые циклами. Эта структура имеет особое значение для построения алгоритмов, т.к. только на их основе можно добиться компактной записи алгоритмов, требующих выполнения большого числа действий. При выполнении этого оператора серия, включающая одну или несколько команд, повторяется несколько раз подряд до тех пор, пока условие соблюдается. Как только условие нарушается, выполнение серии прекращается. Если условие изначально неверно, то серия не выполняется.^[7]

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

При использовании различных структур в одном алгоритме, мы получим смешанную структуру.

Алгоритм, в состав которого входит итерационный цикл, называется итерационным алгоритмом. Итерационные алгоритмы используются при реализации итерационных численных методов.

Также существуют структуры вложенных циклов – когда для решения задачи требуется организовать внутренний цикл для повторения некоторой последовательности операторов. Вложенные циклы используются, например, при работе с двумерными массивами, для удобного перебора элементов в определенном порядке. Количество вложенных циклов может быть различным. ^[8]

Таблица 2

Основные структуры алгоритмов

Линейная структура	Ветвящаяся структура (если)	Циклическая структура (параметрический цикл)

---

По основной характеристике все три структуры одинаковы – все они имеют один вход и один выход.

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

Стоит сказать, что ветвящаяся структура может реализовать циклическую через условие и прямые переходы. Такие алгоритмы будут не оптимальны с точки зрения потребления ресурсов ПК и объемны, но, тем не менее, будут работать.

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

Примеры трех основных структур, записанных в виде блок-схемы, представлены в таблице 2.

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

Глава 2. Сравнительный анализ основных структур алгоритмов

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

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

---