1. 1.7. Алгоритмы. Основные понятия

1. 1.7.1. Определение алгоритма. Запись алгоритма. Свойства алгорит­мов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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