39019

Теория графов и графовые сети

Лекция

Информатика, кибернетика и программирование

Кстати наш вебкурс также представляет собой сложную систему.1 Вебсистемы После построения Интернет и создания на его базе Всемирной паутины World Wide Web WWW в компьютерном мире появились вебинформационные системы или кратко вебсистемы. Под вебсистемой мы будем понимать компьютерную систему работающую на основе Интернет Веб. Можно привести многочисленные примеры конкретных вебсистем.

Русский

2013-09-30

98.5 KB

36 чел.

               ЧАСТЬ 2. ГРАФОВЫЕ И ПАТТЕРНОВЫЕ СЕТИ

                                       Эпиграф.

                           Математики изучают не предметы, а

                           только лишь отношения между ними.

                                      Анри Пуанкаре

               ЛЕКЦИЯ 6. Теория графов и графовые сети

    Разделы Лекции 5:  5.1 Диаграмма прецедентов,  5.2 Проектирование баз данных, 5.3 Другие диаграммы компьютерной системы Истерн.

                6.1. Графы как модели сложных систем.

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

    Модель, отображающую точку зрения на  систему,  называют  "видом" или "взглядом" (view).

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

    Разработчики сложной системы, когда они рассматривают ее с разных точек зрения и строят для каждой точки зрения модели (виды), действуют примерно также как инженер-конструктор, который рассматривает с разных точек зрения сложную деталь изделия и чертит на бумаге ее виды -  "вид прямо", "вид  сверху",  "вид  сбоку" и дополнительные виды по стрелкам А,Б и другим.

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

    Рассматривая язык  UML  мы  отмечали,  что он опирается на теорию множеств и теорию графов.  Мы не будем затрагивать теорию множеств,  а рассмотрим  только  теорию  графов,  поскольку она позволяет создавать наглядные модели сложных систем,  понятные широкому  кругу  людей.  Но прежде чем начать рассказ о теории графов, объясним необходимое для ее понимания математическое понятие "бинарные отношения".

                    6.2. Бинарные отношения

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

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

     Любое бинарные отношение представляется множеством упорядоченных пар элементов. В математике множество элементов обозначается с помощью двух фигурных скобок { }, а упорядоченная пара с помощью символов < >. Множество {<2,4>,<7,3>,<3,3>},  будучи множеством,  состоящим из  трех упорядоченных  пар,  есть  бинарное  отношение.  Пара  <2,4>  является элементом этого бинарного отношения. Элемент бинарного отношения, т.е. упорядоченную  пару  в  общем  случае  обозначим <x1 ,x2>.  Элементы в упорядоченной  паре  нельзя  менять  местами  и,  наоборот,   элементы множества  можно менять местами и при этом множество не меняется,  т.е два множества с одинаковыми,  но по разному расположенными  элементами равны. Например {1,2}={2,1}.     В качестве    примера    бинарного   отношения   рассмотрим   все упорядоченные пары элементов,  которые можно  составить  на  множестве {1,2}. Для  множества  {1,2}  путем  перестановки  его элементов можно составить всего лишь две упорядоченные пары <1,2> и  <2,1>.  Набор  из двух  упорядоченных  пар  <1,2>,  <2,1>  является  примером  бинарного отношения, установленного на  множестве  двух  элементов  {1,2}.  Если множество  состоит  из  трех  элементов,  то  самое  большое  бинарное отношение, которое  можно  построить   на   нем,   состоит   из   6-ти упорядоченных   пар.  Подмножество  этого  бинарного  отношения  может состоять, например, только из 3-х упорядоченных пар. Очевидно, что для

множества  из  n  элементов  самое большое (полное) бинарное отношение будет состоять из С2n = n(n-1) упорядоченных  пар.  Эти  математические рассуждения пригодятся нам при рассмотрении теории графов.

    Поскольку бинарные отношения постоянно встречаются в математике и науке о компьютерах, то, часто, прилагательное "бинарное" опускается и вместо словосочетания "бинарное отношение" говорят просто "отношение".

    Рассмотрим теперь бинарные отношения,  записываемые не в числовом виде,  а  с помощью слов.  Пусть имеется множество,  состоящее из двух словесных элементов {"отец-Иван",  "сын Ивана-Николай"}. Установленное на нем полное бинарное отношение состоит из двух упорядоченных  пар  - <отец-Иван,  сын-Николай>  и <сын-Николай,  отец-Иван>.  Поименованные бинарные отношения используются в реляционных базах данных.

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

                      6.3. Теория графов

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

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

    Итак в  Кенигсберге (ныне г.  Калининград) течет река Неман.  Она омывает два острова.  Между  берегами  реки  и  островами  во  времена проживания  в  Кенигсберге Эйлера существовали 7 мостов,  расположение которых показывает план на Рис. 6.1.

                                РИС.6.1

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

