Моделирование как метод познания: графы.

И.Л.СОБОЛЕВА

МОУ «ТВЕРСКОЙ ЛИЦЕЙ»

ИНФОРМАЦИОННЫЕ МОДЕЛИ НА ГРАФАХ

Одним из методов познания объектов окружающего мира является моделирование. Модель важна как инструмент, облегчающий познание или наглядное представление объекта. Различают натурные и информационные модели. В преподавании информатики особенно важны информационные модели, которые представляют собой описание объекта-оригинала на языках кодирования информации. Это может быть словесное описание, формула, схема или чертеж.

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

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

Теория графов (греч. grapho – пишу, черчу, рисую) возникла в первой половине XVIII века. Еще в 1736 году Леонард Эйлер впервые опубликовал работу по графам, содержащую решение задачи о Кенигсбергских мостах. Широкое развитие теория графов получила с 50-х годов XX века в связи со становлением кибернетики и развитием вычислительной техники.[4] Простота теоретических сведений, наглядность и доступность теории графов помогает решать довольно сложные задачи. В курсе информатики в 5, 6 и 7 классах рассматривается множество задач, решение которых облегчается благодаря наглядному использованию информационных моделей на графах. Поэтому целесообразно познакомить детей с теорией и способами решения задач при помощи графов.

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

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

Граф на рис. 1 изображает схему дорог между селами A, B, C, D, E и указывает их протяженности. [5] По схеме можно определить, какие села расположены наиболее далеко друг от друга и какая дорога между ними будет кратчайшей. (Ответ: наиболее далеко друг от друга расположены села B и C: кратчайшее расстояние между ними – 17 км)

Рис.1

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

«В шахматном турнире по круговой системе, по которой каждый участник встречается с каждым, участвуют 7 школьников. Известно, что на данный момент Ваня сыграл 6 партий, Толя – 5, Леша и Дима – по 3, Семен и Илья – по 2, Женя – 1. С кем играл Леша?» [6] Рис.2

Каждому игроку будет соответствовать вершина графа (рис. 2). Если два игрока встретились между собой, соединим соответствующие вершины линией – ребром графа. (Ответ: Леша играл с Толей, Ваней и Димой)

Вторым видом графа является иерархия – расположение частей или элементов целого в порядке от высшего к низшему. Таким образом удобно изображать иерархические системы, элементы которых находятся в отношениях "является разновидностью", "входит в состав" и других отношениях подчиненности. Граф иерархической системы называется деревом. Отличительной особенностью дерева является то, что между двумя его вершинами существует единственный путь. Деревья не содержат циклов и петель. Простейшими иллюстрациями дерева может быть графическое представление решения арифметического выражения 5 * (3 + 7) * (8 - 2) по действиям [1] (рис.3), схема аппаратного обеспечения компьютера или классификация частей речи [2].

Рис. 3

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

Блок-схема – это тоже граф, отражающий последовательность выполнения действий. Его вершины называют отдельные действия и изображаются определенными геометрическими фигурами, а связи – дугами [2].

Часто используют графы для решения логических проблем, связанных с перебором вариантов [1]. Наглядный пример такого перебора описан в басне И. А. Крылова «Квартет». «Расселись, начали квартет. Он все-таки на лад нейдет». Сколько всего могло быть вариантов расположения незадачливых музыкантов, если Мишка всегда сидел на своем месте? (Ответ: 6 (см. рис. 4))

Рис. 4

Графы можно использовать и для наглядного решения задач о переливаниях (рис. 5). «Имеется 12 пинт меда в сосуде емкостью 12 пинт и два пустых сосуда емкостью 8 и 5 пинт. Каким образом можно отмерить ровно половину меда?»[3] [4]

Рис. 5

СПИСОК ЛИТЕРАТУРЫ:

1. Босова Л.Л. Информатика и ИКТ: Учебник для 7 класса – М.: БИНОМ. Лаборатория знаний, 2009.

2. Босова Л.Л. Информатика и ИКТ: Учебник для 6 класса – 2-е изд. – М.: БИНОМ. Лаборатория знаний, 2010.

3. Босова Л.Л. Информатика и ИКТ: Учебник для 5 класса – 3-е изд. – М.: БИНОМ. Лаборатория знаний, 2011.

4. Энциклопедический словарь юного математика / cост. А.П.Савин. – М.: Педагогика, 1989.

5. Демонстрационный вариант ГИА по информатике 2011.

6. http://mmmf.msu.ru/vecher/circles/z5/10.html