Графовое моделирование структур решений задач как средство их систематизации

Математические структуры и моделирование 2004, вып. 14, с. 128-139

УДК 519.17.00157:53

Н.П. Быкова, Н.Г. Рыженко

ГРАФОВОЕ МОДЕЛИРОВАНИЕ СТРУКТУР РЕШЕНИЙ ЗАДАЧ КАК СРЕДСТВО ИХ СИСТЕМАТИЗАЦИИ

В психолого-педагогических исследованиях широко применяются методы системно-структурного и количественного анализа. Среди этих методов важное место занимают математические модели. Специфика моделей, по отношению к другим средствам исследования, состоит в том, что модели являются «формой научной абстракции особого рода» [4, с. 282], обеспечивающей предметнонаглядное изображение скрытых закономерностей, особым средством «символизации в научно-теоретическом мышлении» [4, с. 226]. Кроме того, модель является отражением общего в изучаемых явлениях, поэтому моделирование представляет собой не частный приём усвоения знаний, а один из общих методов познания, применяемый в самых различных областях.

«Моделирование в теоретическом исследовании служит также задаче конструирования нового, не существующего ещё в практике» [9, с. 136-137]. Упрощая изучаемый объект, модель даёт возможность выделить исследуемые отношения. Для определения меры соответствия модели реальному объекту используются понятия изоморфизма и гомоморфизма [5]. Изоморфизм создаёт возможность замены объекта его моделью в целях исследования.

Задача как объект исследования представляет собой целостную, сложную систему. Понятие «сложная система» относится к общенаучным понятиям. Однако в настоящее время общепринятого определения этого понятия не существует [3]. «Чаще всего оно дается на структурном уровне (большое количество взаимосвязанных и взаимодействующих между собой элементов, обеспечивающих выполнение некоторой достаточно сложной функции)» [19, с. 65]. Изучение с позиций системно-структурного анализа структуры задачи и её решения создаёт объективную основу для определения сложности задачи и её места в соответствующей системе задач.

© 2004 Н.П. Быкова, Н.Г. Рыженко

Омский государственный аграрный университет Омский государственный педагогический университет

1. Задача как объект моделирования

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

Можно считать общепризнанным, что понятие «задача» может быть рассмотрено на структурном и функциональном уровнях. На структурном уровне задача рассматривается «как сложная дидактическая система», «компоненты которой (заданная и решающая система) состоят из находящихся в динамической зависимости элементов: предмета, условия и требования задачи, с одной стороны, методов, способов и средств ее решения - с другой» [12, с. 16]. Каждый компонент системы представляет собой самостоятельную систему, обладающую специфическими функциями и особым назначением.

Рис. 1.

Заданная система содержит условия и требования, данные и искомые величины, которые составляют содержание задачи, и сюжетную оболочку (форму), в которой заключено содержание. «Характер отношений между условием и требованием раскрывается путем использования определенного аппарата, в частности, устанавливается логическая или математическая функциональная зависимость» [12, с. 18]. При решении задач используются алгоритмические и эвристические методы, причем на определенных этапах преобладает либо тот, либо другой метод. Методы, способы, средства, приемы решения составляют решающую систему задачи. «Известны два типа структур в описании решения задач: внешняя и внутренняя. Внешняя структура описывает решение задачи через логические схемы, алгоритмические и эвристические предписания, тем самым определяя последовательность преобразований заданной системы. Использование мыслительных операций предполагает построение внутренней структуры» [17, с. 85]. Структура задачи представлена на рис. 1.

Таким образом, решающая система имеет внешнюю и внутреннюю структуру, внешняя структура решающей системы задачи определяет структуру решения задачи. Структура решения задачи отлична от структуры задачи и является основой такой важной характеристики задачи, как понятие «сложность». Структура решения задачи — это отношения между элементами, установленные

129

по заданным признакам. Множество элементов, входящих в структуру решения задачи, образуют состав решения задачи. Так как структура решения задачи — это есть зафиксированные некоторым способом алгоритмы её решения, то множество элементов, входящих в структуру решения задачи, задаются посредством порождающей процедуры. «Порождающая процедура — это процедура, которая, будучи запущенной, порождает некоторые объекты, являющиеся элементами определяемого множества» [11, с. 21].

