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

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

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

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

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

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

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

Основные свойства алгоритмов:

дискретность - алгоритм должен представлять процесс решения задачи как последовательное исполнение простых (или ранее определенных) шагов (этапов);
определенность - каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Данное свойство обеспечивает выполнение алгоритма механически не требует никаких дополнительных указаний или сведений о решаемой задаче;
результативность (конечность) - алгоритм должен приводить к решению задачи за конечное число шагов;
массовость - алгоритм решения задачи производится в общем виде, т. е. его можно будет применять для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из определенной области, которая называется областью применимости алгоритма /1, с.6/.

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

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

Свойства алгоритма – это набор свойств, отличающих алгоритм от любых предписаний и обеспечивающих автоматическое исполнение алгоритма.

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

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

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

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

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

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

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

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

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

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

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

Для сложных задач эта характеристика имеет большое значение, так как ее изменение значительно сильнее влияет на время решения, чем изменение быстродействия персонального компьютера. Например, при зависимости f(n) = 2n увеличение производительности в 10 раз увеличивает размерность задачи, решаемой за то же время, всего на 15%.

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

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

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

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

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

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

1.3 Способы записи алгоритмов

1) Словесный способ – запись алгоритмов представляет собой последовательное описание основных этапов обработки данных и задается в произвольном изложении на естественном языке.

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

К недостаткам словесного способа записи алгоритмов можно отнести следующее:

А) полное подробное словесное описание алгоритма получается слишком большим;

Б) естественный язык допускает неоднозначность толкования отдельных инструкций;

В) при переходе к этапу программирования требуется дополнительная работа по формализации алгоритма, так как словесное описание может быть понятно человеку, но не может быть понятно персональному компьютеру /2, с.10-11/.

2) Графический способ (блок-схема) – запись алгоритмов производится с помощью блоков, которые представляют собой геометрические фигуры.

Каждая фигура представляет собой какую-либо операцию или действие, а также процесс решения задачи.

Фигура называется блоком. Порядок выполнения этапов показывается стрелками, которые соединяют блоки.

Блоки размещаются сверху вниз или слева направо в зависимости от порядка их выполнения.

Обозначение блоков и их выполняемые функции «см. Приложение 1» /3, с.10/.

3) псевдокоды – полуформализованные описание алгоритмов на некотором условном алгоритмическом уровне, включает в себя язык программирования, общепринятые фразы и математические символы /1, с.6/.

1.4 Правила построения алгоритмов на языке блок-схем

1. Блок-схема всегда строится сверху вниз.

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

3. В блок-схеме должен быть хотя бы один путь из начала блок-схемы к любому элементу.

4. Должен быть хотя бы один путь от каждого элемента блок-схемы в конец блок-схемы.

в) Операторный способ (алгоритмический язык). Алгоритм – это задание для исполнителя. Исполнитель выполняет алгоритм, т. е. делает то, что написано в алгоритме. Если исполнитель точно выполнит то, что написано в алгоритме, то он получит результат.

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

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

Компьютер понимает машинный язык. Например, равенство 5*2=5+5 на машинном языке имеет вид: 00011110000011100001101100101010000110110000111000011100001011010001111000001110000110110010101100011110.

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

Для того чтобы человек и компьютер понимали друг друга, разработаны специальные языки для записи алгоритмов – алгоритмические языки. Самые известные алгоритмические языки – это Бейсик (Basic), Паскаль (Pascal), Фортран (Fortran).

В отличие от машинного языка, алгоритмический язык состоит из слов и символов, как естественный язык. Алгоритмический язык отличается от естественного языка тем, что в нем мало основных слов (обычно 30-40) и очень строгие правила составления предложений.

Служебные слова – основные слова алгоритмического языка.

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

Алгоритм, который записан на алгоритмическом языке, – это программа для компьютера.

Оператором называется каждое предложение в программе.

Например, можно написать программу решения квадратного уравнения ax 2 +bx+c=0 на компьютере. На алгоритмическом языке Бейсик эта программа будет выглядеть так:

REM РЕШЕНИЕ КВАДРАТНОГО УРАВНЕНИЯ

INPUT “введите а,b,c“; А,B,C

D=B-2 - 4*A*C

IF D<0 THEN “РЕШЕНИЙ НЕТ”

Y1=(-B+SQR(D))/(2*A):Y2=(-B-SQR(D))/(2*A)

PRINT “КОРНИ УРАВНЕНИЯ”;Y1,Y2 /3, с.11-12/.

1.5 Классификация алгоритмов

В зависимости от используемого вычислительного процесса различают следующие алгоритмы:

1) линейные алгоритмы – описывают линейный вычислительный процесс, этапы которого выполняются однократно и последовательно один за другим «см. Приложение 2»;

2) разветвляющийся алгоритм – реализация вычислительного процесса происходит по одному из нескольких заранее предусмотренных направлений. Направления, по которым может следовать вычислительный процесс, называются ветвями. Выбор конкретной ветви вычисления зависит от результатов проверки выполнения некоторого логического условия. Результатами данной проверки, если условие выполняется, является «истина» (да), при невыполнении условия «ложь» (нет) «см. Приложение 3»;

3) циклический алгоритм – этапы вычислительного процесса повторяются многократно. В зависимости от ограничения числа повторений выделяют циклы с известным числом повторений и циклы, число повторений которых заранее неизвестно /4, с.5-6/.

Выполняется циклический алгоритм так: сначала проверяется условие, если условие верно (истина), то выполняется тело цикла (действия или группа операторов) и, далее, изменяются значения параметра цикла и снова проверяется условие и т. д. На каком-то шаге условие не выполнится (ложь) и тогда происходит выход из цикла и продолжается выполнение программы /3, с.15/.