Алгоритмы

1. Подойди к краю тротуара у знака перехода.
2. Стой.
3. Смотри налево.
4. Если идет транспорт слева, то перейди к указанию 2, иначе — к указанию 5.
5. Пройди до середины улицы.
6. Стой.
7. Смотри направо.
8. Если идет транспорт справа, то перейди к указанию 6, иначе — к указанию 9.
9. Пройди вторую половину улицы до противоположного тро­туара.

10. Переход улицы закончен.

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

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

Какие же свойства характеризуют всякий алгоритм?

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

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

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

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

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

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

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

Однако приведенные выше предписания составлены так, что они выявляют шаговую (дискретную) оперативно-логическую структуру алгоритмов. Поясним, что это означает.

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

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

2. В приведенных выше предписаниях можно различить два ос-
новных вида команд, а следовательно, два основных вида шагов,
представленных этими предписаниями алгоритмов: простые ко-
манды, предписывающие выполнение некоторых действий («смот-
ри влево», «пройди до середины улицы», «выбери мерку», «наложи
мерку» и т. д.), и составные, определяющие разветвление процесса
решения задачи в зависимости от выполнения или невыполнения
некоторого условия («если идет транспорт слева, то перейди к ука-
занию 2, иначе — к указанию 5»), называемые условными.

Условная команда имеет вид «если Р, то А, иначе В». Она пред­писывает следующий порядок действий: если условие Р выполня­ется (истинно), то выполняется А (в нашем примере — возврат к указанию 2). Если же условие Р не выполняется (ложно), что обо­значается словом «иначе», то А пропускается и выполняется В (в на­шем примере осуществляется переход к следующему указанию 5).

Условные команды можно записать сокращенно: «если Р, то А», при этом подразумевается, что если условие Р не выполняется, то осуществляется переход к следующей по порядку команде В приведенных выше примерах условные команды, если усло­вие Р выполняется, определяют повторение некоторых действий («стой», «смотри влево», «смотри вправо», «наложи мерку» и т. д.) определенное число раз (пока условие Р выполняется). Такие про­цессы и соответствующие им алгоритмы, в которых некоторые действия повторяются, называются циклическими.

Если же алгоритм состоит из одних простых команд, то он на­зывается линейным.

Таким образом, различают линейные, разветвленные и цикли­ческие алгоритмы.

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

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

На илл. 20 изображена блок-схема алгоритма перехода улицы, нерегулируемого светофором.

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

Приведем в качестве примера игру «Преобразование слов», моделирующую понятие алгоритм преобразования слов в данном ал­фавите.

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

последовательности из нулей и единиц). Любое сколь угодно длинное слово в нашем алфавите преобразовывается по приведен­ным на илл. 21 правилам следующим образом: если в заданном слове имеется квадратик, расположенный левее кружочка, то, со­гласно правилу 1, их нужно поменять местами; если во вновь по­лученном слове опять имеется квадратик, расположенный левее кружочка, нужно опять их поменять местами и т.д.; правило 1 применяется столько раз, сколько возможно, т. е. пока не полу­чится слово, в котором уже нет квадратика, расположенного левее кружочка, или в котором все кружочки лежат левее всех квадрати­ков; затем переходим к применению правила 2, а именно: если имеются два рядом стоящих кружочка, их удаляют, и правило 2 применяется столько раз, сколько возможно, т. е. пока не полу­чится слово, в котором нет двух рядом стоящих кружочков; затем переходим к применению правила 3, а именно: если имеются два рядом стоящих квадратика, их удаляют, и это правило применя­ется столько раз, сколько возможно, т. е. пока не получится слово, в котором нет двух рядом стоящих квадратиков. Полученное слово является результатом преобразования исходного слова по заданным правилам и способу их применения, определяющим вместе неко­торый алгоритм преобразования слов в данном алфавите.

На илл. 22 показано преобразование четырех слов по этому ал­горитму.

Как показывает опыт обучения, повторив эту игру несколько раз для различных «слов», дети 5—6 лет в состоянии заранее пра­вильно определить, какие вообще могут оказаться результаты со­кращения «слов» по заданным правилам: кружочек и квадратик, или один кружочек, или один квадратик, или «ничего» (это «ни­чего» называют «пустым словом»).

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

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