Оценка сложности алгоритмов. Нотация асимптотического роста

Оценка сложности алгоритмов Вычислительная сложность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Нотация асимптотического роста Несмотря на то, что функция временной сложности алгоритма в некоторых случаях может быть определена точно, в большинстве случаев искать точное её значение бессмысленно. Дело в том, что во-первых, точное значение временной сложности зависит от определения элементарных операций (например, сложность можно измерять в количестве арифметических операций, битовых операций и т.д.), а во-вторых, при увеличении размера входных данных вклад постоянных множителей и слагаемых низших порядков, фигурирующих в выражении для точного времени работы, становится крайне незначительным. Рассмотрение входных данных большого размера и оценка порядка роста времени работы алгоритма приводят к понятию асимптотической сложности алгоритма. При этом алгоритм с меньшей асимптотической сложностью является более эффективным для всех входных данных, за исключением лишь, возможно, данных малого размера. Для записи асимптотической сложности алгоритмов используются асимптотические обозначения Память или время Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём. Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив карту города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы. Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти. Из этой зависимости проистекает идея объёмно-временной сложности. При таком подходе алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения потреблённой памяти. Мы будем уделять основное внимание временной сложности, но, тем не менее, обязательно будем оговаривать и объём потребляемой памяти. Оценка порядка При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше. В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N). Рассмотрим код, который для матрицы A[NxN] находит максимальный элемент в каждой строке. В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N. Это определяет сложность алгоритма O(N^2). Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением N^3+N. В таком случае его сложность будет равна O(N^3). Рассмотрение быстро растущей части функции позволяет оценить поведение алгоритма при увеличении N. Например, при N=100, то разница между N^3+N=1000100 и N=1000000 равна всего лишь 100, что составляет 0,01%. При вычислении O можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим шагом 3N^3 рассматривается, как O(N^3). Это делает зависимость отношения O(N) от изменения размера задачи более очевидной. Определение сложности Наиболее сложными частями программы обычно является выполнение циклов и вызов процедур. В предыдущем примере весь алгоритм выполнен с помощью двух циклов. Если одна процедура вызывает другую, то необходимо более тщательно оценить сложность последней. Если в ней выполняется определённое число инструкций (например, вывод на печать), то на оценку сложности это практически не влияет. Если же в вызываемой процедуре выполняется O(N) шагов, то функция может значительно усложнить алгоритм. Если же процедура вызывается внутри цикла, то влияние может быть намного больше. В качестве примера рассмотрим две процедуры: Slow со сложностью O(N^3) и Fast со сложностью O(N^2). Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N^2 )*O(N^3 )=O(N^5). Если же основная программа вызывает процедуры по очереди, то их сложности складываются: O(N^2 )+O(N^3 )=O(N^3) Сложность рекурсивных алгоритмов Простая рекурсия Напомним, что рекурсивными процедурами называются процедуры, которые вызывают сами себя. Их сложность определить довольно тяжело. Сложность этих алгоритмов зависит не только от сложности внутренних циклов, но и от количества итераций рекурсии. Рекурсивная процедура может выглядеть достаточно простой, но она может серьёзно усложнить программу, многократно вызывая себя. Рассмотрим рекурсивную реализацию вычисления факториала: int factorial(int n) { if (n > 1) return n * factorial(n-1); else return 1; } Эта процедура выполняется N раз, таким образом, вычислительная сложность этого алгоритма равна O(N). Многократная рекурсия Рекурсивный алгоритм, который вызывает себя несколько раз, называется многократной рекурсией. Такие процедуры гораздо сложнее анализировать, кроме того, они могут сделать алгоритм гораздо сложнее. Рассмотрим такую функцию: void doubleRecursive(int n) { if (n>0) { doubleRecursive (N-1); doubleRecursive (N-1); } } Поскольку она вызывается дважды, можно было бы предположить, что её рабочий цикл будет равен O(2N)=O(N). Но на самом деле ситуация гораздо сложнее. Если внимательно исследовать этот алгоритм, то станет очевидно, что его сложность равна O(2^(N+1)-1)=O(2^N). Всегда надо помнить, что анализ сложности рекурсивных алгоритмов весьма нетривиальная задача. Объёмная сложность рекурсивных алгоритмов Для всех рекурсивных алгоритмов очень важно понятие объёмной сложности. При каждом вызове процедура запрашивает небольшой объём памяти, но этот объём может значительно увеличиваться в процессе рекурсивных вызовов. По этой причине всегда необходимо проводить хотя бы поверхностный анализ объёмной сложности рекурсивных процедур. Средний и наихудший случай Оценка сложности алгоритма до порядка является верхней границей сложности алгоритмов. Если программа имеет большой порядок сложности, это вовсе не означает, что алгоритм будет выполняться действительно долго. На некоторых наборах данных выполнение алгоритма занимает намного меньше времени, чем можно предположить на основе их сложности. Например, рассмотрим код, который ищет заданный элемент в векторе A. Если искомый элемент находится в конце списка, то программе придётся выполнить N шагов. В таком случае сложность алгоритма составит O(N). В этом наихудшем случае время работы алгоритма будем максимальным. С другой стороны, искомый элемент может находится в списке на первой позиции. Алгоритму придётся сделать всего один шаг. Такой случай называется наилучшим и его сложность можно оценить, как O(1). Оба эти случая маловероятны. Нас больше всего интересует ожидаемый вариант. Если элемента списка изначально беспорядочно смешаны, то искомый элемент может оказаться в любом месте списка. В среднем потребуется сделать N/2 сравнений, чтобы найти требуемый элемент. Значит сложность этого алгоритма в среднем составляет O(N/2)=O(N). В данном случае средняя и ожидаемая сложность совпадают, но для многих алгоритмов наихудший случай сильно отличается от ожидаемого. Например, алгоритм быстрой сортировки в наихудшем случае имеет сложность порядка O(N^2), в то время как ожидаемое поведение описывается оценкой O(N*log(N)), что много быстрее. Общие функции оценки сложности Сейчас мы перечислим некоторые функции, которые чаще всего используются для вычисления сложности. Функции перечислены в порядке возрастания сложности. Чем выше в этом списке находится функция, тем быстрее будет выполняться алгоритм с такой оценкой. 1. C – константа 2. log(log(N)) 3. log(N) 4. N^C, 01 8. C^N, C>1 9. N! Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит несколько этих функций, то уравнение можно сократить до функции, расположенной ниже в таблице. Например, O(log(N)+N!)=O(N!). Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно считать сложность O(N^2), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N). Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N^C можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями C^N и N! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных. В заключение рассмотрим таблицу, которая показывает, как долго компьютер, осуществляющий миллион операций в секунду, будет выполнять некоторые медленные алгоритмы. Возраст вселенной менее 14 млрд. лет. 1.1. Основные понятия о графах Множество - это совокупность определённых различаемых объектов таких, что для любого объекта можно установить, принадлежит этот объект данному множеству или нет. Множества принято обозначать заглавными латинскими буквами а их элементы – малыми буквами: Пустое множество обозначается символом . Запись означает, что объект a есть элемент множества А (т.е. принадлежит множеству А). Приведённые примеры позволяют разбить все множества на две большие группы: конечные и бесконечные. Математика в основном имеет дело с числовыми множествами, т.е. множествами, элементами которых являются числа. Для таких множеств имеются общепринятые обозначения: • N – множество натуральных чисел; • Z – множество целых чисел; • Q – множество рациональных чисел; • R – множество действительных чисел. Элементы множества - составляющие множество объекты. Способы задания(спецификации) множеств: В основном существует два способа задания (описания) множеств: 1. Множество А определяется непосредственным перечислением своих элементов , т.е. записывается в виде Например: 2. Множество задается характеристически свойством, т.е. определяется как совокупность тех и только тех элементов, которые обладают некоторым свойством (А – множество тех и только тех элементов некоторого основного множества T, которые обладают свойством . Например: . • перечислением (списком своих элементов), • порождающей процедурой (индуктивными или рекурсивными правилами), • описанием характеристических свойств (заданием разрешающей процедуры). ={x: x-множество (не принадлежит) x}={множества, которые не являются элементами самих себя} Утверждения Каждое множество есть подмножество самого себя: Множества А и B равны тогда и только тогда, когда и Пустое множество есть подмножество любого множества. Каждое множество имеет по крайней мере два различных подмножества: само А и пустое множество. Графом называется совокупность 2 множеств не пустого множества V (множества вершин) и множества E (множества рёбер) непорядочных пар элементов множества V. Каждый элемент инцидентен ровно 2 элементам Вершины и рёбра графа G называются его элементами. Смежность: Пусть V1 и V2 вершины тогда – ребро соединяющее их. Вершина V1 и ребро W-инцидентны, вершина V2 и W тоже инцидентны. 2 ребра инцидентные 1 вершине называются смежными, 2 вершины инцидентные 1 ребру тоже смежные. Диаграммы: Обычно граф изображают диаграммой: • вершины – точки или кружки; • рёбра – линии. Другие определения графа: В некоторых задачах инцидентные ребру вершины не равноправны и рассматриваются в определённом порядке. Это означает, что элементами множества W являются упорядоченные пары. Такой граф называется ориентированным графом или орграфом (рис.1.1). Рис.1.1 - Ориентированный граф В этом случае элементы множества V – узлы, а множества W – дуги. Первая по порядку вершина инцидентная ребру орграфа называется его началом, вторая – концом. Если элементами множества W может быть пара одинаковых элементов множества V, то такой элемент множества W называется петлей, а граф – граф с петлями или псевдограф. Если W является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными рёбрами, граф – мультиграфом. Если элементами множества W является не обязательно 2 элемента, а любые подмножества множества V, то такие элементы множества W называются гипердугами, граф – гиперграфом. Если задана функция или , то множество M называется множеством меток, граф – помеченный. Множество вершин смежных с вершиной Vi называют её окрестностью. Иногда используется понятие окрестности, граф определяется как множество вершин и множество её окрестностей. 1.2. Способы задания графа Задать граф означает описать множество вершин, рёбер, а также отношения инцидентности. Графы могут быть конечны и неконечны. Пример конечных и неконечных графов (рис. 1.2; рис.1.3): Рис.1.2 - Неконечный граф Рис.1.3 - Конечный граф Когда граф конечный, для описания вершин достаточно их пронумеровать. Представление конечных графов с помощью матрицы смежности (рис.1.4 - 1.9): или 0 Рис.1.4 - Конечный граф Вершины – строки, Ребра – столбцы. Рис.1.5 - Матрица смежности Рис.1.6 -Орграф Для орграфа 1 – Если Vi инцидентна ребру и является его концом, -1 – Vi инцидентна ребру и является его началом, 0 – Если не инциденты. 1 2 3 1 1 1 2 1 3 Рис. 1.7 -Матрица инцидентности Рис.1.8 -Орграф Матрица инцидентности: или 0 1 – Если вершина инцидентна ребру, 0 – В противном случае. 1 2 3 1 -1 1 -1 2 1 -1 3 1 1 Рис.1.9 -Матрица инцидентности Списки смежности: Представление графа с помощью списочной структуры, отражающей смежность вершин и состоящей из массива указателей (ориентированный - рис. 1.10; неориентированный - рис.1.11). Рис.1.10 -Представление ориентированного графа с помощью списочной структуры Рис.1.11 -Представление графа с помощью списочной структуры Массив дуг(рёбер) отражает списки пар смежных вершин. Обходы графа: Обходы графа или представление графа - это некоторое систематическое разложение его вершин или рёбер в глубину или ширину (рис.1.12; рис. 1.13). Обход в ширину (дерева и графа) происходит по уровням: сначала посещается вершина уровня 0 (заданная начальная вершина обхода), затем вершины уровня 1, находящиеся на расстоянии в 1 шаг от начальной вершины, затем – вершины уровня 2, расположенные на 2 шага от начала обхода, т. е. на 1 шаг от вершин уровня 1 и т. д. Уровень i+1 включает преемников вершин уровня i. Обход в ширину выполняется с помощью очереди вершин на посещение. Из головы очереди выбирается случайная вершина, а ее преемники заносятся в хвост очереди. Обход графа в глубину выполняется по принципу: если можно – вперед (вглубь) к приемнику, дальше от начала обхода, иначе – назад к предшествующей вершине на пути начала обхода. Рис.1.12 –Исходный граф Рис.1.13 -Разложение в глубину 1.3. Характеристики графов и операции над графами Степень вершин Степень вершины графа называются число инцидентных ей рёбер. Степень вершины vi обозначается. Максимальную степень графа обозначают ,а минимальную . Список степеней графа называется его степенной последовательностью. Вершина со степенью 0 называется изолированной. Со степенью 1 концевой или периферийной. Ребро инцидентной, концевой вершины называется концевым. Вершина графа смежная с каждой другой, называется доминирующей (рис.1.14). [15] Рис.1.14 - Доминирующая вершина Пусть не совпадающие вершины. Длина кратчайшего маршрута (простой цепи) называется расстоянием между вершинами и обозначается . Для фиксированной вершины Vi величина– эксцентриситет вершины I. Max из всех эксцентриситетов вершины – называется диаметром графа. Вершина Vi называется периферийной, если . Маршрутом в графе, называют чередующую последовательность вершин и рёбер, в которой 2 любых элемента инцидентны. Если где n – начало маршрута , k – конец маршрута, то маршрут замкнутый, иначе открытый(рис.1.15). Рис.1.15 - Маршрут графа Говорят ,что цепь с концами Vn и Vk соединяют вершины Vn и Vk и обозначают . Если все вершины и рёбра различны, то маршрут называют простой цепью. 1. – маршрут, но не цепь 2. – не простая цепь 3 – простая цепь 4. - цикл 5. – прострой цикл Цепь длины называется диаметральной цепью (рис.1.16). Рис.1.16 - Диаметральная цепь Минимальным из эксцентриситетов графа G называется его радиусом и обозначается r. Вершина Vi называется центральной, если . Множество всех центральных вершин графа называется его центром. Операции над графами: Граф h называется частью графа G, если множество вершин и множество рёбер ). Если , то часть графа называется частным графом(рис.1.17). Рис.1.17 - Частный граф Подграфом с множеством называется часть графа, которому принадлежат все рёбра с обоими концами и(рис.1.18; рис.1.19) Рис.1.18 – Исходный граф Рис.1.19 - Подграф Унарные операции: a) Удаление ребра количество рёбер. После удаления всех рёбер граф оказывается без рёбер. b) Удаление вершины c) Отождествление вершин. Алгоритм: 1.Определяется окружение отождествлённых вершин (создание списка рёбер, с которыми инцидентны вершины). 2.Удаление вершин. 3. Введение новой вершины. 4. Введение новых рёбер из списка вершин, которые инцидентны ближайшему окружению удалённых вершин и созданной вершине (рис.1.20). Рис.1.20 -Отождествление вершин Бинарные операции над графами: 1. Дополнением графа G1 является граф G2, у которого , множество рёбер не принадлежит графу G1. А множество рёбер не принадлежит графу G1 (рис.1.21; рис.1.22). . Рис.1.21 – Граф Рис.1.22 - Дополнение графа2 2. Объединение графа G1 и G2 (рис.1.23). Рис.1.23 -Объединение графа 3. Пересечение графа. Пересечение двух множеств и называется граф(рис. 1.24 ). Рис.1.24 -Пересечение графа 4. Суммой графов G1 и G2 называется граф G3 представляющий собой объединение графов G1 и G2 и полного двудольного графа K. Двудольный граф – это граф такой, что множество V разбито на два пересекающихся множества V1 и V2. Причём всякое ребро из W инцидентно вершине из W1 и W2. Множество V1 и V2 называются долями двудольного графа. Если двудольный граф содержит все рёбра соединяющие множество V1 и V2, то он называется полным двудольным графом (рис.1.25; рис.1.26; рис.1.27; рис.1.28). Рис.1.25 - Сумма графов Рис.1.26 - Сумма графов Рис.1.27 -Двудольный граф К . Рис.1.28 -Сумма графов . 5. Декартово произведение графов. Если даны два графа, то их декартово произведение строится так. В качестве множества вершин берётся декартово произведение множеств вершин, то есть вершинами нового графа будут все пары вида и будет равно (рис.1.29): Рис. 1.29 -Декартово произведение графов 6. Рассмотрим алгоритм определения эксцентриситета вершины связанного графа (рис.1.30). Рис.1.30 - Связный граф Матрица смежности(рис.1.31): 1 2 3 4 5 6 1 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 Рис.1.31 - Матрица смежности Возьмём 3-ю вершину и определим её эксцентриситет. Вектор запуска . Умножив вектор на матрицу смежности, получим вектор: первый шаг второй шаг 1.4. Связность Говорят, что две вершины в графе связаны, если существует соединяющая их простая цепь. Граф, в котором все вершины связанны, называется связным. Отношение связности вершины является эквивалентностью. Число компонент связности графа G обозначается Граф G является связным, тогда когда . Если , G- несвязный граф. Вершина графа называется точкой сочленения, если её удаление делает граф несвязным. Мостом называется ребро, удаление которого увеличивает число компонент связности. Вершиной связностью графа G, обозначается и обозначает наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Если , граф не связный. Если , граф имеет точку сочленения. Очевидно, что граф тем больше связан, чем больше существует разных цепей соединяющих одну вершину с другой. И тем менее связан, чем меньше нужно удалить промежуточных вершин, чтобы отделить одну вершину от другой. Рёберной связностью графа G обозначается , называется наименьшее число рёбер, удаление которых приводит к несвязному или тривиальному графу. – граф не связан. – хотя бы один мост. Не пересекающиеся цепи. Пусть связный граф. - две не смежные вершины. Две цепи называются вершинно-непересекающимися, если у них нет общих вершин кроме U и V. Множество вершин и (или) рёбер, разделяющих две вершины U и V называется разделяющим множеством рёбер или разрезом. Теорема Менгера. Пусть U и V не смежные вершины в графе G. Наименьшее число вершин в множестве разделенном U и V, равно наименьшему числу вершинно-непересекающихся простых цепей. Варианты теоремы Менгера. 1. Для любых двух не смежных вершин U и V графа G наибольшее число рёбер пересекающихся цепей равно наименьшему числу рёбер в разряде. 2. Чтобы граф G был k- связным необходимо и достаточно чтобы любые две не смежные вершины были соединены не менее чем k - вершинно-непересекающимися простыми цепями. Для нахождения характеристик связности часто применяют метод нахождения точек сочленения. Граф называется k – связным, если удаление любых k -1 вершин не приводит к расчленению графа. В частности граф имеет связность два и выше тогда, когда он не имеет точек сочленения Напишем простой алгоритм нахождения всех точек сочленения простого графа, основанный на методе поиска в глубину (рис. 1.32; рис. 1.33). Рис.1.32 -Алгоритм нахождения всех точек сочленения простого графа Рис.1.33 -Алгоритм нахождения всех точек сочленения простого графа При разложении графа в глубину сначала строится главное остовное дерево. Потом путём от последней к первой обходятся все вершины в поисках их потоков (не участвовавших в предыдущих обходах). После укладки всех вершин строятся все связи. При построении остовного дерева большое значение надо уделять максимальной длине остов. Далее анализ графов происходит снизу вверх, по каждой из веток. Возможно, 4-0 и 9-0 являются точками сочленения. Определяя, таким образом, точки сочленения надо дополнительно проверять путём их удаления из графа и применения алгоритма определения компонент связности. Алгоритм определения компонент связности методом перебора (рис.1.34; рис.1.35). Рис.1.34 - граф для определения компонентов связности Рис. 1.35 - Матрица инцидентности 1) Анализ первой строки: Находим 1 и складываем арифметически первую строку со строкой, в которой в той же позиции есть 1. 2) Алгоритм повторяется, пока в строках есть 1. Вывод: количество не нулевых строк равно количеству компонент связности. 1.5. Вершинная и рёберная независимость Множество вершин называется независимым, если никакие две из них, не смежны. Независимое множество вершин называется максимальным, если оно не является собственным подмножеством некоторого другого независимого множества. Наибольшее по мощности из максимальных независимых множеств называется наибольшим. Число вершин в наибольшем независимом множестве графа G называется числом независимости (внутренней устойчивостью) обозначается (рис.1.36). Рис.1.36 -Пример независимого множества Число независимости Множество вершин: или или Множество максимальное независимое множество, но не наибольшее. Произведение подмножеств попарно не смежных ребер графа называется паросочетанием (независимым множеством ребер). Паросочетание графа G называется максимальным, если оно не содержится в паросочетании с большим числом рёбер. Число рёбер в наибольшем паросочетании называется числом паросочетаний или рёберной независимости (рис.1.37). Рис.1.37 - Граф паросочетаний Несмежные ребра Рис.1.38 -Построение реберного графа Вершины в реберном графе смежные, если рёбра в исходном графе инцидентны одной вершине. Алгоритм определения максимального множества независимых вершин (рис.1.39): Рис.1.39 -максимального множества независимых вершин Строим вектор для степени вершин – удаляем вершины с максимальной степенью – 6: ; Определяем следующую вершину с максимальной степенью - 2 и удалим её: - максимальное множество независимых вершин. 1.6.Сети Петри Теория сетей Петри. Сети Петри – инструмент для исследования систем. В настоящее время сети Петри применяют при моделировании. Модель – это представление, как правило, в математических терминах того, что считается наиболее характерным в изучаемом объекте или системе. Манипулируя моделью системы можно получить новые знания о ней, избегая опасности дороговизны или неудобства анализа. Развитие сетей Петри: - формальная теория сетей Петри занимается развитием основных средств, методов и понятий, необходимых для применения сетей Петри; - прикладная теория сетей Петри связана с применением сетей Петри к моделированию систем. Моделирование в сетях Петри осуществляется на событийном уровне. Определяется, какие действия происходят в системе, какие состояния предшествовали этим действиям и какие состояния примет система после выполнения этих действий. Анализ результатов выполнения может сказать о том, в каких состояниях пребывала или не пребывала система, какие состояния не достижимы. Однако, такой анализ не дает числовых характеристик. Развитие теории сетей Петри привело к появлению цветных сетей Петри. Понятие цветности тесно связано с последовательностью переменных, типов данных, условий и других конструкций, более приближенных к языкам программирования. Сеть Петри могут эффективно применяться для описания параллельных систем, наряду с MPI. Сеть первого рода – Сеть Петри, написанная на языке предписаний. Сеть второго рода – Сеть представляется в виде иерархической композиции объектов. Аналитическое определение сетей Петри – набор, который является четверкой. – конечное множество позиций; T - множество переходов; I – входная функция инцидентности; O - выходная функция инцидентности. Другое определение сетей Петри. Сеть Петри есть двудольный ориентированный граф. Двудольный, это такой граф, множество вершин которого разбито на два подмножества: не существует дуги соединяющей две вершины из одного подмножества. По определению дуга определяет либо место с переходом, либо переход с местом (рис.1.40). Рис.1.40 -Сеть Петри Продукционное правило: Сеть Петри можно интерпретировать по-разному. Можно сказать, что место представляет собой условия (буфер пуст, файл закрыт), а переходы - события (посылки, получения, сообщения в буфер, запись в файл. Состояние сетей Петри в каждый момент определяется системой уравнений. Для того, чтобы стало возможным и удобным задавать условия типа, в буфере находится три записи, в модель сети Петри добавляются фишки. Фишки изображаются точками внутри места. Токен свидетельствует о том, что буфер имеет значение, а если место имеет три фишки, то это может интерпретироваться, как наличие трёх разных значений в буфере. Если место содержит фишку, то место маркировано и сеть называется маркированной. Начальное распределение фишек задаёт начальную маркировку m0-сети Петри. Маркировка сети определяет её текущее состояние. Фишка (Маркер, Токен) - это примитивное понятие сети Петри. Количество и положение фишек сети Петри может изменяться после срабатывания перехода, при этом маркировка сети Петри определяется как вектор: Сеть переходит из одного состояния в другое (рис. 1.41). Рис.1.41 - Переход сети Петри из одного состояния в другое Количество фишек в позиции не ограниченно. Маркированная сеть Петри, совокупность сети Петри и токенов. Последовательности срабатывания переходов могут привести к разметке, при которой ни один переход не может сработать. Другое направление исследования сетей – это исследование изменения фишек. Если ни в одной позиции сети при любой последовательности срабатывания сети количество фишек не превышает k, то сеть называется k– ограниченной. Пример: Выработка условного рефлекса у собаки на электрический звонок (рис.1.42) Рис.1.42 -Выработка условного рефлекса у собаки на электрический звонок U-буфер эксперимента (поглощение); E– накопление опыта эксперимента (привыкание); R – рефлекс выработан; P3 – звонок после накопления опыта эксперимента. Матричный способ описания сетей Петри. Сеть Петри может быть задана с помощью матриц инциденций (рис.1.43; рис.1.44; рис.1.45). Рис.1.43 - Сеть Петри Рис.1.44 - I- входная функция Рис.1.45 - I+выходная функция Результирующая матрица представлена на рис.1.46 (I=I+-I-). Рис.1.46 - Результирующая матрицаI При μ0=[1,2,1,0,1] - μj0 ≤ I-j,i (разрешён). В случае если разрешёнными являются несколько переходов, возникает конфликт. В теории сетей Петри не предусмотрено никаких рекомендаций по решению этого конфликта. Он решается случайным образом. Для вычисления следующей маркировки необходимо задать вектор пуска, разрешённого и выбранного перехода. Если принять, что этот переход t1, то вектор запуска V будет иметь вид: , при этом маркировка μ1 вычисляется следующем образом: Сеть Петри консервативна, если существует положительное число для каждой позиции, такое, что сумма токенов постоянно для любой маркировки из . Позиция, сумма фишек в которой не может превысить число I, называется безопасной. Сеть Петри повторима, если существует последовательность срабатывания G- переходов из такая, что каждый переход срабатывает бесконечное число раз. Сеть Петри не противоречива G из в. Такая, что переход последовательности G, запускается, по крайней мере, один раз. Очевидными являются задачи достижимости и покрываемости. Задача достижимости – можно ли из данной маркировки μ достигнуть маркировки. Задача покрываемости – для данной маркировки существует ли маркировка μ такая что 1.7. Понятие о внешней устойчивости и покрытии граф. Вычисление внешней устойчивости и покрытии граф Если ребро инцидентно вершине, то говорят, что они покрывают друг друга. Множество вершин, покрывающих все рёбра графа называются вершинным покрытием графа. Минимальная мощность вершинного покрытия называется числом вершинного покрытия графа Множество ребер, покрывающих все вершины графа называется рёберным покрытием графа. Минимальная мощность рёберного покрытия называется числом рёберного покрытия графа [16] Принято считать, что любые вершины графа покрывают сами себя, а 2 смежные вершины покрывают друг друга. Минимальная мощность множества вершин покрывающих все вершины графа называется вершинным числом внешней устойчивости . Будем считать, что каждое ребро графа покрывает само себя, а 2 смежных покрывают друг друга. Тогда, минимальная мощность множества рёбер, покрывающая все рёбра, называется рёберным числом внешней устойчивости (рис.1.47) Рис.1.47 -Рёберное число внешней устойчивости Вычисление числа внешней устойчивости на примере (рис.1.48 ) [47]: Рис.1.48 -Матрица смежности 1) Начисляем степень вершины. 2) Выбираем вершину с максимальной степенью. Отмечаем его токеном. 3) Определяем число маркированных вершин z=4. Если (число вершин), то множество внешней устойчивости определяется начальной маркировкой [48]. Если то число внешней устойчивости равно. Если , то выбирают вершину с наибольшей степенью и возвращаются к предыдущему пункту. 1.8. Циклы и разрезы в графах Цикл может входить только в 1 компонент связности, поэтому даже без ограничения общности граф считается связанным. Разрезом связанного графа называется множество рёбер, удаление которых делает граф несвязанным. Цикл (простой) рассматривается как множество рёбер. Простым разрезом называется минимальный разрез, т.е. такой разрез, собственное подмножество которого разрезом не является. Между циклом и разрезом существует определённая двойственность, поэтому разрезы иногда называются коциклами[38, 50]. Для исследования циклов в графах исследуют цикломатическую матрицу. Каждому циклу графа взаимно однозначно соответствует вектор строка матрицы. Каждый элемент этой матрицы определён следующим образом: Множество всех векторов матрицы С образуют векторное пространство, которое называют пространством циклов графа G. При этом выполняются следующие условия: Для любых 2 циклов R1 и R2 пересечение которых существует некоторый цикл (рис.1.49). Пример: Рис.1.49 - Цикл в графе Сложение по модулю 2 циклов R1 и R2 обладает свойствами: 1) Коммутативности 2) Ассоциативности Базисом векторного пространства называется связанная система линейно независимых векторов порождающих данное пространство. Множество векторов тогда и только тогда является элементами векторного пространства, когда всякий элемент состоит в виде линейной комбинации вектора этого множества [39]. Базис циклов графа G – это базис пространства цикла графа G, состоящий из простых циклов. Вектор R зависит от простых циклов. Сумма этих простых циклов по модулю 2 (рис.1.50). Рис.1.50- Циклы и разделы в графе. Таблица 1.1 a b c d e f m g h R1 1 1 1 1 R2 1 1 1 1 R3 1 1 1 1 R4 1 1 R5 1 1 1 1 1 1 R6 1 1 1 1 1 1 R7 1 1 1 1 1 1 В качестве базисной системы циклов необходимо взять цикл все остальные циклы являются линейной комбинацией базисных циклов по модулю 2 [49]. Анализ циклов в графах: Деревом называется связанный граф, не содержащий ни одного цикла. Не связанный, ацикличный граф называется лесом. Пример: свободные деревья с 5 вершинами (рис.1.51): Рис.1.51 -Анализ циклов в графах с 5 вершинами С 6 вершинами (рис.1.52, рис.1.53): Рис.1.52 -Анализ циклов в графах с 6 вершинами Рис.1.53 -Анализ циклов в графах с 6 вершинами Остовный подграф графа G это подграф, содержащий все вершины графа G. Остовом графа называется остовный подграф, являющийся деревом. Хордой остова D в связном графе G называется всякое ребро, не принадлежащее остову D. Любой граф, состоящий из хорды и остова, имеет точно 1 цикл. Цикломатическое число числу хорд любого остова в графе G (рис.1.54). Рис.1.54 - Граф, состоящий из 3 хорд и остова Если связанный граф G имеет n вершин и m ребер то Если граф G содержит K компонент связности то (рис.1.55). Рис.1.55 - Граф, содержащий компонент связности Остовным лесом называется граф, каждый компонент которого является остовным деревом. Метод Эйлера. Число базисных циклов графа постоянно и равно . Базисной системой циклов для данного остовного леса графа G называется множество всех циклов графа, каждый из которых имеет только одну хорду [40]. Базисная цикломатическая матрица относительно остова дерева (рис.1.56; рис.1.57) представлена в таблице 1.2. Рис.1.56 - Остов дерева H= Рис.1.57 - Цикломатическая матрица Таблица 1.2 При этом базисная система разрезов в графе получается следующим образом: 1)Удаляется ребро остова d. .Множество вершин при этом распадается на 2 непересекающихся подмножества. 2) Множество рёбер в графе G, каждое из которых соединяет вершину из V1 c вершиной из V2, является разрезом графа G. Множество всех разрезов для каждого ребра остова D является базисной системой для данного остова D. для ребра m, для ребра b, для ребра e, для ребра fдля ребра g, для ребра h. Полученная система разрезов может быть записана в виде матрицы разрезов K (таблица 1.3). Таблица 1.3 m b e f g h a c d m 1 1 1 b 1 1 e 1 1 f 1 1 g 1 1 1 h 1 1 1 ОСТОВ ХОРДЫ 1.9. Изоморфизм Рис.1.58 -Изоморфизм Эти три графа (рис.1.58), с геометрической точки зрения, совершенно различны, однако, что касается связи между вершинами, то эти графы отличаются только начертанием. Отношение инцидентности для всех этих графов одинаковы. Графы, для которых сохраняются отношения инцидентности, называются изоморфными. Матрица инцидентности определяет граф без петель с точностью до изоморфизма. Каждый из изоморфных графов называется геометрической реализацией. Графы, которые имеют одинаковые начертания и отличаются только нумерацией вершин и рёбер, не являются тождественными, но являются изоморфными. Если существенные свойства графов не связаны со способом его изображения на плоскости или с нумерацией вершин и рёбер, то изоморфные графы практически между собой не отличаются.