Использование теории мультимножеств в процессе построения UFO-моделей

Міністерство освіти і науки України Харківський національний університет радіоелектроніки Факультет прикладної математики та менеджменту Кафедра соціальної інформатики Магистерская аттестационная работа Использование теории мультимножеств в процессе построения UFO-моделей

Реферат Об'єкт дослідження — процес побудови UFO-моделей.

Мета роботи — дослідження можливості використання теорії мультимножин у процесі побудови UFO-моделей.

Методи дослідження — методи теорії мультимножин та сучасні комп’ютерні технології обробки табличних даних.

Результати роботи — формальний опис UFO-моделей та операцій з ними засобами теорії мультимножин; UFO-моделі методичної роботи викладачів кафедри вузу; реалізація UFO-моделей як мультимножин та операцій з ними у табличному процесорі Microsoft Excel.

теорія мультимножин, UFO-аналіз, моделювання, кафедра, табличний процесор

ABSTRACT

Research object — process of UFO-models construction.

Work purpose — researching of possibility of multisets theory using in process of UFO-models construction.

Research methods — methods of multisets theory and modern computer technologies of tabular data processing.

Work results — formal description of UFO-models and UFO-models manipulation by using of conceptions of multisets theory; UFO-models of teachers' methodical working; realizing of UFO-models as multisets and UFO-models manipulation in tabular processor Microsoft Excel.

multisets theory, UFO-analysis, modeling, sub-faculty, tabular processor

Перечень условных обозначений, символов, единиц, сокращений и

терминов

— симметрическая разность

/A/ - размерность мультимножества A

|A| - мощность мультимножества A

— A — дополнение мультимножества A

CASE — computer-aided system engineering

hgt A — высота мультимножества A

IDEF0 — стандарт функционального моделирования

Qi — i-ый критерий

qij — j-е значение i-го критерия

SQL — структурированный язык запросов

Supp A — носитель мультимножества A

UML — Unified Modeling Language

СУБД — система управления базами данных УФО — Узел-Функция-Объект

Введение

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

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

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

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

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

Целью данной магистерской аттестационной работы является исследование возможности использования теории мультимножеств в процессе построения UFO-моделей. Полученные результаты можно использовать в процессе UFO-анализа, а также для внедрения в CASE-инструментарии, используемые в процессе моделирования систем.

1. Обзор современного состояния проблемы

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

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

Так, например, метод системного структурного анализа IDEF0 предназначен для функционального моделирования путем создания описательной графической модели, показывающей что, как и кем делается в рамках функционирования организационной системы. Функциональная модель представляет собой структурированное изображение функций организационной системы, информации и объектов, связывающих эти функции [2, 3]. CASE-средством, поддерживающим стандарт функционального моделирования IDEF0, является BPwin [4, 5].

Объектно-ориентированное моделирование, как и методы системного анализа, предполагает использование некоторой нормативной системы. Наиболее распространенной на сегодня является нормативная система языка UML, включающая два вида символов: сущности и отношения, а также правила создания комбинаций из этих символов — диаграммы [6, 7]. Хотя UML изначально создавался для моделирования программных систем, он также оказался очень подходящим языком для моделирования бизнес-процессов. Он способен описывать как структурные и поведенческие аспекты бизнеса, так и бизнес правила, влияющие на структуру и поведение. CASE-средством, поддерживающим язык UML, является Rational Rose [9, 10].

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

Метод системно-объектного анализа и моделирования основан на разбиении системы на подсистемы, представляющие собой трехэлементные конструкции «узел-функция-объект» (так называемые УФО-элементы). При исследовании множества библиотечных УФО-элементов была использована математическая теория паттернов [13−15], которая позволила строго формально подойти к выбору УФО-элементов, соответствующих контекстной модели системы, и сборке из них конфигурации, обеспечивающей декомпозицию системы. При этом библиотечные УФО-элементы рассматривались как мультимножества образующих, в том смысле, что любой УФО-элемент мог в конфигурации встречаться несколько раз. Однако, никакие операции с мультимножествами УФО-элементов не рассматривались. CASE-средством, поддерживающим УФО-анализ, является UFO-toolkit.

В работе УФО-элемент представлялся как мультимножество его входов и мультимножество его выходов. При этом операции над УФО-элементами сводились к операциям с мультимножествами их входов и выходов.

Таким образом, актуальным является представление системы как мультимножества УФО-элементов и исследование операций над ними.