островами и мостами,  3) абстрагировал ассоциированный с данными  граф от  его  содержания  (см.  Рис.6.1.б);  это  решающий  шаг рассуждений Эйлера,  поскольку абстрактный граф можно ассоциировать с чем  угодно, например с площадями и улицами между ними,  4) сформулировал и доказал следующую теорему - Конечный граф G является эйлеровым графом тогда  и только тогда, когда

    а) Граф G связан

    б) Все его локальные степени четные.

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

    Любой граф может быть нарисован на бумаге или экране компьютера и представлен формально.  Поэтому нарисованный на экране компьютера граф может  быть  транслирован  в память компьютера.  Покажем каким образом графы рисуются на бумаге и представляются формально  на  примере  трех простейших  графов,  каждый  из  которых состоит из одного ребра.  Они показаны на Рис. 6.2.

                               РИС. 6.2

    Рис.6.2 раскрывает   сущность   теории   графов   в  наглядной  и

формальной формах.

              Четыре задачи для домашнего решения:

 1. Построить   полный   ориентированный   граф,   моделирующий   все родственные отношения в семье,  состоящей из отца-Ивана, матери-Марии, сына-Николая и деда Федора (отца отца-Ивана).

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

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

 4. Показать,  что оба ассоциированные графа,  построенные в  задачах 1,3, имеют одинаковую структуру ( один и тот же "скелет").

           ЛЕКЦИЯ 7  Теория паттернов и паттерновые сети

  Разделы Лекции  6:  6.1 Значение графов как моделей сложных систем.

6.2 Бинарные отношения,  6.3 Теория графов.

                         7.1 Веб-системы

    После построения  Интернет  и  создания  на  его  базе  Всемирной паутины (World  Wide  Web,  WWW)   в   компьютерном   мире   появились веб-информационные системы или кратко веб-системы. Под веб-системой мы будем   понимать   компьютерную   систему,   работающую   на    основе Интернет/Веб.   Можно   привести   многочисленные  примеры  конкретных веб-систем. Например, веб-системами являются электронные правительства (е-правительства,  е-gov), создаваемые в настоящее время, практически, во всех странах мира.  Если обратиться к  России,  то  у  нас  сегодня создаются  федеральное  е-правительство  и  е-правительства  некоторых субъектов  Р.Ф.  Примером   регионального   е-правительства   является создаваемое в настоящее время е-правительство Чувашской республики.

    В состав     веб-систем    входят    веб-компоненты,    например, веб-документы,  веб-страницы.  Одной  из   разновидностей   веб-систем являются виртуальные университеты,  работающие на основе Интернет/Веб. Веб-курсы - это компоненты виртуальных университетов.

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

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

  7.2 Паттерновые (модульные) сети и парадигма модульного мышления

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

    Модули и модульные системы повсеместны.  Тем  более  удивительно, что  до  последнего  времени  не  было создано единой теории модульных систем,  позволяющей формально и наглядно представлять различные  виды модулей и составленные из них разнообразные модульные системы. Лишь во второй  половине  20  века  выдающийся  американский  математик   Ульф Гренандер построил основы такой теории и назвал ее теорией паттернов.

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

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

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

    Паттерновые сети   состоят  из  модульных  логических  элементов, неотделимыми от    нее    связями    (bonds),   которые   могут   быть ориентированными    (входными/выходными)    или    неориентированными. Образующая,  имеющая  только входные и/или выходные связи,  называется ориентированной,  а  образующая   с   неориентированными   связями   - неориентированной.

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

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

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

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

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

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

    Практика показала, что благодаря детальному описанию внутренних и внешних границ модульных систем, паттерновые сети являются эффективным средством моделирования   и  проектирования  веб-систем,  веб-страниц, учебных веб-курсов и иных веб-компонентов.  Вместе с тем, исследования свидетельствуют  о перспективности их использования для решения многих других компьютерных задач,  требующих модульного подхода.  Например, с помощью  паттерновых  сетей  можно  расширить возможности стандартного языка  UML  за  счет   создания   модульных   диаграмм,   изображающих внутренние и  внешние  границы  веб-систем.  Перспективно   применение паттерновых сетей  к  обучению студентов и к объектно-ориентированному программированию.  Значительный  практический   интерес   представляет применение паттерновых  сетей к моделированию модульных свойств языков X-Link и X-Pointer,  а также к стандартизации гипертекстовых навигаций внутри   XHML-документов и  между  ними.  Паттерновые  сети  позволили обнаружить структурную аналогию компьютерных гипертекстов и нейросетей мозга.   Учитывая   полученные  результаты  и  перспективы  модульного моделирования,  следует ожидать, что уже в ближайшее время паттерновые сети   найдут   широкое   применение   в  компьютерном  мире  и  будут использоваться во многих других областях знаний.

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

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

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

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

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

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

               7.3. Дискретная теория паттернов

                       Единственный   естественный   предмет

                       математической мысли есть целое число

                                        Анри Пуанкаре

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

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

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

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

             7.4  Модульные свойства паттерновых сетей

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

                            РИС.7.1

    На Рис.7.1а изображен элементарный ориентированный граф.  На  нем показано,  что  ребро  графа  нельзя разрезать (разъединить).  Ниже на Рис.7.1б изображена наглядная схема линейной ориентированной паттерновой сети,  состоящей  из двух линейных ориентированных образующих g1,  g2. Образующая g1 имеет вершину и две связи  (bonds).  Вершина  изображена точкой  и помечена именем (идентификатором) образующей,  роль которого выполняет символ g,  помеченный индексом 1.  Помимо вершины образующая g1 имеет две ориентированный связи - входную и выходную. Входная связь представлена  треугольником  и  стрелкой,  направленной  к  точке,   а выходная   связь  стрелкой  направленной  от  точки  и  треугольником. Образующая g2 имеет аналогичную наглядную схему.  На рисунке  выходная связь  первой образующей соединена с входной связью второй образующей, в результате чего из двух соединенных треугольников образовался  ромб. Ромб и две примыкающие к нему стрелки называются связкой образующих g1 и g2 или связкой паттерновой сети. Каждой связи на Рис.7.1б  приписаны переменные, обозначенные символами    с   соответствующими  нижними числовыми индексами и верхними индексами in и out.  Индексы in  и  out означают,  что  переменные присвоены соответственно входным и выходным связям образующих. Четырем переменным поставлены в соответствие четыре области  значений  (данных),  обозначенные  символами D,  и называемые доменами.  В доменах содержатся значения,  которые могут присваиваться переменным     .  Если  двум  переменным ,  участвующим  в связке присвоены значения,  удовлетворяющие  условию  соединения  связки,  то связка является истинной (замкнутой) . Если переменным присвоены значения, не удовлетворяющие  условию  соединения  связки,  то  связка является  ложной (разомкнутой).  Образующие g1 и g2 служат обобщенными моделями двух реальных модулей,  каждый их которых имеет один  вход  и один  выход. Паттерновая сеть, показанная на Рис.7.1б, моделирует два реальных модуля выход одного из которых  соединен  с  входом  другого. Несоединенные  связи  этой  паттерновой  сети  изображают открытые для соединения  вход  и  выход  реальной  системы,   состоящей   из   двух соединенных модулей.

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

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

    Наглядная схема простой линейной ориентированной паттерновой сети (Рис.7.1)  и  приведенное  здесь  ее  словесное  пояснение помогут вам понять формальные описания и  наглядные  схемы  сложных  образующих  и паттерновых сетей, рассмотренных в последующих лекциях.


