Глава VIII. АЛГОРИТМЫ § 1. Что такое алгоритм!

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

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

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

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

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

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

1. Подойди к краю тротуара у знака перехода.

2. Стой.

3. Смотри налево.

4. Если идет транспорт слева, го перейди к указанию 2,иначе — к указанию 5.

5. Пройди до середины улицы.

6. Стой.

7. Смотри направо.

8. Если идет транспорт справа, то перейди к указанию 6,иначе — к указанию 9.

9. Пройди вторую половину улицы до противоположного тро­туара.

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

В виде аналогичного предписания можно сформулировать и алгоритм приближенного измерения длины отрезка с точностью

до 1:

1. Выбери мерку.

2. Наложи мерку с одного (левого) конца измеренного отрезка.

Отметь на отрезке второй конец мерки.

3. Теперь оставшаяся часть отрезка — измеряемый отреаок.

4. Если измеряемый отрезок больше мерки, то перейди к ука­занию 2, иначе — к указанию 5.

5. Сосчитай метки на отрезке.

6. Полученное число — значение длины отрезка.

7. Измерение закончено.

Приведенные примеры позволяют нам несколько разъяснить, что имеется в виду под «общим способом» решения однотипных

задач.

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

задач.

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

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

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

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

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

в) результативность, т. е. решая любую задачу из данного вида

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

Слово «алгоритм» происходит от имени известного математика IX в. аль-Хорез-ми, что означает «из Хорезма», впервые сформулировавшего правила выполнения арифметических действий над многозначными числами. Через труды аль-Хорезми в Европу проникли способы действий с числами в десятичной системе счисления, которые стали называть алгоритмами согласно латинской транскрипции имени

ученого.

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

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

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

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

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

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

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

Измерение длины

Выбирай мерку!

. Наложи мерку с левого ¹ конца измеряемого отрезка

Отметь на отрезке второй конец мерки

Оставшаяся часть отрезка -измеряемый отрезок

I Сосчитай метки на отрезке! I

Полученное число-значение длины отрезка

Рис. 26.

Оо

к указанию 2, иначе — к указа­нию 5»), называемые условны­ми.

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

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

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

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

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

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

попо_>пр„„₀,

ODDO-ODO OODI Dl

Рис. 28.

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

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

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

На рисунке 26 изображена блок-схема алгоритма приближен­ного измерения отрезка с точностью до 1 произвольной (условной)

меркой.

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

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

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

раз, сколько возможно, т. е.пока не получится слово, в котором нет двух рядом стоящих кру­жочков; затем переходим к применению правила 3, а именно, если имеется два рядомстоящих квадратика, их удаляют, и это правило применяется столько раз, сколько возможно, т. е. пока не получится слово, в котором нет двух рядом стоящих квадратиков. Полученное слово, является результатом преобразования исходного слова по заданным правилам и способу их применения, определяющим вместе некоторый алгоритм преобразования слов в данном алфавите. На рисунке 28 показано преобразование четырех слов по этому алгоритму.

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

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

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

§ 2. «Вычислительные машины»

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

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

Если один из участников игры задает на входе машины какое-нибудь число, например 3, размещая в верхней овальной фигуре карточку с соответствующей цифрой, то другой участник, выполняю­щий роль «вычислительной машины», должен положить на выход карточку с результатом, т. е. с числом 4. Если он ошибочно кладет другую карточку, то ее отбирают. Проигрывает тот, у кого не хва­тает карточек с цифрами для продолжения игры.

«Вычислительная машина» постепенно усложняется. На рисунке 30,2 изображена «машина», последовательно выполняющая дейст­вие «прибавление единицы» дважды.

Возникает вопрос: нельзя ли усовершенствовать «гвычислительную машину», выполняющую два одинаковых действия «прибавление единицы», заменив ее другой, выполняющей лишь одно действие? Такая «машина» изображена на рисунке 30,3. В процессе игры подтверждается, что если на входы этих двух «вычислительных машин» попадут карточки с одинаковыми числами, то на их выходах окажутся также карточки с одинаковыми числами, т, е. эти «машины» действуют одинаково, тем самым доказывается тождество

(а+ 1)+ 1 =а + 2 для любого а.

Аналогично в ходе игры с использованием «машины», изображен­ной на рисунке 30,4, обнаруживается, что последовательное выпол­нение двух действий « + 2»— прибавление числа 2 и «—1» — вычитание единицы, равносильно выполнению одного действия « + 1» — прибавление единицы. Следовательно, «машины», изоб­раженные на рисунках 30,/ и 30,4, действуют одинаково ({а + 2) — 1 = = а+1 для любого а). Целесообразно также проведение игры с использованием «машины», изображенной на рисунке 30,5. Можно вместо действий « + 2» и «— 2» взять « + 3» и «— 3» или «-J-1» и «— 1». Проверив для нескольких различных чисел работу этой «машины», дети обнаруживают, что она не меняет исходного числа, т. е. они уже открывают для себя то, что в дальнейшем запи­шут в виде предложения «(а + 2) — 2 = а для любого а» или вообще «(а + 6)— Ь = а для любых а и 6».

«Машину», изображенную на рисунке, можно заменить ей

