39019

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

Лекция

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

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

Русский

2013-09-30

98.5 KB

37 чел.

               ЧАСТЬ 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>

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


 

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

22026. Метод ДСК 195 KB
  Температуры плавления некоторых синтетических фосфолипидов Жирные кислоты Название остатка жирной кислоты Сокращённое название фосффолипида Температура плавления Tc oC 14:0 Миристоил ДМЛ 23 16:0 Пальмитоил ДПЛ 41 18:0 Стеароил ДСЛ 58 18:1 Олеил ДОЛ 21цисформа Полное название фосфолипидов: ДМЛ 12димиристоилфосфатидилхолин еще одно возможное сокращение ДМФХ€ и так далее. На первом этапе нас будут интерессовать три из них: Температура фазового перехода плавления Tc. T полуширина фазового перехода Tc температура...
22027. Активированная хемилюминесценция и биолюминесценция 114 KB
  Так например комплекс редкоземельного иона европия Eu3 c антибиотиком хлортетрациклином усиливает ХЛ при окислении липидов почти в 1000 раз. Хемилюминесцентный иммунный анализ По идеологии хемилюминесцентный иммунный анализ не отличается от радиоиммунного с той только разницей что вместо радиоактивномеченных субстратов или антител используются субстраты и антитела меченные соединением которое вступает в реакции сопровождающиеся хемилюминесценцией в присутствии перекиси водорода и катализатора обычно это фермент пероксидаза....
22028. Биологические мембраны Строение, свойства, функции 403 KB
  Клеточная или цитоплазматическая мембрана окружает каждую клетку. Ядро окружено двумя ядерными мембранами: наружной и внутренней. Все внутриклеточные структуры: митохондрии эндоплазматический ретикулум аппарат Гольджи лизосомы пероксисомы фагосомы синаптосомы и т представляют собой замкнутые мембранные везикулы пузырьки.
22029. Мембранные потенциалы 232.5 KB
  Более подробно межфазные и поверхностные потенциалы будут рассмотрены позже а сейчас мы рассмотрим как повлияет на перенос ионов наличие на мембране трансмембранного потенциала. Однако липидная часть мембраны состоит всегото из двух слоёв молекул фосфолипидов причём размеры подвижных звеньев цепей жирных кислот в этих молекулах соизмеримы с размерами ионов которые передвигаются внутри мембраны. Это заставляет при рассмотрении переноса ионов в мембране отказаться от полностью макроскопического подхода к явлениям и рассматривать процессы на...
22030. Перемещения иона в мембране 347 KB
  В случа переноса ионов через биомембраны за ось Х можно принять ось нормальную к мембране и направленную изнутри везикулы например клетки наружу см. Как же перемещается ион в толще липидного слоя мембраны В разделе 1 говорилось о том что такое перемещение возможно благодаря перестройке конфигурации жирнокислотных цепей и образованию нового кинка . Движение иона поперёк мембраны путём перескакивания из одного кинка в другой. На рисунке показаны не разные молекулы фосфолипидов в бислое а разные стадии процесса переноса иона...
22031. Системы передачи с временным разделением каналов 139 KB
  Напомним что для преобразования аналогового сигнала в цифровой используются операции ДИСКРЕТИЗАЦИЯ КВАНТОВАНИЕ КОДИРОВАНИЕ. Значение шума квантования зависит от количества уровней квантования скорости изменения сигнала и от спосрба выбора шага квантования. не зависит от а } = где вероятность попадания сигнала в iю зону квантования. зависит лишь от шага квантования и не зависит от уровня сигнала.
22032. Дельта - модуляция (кодирование с предсказанием) (ДИКМ) 158.5 KB
  Основные параметры характеристики компрессии по А закону приведены в таблице: № сегмента Вид кодовой комбинации P XYZ ABCD Относительный интервал изменения входного сигнала Значение шага квантования относительно Uогр 0 P 000 ABCD 0  1 128 1 2048 1 P 001 ABCD 1 128  1 64 1 2048 2 P 010 ABCD 1 64  1 32 1 1024 3 P 011 ABCD 1 32  1 16 1 512 4 P 100 ABCD 1 16  1 8 1 256 5 P 101 ABCD 1 8  1 4 1 128 6 P 110 ABCD 1 4  1 2 1 64 7 P 111 ABCD 1 2  1 1 32 Кодовая комбинация и есть код квантованного сигнала P  ABCD ...
22033. Особенности передачи сигналов данных 67 KB
  Качество передачи при этом оценивается не искажениями формы сигналов как в аналоговых системах а числом ошибок в принятой информации т. верностью передачи. В хороших модемах перед началом передачи информации вначале устанавливается связь между модемами которые автоматически обмениваясь сигналами подстраиваются под конкретную линию связи и автоматически выбирают необходимую скорость передачи а затем передают саму информацию.
22034. Графическая визуализация вычислений 83.54 KB
  В ходе выполнения данной лабораторной работы я освоил визуализацию вычислений средствами указанных функций