f

g

d

c

b

р. Неман

a

B

C

D

g

c

b

a

A

D

B

f

C

d

Составы графов: 1,2

1

2

2

1

2

1

{1,2}

<2,1>

<1,2>

Структуры графов:


 

А также другие работы, которые могут Вас заинтересовать

16487. Византология. Учебное пособие 276.2 KB
  Византология III курс 2е полугодие Пособия к курсу Византологии: 1. Терновский Ф.А. Терновский С.А. ГрекоВосточная Церковь в период Вселенских Соборов. Киев 1883. Само название книги связано с церковной историей. Курс Византологии в Академии до сих пор и это себя оправды...
16488. ЛЕКЦИИ ПО ВИЗАНТОЛОГИИ 218.24 KB
  Феномен Византии - соединение христианской веры, Римской государственности и греческой культуры. Два их этих комп.уже сочетались задолго до Р.Х., и в царствование Константина Великого к ним добавился третий компонент. Царствование его и считают началом Византии
16490. Искусство домонгольской Руси 17.5 KB
  Искусство домонгольской Руси Киевское государство возникшее в IX веке достигло своего могущества в X–XI столетиях. При князе Владимире жившем в конце X–начале XI столетия Русь приняла крещение от Византии. Этот акт имел существенные последствия для дальнейшего разви...
16491. Музей боярского быта на примере дома бояр Романовых 37.5 KB
  Тема: Музей боярского быта на примере дома бояр Романовых Музей боярского быта на примере дома бояр Романовых Зарядье один из древнейших районов Москвы который был расположен к востоку от Кремля между улицей Варварка и Москвойрекой. ...
16492. Василий Иванович БАЖЕНОВ (1737–1799) 21.78 KB
  Василий Иванович БАЖЕНОВ 1737–-1799 Баженов Василий Иванович художникархитектор сын священника одной из придворных кремлевских церквей. Родился 1 марта 1737 года в Москве. Баженов имел природный талант к искусству который обнаружил еще в детстве срис
16493. Подмосковная усадьба Кусково 37 KB
  Тема: Подмосковная усадьба Кусково В круг памятников архитектуры нельзя не ввести ряд подмосковных усадеб некогда располагавшихся близко от границ столицы а ныне вошедших в ее территорию. Среди них имеются как очень большие типа дворцовых рези
16494. Искусство Среднего царства 76 KB
  Искусство Среднего царства На время VII–X династии приходится первый Период распада страны. По свидетельству Манефона 70 царей VII династии правили 70 дней. Эта образная характеристика воссоздает перед нами картину смут которые наступили после деце
16495. Римское искусство 21.5 KB
  Римское искусство. Искусство древнего Рима как и древней Греции развивалось в рамках рабовладельческого общества поэтому именно эти два основных компонента имеют ввиду когда говорят об античном искусстве. Искусство Рима считают завершением художественного твор...