1.2 Формальное описание многопризнаковых объектов Многопризнаковые объекты Ai (i = 1, …, n) обычно принято представлять как векторы или кортежи qi = (qi1e1, …, qimem) в пространстве Q = Q1 … Qm, где Qs = {qses} - непрерывная или дискретная шкала s-го признака, es = 1, …, hs, s = 1, …, m. Ситуация существенным образом усложняется, если одному и тому же объекту Ai может соответствовать не один, а несколько m-мерных векторов с различающимися значениями признаков. Подобные ситуации возникают, например, когда объект Ai оценивается k независимыми экспертами по m критериям, или когда необходимо одновременно учесть m параметров объекта Ai, измеренных k различными способами. В таких случаях объект Ai представляется в m-мерном пространстве Q уже не одним вектором qi, а группой, состоящей из k векторов {qi (1), …, qi (k)} вида qi (j) = (qi1e1(j), …, qimem (j)), j = 1, …, k, которая должна рассматриваться как единое целое. При этом, очевидно, измеренные разными способами значения параметров, как и индивидуальные оценки, данные экспертами, могут быть похожими, различающимися и даже противоречивыми, что в свою очередь может приводить к несравнимости векторов qi (j), характеризующих один и тот же объект Ai.

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

Для этого можно ввести вместо прямого произведения m шкал признаков Q = Q1 … Qm обобщенную последовательную шкалу признаков — множество G = {Q1, …, Qm}, состоящее из m групп признаков, и представить объект Ai в таком символическом виде:

Ai = {kAi (q11)*q11, …, kAi (q1h1)*q1h1, …, kAi (qm1)*qm1, …, kAi (qmhm)*qmhm},

где число kAi (qses) указывает сколько раз признак qses Qs встречается в описании объекта Ai, знак * обозначает кратность вхождения признака qses. Например, при многокритериальной оценке объекта Ai несколькими экспертами число kAi (qses) равно числу экспертов, давших объекту Ai оценку qses по критерию Qs. Объект Ai можно записать и более единообразно как Ai = {kAi (x1)*x1, …, kAi (xh)*xh}, определив элементы множества G = {x1, …, xh} следующим образом:

x1 = q11, x2 = q12, …, xh1 = q1h1,

xh1+1 = q21, xh1+2 = q22, …, xh1+h2 = q2h2, …,

xh1+…+h (m-1)+1 = qm1, xh1+…+h (m-1)+2 = qm2, …, xh1+…+hm = qmhm,

где h = h1 + … + hm. Множество G характеризует свойства совокупности объектов A = {A1, …, An}. Такая запись объектов Ai представляет их как множества с повторяющимися элементами xj G или мультимножества.

1.3 Основные понятия теории мультимножеств и операции над ними Дадим краткий обзор теории мультимножеств [17, 20]. Мультимножеством A, порожденным обычным множеством G = {x1, x2, …}, все элементы которого различны, называется совокупность групп элементов вида A = kA (x)*x. Здесь kA: G Z+ = {0, 1, 2, …} называется функцией числа экземпляров мультимножества, определяющей кратность вхождения элемента xi G в мультимножество A, что обозначено символом *. Если kA (x) = A (x), где A (x) = 1 при x A и A (x) = 0 при x A, то мультимножество A становится обычным множеством A. Обычное множество SuppA = x G, SuppA (x) = min (kA (x), 1) называется носителем мультимножества A. Мощность мультимножества |A| = xkA (x) определяется как общее число экземпляров всех его элементов; размерность мультимножества /A/ = xA (x) = |SuppA| - как общее число различных элементов. Мультимножество называется пустым, если k (x) = 0, постоянным C[t], если kC[t](x) = t = const, и максимальным Z, если kZ (x) = maxAA kA (x), x G. Величина hgtA = maxxG kA (x) называется высотой мультимножества. Обычное множество A является, таким образом, постоянным мультимножеством A[1] высоты hgtA = 1.

Вводятся следующие операции над мультимножествами [21]:

Объединение

A B = kAB (x) = max (kA (x), kB (x));

Пересечение

A B = kAB (x) = min (kA (x), kB (x));

сложение

A + B = kA+B (x)*x ;

вычитание

A — B = kA-B (x)*x ;

симметрическая разность

A B = kA (x) — kB (x);

дополнение

— A = Z — A = k-A (x) = kZ (x) — kA (x);

умножение на число

t*A = kt*A (x)*x ;

умножение

A * B = kA*B (x) = kA (x) * kB (x);

n-я степень

An = kAn (x)*x ;

прямое произведение

A B = kAB (x)*(xi, xj) ;

прямая n-я степень

(A)n = k (A)n (x) = kA (x1) * … * kA (xn), xiA.

Носители операций над мультимножествами удовлетворяют следующим соотношениям:

Supp (AB) = Supp (A+B) = (SuppA) (SuppB);

Supp (AB) = Supp (A*B) = (SuppA) (SuppB);

Supp (AB) = (Supp (A-B)) (Supp (B-A));

Supp (t*A) = SuppA = Supp (An);

Supp (AB) = (SuppA) (SuppB);

Supp (A)n = (SuppA)n.

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

-(AB) = -(A) -(B);

-(AB) = -(A) -(B);

-(A+B) = -(A) — B = -(B) — A;

-(A-B) = -(A) + B;

-(A) — -(B) = B — A.

Некоторые свойства, которыми обладают операции над множествами, у мультимножеств отсутствуют. В то же время появляются новые свойства, не имеющие аналогов для множеств. Например:

A + -A = Z;

