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

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

Типы материала
Информационно-коммуникационные технологии
Дополнительные информационные материалы
Нормативно-правовое обеспечение
Организация и методики обучения
Экономика образования
Межгосударственное сотрудничество
Образовательные центры
Методики обучения
Межвузовское сотрудничество
Повышение квалификации
Международные проекты и гранты, конкурсы
Конференции, симпозиумы, семинары и др.
Библиотека
 
Журнал «Вестник РУДН» серия «Информатизация образования»
 
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]

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

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

Определение 1. Отношение эквивалентности, классификационные иерархии.

Пусть Μ — множество произвольных элементов,?— некоторое бинарное отношение на нем (a?  bчитается как «a эквивалентноb»), удовлетворяющее следующим условиям:

a)    aM(a?  a) — рефлексивность;

b)   a,bM(a?  b b?a) — коммутативность;

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

Тогда ?называется отношением эквивалентности.

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

Заданное отношение эквивалентности однозначно разбивает Μ на классы эквивалентных элементов, т.е. строит так называемое фактор-множество Μ/?, элементами которого являются эти классы. И наоборот, любое разбиение Μна непересекающиеся подмножества порождает соответствующее разбиению отношение эквивалентности. Таким образом, классификация, исходящая из такого отношения, является одноуровневой. Для получения следующих уровней классификации нужно использовать другие отношения эквивалентности. Это построение делается ниже.

Определение 2. Уровни внешней классификации.

Внешняя иерархия множества Μ сотношением эквивалентности ?, или внешняя иерархическая структура, а также связанные с ней понятия определяются следующим построением. Μ пополняется дополнительными символами классов эквивалентностей, соответствующих отношению эквивалентности ? на исходном множестве Μ: Μ1 = ΜK1,
ΜK1 =ø, K1 — фактор-множество Μ/?. Исходное множество Μ— объявляется нулевым уровнем классификационной иерархии.

Далее, с помощью другого отношения эквивалентности ?1на K1, определяемого для K1 специально, строятся классы K2, надстраивающие следующий уровень иерархии: Μ2 = Μ1K2,Μ1 K2 =ø. Процесс повторяется, пока при некотором n не окажется, что Kn есть одноэлементное множество. Тогда Kn объявляется главным элементом иерархии Μn и ее верхним уровнем.

Таким образом, классификационная иерархия для Μ, основанная на последовательности отношений ?,?1, …,?n-1, оказывается построенной: под Kn лежат элементы-классы  Kn-1 и т.д. вплоть до уровня, определенного исходным отношением ?, и ниже его — элементами из Μ.

Классификационная иерархия дляΜ, основанная на последовательности отношений ?,?1, …,?n-1, называется также иерархической структурой  <Μ; ?,?1, …,?n-1>.

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

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

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

1.    Разрешить пополнять классы некоторых уровней элементами предыдущих уровней.

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

Первая идея реализуется за счет того, что некоторые из символов классов в множестве Ki-1 подменяются своими элементами, и, тем самым, на уровне iпоявляются как символы классов этого уровня, так и элементы уровня i-1 (понятия или исходные элементы из Μ). Все отношения ?iостаются эквивалентностями, но что листья дерева могут размещаться не только на самом нижнем уровне дерева, а вертикально связанные понятия могут перескакивать через уровни.

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

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

 

Рис. 1.1. Три варианта внешней иерархической структуры

На схемах (a) и (b) каждый уровень разбивается  на классы соответствующим  отношением эквивалентности.

Для построения уровня 2 по схеме (b) A и B заменены своими элементами (листьями x и y). Соответствующее отношение эквивалентности стало таким, что x и y оказались эквивалентными (попали в один класс D).

Аналогично, построение уровня 3 схемы (b) выполнено так, что u и v стали вершинами уровня 2, и мощность классифицируемого множества увеличилась. В данном случае по сравнению со схемой (a)  не изменилось число уровней.

В схеме (c) образующее отношение (нулевого уровня) по сравнению со схемой (a) перестало быть эквивалентностью: классы E и A пересекаются.

D

C

E

z

u

v

A

B

x

y

а)  Иерархия, построенная в соответствии со строгой схемой

3

2

0

1

b)  Иерархия, в которой разрешено вертикальное перемещение элементов

u

v

D

x

y

3

2

0

1

z

E

A

c)   Иерархия, в которой разрешено пересечение классов

3

2

0

1


     

 

 

 

 

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

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

Если на множестве Μ определены несколько отношений эквивалентности ?1, …,?n, то можно строить на нем внутренние многоуровневые иерархии, т.е. не прибегать к заданию специальных отношений между классами. Будем считать, что набор этих отношений включает отношение?T, справедливое для любой пары элементов, и ?T= ?n.

Определение 3. Уровни внутренней классификации.

Внутренняя классификационная иерархия множества Μ сотношениями эквивалентности ?1, …,?n, или внутренняя классификационная иерархическая структура <Μ; ?1, …, ?n> определяется следующим построением.

Максимально возможный (n–ый) уровень (любой) внутренней классификационной иерархии множества Μ определяется для отношения ?n=?T как одноуровневая классификация Μ, т.е. т.е. как фактор-множество Kn= Μ\\?T=Μ\\?n, которое содержит единственный класс со всеми элементами из Μ.

Пусть построен iый, 1<in, уровень внутренней классификационной иерархии
Ki={k1, …,kt}, где классы из Kiудовлетворяют условиям:

a)    r {1, …, t}((krΜ)

b)   r, kr’’ {1, …, t}(krkr’’= ø)

c)    k1kt= Μ

d)   r {1, …, t}a, b kr (a?ib)))

Тогда i-1ый уровень внутренней классификационной иерархии множества ΜKi-1 определяется как объединение всех фактор-множеств k1\\?i-1, …,kt\\?i-1.

 Процесс повторяется, пока не исчерпываются все отношения ?1, …,?n.Kn объявляется главным элементом иерархии Μ.

Таким образом, внутренняя классификационная иерархия для Μ, основанная на последовательности отношений  ?1, …,?n на Μоказывается построенной: под Kn лежат элементы-классы  Kn-1 и т.д. вплоть до уровня, не содержащего классов.

Оперируя при построении классификационных иерархий сразу несколькими отношениями эквивалентности, мы находимся в ситуации зависимости результата от выбора порядка этих отношений. Для реального моделирования очень важно упорядочивать  ?1, …,?nтак, чтобы достигалась согласованность построения с требованием использования модели. Это важно и еще по одной причине. Дело в том, что классы k1, …,ktопределения 3, вообще говоря, не обязательно являются классами ?iэквивалент­ных элементов множества Μ, поскольку не требуется, чтобы

r,r’’ {1, …, t} a krb kr’’((rkr’’)  ¬(a?i  b)) (*)

и приходится учитывать возможную несогласованность иерархии с классами эквивалентностей на Μ, которые задаются отношения ?1, …,?n. Мы должны либо идти на нарушение строгой иерархичности, которое уже обсуждалось выше, т.е. разрешить классам некоторых уровней пересекаться, либо ограничиваться частными случаями, когда удается строить иерархии, согласованные с классификациями по отношениям эквивалентности.

Определение 4. Согласованность  внутренней  иерархической структуры с отношениями эквивалентности.

Внутренняя  иерархическая структура <Μ; ?1, …, ?n> называется согласованной с отношениями эквивалентности, если в обозначениях определения 3 для каждого отношения ?i  фактор-множество Μ\\?i  ={f1, …, fw}и каждого i-го уровня иерархии Ki={k1, …,kt} справедливо:

a)  r{1, …, t} s{1, …,w}(krfs) — вложенность иерархических классов в классыэквивалентности

b)  s{1, …,w}afsr{1, …, t} (a kr) — полное покрытие классов эквивалентности иерархическими классами.

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

Утверждение 1. Если в условиях определения 3 отношения существует порядок отношений, обладающих свойством вложенности

?1?2 ?n,

т.е.

i, j  {1, …, n}((i< j) a, b Μ ((a ?i b)  (a ?j b))

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

В качестве метода достижения согласованности при построении классификации, можно рекомендовать преобразовывать иерархические классы, для которых не выполняется условие (a), путем подмены отношений эквивалентности: вместо одного отношения ?i рассматривать t отношений, каждое из которых совпадает с ?i на одном их классов k1, …,kt, а для пар с одним или обоими элементами не из этого класса определяется ложным. Подчеркнем, что это всего лишь формальный прием, и его использование необходимо увязывать с интерпретацией модели. Если это не удается, то, скорее всего, построение внутренней классификационной иерархии неадекватно. Быть может, правильнее в таких случаях воспользоваться множественными совместно и равноправно сосуществующими структурированиями моделируемой системы (см. [3]).

Внутренняя иерархия на базе нескольких отношений эквивалентности представляет собой систему вложенных множеств, являющихся подмножествами Μ. Введение символов классов как обозначений для э??их подмножеств позволяет представлять внутреннюю иерархию в виде дерева, подобного тому, которое обсуждалось при построении внешних иерархий. Листьями такого дерева являются элементы из Μ — нижний уровень иерархии, а символы классов следующего и всех последующих более высоких уровней (их, как и в предыдущем случае, можно считать понятиями) — вершины, связанные дугами с элементами предыдущего уровня и только с ними. Корнем дерева становится символ главного элемента иерархии. Это представление отличается от подобного дерева внешней иерархии только тем, что, по построению, элементы из Μ и классы подтянуты вверх по уровням. При желании можно разрешить перемещение листьев и других вершин вниз по иерархии в пределах, не нарушающих уровневое расслоение.

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

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

 

ЛИТЕРАТУРА

 

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

[2] Гриншкун В.В. Теоретические и методологические основы использования иерархических структур в информатизации образования и обучении информатике // Вестник московского университета. Серия 20. Педагогическое образование. – 2004. – № 1. – С. 125–126.

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

 

 



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


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

Новости
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

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