«равносильной», изображенной на рисунке 30,6, моделирующей тождество а + 0 = а для лю­бого а.

Изображенные на рисунке 30 «машины» представляют простейшие линейные алгорит­мы. Проводимые эксперименты подтверждают, что дети 5—6 лет легко усваивают и работу «машин», представляющих про­стейшие разветвленные и цик­лические алгоритмы.

Изображенная на рисунке 31,1 «машина» работает сле­дующим образом: если на вход «машины» подано некоторое число а, «машина» прежде всего проверяет, выполняется ли условие «а<5». Если оно выполняется, то «машина» прибавляет к данному числу 2, если не выполняется, то вычитает 2. Знак вопроса на выходе «машины» нужно заменить полученным результатом. На рисунке 31,2 дана таблица, показывающая работу этой «машины» для значений а: 1, 2, 3, 4, 5, 6, 7, 8, 9.

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

(в прямоугольниках).

На рисунке 33,/ изображена «машина», представляющая цикли­ческий алгоритм: если на вход подано некоторое число а, то «машина» прибавляет к нему 2, если полученное число меньше 9, она опять прибавляет 2 и т. д., пока не получится число, не меньшее 9, т. е.

Рис.31

.

равное или большее 9. Это число и будет результатом. Работа этой «машины» иллюстрируется для чисел 1 и 2 в таблице на рисунке 33,2. В описанных выше играх моделируются различные алгоритмы в виде блок-схем. В следующей серии игр «Вычислительные ма­шины» моделируются некоторые алгоритмы в виде машин Поста, представляющих собой одно из разработанных в математике уточнений интуитивного понятия алгоритма.

Машина Поста представляет собой точное предписание в виде программы, состоящей из конечной последовательности определен­ного рода команд, предназначенной для решения любой задачи из целого вида однотипных задач. Хотя машина Поста — чисто те­оретическое понятие («теоретическая машина»), ее программа яв­ляется прообразом программы для реальной ЭВМ.

Профессор МГУ В. А. Успенский в своей популярной брошюре «Машина Поста» (М., 1979.— С. 4) говорит о том, что школьники первых классов и даже старшие дошкольники без труда могут осуществлять «вычисления» на машине Поста по заданной програм­ме, например, при помощи разграфленной на секции бумажной ленты и канцелярских скрепок или пуговиц в качестве меток, а также составлять простейшие программы (не содержащие команд передачи управления). Это высказывание В. А. Успенского под­тверждается и проводимыми экспериментами. Опишем две простей­шие машины Поста, осуществляющие «прибавление единицы».

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

На рисунке 34,1 изображена простейшая программа прибавле­ния единицы, а на рисунке 34,2 показано,. как выполняется эта программа, если в начале работы машины в памяти хранятся три кружочка, а машина «смотрит» на самую правую заполненную клетку, что обозначено стрелкой.

По команде 1 машина «передвигает» свое внимание на одну клетку вправо и переходит к выполнению команды 2 (в конце этой команды указан номер команды, к выполнению которой должна пе­реходить машина). По команде 2 машина кладет кружочек в пустую клетку, на которую она смотрит, и переходит к выполнению команды 3 («стоп»), по которой останавливается.

Если эту программу применить к начальному состоянию, изобра­женному на рисунке 34Д то машина сломается, так как командой 100

Машина сломалась 3

Рис. 34,

2 ей предписано положить кружочек в заполненную клетку. Значит, для случая, когда машина «смотрит» вначале не на самую правую заполненную клетку, эта машина не годится, нужна более совершен­ная программа прибавления единицы. Такая программа изображена на рисунке 35,1.

На рисунке 35 имитируется работа этой машины.

По команде 1 машина совершает сдвиг вправо на одну клетку и переходит к выполнению команды 2. Команда 2 выполняется в зависимости от того, «смотрит» машина в данный момент на пустую или на заполненную клетку. В нашем случае машина «смот­рит» на заполненную клетку. Поэтому надо смотреть на нижнюю стрелку команды 2, на которой нарисована заполненная клетка. Она указывает на то, что нужно возвратиться (еще раз выпол­нить) к команде 1. По этой команде машина еще раз «сдвигается» вправо на одну клетку и переходит к выполнению команды 2. Теперь, так как машина «смотрит» . на пустую клетку, верхняя стрелка команды 2, на которой нарисована пустая клетка, указывает,

Т

Стоп

Рис. 35.

что надо перейти к выполнению команды 3. По команде 3 маши­на кладет в пустую клетку, накоторую она «смотрит», кружо­чек и переходит к выполнению команды 4. По команде 4 ма­шина останавливается.

Дети с увлечением имити­руют работу машины при раз­личных начальных состояниях. После имитации работы вычи­слительной машины рекомен­дуется показать им с помощью карточек с цифрами и знаками + и =, какое действие вы­полнила машина (рис. 35,<3), что с успехом выполняют са­ми дети. Повторяя эту игру для различных исходных чисел (кружочков в памяти машины), дети могут самостоятельно по­лучить таблицу прибавления единицы: 1 + 1=2; 2 + 1=3; 3+1=4; ...; 9+1= 10.

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

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

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

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