В статье представлена демонстрационная компьютерная модель «Обход графов», которая может быть использована в учебном процессе, что позволит сделать его более гибким, повысит мотивацию учащихся, студентов и интерес к изучению дисциплин информатики. Модель была создана под руководством доцента, зав.кафедрой информатики КГПА Филимоновой Е.В.
В настоящее время разработано и применяется несколько тысяч электронных образовательных ресурсов (ЭОР) по самым различным областям знаний. Эти программы существенно различаются своими возможностями: имеются очень простые ЭОР, предусматривающие последовательную выдачу учебных текстов, и достаточно сложные интеллектуальные программные комплексы. Существующие ЭОР не полностью реализуют дидактические функции, охватывают не все темы, в связи с этим проблема разработки ЭОР является актуальной.
В информатике есть ряд сложных для понимания тем, одна из которых «Обходы графов». Данная тема требует визуализации и наглядного представления для лучшего усвоения и понимания. Существующих демонстрационных компьютерных моделей (ДКМ) по данной теме не так много, они имеют только демонстрационную направленность. Этим объясняется необходимость создания модели, способной не только визуализировать пошаговое выполнение алгоритмов обхода графов, но и реализовать самоконтроль пользователя.
Элементы теории графов.
При решении многих задач, касающихся ориентированных и неориентированных графов, необходим систематический перебор вершин графа такой, что каждая вершина просматривается только один раз. Два наиболее распространенных алгоритма обхода графов называются:
обход графа в глубину (поиск в глубину (англ. Depth First Search);
обход графа в ширину (поиск в ширину (англ. Breadth First Search).
Обход в глубину есть обход графа по следующим правилам:
находясь в вершине x, нужно двигаться в любую другую, ранее не посещенную вершину (если таковая найдется), одновременно запоминая дугу, по которой мы впервые попали в данную вершину;
если из вершины x мы не можем попасть в ранее не посещенную вершину или таковой вообще нет, то мы возвращаемся в вершину z, из которой впервые попали в x, и продолжаем обход в глубину из вершины z.
При выполнении обхода графа по этим правилам мы стремимся проникнуть "вглубь" графа так далеко, как это возможно, затем отступаем на шаг назад и снова стремимся пройти вперед и так далее.
Важность этого метода: он составляет основу многих других эффективных алгоритмов работы с графами, является гибким, мощным, применимым для решения трудных задач.
Алгоритм обхода графа в ширину (поиск в ширину). Прежде чем описать его, необходимо отметить, что при обходе в глубину, чем позднее будет посещена вершина, тем раньше она будет использована. Это прямое следствие того факта, что просмотренные, но еще не использованные вершины накапливаются в стеке. Обход графа в ширину основывается на замене стека очередью. После такой модификации, чем раньше посещается вершина (помещается в очередь), тем раньше она используется (удаляется из очереди). Использование вершины происходит с помощью просмотра сразу всех еще не просмотренных вершин, смежных с этой вершиной. Таким образом, "поиск ведется во всех возможных направлениях одновременно".
Поиск начинается с фиксированной вершины x.
Проверяются все вершины, смежные с x и не посещенные ранее.
Посещаются все эти вершины, и их номера заносятся в очередь.
Процесс продолжается с первой вершины, записанной в очередь, и до тех пор, пока очередь не станет пуста.
Средства реализации компьютерных моделей. Macromedia Flash
Существует множество систем и языков программирования, обладающих широким спектром возможностей для создания демонстрационных компьютерных моделей. К ним относятся Java, C++, Delphi, Visual Basic, Macromedia Flash (ActionScript).
Пакет Macromedia Flash – эффективное мультимедийное инструментальное средство, способное интегрировать широкий набор языков и мультимедийных форматов.
Программа Macromedia Flash представляет собой приложение, позволяющее распространять в Web разнообразную продукцию (от потоковой анимации до интерактивных и динамических презентаций), которая взаимодействует с серверными приложениями и совместима с серверными языками. Производимые фильмы могут быть доступны на самых разных платформах: от портативных устройств до настольных компьютеров и вещательной телевизионной аппаратуры. В Macromedia Flash применяется язык объектно-ориентированного программирования Action Script, который прошел значительный путь развития от первоначального программирования методом "перетаскивания" в версии Flash 4 до надежного и стандартизированного объектно-ориентированного языка в настоящее время. Возможности использования Macromedia Flash в качестве основного инструментального средства авторских работ практически безграничны.
Составляющими Flash-технологии, обусловившими выбор данного программного средства, являются:
векторная графика;
поддержка нескольких видов анимации;
возможность создания интерактивных элементов интерфейса;
поддержка взаимодействия с импортируемыми графическими форматами (в том числе растровыми);
возможность включения синхронного звукового сопровождения;
обеспечение экспорта Flash-фильмов в формат HTML, а также в любой из графических форматов, используемых в Интернете;
платформная независимость;
возможность просмотра Flash-фильмов как в автономном режиме, так и посредством Web-браузера;
наличие инструментов визуальной разработки, избавляющих создателя Flash-фильмов от многих рутинных операций, а также от детального изучения технических аспектов реализации Flash-технологии.
Демонстрационная компьютерная модель «Обход графов»
Модель «Обход графов» встроена на web-страницу и снабжена инструкцией и описанием заложенных в нее возможностей.
Задачи, решаемые моделью:
конспективное представление материала;
структуризация материала;
визуализация содержательной части учебного материала с помощью текстово-графических и анимационных элементов, облегчающих восприятие и запоминание;
реализация самоконтроля.
Принципы построения модели:
Нелинейное и многоуровневое представление учебной информации.
Нацеленность на личность (личностно-ориентированное обучение), на самостоятельную и индивидуальную работу.
Интеграция различных видов деятельности при работе с моделью: наблюдения, мыслительной деятельности, практических действий (демонстрация, моделирование, информативность, интерактивность).
Возможности, реализованные в модели:
Ввод пользователем количества вершин в графе и номера вершины, с которой следует начать обход.
Изображение на экране случайного графа с заданным пользователем количеством вершин.
Конструирование графа пользователем с указанным количеством вершин.
Демонстрация обхода графа, начиная с заданной пользователем вершины.
Возможность многократного изменения параметров.
Контроль понимания в форме теста с целью самопроверки.
Модель состоит из трех разделов:
теория;
практика;
тест.
В разделе «Теория» представлена краткая информация по теории графов, описаны правила, по которым осуществляются обходы графов в глубину и ширину, с демонстрацией на готовых примерах.
Практический раздел включает в себя шесть сцен: три сцены посвящены обходу в глубину, три – обходу в ширину. С точки зрения назначения, возможностей, технологии создания сцены, демонстрирующие поиск в ширину, аналогичны сценам, посвященным поиску в глубину, поэтому рассмотрим описание на примере сцен для обхода в глубину.
1 сцена.
Пользователь задает количество вершин в графе (максимум - 10) и номер вершины, с которой следует начать обход (вершины нумеруются с ноля). При щелчке по кнопке "Граф" изображается случайный граф. Нажимая многократно кнопку "Обход", пользователь может просмотреть обход данного графа, одновременно будут окрашиваться вершины графа, выводиться комментарии, изменяться состояние стека/очереди, изменяться поле "Результат". По окончании обхода весь граф будет окрашен в красный цвет, стек/очередь будет пуст, а поле "Результат" будет содержать последовательность вершин при обходе данного графа в глубину/ширину. Пользователь может продолжить работу с этим же графом, изменив вершину начала обхода, или поработать с другим графом.
2 сцена.
Эта сцена отличается тем, что пользователь сам конструирует граф. Для этого необходимо ввести количество вершин в графе и нажать кнопку "Вершины". Появившиеся вершины можно расположить удобным образом в заданной прямоугольной области. Далее следует расставить ребра. Для этого имеются два раскрывающихся списка. Необходимо указать пару вершин (начало и конец ребра), при щелчке по кнопке "Ребра" соответствующее ребро появится, при этом поменять расположение вершин будет невозможно.
3 сцена.
Эта
сцена предназначена для самоконтроля. При щелчке по кнопке "Граф"
появится случайный граф и номер вершины, с которой необходимо начать
обход. Задача пользователя: ввести номера вершин в последовательности
обхода в поле "Результат" и проверить себя. Если
пользователь начнет обход не с заданной вершины, то будет выведено
соответствующее сообщение. Если пользователь введет верный результат,
то все вершины графа будут окрашены в красный цвет, иначе на экране
появится верный результат.
Апробация ДКМ «Обход графов» на занятиях по информатике.
Разработанная модель была апробирована на практике в рамках преподавания дисциплины «Информационное компьютерное моделирование» студентам 3 курса физико-математического факультета КГПА. Адрес модели «Обход графов» в Интернете – http://kspu.karelia.ru/kafinfor/model/index.html
Литература:
Пак, Н. И., Глазко, Т. П. Использование демонстрационных моделей в курсе информатики Сайт «Информационные технологии и образование». Режим доступа http://www.ito.su/1998/2/PAK.html
Липский, В. Комбинаторика для программистов: Пер. с польск. / В. Липский. - М.: Мир, 1988. - 213 с.
Кафедра информационных технологий Курганского Государственного Университета. Информатика и программирование: шаг за шагом (Обходы графов). Режим доступа http://khpi-iip.mipk.kharkiv.edu/library/datastr/book_sod/kgsu/oglav5.html