Z — -A = A;

AA Z;

AA ;

A — -AA — A .

При переходе от мультимножеств к множествам и замене kA (x) на A (x) многие из выше сформулированных утверждений для мультимножеств останутся справедливыми и для множеств, но некоторые из них могут изменить или потерять смысл. Например, операции арифметического сложения и умножения на число для множеств неопределимы, вычитание множеств определяется иначе, а арифметическое умножение множеств будет совпадать с их пересечением.

1.4 Практическое применение теории мультимножеств

1.4.1 Задача конкурсного отбора Рассмотрим важную практическую задачу конкурсного отбора проектов для их финансирования из некоторого фонда или для включения в состав программы, направленной на решение какой-либо важной проблемы (научно-технической, экономической, экологической, производственной). Каждая конкурсная заявка Ai (i = 1, …, k) независимо оценивается несколькими экспертами по определенным критериям. Такими критериями могут быть, например:

важность проекта для программы (Q1);

перспективность проекта (Q2);

новизна подхода к решению поставленных задач (Q3);

квалификация исполнителей проекта (Q4);

ресурсное обеспечение работ (Q5);

возможность быстрого выхода результатов в практику (Q6).

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

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

для использования запланированных результатов на практике потребуются дополнительные исследования и разработки (q62);

результаты будут носить в основном теоретический характер (q63).

Рисунок 1.1 — Шкала критерия Q6

Каждый эксперт, наряду с оценкой заявки по всем критериям, дает одну из следующих рекомендаций:

включить проект в программу (r1);

отклонить проект (r2);

отложить рассмотрение заявки и отправить проект на доработку (r3).

Указанные рекомендации экспертов являются, по существу, правилами предварительной классификации (сортировки) множества рассматриваемых заявок A = {A1, …, Ak}. Основываясь на заключениях экспертов, конкурсная комиссия принимает решение о включении того или иного проекта в соответствующий раздел программы. В других задачах критерии оценки объектов и правила их сортировки могут быть и иными.

Если бы заявка оценивалась только одним экспертом, то найти на множестве многокритериальных оценок обобщенное решающее правило для отбора предложений не составило бы особого труда. Известно большое число разных подходов к решению подобного рода задач классификации [22−25]. В случае оценки несколькими экспертами появляется несколько различных вариантов («экземпляров») одной и той же заявки, причем и многокритериальные экспертные оценки, и заключения экспертов могут быть как схожими, так и противоречивыми. Эксперты могут относить сильно различающиеся объекты в один и тот же класс, а объекты со сходными значениями признаков — в разные классы. Несогласованность индивидуальных решающих правил может быть вызвана:

неоднозначностью понимания экспертами решаемой задачи;

ошибками или неточностями, допущенными экспертами при первоначальной классификации объектов;

субъективным различием решающих правил, используемых разными экспертами;

специфичностью знаний самих экспертов;

нетранзитивностью отдельных экспертных суждений;

многими другими причинами.

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

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

уровень деловой активности (Q1);

объем прибыли от реализации продукции (Q2);

объем продаж (Q3);

число выполненных проектов (Q4);

квалификация персонала (Q5);

численность сотрудников компании (Q6).

Шкалы критериев оценки могут быть как количественными, так и качественными. Для удобства оценки и сравнения компаний количественные критерии можно трансформировать в качественные с небольшим числом упорядоченных градаций шкал. Шкала критерия Q4 может иметь, например, такой вид (рис. 2.2):

очень высокое (больше ста) — q41;

высокое (от пятидесяти до ста) — q42;

среднее (от десяти до пятидесяти) — q43;

низкое (меньше десяти) — q44.

Рисунок 1.2 — Шкала критерия Q4

Каждая компания из совокупности A = {A1, …, Ak} оценивается несколькими экспертами по всем критериям. Оценки разных экспертов могут отличаться друг от друга и даже противоречить друг другу. Каждая компания Ai представляет собой многопризнаковый объект, и определение рейтинга можно рассматривать как задачу упорядочивания многопризнаковых объектов. Основной трудностью при решении таких задач является необходимость учета всех описаний объекта — различающихся оценок, сделанных разными экспертами, при условии, что не существует «главного» эксперта, и мнения всех экспертов считаются одинаково важными.

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

1.4.3 Классификация многопризнаковых объектов Перейдем к формальной постановке задачи классификации совокупности объектов A = {A1, …, Ak}, которые описываются m дискретными признаками Q1, …, Qm, имеющими качественные (номинальные, либо порядковые) значения qses (es =1, …, hs; s = 1, …, m). Порядковые значения качественного признака обычно считаются упорядоченными от лучшего значения к худшему: qs1 > qs2 > … > qshs.

