Случай неориентированных графов, мультиграфов

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

Неориентированное ребро (i,j) - это фактически два ориентированных ребра (i,j) и (j,i) с одинаковыми пропускными способностями и стоимостями. Поскольку вышеописанный алгоритм min-cost-flow требует для каждого неориентированного ребра создать обратное ему ребро, то в итоге получается, что неориентированное ребро расщепляется на 4 ориентированных ребра, и мы фактически получаем случай мультиграфа.

22 элементы сетевого планирования

7.2. Основные элементы сетевого графика и правила его построения

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

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

Событие — это факт окончания одной или нескольких работ, необходимый и достаточный для начала последующих работ. Таким образом события определяют технологическую и организационную последовательность работ. Событие обозначают геометрическими фигурами (кружками, квадратами и т. п.) с циф­ровым кодом внутри. Между двумя событиями может выполняться толь­ко одна работа, но к каж­дому событию может при­мыкать одна или несколь­ко оканчивающихся работ и одна или несколько на­чинающихся работ (рис. 7.1, а). Смежные два со­бытия ограничивают дан­ную работу и по отноше­нию к ней могут быть начальными и конечными (рис. 7.1, б). Начальное событие (/) определяет начало данной работы и является конечным для предшествующих работ. Конечное событие (/) оп­ределяет окончание дан­ной работы и является начальным для последую­щих работ \ Исходное со­бытие (А) определяет начало выполнения всех работ по строитель­ству объекта. Оно не имеет предшествующих работ, т. е. в него не входит ни одна работа. Завершающее событие (k)—достижение конечной цели, оно не имеет последующих работ в рамках рассмат­риваемого сетевого графика, т. е. из него не следует ни одна ра­бота.

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

Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров: , где:

· Q — конечное множество состояний автомата;

· q0 — начальное (стартовое) состояние автомата ();

· F — множество заключительных (или допускающих) состояний, таких что ;

· Σ — допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;

· δ — заданное отображение множества во множество подмножеств Q:

 

(иногда δ называют функцией переходов автомата).

Автомат начинает работу в состоянии q0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».

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

Другие способы описания

1. Диаграмма состояний (или иногда граф переходов) — графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф, вершины которого — состояния КА, ребра — переходы из одного состояния в другое, а нагрузка — символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью графа) должны быть надписаны все они.

2. Таблица переходов — табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.

[править]Детерминированность

Конечные автоматы подразделяются на детерминированные и недетерминированные.

 

 

Детерминированный конечный автомат

· Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.

 

· Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:

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

Если рассмотреть случай, когда автомат задан следующим образом: , где:

· S — множество стартовых состояний автомата, такое что ;

Тогда появляется третий признак недетерминизма - наличие нескольких начальных (стартовых) состояний у автомата .

Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.

В силу последних двух замечаний, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.

[править]Автоматы и регулярные языки

Для автомата можно определить язык (множество слов) в алфавите Σ, который он представляет — так называются слова, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.

Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков. Кроме того, этот класс совпадает с классом языков, задаваемых регулярными грамматиками.

24

Понятие конечного детерминированного автомата

К.Д.А. называется система , где - алфавит состояний, – входной алфавит, – выходной алфавит. Множества S, X, Y – конечные.

– функция переходов,

– функция выходов.

Если в автомате выделено одно состояние , называемое начальным (обычно ), то автомат называется инициальным.

4.2 Способы задания автоматов.

1.Таблица переходов–выходов.

S\X		…		…
M
M

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

Этой дуге приписывается пометка :

Начальное состояние в инициальном автомате помечается символом . Описанный таким образом орграф с пометками называется диаграммой Мура.

3.С помощью канонических уравнений:

 

в момент t=1 автомат находится в начальном состоянии . В каждый момент t=1,2,3,… дискретного времени автомат, находясь в некотором состоянии s(t) из множества S, под действием входного сигнала выдает выходной сигнал из множества Y, согласно функции выходов l , а затем меняет свое состояние на s(t+1) согласно функции переходов d.

Для определения множества состояний автомата необходимо уяснить содержательный смысл и назначение понятия состояния.

После преобразования входного сигнала в выходной его значение к следующему такту времени теряется. Иначе говоря, в любой тактовый момент t в устройстве нет информации о сигналах в предыдущие моменты, то есть о значениях ,, ,… . Поэтому, если при вычислении значения функции переходов и выходов по формуле необходима информация об этих тактовых моментах, то ее нужно каким-либо образом "запомнить". В этом и состоит содержательное назначение состояний. Состояния – это вспомогательные объекты, которые подбираются таким образом, чтобы в совокупности с входным значением однозначно определить выходное значение . Обычно состояния кодируют ту информацию, которая поступила до момента t.

Пример. Построить таблицу переходов–выходов К.Д.А, реализующего функцию:

 

 

Чтобы на любом, отличном от первого, такте иметь информацию о , введем два следующих состояния:

={"на первом такте поступил 0"};

={"на первом такте поступила 1"}.

И –начальное состояние.

Построим таблицу переходов–выходов:

 

Для нарисуем диаграмму Мура:

И дополним таблицу переходов–выходов: