Информационно-образовательный портал СОДРУЖЕСТВА НЕЗАВИСИМЫХ ГОСУДАРСТВ
ИНФОРМАТИЗАЦИЯ ОБРАЗОВАНИЯ
И ДИСТАНЦИОННОЕ ОБУЧЕНИЕ В СНГ
Информационно-образовательный портал СОДРУЖЕСТВА НЕЗАВИСИМЫХ ГОСУДАРСТВ  

Страны
Азербайджанская Республика
Республика Армения
Республика Беларусь
Республика Казахстан
Кыргызская Республика
Республика Молдова
Российская Федерация
Республика Таджикистан
Туркменистан
Республика Узбекистан
Украина

Типы материала
Информационно-коммуникационные технологии
Дополнительные информационные материалы
Нормативно-правовое обеспечение
Организация и методики обучения
Экономика образования
Межгосударственное сотрудничество
Образовательные центры
Методики обучения
Межвузовское сотрудничество
Повышение квалификации
Международные проекты и гранты, конкурсы
Конференции, симпозиумы, семинары и др.
Библиотека
 
Журнал «Вестник РУДН» серия «Информатизация образования»
 
2014, №4
2014, №3
2014, №2
2014, №1
2013, №4
2013, №3
2013, №2
2013, №1
2012, №4
2012, №3
2012, №2
2012, №1
2011, №4
2011, №3
2011, №2
2011, №1
2010, №4
2010, №3
2010, №2
2010, №1
2009, №4
2009, №3
2009, №2
2009, №1
2008, №4
2008, №3
2008, №2
2008, №1
2007, №4
2007, №3
2007, №2-3
2007, №1
2006, №1(3)
2005, №1(2)
2004, №1
Научные и специальные электронные ресурсы
Учебная, научная и специальная литература
Комиссия по дистанционному обучению совета по сотрудничеству в области образования государств-участников СНГ
Новости

СУБОРДИНАЦИОННЫЕ ОТНОШЕНИЯ В МЕТОДИКЕ ИЗУЧЕНИЯ ПОНЯТИЯ ИЕРАРХИЧНОСТИ


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

Текст документа

Введение. Предыдущая публикация [1], в которой обсуждалась формализация иерархических отношений в качестве методической основы изучения понятия иерархии, определила ряд базовых свойств, полезных для углубленного преподавания предмета. Была отмечена относительная независимость классификационной и субординационной иерархичности. Основное внимание в той статье уделено классификационным отношениям, т.е. эквивалентностям. В этом плане предлагаемый ниже материал можно рассматривать как продолжение, которое заостряет внимание на формализации субординационной иерархичности и на сопоставлении двух видов иерархий. По-прежнему мы придерживаемся взгляда на построение и использование иерархий, согласно которому необходимо всегда знать, какое отношение лежит в основе иерархии, каким образом оно выделяет иерархическую структуру системы. Это положение должно лежать в основе какого-бы то ни было инструментария автоматизации оперирования иерархически??и структурами.

 

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

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

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

Определение 5.    Рефлексивное и транзитивное замыкания отношения. Пусть M— множество с бинарным отношением ?на нем. Тогда

a)            ?0: aM(a?0a)— рефлексивное доопределение ?;

b)           ?1 = ?;

c)            ?i, i целое, такое, что для всех i>1:
a,b,cM(((a?b) & (b?i-1c))(a?ic)) — индуктивное определение i-ой степени ?;

d)           ?+ = ?1?1?2 … — транзитивное замыкание ?;

e)            ?* = ?0?1?2 … — рефлексивное и транзитивное замыкание ?.

Определение 6.    Отношения порядка. Пусть ?— отношение на множестве M(a?baмладшеb, или bстаршеa). Тогда

a)    если

              I.     a,b,cM((a?b) & (b?c))(a?c) — транзитивность,

           II.     aMa?a — рефлексивность,

то ?называется отношением предпорядка (или квазипорядком).