Характеризуя понятие элемента, И.В. Блауберг и Э.Г. Юдин отмечают, что «... элемент — единица, свойства и функции которой определяют её место в рамках целого. Причём эти свойства и функции являются в известных пределах взаимоопределяющими со свойствами целого, есть свойства целого и не могут быть поняты без учёта хотя бы некоторых свойств элементов и наоборот» [2, с. 61]. В структуре решения физической задачи в качестве составляющих элементов (концептов) выступают физические понятия и суждения, связанные внутренними отношениями. Отношения являются внутренними, т. к. определяются только структурными элементами решения задачи.

«Моделирование по своей логической структуре напоминает умозаключение по аналогии.... Вывод по аналогии о некоторых свойствах модели может быть экстраполирован на оригинал только в том случае, если отношения являются внутренними» [7, с. 107]. А.И. Уемов установил, что «если для определения отношений элементов системы нет необходимости выходить за её пределы, т.е. отношение определяется только соотносящимися объектами, то оно будет обязательно внутренним, а сама система будет называться замкнутой или полной» [18, с. 73].

Отношения являются базовыми средствами для построения подавляющего большинства математических моделей, используемых при решении практических задач. Для моделирования отношений широко используются графы или родственные им объекты. «Между понятием графа и понятием отношения имеется глубокая связь — в сущности, это равнообъёмные понятия» [11, с. 189]. В теории интеллектуальных систем используется понятие «концептуальная модель», которое образуется из двух понятий: «модель» и «концепт» (лат. conceptus - понятие). Тогда «система в виде совокупности понятий (концептов), определяющих моделируемый объект, и отношений между понятиями (концептами) называется концептуальной моделью» [10, с. 126].

H. А. Жигачёва проводит аналогию между понятиями «концептуальная модель» и «решение сюжетной задачи»:

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

2. И в той и в другой системах в качестве элементов выступают понятия (концепты).

130

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

4. Концептуальная модель — это модель отношений. Можно дефинировать: математической моделью решения сюжетной задачи является кортеж (М; i?i, i?2,..., i?m), где М — множество концептов (величин и их значений, результатов разностного

или кратного сравнения двух значений одной и той же величины), a R\, і?2,..., Rm — внутренние отношения на этом множестве (не обязательно бинарные) [8, с.46].

Основы графового моделирования отношений рассмотрены Ю.А. Шрейдером

[21].

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

Основы моделирования структур решений алгебраических задач с помощью графов изложены в работах Н.Г. Рыженко, Н.А. Жигачевой [7,14]. Рассмотрим применение этого метода для систематизации физических задач по сложности их решения. Заметим, что в дальнейшем мы будем исследовать только структуру решения задачи, которая отлична от структуры задачи.

2. Графовое моделирование структур решений физических задач

Графовое моделирование как одно из направлений математического моделирования применяется, когда исследуемые объекты обладают структурностью. Графовые модели, являясь структурными моделями, удовлетворяют условию соответствия: каждый элемент модели поставлен в однозначное соответствие единственному элементу в структуре моделируемого объекта (т.е. в структуре решения задачи). Таким образом, существует изоморфизм внутренней конструкции структурной модели и моделируемого объекта. Графом G(V,E) называют совокупность двух множеств - непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элементов множества V (Е - множество ребер): G(V, Е) =< V]E >,V ^0,ВсУ х V, Е = Е~х. Если в графе ориентировать все ребра, то получится орграф, который называется направленным. Самым распространенным классом графов являются деревья. Ориентированные (упорядоченные) деревья являются абстракцией иерархических отношений. Ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами:

1. Существует единственный узел, полустепень захода которого равна нулю.

131

Он называется корнем дерева.

2. Полустепень захода всех остальных узлов равна 1.

3. Каждый узел достижим из корня. (Для орграфа число дуг, исходящих из вершины, называется полустепенью исхода, а входящих — полустепенью захо-да).

Для дерева существует несколько числовых характеристик, одна из которых характеризует сложность конечного дерева. Нахождение сложности дерева покажем на конкретном примере (рис. 2).

1

Рис. 2.

