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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

б = 15 (5 х 3).

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

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

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

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

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

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

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

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

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

Вход	Выход
кот	1
котенок	2

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

Вход	Выход
Кот	1
Котенок	2
Молоко	3

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

Вход	Выход
кот	4
человек	2
паук	8
береза	1
муравей	6
рояль	3

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