b)   если

              I.     a,b,cM((a?b) & (b?c))(a?c) — транзитивность,

           II.     a,bM((a?b) & (b?a))(a=b) — антисимметричность,

        III.     aMa?a — рефлексивность,

то ?называется отношением нестрогого частичного порядка (или нестрогим порядком).

c)    если

              I.     a,b,cM((a?b) & (b?c))(a?c) — транзитивность,

           II.     a,bM(a?b)¬(b?a) — асимметричность,

то ?называется отношением строгого частичного порядка (или строгим порядком).

d)   множество, на котором определен частичный порядок, называется частично упорядоченным.

e)    отношение порядка ?, являющееся полным, т.е. таким, что

a,bM(a?b)?(b?a)

называется полным порядком. Множество, на котором определен полный порядок, называется полностью упорядоченным, или цепью.

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

Определение 7.    Отношения субординации, главный элемент, конкуренция, листья. Пусть Mконечное множество с бинарным отношением ?на нем и непустое множество G = {g1,..., gn}M, удовлетворяющие условиям:

a)           gGaM((ag) ¬(g?  a)) недостижимость элемен­тов Gот элементов M;

b)           aM\\GgG(a?+g) достижимость всех элементов множества M\\Gот элементов из G;

c)           a,bM (a?*b) ¬(b? a)ацикличность.

Отношение ?называется отношением субординации.

Множество G называется множеством главных элементов. Если G содержит более одного элемента, то ?называется отношением субординации с конкуренцией главных элементов.

Множество L ={l1,..., lk}M всех элементов, называемых листьями, которые минимальны в смысле отношения субординации, т.е. удовлетворяют условию

d)          lL¬aM(a?l)недостижимость элемен­тов Mот L.

Если условие

e)           aM (aG) bM (a?b) полнота G,[1]

верно хотя бы для одного aи для более чем одного b, то отношение ?называется множественным отношением субординации (с конкуренцией или без нее). В противном случае оно называется простым.

Непосредственно из определений следуют

Утверждения 3–7.

3.    Среди элементов есть листья, т.е. L≠ø.

4.    Отношение субординации ? является антирефлесивным, т.е.

aM¬(a?a)

5.    В нетривиальных случаях, т.е. когда неверно, что M=G=L, (т.е. в M нет сравнимых по отношению ?элементов) транзитивное замыкание ?* отношения ? приводит к множественной субординации.

6.    Отношения ?* и ?+ являются отношениями частичного порядка: строгого в первом случае и нестрогого во втором.

7.    Для любого подмножества Mмножества M отношение, унаследованное от ?, является отношением субординации, которое с точностью до множества главных элементов совпадает с исходным отношением. Множество Gможет измениться следующим образом:

a.    G’= GM, если достижимость элемен­тов M отG сохраня­ется (усло­вие (b) из определения 5);

b.    G’= (GM) Gnew, где Gnew множество новых элементов, недостижимых от G(для них усло­вие (a) определения 5 было неверным, но стало верным на множестве M).

Определение 8.    Усечение отношения субординации, консервативность усечения

В обозначениях утверждения 7 подмножество Mмножества M с отношением субординации, унаследованным от ?, называется консервативным усечением ?, если выполнено условие (a). При выполнении условия (b) усечение называется неконсервативным.

Вводятся понятия меры консервативности усечения: это мощность множества Gnew и относительной меры консервативности усечения: это мераконсервативностиусечения, деленная на мощность G.

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

Для доказательства достаточно множество всех максимальных элементов для отношения « объявить множеством главных элементов. Из-за транзитивности отношения порядка это будет максимально большое по числу связей отношение субординации, соответствующее транзитивному замыканию любого другого. Можно строить субординацию с меньшим числом связей, если из отношения « последовательно исключать пары, являющиеся следствием транзитивности, т.е. такие (a, b), для которых существует c, удовлетворяющее условию (a«с)&(с«b). Они всегда существуют, если (a«с) и (с«b), в силу транзитивности «. Этот процесс можно прервать в любой момент или продолжать до тех пор, пока все рассматриваемые пары (a, b)не будут удалены. В последнем случае получается минимальное по числу связей отношение субординации, транзитивное замыкание которого совпадает с «. Индукцией по числу элементов M доказывается единственность минимального отношения субординации, т.е. независимость результата от порядка удалений пар (a, b).

