Урок 18. Путь дерева

Урок 18. Путь дерева

Ветвление

Ветвление времени, возможность выбора в истории всегда занимали философов и теологов. Если весь ход истории заранее записан в Книге или спланирован Господом, то что зависит от человека? Проблема эта неоднократно обыгрывалась и в научной фантастике. В частности, «эффект бабочки» (Рей Брэдбери) состоит в том, что выбор, случившийся в далеком прошлом и выглядевший там весьма незначительно (раздавленная бабочка), приводит к достаточно радикальным изменениям в истории цивилизации, грамматические правила и политические партии становятся иными.

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

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

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

Языковые структуры тоже удобно представлять в виде деревьев.

Полный перебор и деревья

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

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

Решение задач из учебника

Задача 103. Задача на понимание нового листа определений. Если вы видите, что кто-то выписывает цепочки, которые путями дерева D не являются, попросите его еще раз разобрать примеры листа определений и внимательно прочитать текст. В дереве D всего пять путей – БУМ, БУР, МИГ, МИР и МИФ, все они различны, и любые три в данном случае являются ответом.

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

Пути дерева:

ДЕТИ ЛЕТОМ КУПАЮТСЯ
ДЕТИ ЛЕТОМ ЗАГОРАЮТ
ДЕТИ ЛЕТОМ ИГРАЮТ
ДЕТИ ЗИМОЙ КАТАЮТСЯ НА КОНЬКАХ
ДЕТИ ЗИМОЙ КАТАЮТСЯ НА ЛЫЖАХ
ДЕТИ ЗИМОЙ КАТАЮТСЯ НА САНКАХ

Задача 105. Задача требует от ребят более глубокого понимания того, что такое путь дерева. Дети могут заметить, что некоторые пути дерева (выходящие из разных корневых вершин) совершенно не связаны между собой, т. е. вершины, которые принадлежат одному пути, не принадлежат другому. Совершенно иной будет ситуация, если два пути выходят из одной корневой вершины. В этом случае корневая вершина определяет начало сразу нескольких путей, которые из нее выходят. Так, например, прогуливая школу, ученик определяет несколько возможных сценариев дальнейшего развития событий, связанных между собой и неприятных. Эти сценарии никак не связаны с развитием событий в том случае, если бы он пошел в школу.

Скорее всего, ребята начнут решать задачу методом проб и ошибок, ставя различные знаки в различные окна и проверяя условия. Здесь постепенно и начнет формироваться идея связи. В ходе экспериментов ребята начнут понимать, что нельзя поставить в корневую вершину, из которой берут начало четыре пути, ни знак приоритета, ни знак сервиса. Действительно, в этом случае мы задаем сразу четыре пути, и тогда путей в дереве потом просто не хватит. Если же мы поставим в эту вершину запрещающий знак, дальше решение достраивается само собой – во все следующие за ней вершины мы ставим также запрещающие знаки, за той из них, что не является листом, тоже ставим запрещающие знаки. Итак, первое условие выполнено – есть четыре разных пути, все знаки в которых запрещающие. При этом все оставшиеся пути, оказывается, никак не связаны между собой, их можно строить по отдельности: три из знаков приоритета, один из знаков сервиса. Количество знаков на листе вырезания в данной задаче также не накладывает никаких дополнительных ограничений.

Задачу можно рассматривать как хороший повод продолжить знакомство со знаками дорожного движения. С дорожными знаками дети уже работали при решении задачи 5. В комментарии к этой задаче мы советовали обсудить с ребятами смысл данных знаков и поговорить о них. Теперь можно продолжить эту работу на другом наборе дорожных знаков. Ниже мы приводим информацию об использованных в задаче дорожных знаках.

Задача 106. Задача на повторение листа определений «Перед каждой бусиной. После каждой бусины». Нетрудно догадаться, что в результате раскраски в цепочке появятся одинаковые последовательности цветов: зеленый – желтый – синий – красный.

Задача 107. Это первая задача на новую тему, где требуется не просто выписать какие-нибудь пути дерева, а найти путь, удовлетворяющий определенным условиям. Эту работу будут затруднять особенности дерева G. Во-первых, оно достаточно большое, во-вторых, слишком много одинаковых вершин на одном уровне (в том числе все корневые вершины одинаковые). Задание (а) включает также новую деталь – словосочетание «путь длины 2»: путь – это цепочка, а что такое длина цепочки, ребятам известно, значит, речь идет просто о цепочке длины 2. Найти ее не слишком сложно, так как деревья мы всегда рисуем по уровням (и ребят приучаем к тому же). Поэтому достаточно найти на втором уровне хотя бы один лист и пометить путь, который в него ведет (это слово КУ). Найти путь КРОНА оказывается сложнее. Здесь ребята, скорее всего, воспользуются методом перебора, просматривая пути один за другим до тех пор, пока не найдут нужный. Кто-то может догадаться, что КРОНА – путь длины 5, значит, его последняя вершина находится на пятом уровне. Последняя вершина этого пути – А, значит, остается найти на последнем уровне все вершины А (таких оказывается всего 4) и проверить все пути, идущие в эти листья.

Задание (в) самое сложное. Если ребята в первых двух заданиях могли случайно наткнуться на решение, то здесь без перебора обойтись трудно. Учитывая второе утверждение, можно вести перебор только путей длины 5 (по листьям последнего уровня), но и такой перебор будет достаточно большим. Поэтому предоставьте ребятам достаточно времени для выполнения этого задания. Возможно, сообразительные ребята, не склонные к рутинной работе, придумают нечто, чтобы отсечь часть вариантов. Это очень хорошо, но не стоит требовать этого ото всех. Например, нетрудно догадаться, что последняя буква искомого пути не может быть гласной, иначе первое утверждение потеряет смысл. Тогда перебор по возможным буквам последнего уровня уже гораздо меньше, их всего 5. При этом обнаруживается только два подходящих слова – КРОЛЬ и КРЕСТ.

Задача 108. Необязательная. Это задача на склеивание цепочек, но языковая составляющая ее настолько велика, что формально решить ее невозможно. Перебрать все слова русского языка невозможно, значит, перебор будет лишь дополнять различные языковые соображения ребят и простое угадывание. Поэтому не стоит требовать от всех ребят решения. Если вы видите, что у кого-то задача совсем не идет – просто предложите ученику другую задачу.

Решений здесь много, например, в качестве результатов склеивания подойдут слова: ТЕПЛОВОЗ, ПОЙМАЛ, ПАРАД, КОРАБЛИК. Проще всего построить решение, имея в виду, что все предлоги и союзы тоже являются словами русского языка.

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

Задача 110. Задача представляет собой комбинацию двух типов задач, с которыми ребята по отдельности уже встречались. Первый – вписать в программу пропущенные команды, когда начальная позиция и позиция Робика после выполнения программы известны. Второй – найти начальное и конечное положения Робика на поле, если даны программа и ее результат. Здесь учащимся предстоит сделать и то и другое. Прежде всего стоит определить начальное положение Робика на поле. Это можно сделать разумным перебором, ставя Робика в любую закрашенную клетку и начиная выполнять команды. Оказывается, не выходя за пределы закрашенных клеток, три начальные команды программы можно выполнить только из одной клетки. Теперь уже нетрудно восстановить пропущенные команды – влево, влево. Лучше всего по окончании этой работы еще раз проверить себя – выполнить получившуюся программу из найденного начального положения на запасном поле с листа вырезания. Проконтролируйте также, чтобы ребята не забыли отметить положение Робика на поле до и после выполнения программы.

Ответ:

Задача 111. По сути, это задача, обратная задаче 109. Здесь нужно выполнить «разрезание» цепочки на три части так, чтобы получившиеся цепочки удовлетворяли некоторым условиям. Первое задание выполнить проще. Для этого достаточно посчитать число букв в слове КАНАРЕЙКА и разделить его на три. Второе задание можно выполнить с помощью несложных рассуждений или перебора. Большинство детей справится с этим заданием хаотичным просматриванием или простым угадыванием.

Задача 112. Необязательная. При решении задачи можно применить обычную тактику – перебирать все возможные пары фигурок, каждый раз проверяя, можно ли из одной фигурки сделать другую, раскрасив лишь один квадратик. Однако условие задачи подводит к идее, позволяющей существенно уменьшить перебор. То, что нужно закрасить лишь в одной фигурке один квадратик, подсказывает использовать в решении инвариант – число квадратиков, закрашенных в фигурках. Число закрашенных квадратиков в фигурках соответственно равно 8, 6, 8, 8, 7 и 9 (перечисляем фигурки слева направо). Исходя из этого, можно существенно сократить количество рассматриваемых вариантов.

Ответ: нужно в пятой (считая слева) фигурке закрасить верхний левый угол в желтый цвет и она станет такой же, как третья.

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

Если возникнет вопрос, как пометить два одинаковых пути, попросите сделать это так же, как в задаче 107.

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

Задача 114. Необязательная. Предоставьте ребятам самостоятельно найти для себя подсказку: латинский алфавит есть в учебнике на второй странице обложки. Формирование умения сориентироваться и найти необходимую информацию – одна из основных задач курса, даже если ребята работают пока в пределах одного учебника.

Ответ: истинные утверждения – третье и пятое, остальные – ложные.

Задача 115. Необязательная. Задача на повторение листа определений «Цепочка цепочек». Некоторую трудность может вызвать третье утверждение (в совокупности со вторым): ребята, скорее всего, просто не задумывались над тем, что пустая цепочка тоже может быть словом, в котором нет ни одной буквы.

Компьютерный урок «Путь дерева», задачи 114 - 121

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

Задача 115. Задача среднего уровня сложности. Для ее решения учащемуся нужно не только владеть понятием «путь дерева», но и представлять себе связь нового понятия с уже известными понятиями. Например, ребенок должен понимать, что каждому пути дерева соответствует свой лист. Поэтому условие «в данном дереве есть один путь длины 1» означает то же самое, что «в данном дереве на первом уровне есть один лист». Таким образом, один из способов решения состоит в том, чтобы поставить на каждый уровень нужное число листьев, а затем соединить их в дерево, по ходу ставя вершины, которые листьями не являются. Конечно, сделать это можно по-разному. Кроме того, в дереве могут быть и «дополнительные» листья на каждом уровне. Поэтому данная задача имеет довольно много решений.

Задача 116.  Усложненная задача на новое понятие. Здесь ребенок должен не только знать основные понятия, в частности, «путь дерева», но и уметь сделать некоторые выводы из условия задачи. Так, наиболее важно решить, в какой из корневых бусин стоит буква М, а в какой – Л. Как видим, в нашем дереве есть лишь один путь длины два, значит это слово – МЫ. Поэтому в правой корневой бусине стоит буква М, а в левой – Л. Теперь исходя из длин данных путей, можно однозначно поместить в дерево слова ЛУНКА и МАЛЫШ. После этого используем данные в задаче утверждения, и все окна окажутся заполненными.

Задача 117. Задача на повторение листа определений «Перед каждой бусиной. После каждой бусины» среднего уровня сложности. В данном случае усложняет решение то, что два условия описания не удается использовать отдельно друг от друга. У нас есть 3 треугольные бусины, значит, в цепочке будет три кусочка вида «фиолетовая - … - треугольная». Однако если строить эти кусочки произвольно, может оказаться невозможным соблюсти второе условие описания. Поэтому если рассматривать условия изолированно, то цепочку придется перестраивать несколько раз. К счастью электронная «лапка» позволяет без труда проводить пробы до тех пор, пока оба условия не окажутся выполненными.

Задача 118. Необязательная. По сравнению с задачами такого типа, которые ребята уже решали, здесь ситуация более сложная, поскольку вариантов программы существенно меньше и стенки на поле ограничивают действия Робика довольно жестко. Во-первых, становится ясно, что первая команда Робика должна быть «влево». Во-вторых, чтобы попасть в верхний ряд, Робику необходимо выполнить 5 команд «вверх». Также после нескольких проб и ошибок выясняется, что Робику нужно в процессе выполнения программы сдвинуться по крайней мере один раз по горизонтали, помимо первой команды: либо вправо, либо влево. Таким образом, мы делаем вывод: чтобы попасть в клетку верхнего ряда, Робику необходимо выполнить хотя бы 7 команд. У нас команд 8. Это значит, что Робик не может возвращаться, например, проходить по одной клетке дважды или выполнять команду «вниз», так как для возвращения понадобится чётное число команд, т. е. как минимум две дополнительные команды, а у нас – только одна. Значит, надо попытаться удлинить путь Робика на один шаг. Пытаясь заставить Робика попасть в различные клетки верхнего ряда, мы понимаем, что существует лишь одна возможная клетка, в которой закончится программа Робика, – вторая клетка верхнего ряда. В неё приводят всего две программы.

Ответ:

ВЛЕВО           ВЛЕВО
ВВЕРХ            ВВЕРХ
ВВЕРХ            ВВЕРХ
ВВЕРХ            ВЛЕВО
ВЛЕВО            ВВЕРХ
ВВЕРХ            ВВЕРХ
ВВЕРХ            ВВЕРХ
ВЛЕВО           ВЛЕВО

Задача 119. Задача на повторение понятий «перед каждой бусиной/после каждой бусины» среднего уровня сложности. Здесь решение можно просто сложить из частичных решений вида «птица – медведь – заяц». Поскольку в цепочке должны быть три разные птицы, то наименьшее возможное число фигурок в цепочке – девять. Конечно, их может быть и больше, ведь выражение «есть три разные птицы» не исключает, что в цепочке 4 разные птицы или есть несколько одинаковых птиц. Кроме того, ребенок может вставить в цепочку сколько угодно пар «медведь – заяц» или просто фигурок медведей.

Задача 120. Задача на расстановку слов в словарном порядке повышенного уровня сложности. Как видите, здесь все слова имеют одинаковые начало. Кроме того, в задаче содержатся сложные случаи расстановки слов, в том числе слова с дефисами и пары слов, когда одно является частью другого.

Задача 121. Задача на закрепление понятия «после каждой», которое в данном случае употребляется для бусин дерева. Подходящих решений здесь довольно много. Так, в дереве могут быть какие-то дополнительные звездочки кроме пятиугольных и восьмиугольных, а может их и не быть. Например, подойдет дерево с шестью корневыми восьмиугольными звездами разного цвета, после каждой корневой бусины ровно одна бусина-лист – пятиугольная звезда.