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

Обработка информации предполагает выполнение какого-то прави­ла (алго­ритма), исходные данные для которого отождествляют­ся с со­стояни­ем того или иного носителя.

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

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

Говорят, что алгоритм - это точное предписание, которое зада­ёт дис­кретный пошаго­вый процесс, начинающийся с некоторых произ­воль­ных ис­ход­ных объектов и направленный на получение полностью опре­де­ляе­мого этими исходными объ­ектами результата.

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

Каждый уни­версальный исполнитель обладает не­кото­рым языком для за­писи алго­ритмов. Универ­сальным исполни­телем ал­горитма мо­жет быть как человек, так и некото­рое авто­матическое устройство, на­пример, ком­пьютер. Язык записи алго­ритмов компьютера называ­ется язы­ком про­грам­мирования. Запись лю­бого алго­ритма на языке программирова­ния назы­вается програм­мой.

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

Алгоритмы характеризуются следующими основными свойст­вами:

дискретностью,

определенностью,

результативностью,

массовостью.

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

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

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

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

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

В состав алгоритма могут входить:

· последовательно выполняемые операторы

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

· циклические операторы (циклы) – операторы, выполняющие группу операторов указанное количество раз (циклы со счётчиком) или неопределённое количество раз в зависимости от некоторого условия, заданного перед (предусловие) или после выполняемых действий (постусловие)

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

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

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

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

При блок-схемном методе записи алгоритма весь процесс решения задачи разделяется на отдельные этапы – блоки. В блок-схеме каждому типу действий соответствует геометрическая фигура с пояснительным текстом. Направление процесса обработки в блок-схеме указывается путём соединения отдельных элементов блок-схемы линиями переходов (стрелками). В таблице представлены используемые элементы:

Обозначение	Пояснение
	Вычислительное действие или последовательность действий
a<b	Проверка условия
a<b	Начало цикла (с предусловием, со счётчиком, с постусловием)
ИмяПроцедурыы	Вызов подпрограммы
Ввод а,b	Ввод-вывод данных
Печать а,b	Печать результатов

В диаграммах Насси-Шнейдермана обозначения операторов имеют следующий вид

Обозначение	Пояснение
	Вычислительное действие или последовательность действий
	Проверка условия
	Оператор выбора
	Цикл с предусловием
	Цикл со счётчиком
	Цикл с постусловием
Название подпрограммы	Вызов подпрограммы

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

Обозначение	Пояснение
ОПЕРАТОР	Вычислительное действие или последовательность действий
если УСЛОВИЕ то ОПЕРАТОР1 иначе ОПЕРАТОР2 конецесли	Проверка условия
циклпока УСЛОВИЕ1ИСТИННО ОПЕРАТОР конеццикла   для ПЕРЕМЕННАЯ = НАЧАЛО до КОНЕЦ с шагом ШАГ ОПЕРАТОР конеццикла   выполнять ОПЕРАТОР циклпока УСЛОВИЕ1НЕИСТИННО	Цикл (с предусловием, со счётчиком, с постусловием)

Рассмотрим пример программы и приведённые для неё блок-схему, диаграмму Насси-Шнейдермана и запись на языке псевдокода. Программа на языке Visual Basic for Application даёт возможность ввести с клавиатуры массив чисел и вызывает подпрограмму-процедуру SumArray, суммирующую его отрицательные элементы:

Sub SumArray(A() As Integer, n As Integer, _

m As Integer, S As Integer)

S = 0

For i = 1 To n

For j = 1 To m

If A(i, j) < 0 Then S = S + A(i, j)

Next j

Next i

End Sub

Sub VV()

Dim B(1 To 3, 1 To 2) As Integer

Dim S As Integer

For i = 1 To 3

For j = 1 To 2

B(i, j) = InputBox("B(" & i & "," & j & ")=")

Next j

Next i

SumArray B, 3, 2, S

MsgBox "Сумма отрицательных элементов массива равна: " &_

CStr(S)

End Sub

Блок-схемы программ

Процедура SumArray

Программа VV

Диаграммы Насси-Шнейдермана

Программа VV Процедура SumArray

Запись программы с помощью псевдокода:

1. Программа VV:

начало

целый массив B(от1 до 3, от 1 до 2)

целая переменная S,i,j

для i=1 до 3 с шагом 1

для j=1 до 2 с шагом 1

ввод B(i,j)

конеццикла

конеццикла

процедура SumArray(B,3,2,S)

вывод S

конец

2. Процедура SumArray:

начало

целый массив B(от1 до 3, от 1 до 2)

целая переменная S,i,j

S=0

для i=1 до 3 с шагом 1

для j=1 до 2 с шагом 1

если B(i,j)<0 то S=S + B(i,j)

конеццикла

конеццикла

конец

Дата добавления: 2015-05-10