Сложность вершины 1: о\ = 3 х 9 = 27, где 3 - число дуг, выходящих из 1, 9 -число всех вершин, включая и саму вершину 1. Аналогично, а2 = 1 х 4 = 4, сг3 = 2 х 3 = 6, а4 = 2 х 3 = 6. Суммарная сложность всех вершин и дает сложность дерева: а = о\ + сг2 + сг3 + од = 27 + 4 + 6 + 6 = 43. Таким образом, структура решения задачи может быть представлена последовательностью стереотипных связей (методом пошагового наращивания дерева графа). Сложность вершины графа равна произведению количества нижележащих вершин, включая и саму вершину X, на число дуг, входящих в X или выходящих из X : а (X) = пх • тх. Сложность дерева определяется как суммарная сложность всех его вершин:

a{D)=

Хем

Более подробно с этим и с другими понятиями в теории графов можно ознакомиться в [1 , 13]. Деревом моделируются лишь бинарные отношения, в задаче же отношения в основном тернарные.

Л.М. Фридман [20] выделил следующие виды отношений, связывающих величины и их значения: отношения соединения, отношения отнимания, отношения сравнения (если величина задана двумя своими значениями); разностное отношение или кратное отношение двух значений величин, отношение разбиения (разделения), отношение-зависимость. Для моделирования тернарных отношений вводится понятие семантического дерева [7], которое отличается от

132

и

t

Рис. 3.

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

Задача 1. Товарный поезд идет со скоростью 36 км/час. Какое расстояние он пройдет за 2 часа?

Предметная область решения этой задачи состоит из трех величин: S - расстояние, значение этой величины неизвестно и является искомым; v - скорость, t - время, значения этих величин известны. Величины и их значения образуют состав решения задачи (элементы решения задачи). Эти элементы решения задачи связаны между собой тернарным соотношением равенства: S = v • t , которое и образует структуру решения задачи.

Структура решения задачи наглядно изображается в виде семантического дерева (рис. 3). Дерево называют семантическим, т.к. в каждую вершину дерева привнесена некоторая семантическая информация (величины и их значения). Эту графовую модель можно перемоделировать в знаковую (решающую модель): S = v-t = 36*2 = 72км. По этой модели можно найти решение и взаимно обратных задач: v = S/t,t = S/v. Этот граф (дерево) называется графом зависимости.

Задача 2. Товарный поезд идет со скоростью щ = 36 км/час, спустя время т = 30 мин. с той же станции по тому же направлению вышел экспресс со скоростью г?2, в 2 раза большей, чем щ. Через какое время после выхода товарного поезда и на каком расстоянии S от станции экспресс нагонит товарный поезд?

В состав решения задачи входят три величины: Д v) t (основные). Кроме них есть еще вспомогательные значения: > Щ в 2 раза - значение кратного

сравнения двух значений величины скорости, Д > £2 на т = 30 мин - значение разностного сравнения двух значений величины времени. Следовательно, состав решения задачи содержит основные величины и их значения, которые связаны между собой тернарным отношением равенства S = v • t и моделируются графом зависимости и вспомогательные величины и их значения: значение

133

а)граф кратного сравнения

б) граф разностного сравнения

Рис. 4.

кратного сравнения Ц2 = 2щ) и значение разностного сравнения (t2 = Ц — т). Эти соотношения также являются тернарными отношениями равенства. Следовательно, структура решения задачи состоит из следующих соотношений: S = v • С v2 = Vi • ф где d = 2, t2 = h — т. Последние два соотношения моделируются графами, приведенными на рис. 4 а) и б).

В задаче рассматриваются две ситуации: равномерное движение товарного поезда и равномерное движение экспресса. Целесообразно две заданные ситуации моделировать двумя деревьями, которые образуют лес. При этом нужно учитывать то, что пройденные расстояния товарным поездом и экспрессом одинаковы, т.е. Si = S2 = S (рис. 5). Перемоделируем графовую модель в знаковую. Для этого опишем графы «сверху вниз».

1. S = Vi • Ц 2uS1 = S2 = S

3. S = V2 • t2

4. v2 = Vi • d

5. t2 = h - r

6. S = V\ • d • (Ц — т) знаковая (решающая) модель

7. Щ • h = щ • d • (Ц — т) щ * h = щ • d • ti — Vi • d • t щ • d • Ц — щ • Ц = щ • d • t

t\ = V\ - d - tj{v\ - d — V\) = 1 час.

s

s

Рис. 5.

134

S = V\ • t\ = 36 km.