Отношение субординации позволяет строго ввести следующее понятие.

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

Определение отношения ?гарантирует, что в обобщенной древовидной структуре:

§  не может быть циклов (как и в дереве);

§  имеются элементы-вершины, у которых нет младших элементов, именуемые листьями (как и в дереве). Каждому листу обобщенной древовидной структуре соответствует элемент из L, и наоборот: каждому элементу из L соответствует лист структуры;

§  может появиться несколько вершин, в которые не ведут дуги, именуемые главными вершинами  (аналоги корней деревьев), они в точности соответствуют главным элементамM;

§  в отличие от дерева в случае множественного отношения субординации элемент-вершина может иметь несколько непосредственно старших вершин (для такого элемента a, условие (e) в определении субординации верно с несколькими b). Структура, в которой есть хотя бы один такой элемент, называется множественной (что соответствует понятию множественной субординации);

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

§  обобщенная древовидная структура, которая строится по любому усечению отношения субординации ?, является обобщенной древовидной структурой на множестве M, определяемом усечением.

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

Предварительно введем следующие п??нятия и обозначения.

Определение 10.     Цепи, полные цепи, максимальные полные цепи, высота. Пусть Mмножество элементов с отношением субординации ? и a произвольный элемент M. Тогда

§  последовательность элементов M α = v1, …, vt , такая, что v0=a, vi?vi+1, i{1,…,t-1}, называется цепью элемента a. Длина цепи обозначается | α |;

§  цепь называется полной, если vtG. Множество всех полных цепей элемента a обозначается как C(a);

§  h(a) — максимальная длина цепей изC(a), называется высотой a;

