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

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

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

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

КОЗА ->

может означать «переезд с козой» на правый берег, а

<-

«переезд одного перевозчика на левый берег».

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

КОЗА ->

<-

ВОЛК ->

КОЗА <-

КАПУСТА ->

<-

КОЗА ->

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

Рис.1. Переправа через реку

При наличии достаточного количества алгоритмических этюдов удается совместить основную педагогическую задачу программ этой группы с рядом вспомогательных методически важных задач. Так, Ханойские башни {Монах) представляются замечательным дидактическим материалом для обсуждения темы «Большие числа», а также для первого выхода на цифровую часть клавиатуры при обработке клавиатурных навыков. Изучение программы Конюх, наряду с алгоритмической и математической задачами (пропедевтика координат), помогает формированию первичных навыков работы с латинским регистром компьютерной клавиатуры. Такой комплексный характер алгоритмических этюдов должен постоянно находиться в поле зрения педагога. При этом важно подчеркнуть роль темы алгоритмов в пропедевтическом курсе информатики: очень многие важные аспекты алгоритмов в этой теме умышленно опущены. Так, практически все рассматриваемые алгоритмы линейны и потому не дают пока возможности говорить о логически полном наборе управляющих структур — пока еще школьникам не показаны ни циклические, ни ветвящиеся алгоритмы. Опущены и описания свойств алгоритмов. Все это ожидает школьников позднее.

Наполнение темы «Алгоритмические этюды»

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

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

Перенос малого кольца с исходного стержня на промежуточный

Перенос большого кольца с исходного стержня на конечный

Перенос малого кольца с промежуточного стержня на конечный

У решения два качества: с одной стороны, оно единственно, с другой стороны, универсально. Алгоритм записан без привязки к нумерации стержней, поэтому можно переходить к описанию конкретных примеров. Дальнейшее продвижение вперед рекомендуется только после сформированного умения переносить любые башни из двух колец и записывать алгоритм такого переноса. Итог следующего этапа изучения — перенос трех колец — можно подводить после того, как зафиксирована запись:

перенос трех колец — это:

перенос двух колец исходного стержня на промежуточный

перенос большого кольца с исходного стержня на конечный

перенос двух колец с промежуточного стержня на конечный

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

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

количество перекладываемых колец — к;

номер исходного стержня — а;

номер конечного стержня — б.

Значит, любой алгоритм переноса колец Ханойской башни можно записать так:

Монах (к, а, б).

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

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

Монах (к - 1, а, б)

Монах (к,а,б) = а - б

Монах (к - 1, в, б)

Школьники, уже поработавшие с программой Монах, готовы принять необычное обозначение второй строки: здесь ее надо читать не «а минус б», а «перенос кольца со стержня а на стержень б». Теперь должно стать понятным, что можно переложить любое число колец, последовательно понижая сложность алгоритма: например, Монах(6,а,б) состоит из двух алгоритмов — Монах(5,а,в) и Монах(5,в,б); в свою очередь, Монах(5,а,в) состоит из двух алгоритмов — Монах(4,а,б) и Монах(4,б,в) и т. д. В конце концов, оказывается, что решение сводится к нескольким переносам двух колец — хорошо известному алгоритму.

Рис. 2. Перенос пяти колец

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

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

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

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

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

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

Пусть существует некоторый алгоритм обработки числовой информации. Это значит: если этому алгоритму предложено число а, то, обработав его, алгоритм выдает в качестве результата число б. Пусть, алгоритм обработки состоит в утроении числа. Тогда на предложенное (входное) число а = 5 алгоритм выдаст результат

б = 15 (5 х 3).

Выполнить алгоритм это значит — применить его к числу а, входу алгоритма.

Схема задачи имеет вид:

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

На этот раз речь идет о построении обратного алгоритма. Если известен «прямой» алгоритм, то обычно по нему можно восстановить обратные операции. Такая задача обычно вызывает трудности у младших школьников, но материал для подобного рода упражнений у учителя всегда найдется. В приведенном примере: а = б : 3, и так как б = 15, то а = 15 : 3 = 5. Теперь представим, что в тройке «вход-алгоритм-выход» вопросительный знак стоит в середине схемы: алгоритм обработки неизвестен, но известны вход и выход:

Эта задача существенно сложнее, прежде всего, своей неоднозначностью. Нет никаких оснований утверждать, что алгоритмом является пятикратное увеличение входного числа. Ведь тот же результат получается и по алгоритму а + 12.

и по алгоритму а х а х а — 12...

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

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

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

ученик мог бы выдвинуть гипотезу — алгоритм подсчитывает число букв к. Однако, если бы он не поторопился, а сделал бы еще одно испытание:

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

Из этого протокола не очень трудно сделать вывод: задуманный алгоритм подсчитывает число ног у входного объекта. В меню Буквоеда есть пиктограммы, используемые как кнопки включения вспомогательных операций. Одна из них — калькулятор, выполняющий обычные арифметические операции (чтобы ученик не отвлекался на числовые подсчеты карандашом на листке бумаги), а другая — это справочник по русскому алфавиту (учитывая, что в ряде встроенных и проектируемых алгоритмов могут встречаться задачи, связанные с определением номера буквы в алфавите). Такая автоматизация вспомогательных операций делает программу Буквоед своеобразным АРМом — автоматизированным рабочим местом школьника, анализирующего алгоритмы Буквоеда. Когда значительно позднее — в старших классах — ученик встретится с оснащенным компьютером автоматизированным рабочим местом, он, вероятно, вспомнит свой первый АРМ.