Сложность леса находится как суммарная сложность деревьев, его составляющих. Сложность структуры решения задачи отождествляется со сложностью дерева или леса, которые являются моделями структуры решения задачи. Сложность графовой модели (рис. 5): а = о\ + сг2, где о\ - сложность дерева, изображенного на рис. 5 а), о2 - сложность дерева, изображенного на рис. 5 б). о\ = 2 х 3 = 6, где 2 - число дуг, входящих в вершину А, 3 - число всех вершин, включая и саму вершину S.

Аналогично о2 = cr(S') + o-(v2) + cr(t2), где: a(S) = 2 х 7 = 14 - сложность вершины А; a(v 2) = 2хЗ = 6- сложность вершины г?2; сг(і2) = 2хЗ = 6- сложность вершины £2, тогда о2 = 14 + 6 + 6 = 26 - суммарная сложность дерева.

Сложность леса: а = 6 + 26 = 32.

Таким образом, сложность структуры решения задачи а = 32.

При решении задач возникает необходимость введения еще некоторых видов графовых моделей. По двум известным значениям одной величины найти третье (неизвестное) значение этой же величины. Например, относительная скорость может находиться по следующим соотношениям: v = V\ + v2) v = V\ — v2) которые моделируются графами (рис. 6 а) и 6 б)).

Рис. 6. Рис. 7.

Графы зависимости, кратного и разностного сравнений, суммирования и вычитания называют семантическими графами I порядка сложности а = 6 [7]. Они являются теми структурными элементами, которые позволяют моделировать структуру решения любой задачи. Довольно часто в структуре решения задачи встречаются соотношения деления с = а/Ь или возведения в степень. Можно было бы их свести к соотношению умножения, но тогда граф получается более сложный. Поэтому рассмотрим еще графы деления и возведения в степень (рис. 7 а) и б)).

Задача 3. На изделие, поверхность которого 20ст2, нанесен слой серебра толщиной 1 мкм. Сколько атомов серебра находится в покрытии?

Аналогичные рассуждения приводят к выявлению структуры решения задачи. Граф структуры решения задачи изображен на рис. 8.

Решение задачи:

1. N = Na • v

135

N

2. v = т/р

3. т = р • V 4 .V = S-d

т

5. N = Na • — = Na

р

P-V

р

= NA

р' S ' d

p

Сложность структуры решения задачи а = cr(N) + cr(v) + а(т) + cr(V) = 2х9 + 2х7 + 2х5 + 2хЗ = 48. Отметим, что действие моделирования расширяет выбор методов решения задачи. Это может быть графовый метод решения. Переход же от графовой модели к знаковой может осуществляться двумя способами, что и определяет два общепринятых метода решения задачи:

1) аналитико-синтетический метод решения задачи, при котором описание графа идёт «сверху вниз»;

2) синтетический метод решения задачи, при котором описание графа идёт «снизу вверх».

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

136

3. Система задач в обучении

Чтобы деятельность по решению задач обеспечивала заданный уровень усвоения содержания, необходимо, чтобы система задач удовлетворяла дидактическим принципам. В основу построения дидактической системы задач положены следующие принципы: целостность, структурность, иерархичность, многоуров-невость, множественность и другие. Систематизация учебных задач по степени возрастания сложности их решения соответствует такому системному принципу, как иерархичность, т.е. последовательность расположения задач в системе должна осуществляться на основе упорядоченности. Сложность предъявляемых учащимся задач должна находиться в зоне их ближайшего развития, т.

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

Рис. 9. Сравнительная характеристика сложности задач по теме «Молекулярная физика и

термодинамика».

Структурный анализ задач по молекулярной физике и термодинамике, а также по электромагнетизму, проведенный нами в сборниках задач по физике для средней школы (А.П. Рымкевич, П.А. Рымкевич [15], А.П. Рымкевич [16],

В.П. Демкович, Л.П. Демкович [6]), выявил:

1) распределение задач по сложности решения (в процентах от общего количества задач), а - сложность решения задачи.

Диаграмма распределения задач по сложности решения по теме «Молекулярная физика и термодинамика» приведена на рис. 9.

137

70%

60°/o -50% _ 40% -30% -20% -10% -

38,83%

36,84%

39,23%

%

31,91% 21,28%

4,79%

2,13%

1,06%