§  Cmax(a множество полных цепей, начинающихся с элемента a, длина которых максимальна и равна h(a);

§  если S = {a1,..., an}, то Cmax(S) определяется как множество полных цепей, начинающихся с элементов из S, длина которых максимальна и равна h(S) = max(h(a1),...,h(an));

§  максимум h(a)для всех aM называется высотой M(обозначается какh(M)).

Если a — главный элемент, тоC(a) является множеством, состоящим из единственной одноэлементной цепи α = a. В случае простого отношения субординации с конкуренцией или без нее C(a) содержит ровно одну полную цепь для каждого a из M, а h(a) всегда равно длине самого длинного пути в графе от вершины, представляющей a, до соответствующей вершины главного элемента. Только для множественной субординации C(a) — нетривиальное множество: для a, которые имеют несравнимые транзитивно старшие элементы, мощность C(a) не меньше их числа. Мощность множества C(v) всех цепей, включающих в себя такие элементы (т.е. α=v1, …, vt, у которых v1=v, представимы в виде α=v1, …, vi, a, vi+2, … vt), больше единицы.

Определение 11.                   Уровни субординационной иерархии и субординационная иерархическая структура. Пусть M— множество с отношением субординации ?, каждому элементу x которого приписано целое число rx. Тогда если

a,bM (a?b)(ra<rb),

то M считается разбитым на уровни субординационной иерархии: все x из M такие, что rx=r отнесены к уровню с номером r.

Пусть w = a0, …, a|w|-1, — полная цепь элементов M из Cmax(a0), у которой a0L— лист (т.е. bM ¬(b?a0)и |w|=h(M)).

Если минимальное r, для которого существует x, отнесенное к уровню с номером r, равно нулю, а максимальное — h(M)-1, то разбиение субординационной иерархии на уровни называется правильным.

Пара <M; ?>, где ?отношение субординации на множестве M, называется субординационной иерархической структурой, или иерархией с конкуренцией или без нее (в зависимости от мощности множества главных элементов G), если на M определено правильное разбиение на уровни.

Утверждения 9–10.

9.    Определение правильности корректно, т.е. не зависит от выбора w.

10.    К каждому уровню r в пределах от минимального (ноль) до максимального (h(M)-1), отнесен по крайней мере один элемент из M. (Такими элементами являются все a0, …, a|w|-1, последовательно относимые к определяемым уровням; у других элементов M, вообще говоря, имеется некоторая свобода выбора уровней).

Определение 12.     Распределение элементов по уровням, согласованное с отношением субординации

Пусть xM, а L(x) и H(x) — множества элементов из M с отношением субординации ?, определяемые следующим образом:

L(x) = {a | (a?x) & a отнесено к уровню ra};

H(x) = {b | (x?b) & b отнесено к уровню rb}.

L(x) = ø, если xL — лист, а H(x) = ø, если xG —  главный элементM.

Пусть xотнесен к некоторому из уровней rx, удовлетворяющих соотношению

maxL(x)<rx<minH(x),                                                                                                 (*)

где maxL и minH для xопределяются  следующим образом:

maxL(x) = maxra (aL(x)),                                  еслиL(x) ≠ ø,

                               -1,                                           еслиL(x) = ø,

minH(x) = minrb (aH(x)),                                   еслиH(x) ≠ ø,

                               |w|,                                          еслиH(x) = ø,

Тогда, если (*) выполнено для всех x из M, то распределение элементов по уровням называется согласованным с отношением субординации. Если оно нарушается хотя бы для одного x, то не выполняется условие определения 11, и распределение элементов по уровням считается несогласованным с отношением субординации.

Утверждение 11. Для любого отношения субординации существует распределение элементов по уровням, согласованное с отношением субординации. Значения maxL(x) и minH(x) играют роль ограничителей, пределов для уровней, на которых xможет  быть размещен корректно. В указанных пределах x может перемещаться (расставляться) по обобщенной древовидной структуре согласовано с отношением субординации. Оба предель­ные варианта иерархической структуры называются нормализованными, что отражено в следующем определении.

Определение 13.     Нормализованные субординационные иерархии. Пусть <M; ?> субординационная иерархическая структура. Если xM rx = maxL(x)+1, то об элементах M говорится, что они подтянуты вниз по уровням иерархии. Считается, что в этом случае иерархическая структура представлена своей нижней нормальной формой.

Если xM rx = minH(x)-1, то об элементах M говорится, что они подтянуты вверх по уровням иерархии. Считается, что в этом случае иерархическая структура представлена своей верхней нормальной формой.

Эти представления называются нормализованными.

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

Алгоритм 1.  Построение нижней нормальной формы иерархической структуры. Пусть M0 — подм??ожество M, состоящее из листьев, т.е. M0=L. Тогда M0 объявляется  нижним, нулевым уровнем иерархии множества M.

Множество M \\ M0 наследует отношение субординации ?. Подмножество M1=Lлистьевмножества M \\ M0 объявляется уровнем иерархии с номером 1 множества M.

Пусть для некоторого r≥0 M \\ M0\\...\\ Mr — непустое множество,наследующее отношение субординации ?. Подмножество Lлистьев этого множества, обозначаемое как Mr+1, объявляется следующим для r уровнем иерархии с номером r+1 множества M.

Если же M \\ M0\\...\\ Mr= ø, то Mrверхний уровень иерархии множества M.

Утверждение 10. Алгоритм 1 построения нижней нормальной формы иерархической структуры корректен (доказывается по индукции с применением утверждения 7 о том, что невырожденное подмножество субординационной структуры также является субординационной структурой).

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

Алгоритм 2.     Построение верхней нормальной формы иерархической структуры. Пусть M0 — подмножество M, состоящее из всех тех листьев M, которые начинают максимальные полные цепи, т.е. все цепи из Cmax(M). Тогда M0 объявляется  нижним, нулевым уровнем иерархии множества M.

Множество M \\ M0 наследует отношение субординации ?. Подмножество M1L множества M \\ M0, состоящее из всех тех листьев, максимальные полные цепи которых принадлежат Cmax(M \\ M0), объявляется уровнем иерархии с номером 1 множества M.

Пусть для некоторого r≥0 M \\ M0\\...\\ Mr — непустое множество,наследующее отношение субординации ?. Подмножество из тех листьев этого множества, которые принадлежат Cmax(M \\ M0\\...\\ Mr), обозначаемое как Mr+1, объявляется следующим для r уровнем иерархии с номером r+1 множества M.

Если же M \\ M0\\...\\ Mr= ø, то Mrверхний уровень иерархии множества M.

Утверждение 11. Алгоритм 2 построения верхней нормальной формы иерархической структуры корректен (доказательство не отличается от доказательства предыдущего утверждения).

С точностью до условия, налагаемого на листья, отбираемые для конструируемого уровня, алгоритм 2 повторяет предыдущий. Цепи из Cmax(M \\ M0\\...\\ Mr) — это минимум, который требуется для обеспечения корректности построения правильного уровневого разбиения M и размещения всех элементов по уровням:

§  если отложить размещение на уровне r+1 некоторого x из M \\ M0\\...\\ Mr, то это неизбежно увеличит число уровней сверх необходимого;

§  если на уровне r+1 дополнительно разместить какие-то иные элементы-листья из  M \\ M0\\...\\ Mr, то это будет означать подтягивание их вниз по иерархии, что и демонстрирует алгоритм 1, в котором все листья из указанного множества пополняют уровень r+1.

Это наблюдение указывает на возможные обобщения путем добавления к очередному уровню различных элементов-листьев, удовлетворяющих тем или иным условиям. В алгоритме 1 это условие тождественно истинного для всех листьев Lмно­жес­тваM \\ M0\\...\\ Mr, но не исключаются и более слабые условия, запрещающие некоторым из листьев размещаться на соответствующих уровнях, откладывая размещение до тех пор, пока это условие окажется невыполненным или их цепь не попадет в Cmax(M \\ M0\\...\\ Mr).

D

D

C

B

B

a) минимально низкие уровни для A и B                              b) максимально высокие уровни для A, B и F