Пусть каждый из объектов Ai, (i = 1, …, k) может существовать в n экземплярах, которые отличаются наборами признаков, его характеризующих. Различными экземплярами многопризнакового объекта являются, например, наборы экспертных оценок проекта, которые даны n экспертами. Каждый из экспертов предварительно относит объекты Ai к одному из нескольких классов Xt, (t = 1, …, f), тем самым появляется n в общем случае несовпадающих индивидуальных сортировок совокупности объектов A. Принадлежность экземпляра объекта Ai к некоторому классу Xt выражается индивидуальным правилом сортировки R, которое может считаться еще одним качественным признаком объекта со шкалой значений R={rt}. Таким образом, каждый экземпляр объекта описывается только одним каким-то значением признака из каждой группы Q1, …, Qm, R. Других дополнительных предположений об особенностях классов, признаков объектов и их значений (важности, предпочтительности, характерности, упорядоченности и прочее) не делается.

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

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

Предложенный подход к построению обобщенного решающего правила для классификации многопризнаковых объектов, которое аппроксимирует большое число предварительных противоречивых сортировок, был проверен на результатах экспертной оценки и конкурсного отбора проектов при формирования государственной научно-технической программы по высокотемпературной сверхпроводимости. Каждая представленная на конкурс заявка независимо оценивалась 3 экспертами по 6 качественным критериям, которые давали также свое заключение по принятию или отклонению заявки. Всего было подано более 250 заявок, около 170 из них было отобрано для включения в программу. Разработанным методом были сформулированы несколько решающих правил, одно из которых полностью совпало с примененным на практике. Обобщенное решающее правило классификации объектов позволило также выделить наиболее важные для отбора проектов критерии и выявить расхождения в индивидуальных правилах сортировки проектов, применявшихся экспертами.

1.4.4 Упорядочение многопризнаковых объектов Дадим формальную постановку задачи упорядочения совокупности многопризнаковых объектов A = {A1, …, Ak}, которые оцениваются n экспертами по m критериям Q1, …, Qm. Каждый критерий Qs имеет порядковую шкалу количественных или качественных оценок {qses} (es = 1, …, hs; s = 1, …, m), которые упорядочены от лучшего значения к худшему: qs1 > qs2 > … > qshs.

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

Требуется, исходя из многокритериальных оценок объектов, упорядочить объекты от лучшего к худшему.

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

Упорядочивание объектов по их близости к наилучшему объекту в метрическом пространстве мультимножеств дает возможность получать как строгое, так и нестрогое ранжирование объектов при равнозначных или различных по важности критериях. Рассмотренный метод упорядочения многопризнаковых объектов был применен для построения рейтинга российских компаний, работающих в секторе информационно-коммуникационных технологий. Результаты экспертизы обрабатывались по описанной процедуре в предположении равнозначности критериев. В итоге из 50 оцененных компаний были выделены 30 ведущих высокотехнологичных компаний, а также составлены рейтинги 10 наиболее динамично развивающихся компаний и 10 ведущих разработчиков программного обеспечения.

1.4.5 Конструктор типов мультимножества в стандарте SQL:2003

В SQL:2003 произошли некоторые изменения в системе типов SQL. Некоторые типы удалены, а другие добавлены. Среди новых типов наиболее важным является конструктор типов мультимножеств.

В стандарте SQL:1999 допускалась возможность использования только одного вида коллекций — динамических массивов с элементами любого допустимого в SQL типа, кроме типа массива. Тип массива образовывался с помощью конструктора типов массивов ARRAY.

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

При определении местоположения (например, столбца таблицы) типа мультимножеств используется конструкция dt MULTISET, где dt задает тип данных элементов конструируемого типа мультимножеств. Значениями типа мультимножеств являются мультимножества, т. е. неупорядоченные коллекции элементов одного и того же типа, среди которых допускаются дубликаты. Например, значениями типа INTEGER MULTISET являются мультимножества, элементами которых являются целые числа. Примером такого значения может быть мультимножество {12, 34, 12, 45, -64}.

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

Значения-мультимножества создаются путем использования специальной конструкции SQL:2003, называемой конструктором значений-мультимножеств (multiset value constructor). Эта конструкция определяется следующими синтаксическими правилами:

multiset_value_constructor := multiset_value_constructor_by_enumeration> | multiset_value_constructor_by_query> | table_value_constructor_by_query

multiset_value_constructor_by_enumeration := MULTISET left_bracket value_expression_commalist right_bracket

multiset_value_constructor_by_query := MULTISET (query_expression)

table_value_constructor_by_query := TABLE (query_expression>)

Например, следующие выражения являются допустимыми значениями-мультимножествами: MULTISET [14, 16, 17] или MULTISET (SELECT DEPT_NO FROM EMP). Второй случай демонстрирует возможность преобразования таблицы в мультимножество.

Допускается и использование значения-мультимножества в качестве ссылки на таблицу в разделе FROM запроса. Для этого к значению-мультимножеству применяется операция UNNEST. Вот простой пример допустимого запроса:

SELECT T. A, T. A + 2 AS PLUS_TWO

FROM UNNEST (MULITISET [14,16,17]) AS T (A)

В результате выполнения запроса будет получена таблица 1.1.

Таблица 1.1 — Результат выполнения запроса