53,43%

3,83%

0,96% 0,96%

26,96%

О <7 = 0 - 40 Ш <7 =40 80 0 <7 =80 - 120  (7 = 120-160 D (7= 160 200  (7 =200 240

12,26%

6,86%

0,49% 0%

Сборник задач 1

Сборник задач 2

Сборник задач 3

Рис. 10. Сравнительная характеристика сложности задач по теме «Электростатика,

постоянный ток, электромагнетизм».

Диаграмма распределения задач по сложности решения по теме «Электростатика,постоянный ток, электромагнетизм» приведена на рис. 10.

2) большое число повторов задач малой сложности.

3) с повышением сложности структуры решения уменьшается число соответствующих задач.

Очевидно, что проблема построения оптимальной дидактической системы физических задач решается с помощью метода математического моделирования.

4. Заключение

Подводя итог всему вышеизложенному, можно сделать следующие выводы:

1. Графовое моделирование структуры решения задач по физике позволяет ввести количественный критерий сложности структур решения физических задач.

2. Количественный критерий сложности структуры решения задач позволяет систематизировать задачи по степени возрастания сложности структур их решений.

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

Литература

1. Березина Л.Ю. Графы и их применение. Пособие для учителей. М.: Просвещение, 1979. 191 с.

2. Блауберг И.В., Юдин Э.Г. Становление и сущность системного подхода. М.: Наука, 1973. 270с.

138

3. Бусленко Н.П. Моделирование сложных систем. М.: Наука, 1978. 400 с.

4. Давыдов В.В. Виды обобщения в обучении. М.: Педагогика, 1972. 424 с.

5. Гастев Ю.А. Гомоморфизмы и модели. М.: Просвещение, 1975. 118 с.

6. Демкович В.П., Демкович Л.П. Сборник задач по физике. 10-11 классы: Учебное пособие для общеобразовательных учреждений. М.: ООО «Издательство АСТ», 2001. - 253 с.

7. Жигачева Н.А., Рыженко Н. Г. Графовое моделирование структур решений сюжетных задач // Математические структуры и моделирование. 1999. Вып.4. С. 104 - 117.

8. Жигачёва Н.А. Графовое моделирование структур решений сюжетных задач в курсе алгебры 7 класса: Дис. ... канд. пед. наук. - Омск, 2000. 150 с.

9. Загвязинский В.И. Методология и методика дидактического исследования. М.: Педагогика, 1982. 160 с.

10. Ладенко И.С., Разумов В.И., Теслинов А.Г. Концептуальные основы интеллектуальных систем (систематизация методологических основ интеллектики) / Отв. ред. И.С.Ладенко. - Новосибирск: СО РАН Ин-т Философии и Права, 1994. 270 с.

11. Новиков Ф.А. Дискретная математика для программистов. Санкт-Петербург: Питер, 2001. 304 с.

12. Бухарова Г.Д. Теоретико-методологические основы обучения решению задач студентов вуза. Монография. Екатеринбург, изд. Урал. Гос. проф.- пед. ун-та , 1995. 136 с.

13. Оре О. Теория графов. М.: Наука, 1968. 352 с.

14. Рыженко Н.Г., Жигачёва Н.А. Структуризация и систематизация сюжетных задач по сложности их решения // Вестник Омского Университета. 1998. - N.4.

С.111 - 114.

15. Рымкевич А.П., Рымкевич П.А. Сборник задач по физике. М.: Просвещение, 1982. 191 с.

16. Рымкевич А.П. Физика. Задачник. 10-11 классы: Пособие для общеобразовательных учебных заведений. М.: Дрофа, 2002. 192 с.

17. Тихомиров О.К. Структура мыслительной деятельности человека. М.: МГУ, 1968. 304 с.

18. Уемов А.П. Системы и системные исследования. М.: Мысль, 1970. С.64-86.

19. Флейшман Б.С., Брусиловский П.М., Розенберг Т.С. О методах математического моделирования сложных систем. Системные исследования. Методологические проблемы. Ежегодник. М.: 1982. С.65-79.

20. Фридман Л.М. Логико-психологический анализ школьных учебных задач. М.: Педагогика, 1977. 208 с.

21. Шрейдер Ю.А. Гавенство, сходство, порядок. М.: Наука, 1971. 254 с.

139