Графы и карандаши Teleskop's Блог / 19.06.2016 В посте не будут упомянуты знаменитые персонажи с графскими титулами: ни граф Монте-Кристо, ни граф Дракула, да и прочие графы и графини не задействованы. Зато к теме поста имеют отношение математики Леонард Эйлер, Льюис Кэрролл и среда программирования Pencil Code.Благодаря серии постов Людмилы Рождественской "Карандашное программирование" появилось непреодолимое желание поэкспериментировать в среде визуального программирования Pencil Code. В июне в колледже занятия всё ещё продолжаются. Таким образом, была возможность попробовать поработать в этой среде с учащимися прямо сейчас, не откладывая её испытания на следующий учебный год.Практическую работу в Pencil Code провела с группой студентов-информатиков, которые обучаются по специальности "Информационные системы». Ребята - не новички в кодинге. Они уже изучили курсы "Алгоритмизация и программирование", "Прикладное программирование". Видимо, поэтому довольно легко освоили принцип работы в Pencil Code. Для самостоятельного выполнения заданий хватило небольшого вступительного объяснения и рассмотрения пары-тройки примеров. В работе пригодилась справочная информация "Измерение расстояний и углов" в руководстве от Pencil Code. После моего предупреждения о том, что среда Pencil Code предназначена скорее для детей, студенты жизнерадостно ответили: А мы тоже дети! И, действительно, они занимались карандашным программированием с детской непосредственностью и увлечённостью. Основной темой практической работы стало решение задач-головоломок на рисование геометрических фигур так, чтобы в процессе рисования карандаш не отрывался от бумаги, и ни одна линия не проводилась дважды. Знатоки математики могли заметить, что такого рода задания связаны с топологией и теорией графов.Справка о графах для желающих строить фигуры одним росчеркомГрафом в математике называется конечная совокупность точек, называемых вершинами; некоторые из них соединены друг с другом линиями, называемыми ребрами графа. Граф - фигура, состоящая из точек и линий, связывающих эти точки. Вершины, из которых выходит нечётное число рёбер, называются нечётными, а вершины, из которых выходит чётное число рёбер, называются – чётными.Решая задачу про обход мостов Кенигсберга, Леонард Эйлер стал основоположником теории графов. Если граф можно начертить одним росчерком, не отрывая карандаша от бумаги, проходя при этом каждый участок один и только один раз, то его называют уникурсальным. Признаки уникурсальности графа Если все вершины графа чётные, то его можно начертить одним росчерком. Если у графа две нечётные вершины, то его тоже можно начертить одним росчерком. Движение нужно начинать от любой нечётной вершины, а заканчивать на другой нечётной вершине. Граф с более чем двумя нечётными вершинами, невозможно начертить одним росчерком. Например, определим чётность вершин у схематического рисунка "Открытый конверт".У данного графа 2 нечётные вершины, остальные вершины чётные. Значит его можно построить одним росчерком. Пример построения.Рисунок "Закрытый конверт". У графа 4 нечётные вершины. Следовательно, построение одним росчерком невозможно.На занятии напомнила студентам эти сведения из теории графов. Надо сказать, что ребята успели их основательно забыть. Есть основания полагать, что после практической работы в Pencil Code сведения из теории графов были усвоены более прочно и надёжно. По крайней мере, все ребята научились применять признаки уникулярности и успешно справились с выполнением практических заданий на программирование обхода графов одним росчерком.Примеры программПример 1Пример 2Пример 3Пример 4Пример 5Дополнительным заданием послужила головоломка от Льюиса Кэрролла. Попробуйте, не отрывая карандаша от бумаги и не проводя дважды одну и ту же линию, нарисовать фигуру, изображенную на рисунке. При этом надо выполнить еще одно условие: линии не должны нигде пересекаться между собой (допускается только угловое касание линий). Кстати, в книге "Льюис Кэрролл: История с узелками. Игры, головоломки, задачи, парадоксы" встречаются сложные задачи на построение одним росчерком карандаша.В брошюре Якова Перельмана "Одним росчерком" (1940 г.) рассматриваются задачи по вычерчиванию фигур одной непрерывной линией.В качестве домашнего задания предложила самим придумать фигуры для рисования одним росчерком и запрограммировать их обход в Pencil Code. ПримерУважаемые коллеги, будет интересно увидеть и ваши варианты фигур. Я проводила занятие со студентами колледжа, возраст которых соответствует возрасту учащихся 11-го класса. Считаю, что занятие "Графы в Pencil Code" можно провести и со школьниками более младших классов. Теория доступная, задания имеют занимательный, игровой характер, карандашное программирование делает процесс решения наглядным и ярким. Необходимо заметить, что решение задачи на обход графов - это не только забавные головоломки. Любую систему, в которой можно обозначить вершины и связи между ними, можно рассматривать, используя аппарат теории графов. Примеры практических приложений теории графов: схемы метро, дорожные карты, сетевые соединения и т.д.В целом, отмечу положительный опыт использования среды Pencil Code. Она доступна в освоении, вызывает живой интерес за счёт возможности быстрого достижения зримого результата. Думаю, что для учительской практики перспективно поискать способы визуализировать в Pencil Code некоторые математические темы и алгоритмические конструкции. Pencil Code теория графов