C

E

E

A

0

1

2

3

0

1

2

3

A

F

F


Рис. 1 иллюстрирует возможность перемещения элементов по уровням. На нем элементы иерархической структуры M показаны квадратами, главные элементы — закрашенными квадратами, дуги, концы которых могут перемещаться, выделены пунктиром. Все дуги направлены снизу вверх: от вершины меньшего уровня к большему. Вершины C, D и E имеют более одной непосредственно старшей вершины, следовательно, показанная обобщенная древовидная структура является множественной.

 

Рис. 1. Вариантность распределения элементов по уровням иерархии

 

 

Из иллюстра­ции  видно, что A может быть размещен на одном из двух уровней 1 или 2, B — на одном из трех уровней 0, 1 или 2, а вариантность размещения F зависит от того, как размещена A: если A относится к уровню 1, то для F имеется только один (нулевой) уровень, в противном же случае она может быть размещена на уровне 0 либо 1 (показаны две крайние возможности).

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

До сих пор построение уровней задавалось таким образом, чтобы не нарушалась правильность уровневого разбиения M. В частности, поэтому было невозможно образование пустых уровней (получивших номера, но не имеющих элементов). Следование этому соглашению приводит к тому, что номер уровня для x не превосходит длины самой большой последовательности элементов, связанных отношением ?.

На практике нарушение соглашения как для главных, так и для других элементов не только возможно, но иногда и желательно. Пустые уровни трактуются как заготовки для принудительного размещения на них элементов, которое не будет противоречить требованию согласованности с отношением субординации. К появлению r+1-го пустого уровня приводит отказ от размещения на уровне r+1 всего LM \\ M0\\...\\ Mr. Также допустимо использование разбиенийM, для которых на некоторых уровнях размещаются не все элементы, требуемые правильностью. Это дает средство моделирования ситуаций, когда минимальность числа уровней содержательно не прослеживается. Так устроена реальная структура организации, которая по тем или иным причинам «раздувает» иерархию. Является ли это сигналом к рационализации структуры — вопрос интерпретации модели.

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

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

Утверждения 14–16.

14.    Пусть M– множество с отношением субординации ?. Тогда ?­­-1является отношением субординации, у которого множества G и L меняются ролями: для ?­­-1 множество главных элементов совпадает с прежним L, а множество листьев – с прежним G.

15.    Пусть <M;?> является невырожденной иерархической структурой, т.е. неверно, что она состоит только из непересекающихся цепей. Тогда ?­­-1 оказывается множественным отношением субординации. Наоборот: если <M;?­­-1> — невырожденная иерархическая структура, то исходное отношение субординации ? является множественным.

16.    Нормальные формы <M;?> и <M;?­­-1> меняются ролями: для <M;?­­-1> с точностью до обращения отношения ? нижняя нормальная форма <M;?> становится верхней, а верхняя — нижней.

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

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

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

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

Построение внешней классификационной иерархии исходило из определения множеств Μi, которые содержат элементы уровня Ki-1 (при i = 1 это исходные элементы системы, т.е. множество Μ) и новые классы. На множестве Μ1Μnможно определить следующее отношение субординации: между классами Ki-1 и Kiопределяетсяследующим образом: aKiстарше всех bKi-1, попадающих в класс эквивалентности a, и несравнимо с остальными cKi-1. Таким образом, верно

Утверждение 17. Определение отношения субординации по внешней классификационной иерархии корректно.

Отношение субординации дает распределение элементов множества Μпо уровням, т.е. строит полный набор непересекающихся подмножеств. Это канонические классы эквивалентности. Но можно строить и более мелкое дробление, объявляя в качестве классов эквивалентностей множества элементов, относящихся к общему уровню, которые находятся в отношении субординации к одному и тому же элементу более высокого уровня. В случае простой субординации классы будут непересекающимися и их набор полон по определению. Для множественной субординации приходится специально рассмотреть ситуации с элементами, имеющими более одного непосредственно старшего элемента. Полученные классы пересекаются, т.е. не дают эквивалентностей (см. обсуждение такой возможности расширения понятия иерархичности в [1]). Если по каким-либо причинам, такое построение нежелательно, можно выделить пересечения множеств, полученных по отношению субординации, в специальные классы, и тогда отношение эквивалентности восстанавливается.

Элемент, старший для некоторой (полной) совокупности элементов, становится обозначением класса, а если такая трактовка нежелательно, нужно позаботиться о специальных обозначениях новых классов, а также о классах, в которые будут попадать старшие элементы. Для множественных субординаций приходится вводить обозначения и для классов-пере­се­­че­ний. Следовательно, верно

Утверждение 18

Определение классификационной иерархии на основе эквивалентности всех тех элементов, которые находятся в отношении субординации к одному и тому же элементу или попадают в классы-пересечения в случае множественной субординации, корректно.

Рассмотренные свойства иерархий полезны для поиска сущностей реальных систем, отражающихся в их иерархических моделях. К примеру, изучая эффективность организационной структуры некоего коллектива, вы воссоздаете отношение подчиненности между сотрудниками. Естественно предположить, что оно должно быть отношением субординации. Чисто механически можно выстроить по нему классификационную систему. Сопоставление ее со структурой подразделений может выявить несоответствие, а это источник информации для анализа: почему такое случилось, осознано ли, оправдано ли отклонение от «естественной» схемы — ответы на эти и другие подобные вопросы помогут составить полезные рекомендации для руководства.

