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

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

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

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

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

Теоретическая часть

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

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

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

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

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

Алгоритм характеризуется следующими свойствами: дискретностью, массовостью, определенностью, результативностью, формальностью.

Дискретность (разрывность — противоположно непрерывности) — это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий.

Массовость — применимость алгоритма ко всем задачам рассматриваемого типа, при любых исходных данных.

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

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

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

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

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

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

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

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

Циклическая структура, называемая , повторением, содержит некоторую последовательность действий, выполняемых многократно. Такая структура содержит несколько типовых блоков. Тело цикла – та последовательность действий, которая выполняется многократно. Начальные присвоения – задание начальных значений тем переменным, которые используются в теле цикла. Различают 2 типа цикла «ДО» и «Пока». Цикл «до» применяется при необходимости выполнить какие-либо действия несколько раз до тех пор, пока выполняется некоторое условие. Цикл «Пока» - проверка условия выполняется до выполнения цикла.

Алгоритмизация задач.

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

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

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

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

Существуют следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

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

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

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

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

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

Рассмотрим некоторые основные конструкции, использующиеся для построения блок-схем.

Блок, характеризующий начало/конец алгоритма (для

Начало

Конец

подпрограмм - вызов/возврат):

<Действие>

Блок — процесс, предназначенный для описания

отдельных действий:

Блок — предопределенный процесс, предназначенный для обращения к _______________________________________________________________________________________________________________________________вспомогательным алгоритмам (подпрограммам):

Блок — ввода/вывода с неопределенного носителя:

Блок - ввод с клавиатуры:

Блок — вывод на монитор:

Блок — вывод на печатающее устройство:

Блок — решение (проверка условия или условный блок):

Нет Да

<тело цикла>

Блок, описывающий цикл с параметром:

Блок — границы цикла, описывающий циклические

<тело цикла>

процессы типа: «цикл с предусловием», «цикл

с постусловием»:

Соединительные блоки:

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

Программа — описание структуры алгоритма на языке алгоритмического программирования.

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

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

1.4.1 Линейная алгоритмическая конструкция

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

Линейные вычислительные процессы имеют место, например, при вычислении арифметических выражений, когда имеются конкретные числовые данные и над ними выполняются соответствующие условию задачи действия. На рисунке 1 показан пример линейного алгоритма, определяющего процесс вычисления арифметического выражения у=(b2-ас):(а+с).

Рисунок 1 – Линейный алгоритм

1.4.2 Разветвляющаяся алгоритмическая конструкция

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

Условие

Действие 2

Действие 1

Ложь (Нет) Истина (Да)

Рисунок 2 - Полное ветвление

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

Условие

Действия

Истина (Да)

Ложь (Нет)

Рисунок 3 - Неполное ветвление

В зависимости от типа и числа проверяемых условий различают:

- ветвление с простым условием (условие - выражение отношения);

- ветвление с составным условием (условие - логическое выражение);

- сложное ветвление (несколько условий).