загрузка...

2.1. Предыстория. Математические основы


Представление различных понятий окружающего нас мира при помощи графической символики уходит своими истоками в глубокую древность. В качестве примеров можно привести условные обозначения знаков Зодиака, магические символы различных оккультных доктрин, графические изображения геометрических фигур на плоскости и в пространстве. Важным достоинством той или иной графической нотации является возможность образного закрепления содержательного смысла или семантики отдельных понятий, что существенно упрощает процесс общения между посвященными в соответствующие теории и идеологии.
Теория множеств
Как одну из наиболее известных систем графических символов, оказавших непосредственное влияние на развитие научного мышления, следует отметить язык диаграмм английского логика Джона Венна (1834-1923). В настоящее время диаграммы Венна применяются для иллюстрации основных теоретико-множественных операций, которые являются предметом специального раздела математики – теории множеств. Поскольку многие общие идеи моделирования систем имеют адекватное описание в терминологии теории множеств, рассмотрим основные понятия данной теории, имеющие отношение к современным концепциям и технологиям исследования сложных систем.
Исходным понятием теории множеств является само понятие множество, под которым принято понимать некоторую совокупность объектов, хорошо различимых нашей мыслью или интуицией. При этом не делается никаких предположений ни о природе этих объектов, ни о способе их включения в данную совокупность. Отдельные объекты, составляющие то или иное множество, называют элементами данного множества. Вопрос «Почему мы рассматриваем ту или иную совокупность элементов как множество?» не требует ответа, поскольку в общее определение множества не входят никакие дополнительные условия на включение отдельных элементов в множество. Если нам хочется, например, рассмотреть множество, состоящее из трех элементов: «солнце, море, апельсин», то никто не сможет запретить это сделать.
Примеров конкретных множеств можно привести достаточно много. Это и множество квартир жилого дома, и множество натуральных чисел, с которого начинается знакомство каждого ребенка с великим таинством счета. Совокупность компьютеров в офисе тоже представляет собой множество, хотя, возможно, они и соединены между собою в сеть. Множество живущих на планете людей, как и множество звезд на небосводе, тоже могут служить примерами множеств, хотя природа их существенно различна.
Примечание 11
В теории множеств используется специальное соглашение, по которому множества обозначаются прописными буквами латинского алфавита, и традиция эта настолько общепризнана, что не возникает никакого сомнения в ее целесообразности. При этом отдельные элементы обозначаются строчными буквами, иногда с индексами, которые вносят некоторую упорядоченность в последовательность рассмотрения этих элементов. Важно понимать, что какой бы то ни было порядок, вообще говоря, не входит в исходное определение множества. Таким образом, множество, например, квартир 100-квартирного жилого дома с использованием специальных обозначений можно записать следующим образом: A={aj, 02, а3, ..., а{00}. Здесь фигурные скобки служат обозначением совокупности элементов, каждый из которых имеет свой уникальный числовой индекс. Важно понимать, что для данного конкретного множества элемент ato обозначает отдельную квартиру в рассматриваемом жилом доме. При этом вовсе необязательно, чтобы номер этой квартиры был равен 10, хотя с точки зрения удобства это было бы желательно.
Принято называть элементы отдельного множества принадлежащими данному множеству. Данный факт записывается при помощи специального символа "е", который так и называется – символ принадлежности. Например, запись а10ьА означает тот простой факт, что отдельная квартира (возможно, с номером 10) принадлежит рассматриваемому множеству квартир некоторого жилого дома.
Следующим важным понятием, которое служит прототипом многих более конкретных терминов при моделировании сложных систем, является понятие подмножества. Казалось бы, интуитивно и здесь нет ничего неясного. Если есть некоторая совокупность, рассматриваемая как множество, то любая ее часть и будет являться подмножеством. Так, например, совокупность квартир на первом этаже жилого дома есть ничто иное, как подмножество рассматриваемого нами примера. Ситуация становится не столь тривиальной, если рассматривать множество абстрактных понятий, таких как сущность или класс.
Для обозначения подмножества используется специальный символ. Если утверждается, что множество А является подмножеством множества В, то это записывается как Аа В. Запоминать подобные значки не всегда удобно, поэтому со временем была предложена специальная система графических обозначений.
Как же используются диаграммы Венна в теории множеств? Оказывается, тот факт, что некоторая совокупность элементов образует множество, можно обозначить графически в виде круга. В этом случае окружность имеет содержательный смысл или, выражаясь более точным языком, семантику границы данного множества. Очевидно, что рассмотрение отношения включения элементов одного множества в другое можно изобразить графически следующим образом (рис. 2.1). На этом рисунке большему множеству В соответствует внешний круг, а меньшему множеству (подмножеству) А – внутренний.
Рис. 2.1.Диаграмма Венна для отношения включения двух множеств
Подобным образом можно изобразить и основные теоретико-множественные операции. Так, пересечением двух множеств А и В называется некоторое третье множество С, которое состоит из тех и только тех элементов двух исходных множеств, которые одновременно принадлежат и множеству А, и множеству В. Для этой операции также имеется специальное обозначение: С= А о В. Например, если в качестве множества А для операции пересечения рассмотреть множество сотрудников некоторой фирмы, а в качестве множества В – множество всех мужчин, то нетрудно догадаться, что множество С будет состоять из элементов -± всех сотрудников мужского пола данной фирмы. Операция пересечения множеств также может быть проиллюстрирована с помощью диаграмм Венна (рис. 2.2). На этом рисунке условно изображены два множества А и В, затененной области как раз и соответствует множество С, являющееся пересечением множеств А и В.
Рис. 2.2Диаграмма Венна для пересечения двух множеств
Следующей операцией, которая также допускает наглядную интерпретацию, является операция объединения множеств. Под объединением двух множеств А и В понимается некоторое третье множество, пусть это будет D, которое состоит из тех и только тех элементов, которые принадлежат или А, или В, или им обоим одновременно. Конечно, специальное обозначение есть и для этой операции: D= AuB. Так, если в качестве множества А рассмотреть множество, состоящее из клавиатуры и мыши, а в качестве множества В – множество, состоящее из системного блока и монитора, то нетрудно догадаться, что их объединение, т. е. множество D, образует основные составляющие персонального компьютера. И для этой операции имеется условное графическое представление (рис. 2.3). На этом рисунке объединению двух исходных множеств также соответствует затемненная область, только размеры и форма ее отличаются от случая пересечения двух множеств на предыдущем рисунке.
Рис. 2.3.Диаграмма Венна для объединения двух множеств
Примечание 12
Последнее, на что следовало бы обратить внимание при столь кратком знакомстве с основами теории множеств – это на так называемые понятия мощности множества и отношения множеств. Хотя существуют и другие операции над множествами, а также целый ряд дополнительных понятий, их рассмотрение выходит за рамки настоящей книги. Что касается понятия мощности множества, то данный термин важен для анализа кратности связей, поскольку ассоциируется с количеством элементов отдельного множества. В случае конечного множества ситуация очень простая, поскольку мощность конечного множества равна количеству элементов этого множества. Таким образом, возвращаясь к примеру с множеством А квартир жилого дома, можно сказать, что его мощность равна 100.
Ситуация усложняется, когда рассматриваются бесконечные множества, т. е. множества, не являющиеся конечными. Не вдаваясь в технические детали, которые послужили источником драматичного по своим последствиям кризиса основ математики, ограничим наше рассмотрение бесконечными множествами счетной мощности. Такими множествами принято считать множества, содержащие бесконечное число элементов, которые, однако, можно перенумеровать натуральными числами 1, 2, 3 и т. д. При этом важно иметь в виду, что достичь последнего элемента при такой нумерации принципиально невозможно, иначе множество окажется конечным. Например, есть все основания считать множество всех звезд бесконечным, хотя многие из них имеют свое уникальное название. С другой стороны, множество всех возможных комбинаций из 8 символов, которые могут служить для ввода некоторого пароля, конечное, хотя и достаточно большое. Или, говоря строгим языком, это множество имеет конечную мощность.
Примечание 13
Наконец, было упомянуто и следующее понятие, различные аспекты которого будут служить темой рассмотрения во всех последующих главах. Это фундаментальное понятие отношения множеств, которое часто заменяется терминами связь или соотношение. Данный термин ведет свое происхождение от теории множеств и служит для обозначения любого подмножества упорядоченных кортежей, построенных из элементов некоторых исходных множеств. При этом под кортежем понимается просто набор или список элементов, важно только, чтобы они были упорядочены. Другими словами, если рассматривать первый элемент кортежа, то он всегда будет первым в списке элементов, второй элемент кортежа будет вторым элементом в списке и т. д. Можно ли это записать с использованием специальных обозначений?
Хотя и существует некоторая неоднозначность в принятых обозначениях, кортеж из двух элементов удобно обозначать как , из трех элементов – и т. д. При этом отдельные элементы могут принадлежать как одному и тому же множеству, так и различным множествам. Важно иметь в виду, что порядок выбора элементов для построения кортежей строго фиксирован для конкретной задачи. Речь идет о том, что первый элемент всегда выбирается из первого множества, второй – из второго, и т. д:
Отношение в этом случае будет характеризовать способ или семантику выбора отдельных элементов из одного или нескольких множеств для подобного упорядоченного списка. В этом смысле взаимосвязь является частным случаем отношения, о чем будет сказано в последующем. К сожалению, диаграммы Венна не предназначены для иллюстрации отношений в общем случае. Однако отношения послужили исходной идеей для развития другой теории, которая даже в своем названии несет отпечаток графической нотации, а именно – теории графов. В этой связи наиболее важным является тот факт, что теоретико-множественные отношения послужили также основой для разработки реляционной алгебры в теории реляционных баз данных. Развитие последней привело к тому, что в последние годы именно реляционные СУБД конкретных фирм доминируют на рынке соответствующего программного обеспечения.
Теория графов
Граф можно рассматривать как графическую нотацию для бинарного отношения двух множеств. Бинарное отношение состоит из таких кортежей или списков элементов, которые содержат только два элемента некоторого множества. Хотя основные понятия теории графов получили свое развитие задолго до появления теории множеств как самостоятельной научной дисциплины, формальное определение графа удобно представить в теоретико-множественных терминах.
Графом называется совокупность двух множеств: множества точек или вершин и множества соединяющих их линий или ребер. Формально граф задается в виде двух множеств: G=(V, Е), где V={v1v2, ..., vn} – множество вершин графа, а Е={е1, е2, ..., еm} – множество ребер графа. Натуральное число n определяет общее количество вершин конкретного графа, а натуральное число m – общее количество ребер графа. Следует заметить, в общем случае не все вершины графа могут соединяться между собой, что ставит в соответствие каждому графу некоторое бинарное отношение PQ, состоящее из всех пар вида , где vi, vj = V. При этом пара и, соответственно, пара принадлежат отношению PG в том и только в том случае, если вершины vi и vj соединяются в графе G некоторым ребром ek=Е. Вершины графа изображаются точками, а ребра – отрезками прямых линий.
Рядом с вершинами и ребрами записываются соответствующие номера или идентификаторы, позволяющие их идентифицировать однозначным образом.
Примечание 14
Ниже представлены два примера конкретных графов (рис. 2.4). При этом первый из них (рис. 2.4, а) является неориентированным графом, а второй (рис. 2.4, б) – ориентированным графом. Как нетрудно заметить, для неориентированного графа ребро е1 соединяет вершины v1 и v2, ребро е2 – вершины v1 и v3, а ребро e3 – вершины v2 и v3 и т. д. Последнее ребро, e8, соединяет вершины v4 и v5, тем самым задается описание графа в целом. Других ребер данный граф не содержит, как не содержит других вершин, не изображенных на рисунке. Так, хотя ребра е6 и e7 визуально пересекаются, но точка их пересечения не является вершиной графа.
Для ориентированного графа (рис. 2.4, б) ситуация несколько иная. А именно, вершины v1 и v2 соединены дугой е1, для которой вершина v2 является началом дуги, а вершина v1 – концом этой дуги. Далее дуга е2 соединяет вершины v1 и v4, при этом началом дуги e2 является вершина v1, а концом – вершина v4.
Рис. 2.4.Примеры неориентированного (а) и ориентированного (б) графов
Графы широко применяются для представления различной информации о структуре систем и процессов. Примерами подобных графических моделей могут служить: схемы автомобильных дорог, соединяющих отдельные населенные пункты; схемы телекоммуникаций, используемых для передачи информации между отдельными узлами; схемы программ, на которых указываются варианты ветвления вычислительного процесса. Общим для всех конкретных подобных моделей является возможность представления информации в графическом виде в форме соответствующего графа. При этом отдельные модели, как правило, обладают дополнительной семантикой и специальными обозначениями, характерными для той или иной предметной области.
Важными понятиями теории графов являются понятия маршрута и пути, которые ассоциируются с последовательным перемещением от вершины к вершине по соединяющим их ребрам или дугам. Для неориентированного графа маршрут определяется как конечная или бесконечная упорядоченная последовательность ребер S=<, esl, es2, ..., esk>>, таких, что каждые два соседних ребра имеют общую вершину. Нас будут интересовать только конечные маршруты S=, т. е. такие маршруты, которые состоят из конечного числа ребер. При этом ребро esl принято считать началом маршрута S, а ребро esk – концом маршрута S. Для ориентированного графа соответствующая последовательность дуг S= называется ориентированным маршрутом, если две соседние дуги имеют общую вершину, которая является концом предыдущей и началом последующей дуги.
Примерами маршрутов для неориентированного графа (рис. 2.4, а) являются последовательности ребер: S1=, S2=, S3=. Если в маршруте не повторяются ни ребра, ни вершины, как в случае S1 и S3, то такой неориентированный маршрут называется простой цепью.
Примерами ориентированных маршрутов для графа (рис. 2.4, б) являются такие последовательности дуг: S1=, S2=, S3=. Если в ориентированном маршруте не повторяются ни ребра, ни вершины, как в случае S1 и S2, то такой ориентированный маршрут называется путем. Последнее понятие также иногда применяется для обозначения простой цепи в неориентированных графах и для определения специального класса графов, так называемых деревьев. В общем случае деревья служат для графического представления иерархических структур или иерархий, занимающих важное место в ООАП.
Деревом в теории графов называется такой граф D=, между любыми двумя вершинами которого существует единственная простая цепь, т. е. неориентированный маршрут, у которого вершины и ребра не повторяются. Применительно к ориентированным графам соответствующее определение является более сложным, поскольку основывается на выделении некоторой специальной вершины v0, которая получила специальное название корневой вершины или просто – корня. В этом случае ориентированный граф D= называется ориентированным деревом или сокращенно – деревом, если между корнем дерева v0 и любой другой вершиной существует единственный путь, берущий начало в v0. Ниже представлены два примера деревьев: неориентированного дерева (рис. 2.5, а) и ориентированного дерева (рис. 2.5, б).
В случае неориентированного дерева (рис. 2.5, а) любая из вершин графа может быть выбрана в качестве корня. Подобный выбор определяется специфическими особенностями решаемой задачи. Так, вершина v1 может рассматриваться в качестве корня неориентированного дерева, поскольку между v1 и любой другой вершиной дерева всегда существует единственная простая цепь по определению (или, что менее строго, единственный неориентированный путь).
Рис. 2.5.Примеры неориентированного (а) и ориентированного (б) деревьев
Для случая ориентированного дерева (рис. 2.5, б) вершина v2 является единственным его корнем и имеет специальное обозначение v0. Единственность корня в ориентированном дереве следует из того факта, что ориентированный путь всегда имеет единственную вершину, которая является его началом. Поскольку в теории графов имеет значение только наличие или отсутствие связей между отдельными вершинами, деревья, как правило, изображаются специальным образом в виде иерархической структуры. При этом корень дерева изображается самой верхней вершиной в данной иерархии. Далее следуют вершины уровня 1, которые связаны с корнем одним ребром или одной дугой. Следующий уровень будет иметь номер 2, поскольку соответствующие вершины должны быть связаны с корнем двумя последовательными ребрами или дугами. Процесс построения иерархического дерева продолжается до тех пор, пока не будут рассмотрены вершины, которые не связаны с другими вершинами, кроме рассмотренных, или из которых не выходит ни одна дуга. В этом случае самые нижние вершины иногда называют листьями дерева. Важно иметь в виду, что в теории графов дерево «растет» вниз, а не вверх, как в реальной жизни.
Изображенные выше деревья (рис. 2.5) можно преобразовать к виду иерархий. Например, неориентированное дерево (рис. 2.5, а) может быть представлено в виде иерархического дерева следующим образом (рис. 2.6, а). В этом случае корнем иерархии является вершина v1. Ориентированное дерево (рис. 2.5, б) также может быть изображено в форме иерархического дерева (рис. 2.6, б), однако такое представление является единственным.
В первом случае (рис. 2.6, а) вершина v2 образует первый уровень иерархии, вершины v4 и v3 – второй уровень иерархии, вершина v5 – третий и последний уровень иерархии. При этом листьями данного неориентированного дерева являются вершины v3 и v5. Во втором случае (рис. 2.6, б) вершины v1 и v5 образуют первый уровень иерархии, вершины v4 и v6 – второй уровень иерархии, вершина v3 – третий и последний уровень иерархии. Листьями данного ориентированного дерева являются вершины v3 и v6.
Рис. 2.6.Иерархические схемы неориентированного дерева (а) и ориентированного дерева (б)
В заключение следует заметить, что в теории графов разработаны различные методы анализа отдельных классов графов и алгоритмы построения специальных графических объектов, рассмотрение которых выходит за рамки настоящей книги. Для получения дополнительной информации по данной теме можно рекомендовать обратиться к специальной литературе по теории графов, где эти вопросы рассмотрены более подробно. В дальнейшем нас будет интересовать отдельное направление в теории графов, которое связано с явным включением семантики в традиционные обозначения и получившее самостоятельное развитие в форме семантических сетей.
Семантические сети
Семантические сети получили свое развитие в рамках научного направления, связанного с представлением знаний для моделирования рассуждений человека. Эта область научных исследований возникла в рамках общей проблематики искусственного интеллекта и была ориентирована на разработку специальных языков и графических средств для представления декларативных или, что менее точно, статических знаний о предметной области. Результаты исследований в области семантических сетей в последующем были конкретизированы и успешно использованы при построении концептуальных моделей и схем реляционных баз данных.
В общем случае под семантической сетью понимают некоторый граф Gs= =(Vs, Es), в котором множество вершин Vs и множество ребер Es разделены на отдельные типы, обладающие специальной семантикой, характерной для той или иной предметной области. В данной ситуации множество вершин может соответствовать объектам или сущностям рассматриваемой предметной области и иметь вместо номеров вершин соответствующие явные имена этих сущностей. Подобные имена должны позволять однозначно идентифицировать соответствующие объекты, при этом общих формальных правил записи имен не существует. Множество ребер также делится на различные типы, которые соответствуют различным видам связей между сущностями рассматриваемой предметной области.
Так, при построении семантической сети для представления знаний о рабочем персонале некоторой компании в качестве объектов целесообразно выбрать отдельных сотрудников, каждого из которых идентифицировать собственным именем и фамилией. Дополнительно в сети могут присутствовать такие объекты, как рабочие проекты и подразделения компании. В качестве семантических связей можно выделить такие виды, как должностное подчинение сотрудников, участие сотрудников в работе над проектами, принадлежность сотрудников тому или иному подразделению компании.
Важной особенностью семантических сетей является разработка специальных графических обозначений для представления отдельных типов вершин и ребер. При этом вершины не изображаются, как ранее – точками, а имеют вид прямоугольников, овалов, окружностей и других геометрических фигур, конкретный вид которых определяет тот или иной тип сущностей предметной области. Более разнообразным становится и изображение ребер, приобретающих вид различных линий со стрелками или без них, а также имеющих специальные обозначения или украшения в виде условных значков. Соответствующая система обозначений, предназначенная для представления информации об отдельных аспектах моделируемой предметной области, получила название графической нотации.
Примечание 15
В качестве конкретного варианта представления информации в виде семантической сети рассмотрим дальнейшее развитие примера с классом «Автомобиль» из главы 1. Фрагмент семантической сети, которая описывает иерархию классов данной предметной области, может быть изображен следующим образом (рис. 2.7). На данном рисунке отдельные вершины семантической сети изображаются прямоугольниками с закругленными концами и служат для условного обозначения классов данной предметной области. Соединяющие вершины ребра имеют вполне определенный смысл или семантику. А именно, они явно указывают, что вершина или класс, расположенные на рисунке ниже, являются подклассом того класса уровнем выше, с которым имеется связь в форме соединяющего их ребра.
Например, классы «Легковой автомобиль» и «Грузовой автомобиль» являются подклассами класса «Автомобиль», а классы «Модель ВАЗ-21083» и «Модель ВАЗ-21099» являются подклассами класса «Легковой автомобиль производства ВАЗ». Ребра или связи данной семантической сети имеют единственный тип, определяемый семантикой включения классов друг в друга. Поэтому никаких дополнительных обозначений они не содержат.
Рис 2.7.Фрагмент семантической сети для представления иерархии классов «Автомобиль»
Примечание 16
Построение моделей сложных систем, отражающих десятки различных типов объектов и связей между ними, привело в конце 80-х годов к появлению большого числа различных графических нотаций, которые в той или иной степени были ориентированы на решение специальных классов задач. Сложилась парадоксальная ситуация, которая получила название «войны методов». Многие подходы, хотя и имели общие истоки, совершенно игнорировали другие альтернативные способы представления семантической информации. Наибольшее распространение в эти годы получил подход к моделированию программных систем, который назвали системным структурным анализом (ССА). Поскольку многие идеи ССА оказали непосредственное влияние на развитие языка UML, а используемая графическая нотация была реализована в некоторых CASE-средствах, ниже приводится краткая характеристика основных компонентов данного направления графического моделирования программных систем.
<< | >>
Источник: Александр Леоненков. Самоучитель UML. 2007

Еще по теме 2.1. Предыстория. Математические основы:

  1. ТЕМА 3. Математические основы оценочной деятельности
  2. ГЛАВА 2. МАТЕМАТИЧЕСКИЕ ОСНОВЫ ФИНАНСОВО-ЭКОНОМИЧЕСКИХ РАСЧЕТОВ ПРИ ПРИНЯТИИ ФИНАНСОВО-КРЕДИТНЫХРЕШЕНИЙ
  3. МАТЕМАТИЧЕСКАЯ ЛОГИКА
  4. Математическая теория игр
  5. ТЕОРИЯ СПРОСА — МАТЕМАТИЧЕСКИЙ ПОДХОД
  6. ТЕОРИЯ СПРОСА — МАТЕМАТИЧЕСКИЙ ПОДХОД
  7. Математический подход к анализу «затраты — выход продукции — прибыль»
  8. ПРИЛОЖЕНИЕО ПРОБЛЕМАХ МАТЕМАТИЧЕСКОЙ ИНТЕРПРЕТАЦИИ ДВУХСЕКТОРНОЙ МОДЕЛИ СМЕШАННОЙ ЭКОНОМИКИ
  9. P. S.Через четыре года все опять повторится сначала, поэтому сохраните это пособие. Математическая модель предвыборной кампании для оценки ее эффективности
  10. Аристотель, В. Шкоды. Философы Греции. Основы основ: логика, физика, этика, 1999
  11. А. В, Сидорови. Общие основы экономической теории. Микроэкономика. Макроэкономика. Основы национальной экономики, 2001
  12. 29. ПРАВО НА ОБЪЕДИНЕНИЕ В РФ: СОДЕРЖАНИЕ И НОРМАТИВНАЯ ОСНОВА. ОСНОВЫ ПРАВОВОГО СТАТУСА ОБЩЕСТВЕННЫХ ОБЪЕДИНЕНИЙ