Для типов мультимножеств поддерживаются операции для преобразования типа значения-мультимножества к типу массивов или другому типу мультимножеств с совместимым типом элементов (операция CAST), для удаления дубликатов из мультимножества (функция SET), для определения числа элементов в заданном мультимножестве (функция CARDINALITY), для выборки элемента мультимножества, содержащего в точности один элемент (функция ELEMENT). Кроме того, для мультимножеств обеспечиваются операции объединения (MULTISET UNION), пересечения (MULTISET INTERSECT) и определения разности (MULTISET EXCEPT). Каждая из операций может выполняться в режиме с сохранением дубликатов (режим ALL) или с устранением дубликатов (режим DISTINCT).

Наконец, введены три новые агрегатные функции. Агрегатная функция COLLECT создает мультимножество из значений аргумента в каждой строке группы строк. Функция FUSION производит объединение значений-мультимножеств из всех строк группы строк. Функция INTERSECT производит пересечение значений-мультимножеств из всех строк группы строк. Покажем на простом примере, как работают эти агрегатные функции. Пусть имеется таблица PROGRAMMERS следующего вида:

Таблица 1.2 — Данные о программистах

Тогда в результате запроса

SELECT COLLECT (PROGRAMMER) AS ALL_PROGRAMMERS, FUSION (FAVOURITE_LANGUAGES) AS ALL_LANGUAGES INTERSECT (FAVOURITE_LANGUAGES) AS COMMON_LANGUAGES

FROM PROGRAMMERS

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

Таблица 1.3 — Результат выборки

При использовании мультимножеств в условных выражениях можно применять следующие предикаты:

сравнения по равенству (=);

сравнения по неравенству (<>);

проверки того, что заданное значение является элементом мультимножества (MEMBER);

проверки того, что одно мультимножество входит в другое мультимножество (SUBMULTISET);

проверки того, что мультимножество содержит дубликаты (IS A SET).

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

Дело в том, что даже при наличии определяемых пользователями типов данных и типов массивов SQL:1999 не предоставлял полных возможностей для преодоления исторически присущего реляционной модели данных вообще и SQL, в частности, ограничения «плоских таблиц». Теперь, после появления конструктора типов мультимножеств и устранения ограничений на тип данных элементов коллекции, это историческое ограничение полностью ликвидировано.

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

Другой вопрос, принесут ли эти новые возможности существенную практическую пользу разработчикам и пользователям SQL-ориентированных баз данных? Как это обычно бывает в случае SQL, на этот вопрос трудно ответить однозначно. Скорее всего, большинство разработчиков, традиционно работающих в SQL-среде, просто не будет использовать новые средства, как не использует и объектно-реляционные расширения SQL. Но возможно, что расширенная поддержка типов коллекций привлечет к SQL-ориентированным СУБД новую категорию разработчиков и пользователей из числа, например, тех, которые традиционно использовали объектно-ориентированную или какую-либо другую среду, отличную от SQL.

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

Целью данной магистерской аттестационной работы является исследование возможности использования теории мультимножеств в процессе построения UFO-моделей.

Достижение указанной цели связано с решением трех основных задач:

осуществление формального описания UFO-моделей и операций над ними средствами теории мультимножеств;

применение полученных результатов в процессе UFO-моделирования организационной системы;

представление UFO-моделей как мультимножеств и операций над ними в табличном процессоре Microsoft Excel.

2. Использование мультимножеств для представления UFO-моделей и

операций над ними

2.1 UFO-модель как мультимножество Пусть задана библиотека систем L = {S1, S2, S3, S4, S5} (рис. 2.1).

Рисунок 2.1 — Библиотека из пяти систем Используя библиотеку L, можно собрать некоторую систему S, для которой элементы L будут являться подсистемами (рис. 2.2).

Рисунок 2.2 — Пример системы из шести подсистем Формально система S является мультимножеством [32]

S = {3*S1, 1*S2, 1*S3, 1*S4, 0*S5} = {3*S1, 1*S2, 1*S3, 1*S4},

порожденным обычным множеством L = {S1, S2, S3, S4, S5}.

Носителем системы S является обычное множество Supp S = {S1, S2, S3, S4}. Мощность системы S равна |S| = 6, а ее размерность равна /S/ = 4.

В общем виде задается библиотека систем L = {S1, S2, …, Sm} (рис. 2.3).

Рисунок 2.3 — Библиотека систем Используя библиотеку L, можно собрать некоторую систему S, для которой элементы L будут являться подсистемами (рис. 2.4).

Рисунок 2.4 — Пример системы Формально система S является мультимножеством

S = {ki1*Si1, ki2*Si2, …, ki, j*Si, j, ki, j+1*Si, j+1, …, ki, q-1*Si, q-1, ki, q*Si, q},

порожденным обычным множеством L = {S1, S2, …, Sm}.

Носителем системы S является обычное множество

Supp S = {Si1, Si2, …, Si, j, Si, j+1, …, Si, q-1, Si, q}.

Мощность системы S равна

|S| = ki1 + ki2 + … + ki, j + ki, j+1 + … + ki, q-1 + ki, q,

а ее размерность равна

/S/ = q.

2.2 Операции над UFO-моделями как мультимножествами

2.2.1 Объединение UFO-моделей Рассмотрим фрагмент некоторой системы S1 (рис. 2.5), состоящей из подсистем S1, S2 и S3.

Рисунок 2.5 — Фрагмент системы S1

Рассмотрим также фрагмент некоторой другой системы S2 (рис. 2.6), состоящей из подсистем S1 и S4.

Рисунок 2.6 — Фрагмент системы S2

Формально система S1 является мультимножеством

S1 = {…, 2*S1, 1*S2, 1*S3, …},

а система S2 является мультимножеством

S2 = {…, 1*S1, 1*S4, …}.

Формальное объединение систем S1 и S2 дает некоторую систему S3:

S3 = S1 S2 = {…, 2*S1, 1*S2, 1*S3, 1*S4, …},

изображенную на рис. 2.7.

Рисунок 2.7 — Фрагмент системы S3

Содержательно такую операцию объединения систем S1 и S2 можно трактовать как попытку создания системы S3, которая будет выполнять функции как системы S1 так системы и S2 за счет увеличения нагрузки на некоторые подсистемы, общие для систем S1 и S2. Действительно, при таком объединении систем входы и выходы системы S3 являются объединением входов и выходов систем S1 и S2. Но при этом на одну из подсистем S1, общую для систем S1 и S2, ложится дополнительная нагрузка на выход b (на рис. 2.7 это показано жирной точкой).

2.2.2 Пересечение UFO-моделей Рассмотрим фрагмент некоторой системы S4 (рис. 2.8), состоящей из подсистем S1 — S7.

Рисунок 2.8 — Фрагмент системы S4

Рассмотрим также фрагмент некоторой другой системы S5 (рис. 2.9), состоящей из подсистем S1 — S4, S8 — S10.

Рисунок 2.9 — Фрагмент системы S5

Формально система S4 является мультимножеством

S4 = {…, 3*S1, 1*S2, 1*S3, 1*S4, 1*S5, 1*S6, 1*S7, …},

а система S5 является мультимножеством

S5 = {…, 1*S1, 1*S2, 1*S3, 2*S4, 1*S8, 1*S9, 1*S10, …}.

Формальное пересечение систем S4 и S5 дает некоторую систему S6:

S6 = S4 S5 = {…, 1*S1, 1*S2, 1*S3, 1*S4, …},

изображенную на рис. 2.10.

Рисунок 2.10 — Фрагмент системы S6

Содержательно такую операцию пересечения систем S4 и S5 можно трактовать как попытку выделения процессов, общих для системы S4 и S5. Действительно, при таком пересечении систем выделяется процесс (a, b, c, d, e), общий для систем S4 и S5, а также подсистемы S1 — S4, осуществляющие этот процесс (рис. 2.10).

2.2.3 Сложение UFO-моделей Рассмотрим фрагмент некоторой системы S7 (рис. 2.11), состоящей из подсистем S1 и S2.

Рисунок 2.11 — Фрагмент системы S7

Рассмотрим также фрагмент некоторой другой системы S8 (рис. 2.12), состоящей из подсистем S2 и S3.

Рисунок 2.12 — Фрагмент системы S8

Формально система S7 является мультимножеством

S7 = {…, 2*S1, 1*S2, …},

а система S8 является мультимножеством

S8 = {…, 2*S2, 1*S3, …}.

Формальная сумма систем S7 и S8 дает некоторую систему S9:

S9 = S7 + S8 = {…, 2*S1, 3*S2, 1*S3, …},

изображенную на рис. 2.13.

Рисунок 2.13 — Фрагмент системы S9

Содержательно такую операцию суммирования систем S7 и S8 можно трактовать как простое слияние систем S7 и S8. Действительно, при таком суммировании систем не меняется ни состав ни структура систем S7 и S8, которые фактически, становятся подсистемами системы S9.

2.2.4 Вычитание UFO-моделей Рассмотрим снова системы S4 и S5 (рис. 2.8 и 2.9). Формальная разность систем S4 и S5 дает некоторую систему S10:

S10 = S4 — S5 = {…, 2*S1, 1*S5, 1*S6, 1*S7, …},

изображенную на рис. 2.14.

Рисунок 2.14 — Фрагмент системы S10

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

Если теперь рассмотреть формальную разность систем S5 и S4, то получим некоторую систему S11:

S11 = S5 — S4 = {…, 1*S4, 1*S8, 1*S9, 1*S10, …},

изображенную на рис. 2.15.

Рисунок 2.15 — Фрагмент системы S11

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

2.2.5 Симметрическая разность UFO-моделей Рассмотрим снова системы S4 и S5 (рис. 2.8 и 2.9). Формальная симметрическая разность систем S4 и S5 дает некоторую систему S12:

S12 = S4 S5 = {…, 2*S1, 1*S4, 1*S5, 1*S6, 1*S7, 1*S8, 1*S9, 1*S10, …},

изображенную на рис. 2.16.

Рисунок 2.16 — Фрагмент системы S12

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

2.2.6 Дополнение UFO-модели Рассмотрим снова систему S5 (рис. 2.9), в которой выделим некоторую подсистему S13:

S13 = {…, 1*S8, 1*S4, …},

изображенную на рис. 2.17.

Рисунок 2.17 — Фрагмент системы S13

Формальным дополнением системы S13 до системы S5 будет система S14:

S14 = {…, 1*S1, 1*S2, 1*S3, 1*S4, 1*S9, 1*S10, …},

изображенная на рис. 2.18.

Рисунок 2.18 — Фрагмент системы S14

Содержательно такую операцию дополнения системы S13 системой S14 до системы S5 можно трактовать как расширение функциональности системы S13 до функциональности системы S5 добавлением к ней функциональности системы S14.

2.2.7 Умножение UFO-модели на число Рассмотрим снова систему S2 (рис. 2.6). Формальным умножением системы S2 на число 3 будет некоторая система S15:

S15 = {…, 3*S1, 3*S4, …},

изображенная на рис. 2.19.

Рисунок 2.19 — Фрагмент системы S15

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

3. Использование теории мультимножеств в процессе

UFO-моделирования кафедры вуза

3.1 UFO-модель методической работы преподавателей кафедры Эффективность учебной работы профессорско-преподавательского состава кафедры непосредственно зависит от уровня методического мастерства преподавателей, поэтому методическая работа — неотъемлемая часть учебного процесса.

Основные цели методической работы на кафедре [33, 34]:

систематическое совершенствование методики обучения и воспитания студентов;

повышение педагогического мастерства преподавателей;

разработка новых эффективных методов организации и ведения учебного процесса;

обобщение и распространение передового опыта обучения и воспитания студентов.

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

Методическая работа включается в план работы кафедры. Основные формы методической работы на кафедре [35−40]:

научные исследования по вопросам методики обучения и воспитания студентов;

заседания кафедры и предметно-методических комиссий по учебно-методическим вопросам;

методические разработки, создание учебных пособий, учебников;

инструктивно-методические занятия;

методическое обеспечение демонстрационных открытых и пробных занятий;

взаимное посещение занятий;

участие в научно-методических конференциях и межкафедральных совещаниях, методических семинарах.

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

Рисунок 3.1 — Контекстная модель методической работы преподавателей В этой модели предполагается, что преподаватели кафедры владеют текстологическими методами извлечения знаний, основанными на изучении специальных текстов из учебников, монографий, статей, методик и других носителей профессиональных знаний.

Основные должности преподавателя [41]:

профессор;

доцент;

старший преподаватель;

ассистент.

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

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

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

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

Например, ассистент может создать качественные методические указания к лабораторным работам (рис. 3.2).

Рисунок 3.2 — Модель методической работы ассистента Старший преподаватель способен создать полезные методические указания к практическим занятиям (рис. 3.3).

Рисунок 3.3 — Модель методической работы старшего преподавателя Доценту можно поручить написание учебного пособия (рис. 3.4).

Рисунок 3.4 — Модель методической работы доцента Наконец, профессор должен уметь создавать учебники (рис. 3.5).

Рисунок 3.5 — Модель методической работы профессора На кафедре может работать несколько профессоров, доцентов, старших преподавателей и ассистентов. Поэтому декомпозиция контекстной диаграммы методической работы преподавателей (рис. 3.1) может выглядеть так, как показано на рис. 3.6.

Рисунок 3.6 — Декомпозиция контекстной модели методической работы Таким образом, система S = «Преподаватели кафедры», изображенная на рис. 3.1, формально является мультимножеством

S = {1*S1, 2*S2, 2*S3, 3*S4},

порожденным обычным множеством подсистем L = {S1 = «Профессор», S2 = «Доцент», S3 = «Старший преподаватель», S4 = «Ассистент"}.

Менее формально это можно представить следующим образом:

«Преподаватели кафедры» = {1*"Профессор", 2*"Доцент",

2*"Старший преподаватель", 3*"Ассистент"}.

3.2 UFO-модели взаимодействия преподавателей разных кафедр Пусть кафедры «Прикладная математика» и «Социальная информатика» включили в план своей методической работы на предстоящий учебный год создание учебника по курсу «Системный анализ» и учебного пособия по курсу «Теория принятия решений» (рис. 3.7).

Рисунок 3.7 — Контекстная модель создания учебника и учебного пособия На кафедре социальной информатики (СИ) создание учебника поручили двум профессорам, а учебного пособия — одному доценту (рис. 3.8).

Рисунок 3.8 — Модель создания учебника и учебного пособия на кафедре СИ На кафедре прикладной математики (ПМ) создание учебника поручили одному профессору, а учебного пособия — двум доцентам.

Рисунок 3.9 — Модель создания учебника и учебного пособия на кафедре ПМ Методический отдел вуза, рассмотрев методические планы обеих кафедр, может предложить создать учебник по курсу «Системный анализ» двум профессорам кафедры социальной информатики, а учебное пособие по курсу «Теория принятия решений» — двум доцентам кафедры прикладной математики (рис. 3.10).

Рисунок 3.10 — Модель объединения создания учебника и учебного пособия Формально это будет означать, что система, А = «Кафедра СИ» формально является мультимножеством, А = {2*S1, 1*S2},

а система В = «Кафедра ПМ» формально является мультимножеством В = {1*S1, 2*S2},

порожденным обычным множеством подсистем L = {S1 = «Профессор», S2 = «Доцент"}.

При этом методический отдел вуза формально осуществил операцию объединения этих мультимножеств:

A B = {2*S1, 1*S2} {1*S1, 2*S2} =

= {max (2,1)*S1, max (1,2)*S2} = {2*S1, 2*S2}.

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

В другом случае методический отдел вуза, рассмотрев методические планы обеих кафедр, может предложить создать учебник по курсу «Системный анализ» одному профессору кафедры прикладной математики, а учебное пособие по курсу «Теория принятия решений» — одному доценту кафедры социальной информатики (рис. 3.11).

Рисунок 3.11 — Модель пересечения создания учебника и учебного пособия

При этом методический отдел вуза формально осуществил операцию пересечения мультимножеств, А и В:

A B = {2*S1, 1*S2} {1*S1, 2*S2} =

= {min (2,1)*S1, min (1,2)*S2} = {1*S1, 1*S2}.

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

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

Рисунок 3.12 — Модель сложения создания учебника и учебного пособия

При этом методический отдел вуза формально осуществил операцию сложения мультимножеств, А и В:

A + B = {2*S1, 1*S2} + {1*S1, 2*S2} =

= {(2+1)*S1, (1+2)*S2} = {3*S1, 3*S2}.

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

4. Представление операций над UFO-моделями как

мультимножествами в Microsoft Excel

4.1 Представление UFO-моделей Пусть задана библиотека, состоящая из пяти подсистем S1, S2, S3, S4 и S5, каждая из которых может входить в состав системы A и B (рис. 4.1).

Рисунок 4.1 — Модель библиотеки подсистем Пусть каждая из пяти подсистем S1, S2, S3, S4 и S5 может входить в состав системы от 0 до 9 раз. Для случайной генерации кратности вхождения подсистемы S1 в состав системы A в ячейку B3 можно ввести формулу [42]

=СЛУЧМЕЖДУ (0;9),

которую с помощью маркера заполнения можно распространить и на другие ячейки (рис. 4.2).

Рисунок 4.2 — Модели систем A и B

4.2 Представление операций над UFO-моделями Под таблицей, содержащей модели систем A и B, разместим таблицу, в которой будут отображаться модели операций их объединения, пересечения, сложения, вычитания, симметрической разности, дополнения системы A и ее умножения на число (рис. 4.3).

Рисунок 4.3 — Отображение моделей операций над системами A и B

4.2.1 Представление операции объединения UFO-моделей Для вычисления кратности вхождения подсистемы S1 в систему, являющуюся результатом объединения систем A и B, в ячейку B7 введем формулу

=МАКС (B3:B4),

которую с помощью маркера заполнения можно распространить и на другие ячейки (рис. 4.4).

Рисунок 4.4 — Модель операции объединения систем A и B

4.2.2 Представление операции пересечения UFO-моделей Для вычисления кратности вхождения подсистемы S1 в систему, являющуюся результатом пересечения систем A и B, в ячейку B8 введем формулу

=МИН (B3:B4),

которую с помощью маркера заполнения можно распространить и на другие ячейки (рис. 4.5).

Рисунок 4.5 — Модель операции пересечения систем A и B

4.2.3 Представление операции сложения UFO-моделей Для вычисления кратности вхождения подсистемы S1 в систему, являющуюся результатом сложения систем A и B, в ячейку B9 введем формулу

=СУММ (B3:B4),

которую с помощью маркера заполнения можно распространить и на другие ячейки (рис. 4.6).

Рисунок 4.6 — Модель операции сложения систем A и B

4.2.4 Представление операции вычитания UFO-моделей Для вычисления кратности вхождения подсистемы S1 в систему, являющуюся результатом вычитания системы B из системы A, в ячейку B10 введем формулу

=B3-B8,

которую с помощью маркера заполнения можно распространить и на другие ячейки (рис. 4.7).

Рисунок 4.7 — Модель операции вычитания системы B из системы A

4.2.5 Представление операции симметрической разности UFO-моделей Для вычисления кратности вхождения подсистемы S1 в систему, являющуюся результатом симметрической разности систем A и B, в ячейку B11 введем формулу

=ABS (B3-B4),

которую с помощью маркера заполнения можно распространить и на другие ячейки (рис. 4.8).

Рисунок 4.8 — Модель операции симметрической разности систем A и B