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

Слово «алгоритм» происходит от algorithm — латин­ского написания имени аль -Хорезми, под которым в сред­невековой Европе знали величайшего математика из Хо­резма (город в современном Узбекистане) Мухаммеда бен Мусу, жившего в 783—850 гг., который сформулировал правила выполнения четырех арифметических действий над многозначными числами.

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

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

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

2. Определенность. Каждая команда алгоритма долж­на быть четкой, однозначной и не оставлять места для произвола.

3. Результативность. Алгоритм должен приводить к решению поставленной задачи за конечное число шагов.

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

Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Созда­ние алгоритма, пусть даже самого простого, — процесс творческий. Он доступен исключительно живым суще­ствам, а долгое время считалось, что только человеку. Другое дело — реализация уже имеющегося алгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно, и не спосо­бен его понять. Такой субъект или объект принято назы­вать формальным исполнителем.

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

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

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

Первое правило — при построении алгоритма, прежде всего необходимо задать множество объектов, с которы­ми будет работать алгоритм. Формализованное (закоди­рованное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым на­бором начальных данных, которые называются входны­ми, и в результате работы выдает данные, называемые выходными. Таким образом, алгоритм преобразует вход­ные данные в выходные.

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

Практическая работа с алгоритмами (программирова­ние) начинается с реализации первых двух правил. В язы­ках программирования распределение памяти осуществ­ляется декларативными операторами ( опи­сания переменных).

Третье правило — дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Мно­жество шагов, из которых составлен алгоритм, конечно.

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

Пятое правило — сходимость (результативность). Ал­горитм должен завершать работу после конечного числа шагов. При этом необходимо указать, что считать резуль­татом работы алгоритма.

Виды алгоритмов

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

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

♦ гибкие алгоритмы:

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

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

♦ линейные алгоритмы— наборы команд (указаний), выполняемых последовательно во времени друг за другом;

♦ разветвляющиеся алгоритмы— алгоритмы, содер­жащие хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов;

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

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

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

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

1. Словесно-формульное описание(на естественном языке с использованием математических формул). Дан­ный способ записи алгоритма состоит из перечня действий (шагов), каждый из которых имеет порядковый номер. Алгоритм должен выполняться последовательно шаг за шагом. Если в тексте алгоритма написано «перейти к шагу с номером L», то это означает, что выполнение алгоритма продолжится с указанного шага с номером L. Словесное описание алгоритмов применяют при решении неслож­ных задач, но оно малопригодно для представления слож­ных алгоритмов из-за отсутствия наглядности.

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

3. Описание на каком-либо языке программирования (программа).

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

Программа — это форма представления алгоритма для исполнения его компьютером.

Блок схема

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

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

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

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

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

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

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

Символы блок-схем

Форма блока	Пояснение
	Блок “ввода-вывода”. Отображает данные.
	Отображает данные, хранящиеся в ЗУ с прямым доступом. Магнитный диск, гибкий диск.
	Распечатка, документ.
	Экран для визуального наблюдения. Дисплей.
	Процесс. Вычислительное действие или последовательность вычислительных действий.
	Предопределенный процесс. Вызов процедуры или функции пользователя
	Проверка условия.
	Цикл в начальном блоке – начальное условие, в конечном – условие завершения.
	. «Вход-выход» «Начало-Конец»
Форма блока	Пояснение
из стр	Переход к странице. Комментарий.
	Символ с полосой означает, что в этом же комплекте документации имеется более подробное представление.
	Отображает данные, хранящиеся в ОЗУ. ( Только в схеме работы программ и программных модулей)
	Ручной ввод. Данные, вводимые во время обработки с устройств (клавиатура, переключатель, световое перо, полоски со штрих - кодом)
	Память с последующим доступом
	Сохраненные данные
	Перфолента
	Логический оператор ИЛИ
	Магнитный диск.

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

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

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

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

Структуры алгоритмов

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

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

Рассмотрим составление схем алгоритмов:

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

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

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

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

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

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

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

Значение переменной величины может быть изменено с помощью команды присваивания, имеющей общий вид

< идентификатор > := < выражение >

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

функциональный блок:

Например, команда x:=1; означает, что переменной x присваивается значение 1, а команда y:=y+1; - что переменной y присваивается значение, которое на 1 больше ее прежнего значения.

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

ввод( x, y); означает, что исполнитель должен задать значения, которые должны быть присвоены переменным x и y.

Аналогичная команда вывода:

вывод( x, y); означает, что исполнитель должен выдать для обозрения значения величин x и y (отображение информации).

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

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

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

В общем виде команда следования может быть представлена так:

начало< действие > ; <действие > ; ... ; < действие > конец

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

В дальнейшем будет использоваться запись команд в столбец.

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

Команда следования:

Псевдокод	Паскаль
начало ввод(x); y:=x2+5; z:= Ö x2+y2 конец	BEGIN WRITELN('ЗАДАТЬ ЛЮБЫЕ ЗНАЧЕНИЯ Х И Y'); READLN(X,Y); Y:=SQR(X)+5; Z:=SQRT(X)+SQR(Y) END.

Схема команды следования:

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

На псевдокоде и Паскале эта команда в общем виде записывается так:

Псевдокод	Паскаль
если < условие> то<действие 1> иначе < действие 2> все	IF < логическое выражение > THEN <действие 1> ELSE < действие 2>;

Действия, указанные после служебных слов то и иначе, могут быть простыми или составными командами. При исполнении команды ветвления выполняется только одно из действий: если условие (логическое выражение) соблюдено, т.е. ИСТИНА, то выполняется действие 1, в противном случае - действие 2.

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

Рассмотрим вычисление значения y:

x² , при x<0

y =

x+1 , при x>=0

Схема команды ветвления:

На псевдокоде и Паскале команда ветвления для вычисления значения y будет иметь такой вид:

Псевдокод	Паскаль
если x>=0 то y:=x+1 иначеy:=x2 все	IF X>=0 THEN Y:=X+1 ELSE Y:=SQR(X) ;

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

Псевдокод	Паскаль
если x>=0 то начало y:=x; z:=x+y конец иначе y:=x2 все	IF X>=0 THEN BEGIN Y:=X; Z:=X+Y; END ELSE Y:=SQR(X) ;

В Паскале пара ключевых слов BEGIN END (операторные скобки) позволяют объединить группу операторов.

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

Псевдокод	Паскаль
если <условие> то < действие> все	IF < логическое выражение > THEN <действие 1>;

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

Команда повторения (цикл). Большинство алгоритмов содержат серии многократно повторяемых команд. Если такие команды записывать в виде составной команды следования, то каждую повторяемую команду пришлось бы выписать ровно столько раз, сколько раз она повторяется. Однако это очень неэкономный способ записи. Поэтому для обозначения многократно повторяемых действий используют специальную конструкцию, называемую циклом. Составная команда цикла, называемая также командой повторения, содержит условие, которое используется для определения количества повторений. Рассмотрим два типа команды повторения.

Схема команды повторения с предусловием:

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

Псевдокод	Паскаль
нц пока < условие> тело цикла кц	WHILE_<логическое выражение> DO BEGIN тело цикла END;

Здесь: нц – начало цикла, кц – конец цикла.

Под телом цикла понимается простая или составная команда. Исполнение такой команды повторения состоит в том, что сначала проверяется условие (логическое выражение) - отсюда и название - цикл с предусловием и, если оно соблюдено (значение логического выражения ИСТИНА), то выполняется тело цикла - команда или команды, которые нужно повторять. После этого снова проверяется условие (логическое выражение). Выполнение цикла завершается, когда условие перестает соблюдаться, т.е. значение логического выражения - ЛОЖЬ. Для этого необходимо, чтобы команда, выполняемая в цикле, влияла на условие.

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

(значение логического выражения ИСТИНА). Поэтому этот тип цикла называют также циклом “до”.

Цикл с постусловием записывается в виде:

Псевдокод	Паскаль
нц повторять< действие> тело цикла до < условие> кц	REPEAT тело цикла UNTIL _<логическое выражение>;

Схема команды повторения с постусловием: