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

План урока

      1. Работа с листом определений «Путь дерева».
      2. Решение обязательных бумажных задач 1, 2, 4.
      3. Решение необязательных бумажных задач 6 и 11. 
      4. Проект «Дневник наблюдения за погодой», подведение итогов за ноябрь.

Лист определений «Путь дерева»

Ветвление

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

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

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

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

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

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

Решение обязательных бумажных задач

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

Задача 2. Такие деревья вполне осмысленны с точки зрения современной лингвистики. В дереве всего шесть путей, поэтому задание «напишите шесть разных путей дерева» означает то же, что и «выпишите все пути дерева». Хорошо, если это заметят сами ребята. Если нет, ничего страшного, разговор об этом у нас еще впереди. Главное, чтобы учащиеся нашли все шесть путей и убедились, что они разные (как и в предыдущей задаче, одинаковых путей в дереве J нет).
Ответ:      ДЕТИ ЛЕТОМ КУПАЮТСЯ
                  ДЕТИ ЛЕТОМ ЗАГОРАЮТ
                  ДЕТИ ЛЕТОМ ИГРАЮТ
                  ДЕТИ ЗИМОЙ КАТАЮТСЯ НА КОНЬКАХ
                  ДЕТИ ЗИМОЙ КАТАЮТСЯ НА ЛЫЖАХ
                  ДЕТИ ЗИМОЙ КАТАЮТСЯ НА САНКАХ

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

Решение необязательных бумажных задач

Задача 6. Задача на повторение листа определений «Склеивание цепочки цепочек» среднего уровня сложности. Здесь необходимо выполнить операцию, обратную склеиванию, которую мы условно называем разрезанием, то есть построить цепочку цепочек, которая при склеивании дает исходную цепочку бусин. При этом мы еще должны обеспечить, чтобы первая и последняя цепочки в цепочке были одинаковы. В данном случае одинаковые цепочки выделить достаточно легко – «КА». Поэтому, скорее всего, большинство детей построит решение: КА – СТРЮЛЬ – КА. Однако, это решение не единственное. Во-первых, длина цепочки цепочек S может быть разной. Во-вторых, решение может включать пустые цепочки. В частности, можно построить решение, в котором первая и последняя цепочки – пустые.

Задача 11. Задача содержит два существенных ограничения: с одной стороны, Робот в ходе выполнения программы должен закрасить все незакрашенные клетки, а с другой – длина программы не должна быть больше 16 команд. Нужно постараться «экономить» команды. Какие соображения при этом помогут? Из предыдущих задач про Робота понятно, что удлиняют программу «возвращения», т. е. ситуации, когда Робот без необходимости ходит по одним и тем же клеткам. В нашей задаче добавляется и еще одно: чем меньше Робот будет ходить по изначально закрашенным клеткам, тем лучше.

Проект «Дневник наблюдения за погодой», подведение итогов за ноябрь

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

План урока

      1. Решение обязательных бумажных задач 3, 5 и 7.
      2. Решение компьютерных задач 388–391.

Решение обязательных бумажных задач

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

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


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

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

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

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

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

Решение компьютерных задач

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

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

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

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

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

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

План урока

      1. Проект «Дневник наблюдения за погодой», подведение итогов за декабрь.
      2. Решение обязательных бумажных задач 8–10.
      3. Решение необязательных бумажных задач 12 и 13.

Проект «Дневник наблюдения за погодой», подведение итогов за декабрь

Решение обязательных бумажных задач

Задача 8. Эта задача имеет много ответов. Необходимо предоставить ребятам достаточно времени для самостоятельной работы. Если вы видите, что кто-то не знает, с чего начать, поговорите с ним о том, как он понимает, например, фразу «В дереве есть три пути длины 2». На самом деле это условие означает то же, что и «на втором уровне есть три листа». Когда ученик понял смысл всех условий, решение становится совсем простым. Необходимо помнить, что все бусины должны быть круглыми. Цвет бусин существенной роли в данной задаче не играет, поэтому при дефиците времени бусины можно оставить нераскрашенными.

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

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

Решение необязательных бумажных задач

Задача 12. Если начать рассматривать условия с конца, то возникает естественное решение: последняя бусина – это конец длины 3 цепочки ⊕Г, первые две цепочки одинаковы. Правда, в результате получается цепочка длины 3, а не 4. Ситуацию можно исправить, поставив на третье место пустую цепочку.

Возможно и другое решение, тоже с использованием пустых цепочек. Ставим на первое и второе места пустые цепочки, затем идет цепочка длины 6, затем – «хвост» цепочки ⊕Г длины 3.

Задача 13. Элементов в мешке много, поэтому придется придумать какую-то систему, чтобы ничего не потерять (см. рекомендации к задачам 19 и 23, Часть 1). Особую актуальность приобретает этап проверки. Необходимо проверить не только совпадение общего числа букв в таблице и в мешке (это, как было сказано ранее, не обеспечивает верность ответа, хотя и позволяет выявить многие ошибки), но и совпадение числа букв по строкам (по цветам) и по столбцам (по каждой букве в отдельности).

Приводим здесь названия букв старославянской азбуки (кириллицы).

      Ответ: