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

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

Целью курсовой работы является понять, как правильно написать тот или иной алгоритм.

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

Вся информация в данной курсовой взята из надежных источников таких как: «Основы алгоритмизации и программирования» Г.Р. Кадырова (Ульяновский государственный университет); «Основы алгоритмизации в информационных системах» М.П. Белов(Северо-западный государственный заочный технический университет); «Программирование и основы алгоритмизации» А.Г. Аузяк, Ю.А. Богомолов, А.И. Маликов, Б.А. Старостин (Казанский национальный исследовательский технический университет им. А.Н. Туполева – КАИ).

Глава 1 Алгоритм. Общие понятия

1.1 Понятие алгоритма

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

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

Алгоритм – четкое описание последовательности действий, которые необходимо выполнить для получения результата. [1]

Алгоритм - это точное, сформулированное на определенном языке, конечное описание того или иного способа действия, основанного на применении исполнимых элементарных однозначно трактуемых шагов. [2]

Алгоритм применительно к ПК – точное предписание, т.е. набор операций и правил их чередования, при помощи которого, начиная с некоторых исходных данных, можно решить задачу фиксированного типа. Команда алгоритма – предписание о выполнении отдельного законченного действия исполнителя. [3]

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

1.2 Свойства алгоритмов

Алгоритмы обладают целым рядом свойств:

1. Определенность – каждое правило алгоритма должно быть четким, однозначным. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.

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

3. Результативность – либо завершение решения задачи после выполнения алгоритма, либо вывод о невозможности продолжения решения по какой-либо из причин, т.е. алгоритм должен обеспечивать возможность получения результата после конечного числа шагов.

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

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

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

Временные характеристики алгоритма определяют длительность решения или временную сложность.

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

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

Для сложных задач эта характеристика имеет большое значение, т.к. ее изменение значительно сильнее влияет на время решения, чем изменение быстродействия ПК.

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

Объем текста алгоритма определяется количеством операторов, использованных для записи алгоритма.

Объем внутренней и внешней памяти необходимой для хранения данных и программ при использовании данного алгоритма определяется на основании расчетов или опытным путем. При недостатке памяти носителей информации используется сегментация программ.

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

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

1.4. Способы описания алгоритмов

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

К средствам описания алгоритмов относятся следующие основные способы их представления: словесный; графический; псевдокоды; программный.

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

Словесный способ записи алгоритмов представляет собой последовательное описание основных этапов обработки данных и задается в произвольном изложении на естественном языке. [3] Данный способ получил значительно меньшее распространение из-за его многословности и отсутствия наглядности.

Рассмотрим пример на алгоритме нахождение максимального из двух значений:

Определим форматы переменных x, y, z, где x и y – значения для сравнения, z – переменная для хранения максимального значения;

Получим два значения чисел x и y для сравнения;

Сравним x и y.

Если x меньше y, значит большее число y.

Поместим в переменную z значение y.

Если x не меньше (больше) y, значит большее число x.

Поместим в переменную z значение x.

Такой способ записи удобно использовать на начальном этапе алгоритмизации задачи. К недостаткам словесного способа записи можно отнести следующее:

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

Поэтому словесный способ записи алгоритмов не имеет широкого распространения.

1.4.2. Графический способ описания алгоритмов

Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным. Иначе такой способ называют блок-схемой.

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

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

Символ «Решение» используется для обозначения переходов управления по условию. В каждом блоке решения должны быть указаны вопрос, решение, условие или сравнение, которые он определяет. Стрелки, выходящие из блока решения, должны быть помечены соответствующими ответами (например, ДА, НЕТ), так чтобы были учтены все возможные ответы.

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

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

Символ «Предопределенный процесс» используется для указания обращений к вспомогательным алгоритмам, выделенным автономно, в виде некоторого модуля; для обращений к библиотечным подпрограммам; для обозначения части алгоритма, не зависящей от основной схемы управления; для обозначения определенной части алгоритма, которая будет кодироваться вместе со всем алгоритмом, но в документации представлено отдельной схемой. Если такая часть алгоритма представляет собой итерационный процесс, то в соответствующий ей блок вызова необходимо включить описания условий окончания цикла. По мнению некоторых специалистов, использование более одной схемы для одного алгоритма затрудняет его понимание. Однако практика показывает, что удобнее всего применять схемы алгоритмов, разбитые в соответствии с уровнями абстракции.

Символ «Документ» предназначен для ввода – вывода данных, носителем которых служит бумага.

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

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