2.Способы описания алгоритмов обработки и вычислительных сетей.

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

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

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

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

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

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

2.1.1. Теоретико-множественные понятия.

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

Пусть A и B – множества. Отношением (бинарным) из A в B называется любое подмножество множества A  B (декартова произведения). Если R – отношение из A в B и (a, b)  R, где (a, b) - упорядоченная пара объектов, то это представляется в виде aRb. Отношение R можно считать некоторым условием, задаваемым в различных видах: формульном, перечислением, логическом и т.п.

Если A = B, то тогда считается, что отношение R задано на A.

Пусть A – множество и R – отношение на A. Определим ряд важных свойств бинарного отношения.

Отношение R называется:

• рефлексивным, если aRa для всех а из А (a  A).

• симметричным, если aRb  bRa для a и b из A.

• транзитивным, если aRb и bRc  aRc для a, b, c из А.

Эти отношения могут быть также соответственно записаны:

(a, a)  R

(a, b)  R и (b, a)  R

(a, b)  R и (b, c)  R, то (a, c)  R.

Известно, что отношение R со свойствами рефлексивности, симметричности и транзитивности называется отношением эквивалентности.

Сделаем следующее важное замечание.

Недопустимо считать, что симметричное и транзитивное отношения обязаны быть рефлексивными (так как aRb и bRa  aRa). Свойство рефлексивности выступает самостоятельно, то есть независимо от наличия других свойств.

Транзитивное замыкание отношения R на множестве А, обозначаемое через R⁺, представляется в виде aR⁺b  aRⁱb, где Rⁱ – i-ая степень отношения R, для некоторого i  1 (т.е. существует такая последовательность c₁, c₂,…, c_i-1, состоящая их нуля или более элементов, принадлежащих А, что aRc₁, c₁Rc₂,…, c_i-1Rb; если i = 1, то имеем aRb).

i-ая степень отношения Rⁱ просто дает возможность определить существование пути от a к b, включающего заданное количество промежуточных элементов (рис.2.1).

Р ефлексивное и транзитивное замыкание отношения R на множестве A обозначается через R^* и представляется в виде aR^*b  aRⁱb, i  0, a aR^ob  a = b.

Единственное различие между R^* и R⁺ состоит в том, что aR^*a истинно для всех a  R, но aR⁺a может быть, а может и не быть истинным.

Порядок на множестве A – это любое транзитивное отношение на A. Множество, на котором задан порядок, называется упорядоченным.

Частичный порядок на множестве A – это отношение R, определенное на A, такое, что

• R – транзитивно

• R – иррефлексивно, (a, a)  R, т.е. a утверждение aRa – ложно.

Из этого, в частности, вытекает, что если aRb истинно, то bRa ложно. Последнее определяет свойство асимметричности (либо aRb, либо bRa).

Рассмотрим собственное включение множеств. [Пусть A и B множества. Тогда, если B содержит элемент, не принадлежащий A, и A  B, то эту ситуацию обозначают A  B (A собственно содержится в B)]. Введем исходное конечное множество D = {1, 2, 3} и образуем множество A как множество всех подмножеств D, то есть A = 2^D.

A = 2^D = {0, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

О пределим на A отношение R следующим образом. Для a, b  A aRb тогда и только тогда, когда a  b. Отношение R в этом случае является частичным порядком. На рис.2.2 дано графическое изображение этого порядка, стрелки между двумя элементами указывают на наличие собственного включения.

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

Рефлексивный частичный порядок на множестве A – это отношение R, обладающее свойствами:

• R – транзитивно (a, b)  R и (b, c)  R, то (a, c)  R

• R – рефлексивно (a, a)  R

• R – антисимметрично (a, b)  R и (b, a)  R, то a = b

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

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

Линейный порядок R на множестве A – это такой частичный порядок, что a, b  A - либо aRb, либо bRa, либо a = b (так как для одного и того же элемента отношения не существует). Если A – конечное множество, то линейный порядок R целесообразно представлять, считая все элементы множества A расположенными в виде последовательности a₁,a₂,a₃,…,a_n, для которой a_iRa_j, тогда и только тогда, когда i < j.

Далее будет показано, что любой частичный порядок допускает вложение в линейный порядок.

Аналогично определяется и рефлексивный линейный порядок, то есть рефлексивный линейный порядок R на A – это такой рефлексивный частичный порядок, что a, b  A либо aRb, либо bRa.

Отношение < (меньше), определенное на множестве неотрицательных целых чисел, является линейным порядком; а отношение  (меньше, равно) – рефлексивный линейный порядок.

2.1.2. Некоторые понятия теории графов.

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

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

Ориентированный граф G - это пара (A, R), где А – множество элементов, называемых вершинами (узлами), а R - отношение на множестве А. Пара (a, b)  R называется дугой графа G, то есть дуга выходит из вершины а и входит в вершину b; если (a, b) - дуга, то вершина a предшествует вершине b, а вершина b следует за вершиной a.

На множестве дуг графа каждая встречается только один раз. Тем самым, отношение R в графе интерпретируется совокупностью дуг (a, b)  aRb (рис.2.3).

Часто вершинам и/или дугам графа приписывают некоторую информацию. Тогда такой граф называют помеченным/нагруженным/размеченным.

Пусть (A, R) - граф. Разметкой графа называется пара функций f и g , где f – разметка вершин, отображает А в некоторое множество, а g - разметка дуг, также отображает R в некоторое (в общем, отличное от первого) множество, т.е. например, f: A  , g: R  , где –  множество всех вещественных чисел.

Разметка графа при практическом применении характеризует графовую модель в терминах (параметрах) области применения.

Последовательность вершин (а₀, а₁, …, а_n), n  1 называется путем (маршрутом) длины n из вершины а₀ в вершину а_n, если для каждого 1  i  n существует дуга, выходящая из вершины а_i-1 и входящая в вершину а_i. Если существует путь из вершины а₀ в вершину а_n, то тогда вершина а_n достижима из а₀.

Циклом называется путь (а₀, а₁, …, а_n), в котором а_n = а₀. Граф называется сильно связанным, если для любых двух разных вершин а и b существует путь из а в b. Так граф на рис.2.3 является сильно связанным.

Степенью по входу вершины а называется число входящих в неё дуг; степенью по выходу – число выходящих из неё дуг. Так вершина 4 графа G на рис.2.3 имеет степень входа - 2, и степень выхода - 2.

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

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

Если R – частичный порядок на множестве А, то (A, R) – ациклический граф. Действительно, для частичного порядка следует свойство асимметричности, то есть отсутствие циклов.

Для частичного рефлексивного порядка R на A существуют только циклы длины n = 0 (происходит замыкание каждой вершины графа на себя).

Применительно к замечанию в 2.1.1 наличие свойств симметричности и транзитивности проявляется в графе наличием циклов различной длины n  1 (но не n = 0!).

Если (a, b) – дуга ациклического графа, то a называется прямым предком, а b – прямым потомком. Если в ациклическом графе существует путь из а в b, то тогда а – является предком b, а b потомком а.

Е
сли (A, R) - ациклический граф, и R – отношение - «является потомком», определённое на А, то R - частичный порядок на А.