Возможно построение смешанных иерархий, когда для некоторого уров­ня i, определенного классификационной иерархией, отношение субординации устанавливается между классами Ki. В результате достигается укрупнение, сглаживающее неинформативные различия. Также возможны смешанные иерархии, которые начинают строиться как серия субординационных иерархий. Их вершинами служат некоторые выделенные (главные) элементы, которым подчиняются другие элементы, для которых, в свою очередь, указываются свои подчиненные и т.д. Процесс может оборваться в любой момент. Затем полученные листья и оставшиеся незадействованными элементы используются как база для классификации. Этот прием можно интерпретировать как создание подразделений под структуру их руководителей, когда деятельность сотрудников  нижних звеньев организации не персонифицируется на более ??ысоких уровнях. Здесь уместно использование отношения субординации с конкуренцией главных элементов.

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

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

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

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

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

С точки зрения методик преподавания инструментарий, поддерживающий оперирования иерархиями, весьма перспективен в нескольких аспектах:

·      На основе инструментария поддержки может разрабатываться широкий спектр задач в самых различных дисциплинах, имеющих дело с иерархически устроенной систематикой. Возможности преподавания с использованием иерархий всесторонне  исследованы В.В. Гриншкуном [4];

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

·      Моделирование в обучении позволяет показать варианты изучаемого, которые строятся достаточно быстро. Если модели конструируются самостоятельно, то реализуется обучение в деятельности, что, как хорошо известно, повышает эффективность обучения [5]. Но и тогда, когда модели к занятиям готовятся заранее, возможность показать предмет изучения с разных сторон расширяются;

·      Иерархическое моделирование способствует разработке качественных учебно-методических материалов. Оно дисциплинирует разработчика — не дает делать структурные ошибки, явно показывает пробелы в содержании и др. (этот аспект убедительно обсуждается в [6]).

 

ЛИТЕРАТУРА

 

[1] Скопин И.Н. Иерархические отношения — методическая основа изучения понятия иерархий // Вестник Российского университета дружбы народов. Серия «Информатизация образования». – 2014. – № 1. – С. 56–63.

[2] Скопин И.Н. Множественное структурирование данных // Программирование. – 2006. – Т. 32. – № 1. – С. 54–77.

[3] Скопин И.Н. Иерархичность и моделирование развивающихся систем // Проблемы системной информатики: сб. науч. тр. / Под ред. В.Н. Касьянова. – Новосибирск: Ин-т систем информатики им. А.П. Ершова СО РАН, 2010. – С. 188–214.

[4] Гриншкун В.В. Использование иерархических структур при подготовке педагогов в области информатизации образования // Известия Курского государственного технического университета. – 2008. – № 3 (24). – С. 32–35.

[5] Гальперин П.Я. Четыре лекции по психологии. – М.: Юрайт, 2000. – 112 с.

[6] Гриншкун В.В., Григорьев С.Г. Иерархические структуры в основе создания и применения электронных средств обучения // Сборник научных трудов математического факультета МГПУ. – М.: МГПУ, 2005. – С. 9–16.

 



[1] Существование по крайней мере одногоb, для которого выполняется условие (d), является следствием условий (a) и (b).


Автор оригинала: И.Н. Скопин
Источник оригинала: Журнал "Вестник РУДН" Серия «Информатизация образования», 2014, №2

Новости
16.06.2017

Российский университет дружбы народов объявляет о проведение первой волны вступительных испытаний среди иностранных граждан для обучения на программах магистратуры на контрактной основе. Первая ...

13.10.2016

26 октября-27 октября 2016 года Российский университет дружбы народов проводит Международную конференцию «Сетевые университеты и международный рынок труда (пространства БРИКС, СНГ, ШОС)».

19.05.2016

The Peoples’ Friendship University of Russia (PFUR) announces the beginning of admission of foreign citizens who graduated from Bachelor and Specialist Degree programs of PFUR and other Russian and ...

19.05.2016

Российский университет дружбы народов (РУДН) объявляет о наборе иностранных граждан -выпускников бакалавриата и специалитета РУДН и других российских и зарубежных ВУЗов на программы магистратуры на ...

11.12.2015

Проект рекомендаций Семинара-совещания научной общественности по проблемам международного научно-технического и образовательного сотрудничества