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

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

Основы алгоритмизации.

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

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

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

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

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

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

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

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

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

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

Словесное описание – структура алгоритма на естественном языке. Например, инструкции по эксплуатации электроприборов. Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном языке. Данный способ описания алгоритмов не нашел широкого распространения.

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

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

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

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

№	Название блока	Графическое изображение блока
	Блок, характеризующий начало/конец алгоритма (для подпрограмм – вызов/возврат):
	Блок – процесс, предназначенный для описания отдельных действий:
	Блок – предопределенный процесс, предназначенный для обращения к вспомогательным алгоритмам (подпрограммам):
	Блок – ввода/вывода с неопределенного носителя:
	Блок – ввод с клавиатуры:
	Блок – вывод на монитор:
	Блок – вывод на печатающее устройство:
	Блок – решение (проверка условия или условный блок):
	Блок, описывающий цикл с параметром:
	Блок – границы цикла, описывающий циклические процессы типа «цикл с предусловием», «цикл с постусловием»:
	Соединительные блоки:

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

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

1.Линейная структура:

Линейной называется алгоритмическая конструкция, реализованная в виде последовательности действий (шагов), в которой каждое действие алгоритма выполняется ровно 1 раз, причем после каждого i-ого действия выполняется (i+1)-ое действие, если i-ое действие не конец алгоритма.

2.Разветвляющеяся структура:

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

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

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

3.Циклическая структура:

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

Рассмотрим три основных типа циклических конструкций: цикл с параметром (называется арифметическим циклом), цикл с предусловием и цикл с постусловием (последние два называются итерационными).

Арифметический цикл. В арифметическом цикле число шагов (повторений) однозначно определяется правилом изменения параметра, которое задается с помощью начального (N) и конечного (К) значений параметра, а так же шагом (h) его изменения. На первом шаге цикла значение параметра равно N, на втором – N+h, на третьем – N+2h и т.д. На последнем шаге цикла значение параметра не превышает К, но такое, что дальнейшее его изменение приведет к значению превышающему К.

Цикл с предусловием. Количество шагов цикла заранее не определено и зависит от входных данных задачи. В данной циклической структуре сначала проверяется значение условного выражения (условия) перед выполнением очередного шага цикла. Если значение условного выражения истинно, то выполняется тело цикла. После чего управление вновь передается проверке условия и т.д. Данные действия повторяются до тех пор, пока условное выражение не примет значения ЛОЖЬ. При первом же несоблюдении условия цикл завершается.

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

условный блок блок управления

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

условный блок блок управления

4. Рекурсивная структура:

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

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

Дата добавления: 2014-01-06