Автоматные сети и реализация автоматных функций

 

 

 

 

 

 

 

 

Реферат

 

на тему:

 

«Автоматные сети и реализация автоматных функций»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2010г.

СОДЕРЖАНИЕ

Введение

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

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

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

Цель работы состоит в изучении автоматных сетей и  реализации автоматных функций

Для достижения поставленной цели следует решить ряд поставленных задач:

• рассмотреть теорию автоматов;
• изучить автоматную модель;
• ознакомиться с сетями Петри;
• наглядно рассмотреть реализацию автоматных функций.

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

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

ГЛАВА 1.ТЕОРИЯ АВТОМАТОВ

1.1.Произвольный автомат.

 Теория автоматов – это раздел дискретной математики, изучающей математические модели дискретных преобразователей информации.

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

Зададим следующие множества:

A={a1,a2,...,am} - множество входных знаков (входной алфавит),

B={b1,b2,...,bs} - множество выходных знаков (выходной алфавит),

Q={q1,q2,...,qn} - множество состояний автомата.

Особенность этих множеств состоит в том, что они содержат конечное число элементов.

Тогда автомат можно  представить в следующем виде:

Начальная установка

Особенностью автоматов  является то, что они функционируют  во времени.

Работу любого автомата можно проиллюстрировать с помощью временных диаграмм (приложение 1).

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

Существует три подхода  к изучению автоматов:

1. Макроподход. При макроподходе изучают внешнее поведение автомата, то есть то, как автомат перерабатывает входные данные  и в каких состояниях находиться, абстрагируясь от внутренней структуры автомата. Такие автоматы называются – Абстрактными автоматами.
2. Микроподход. При микроподходе учитывается структура автомата, его составные части, их функционирование и связь между собой. Такие автоматы называются – структурными автоматами.
3. Практический или практический аспект. При практическом подходе учитывается не только внешнее поведение элементарных (абстрактных) автоматов, но и особенности их реализации в виде материальных объектов (дискретных устройств).

1.2. Автоматная  модель процесса

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

Заметим, что с введением  времени модель приобретает еще  одно качество реальных процессов – инерционность. В реальных процессах нет мгновенных действий. Задержке реакции реального объекта на входное воздействие в автоматной модели соответствует один или несколько дискретных тактов.

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

Итак, если немного заглянуть  вперед, то, оперируя даже просто дискретными тактами, мы можем легко согласовать обмен информацией между параллельными автоматными процессами, организовав в определенное время (дискретное) «встречу» между ними.

Автоматы хороши тем, что для них очень просто организовать единое время. Для этого достаточно заставить автоматную сеть работать в общем дискретном времени. В этом случае компонентные автоматы сети могут «встречаться» друг с другом, не рискуя потерять информацию или сорвать моменты обмена ею, а назначив лишь время, которое будет определяться числом тактов дискретного времени. Хорошее обоснование необходимости введения единого времени для параллельно работающих автоматов можно найти у В.М. Глушкова и, пожалуй, только у него.

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

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

1.3. Практическое  приложение автоматных моделей

В программировании применение автоматов не является экзотикой. Наиболее известная область приложения автоматных моделей – проектирование компиляторов. В области проектирования систем весьма популярна автоматная модель языка UML

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

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

ГЛАВА 2.СЕТИ ПЕТРИ

2.1. Знакомство  с сетями Петри

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

Графически сеть Петри  представляется в виде двудольного  ориентированного графа с двумя типами вершин – позициями и переходами (приложение 2). Позиция обозначается кругом, переход – чертой или прямоугольником. Как правило, чертой обозначают простой, мгновенный переход, прямоугольником – длительный.

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

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

2.2. Функционирование  сети Петри

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

Из всего множества  разрешенных переходов сработать  может любой.

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

После каждого срабатывания перехода множество разрешенных  переходов в общем случае меняется, поскольку меняется текущая разметка сети. Считается, что сеть Петри «жива», если в ней есть разрешенные переходы. Если после срабатывания очередного перехода разрешенных переходов в сети не остается, она завершает выполнение.

В случае, когда позиция  является входной для двух или более разрешенных переходов, срабатывание любого из них и соответствующее уменьшение количества фишек в ней может запретить другие переходы. Такой ситуацией моделируются конфликты, когда для выполнения нескольких операций требуется использование общего ресурса. Пример такой ситуации виден в приложении 2. В самом начале работы сети разрешенным является один переход – t1. После его первого срабатывания разрешенными являются все три перехода сети. Если же теперь сработает, к примеру, переход t2, он запретит переход t3, и наоборот, срабатывание t3 запретит переход t2, поскольку переходы t2 и t3 имеют общую входную позицию p3.

Срабатывание простого перехода считается мгновенным.

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

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

2.3. Пример  реализации механизма сетей Петри

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

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

ГЛАВА 3.РЕАЛИЗАЦИЯ АВТОМАТНЫХ ФУНКЦИЙ

3.1. Схемы из  функциональных элементов и элементов задержки.

Будем реализовывать  автоматные функции из множества PE, где E= {0,1}, при помощи функциональных элементов дизъюнкции, конъюнкции и отрицания и элемента единичной задержки (рис 1) .

Рис. 1.

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

В частности канонические уравнения для автоматов, соответствующих элементам дизъюнкции, конъюнкции и отрицания, имеют следующий вид:

y(t)=x1(t)∨x2(t);

q(t+1)=q(t);

q(1)=0,

y(t)=x1(t)&x2(t);

q(t+1)=q(t);

q(1)=0,

 

y(t)=x(t);

q(t+1)=q(t);

q(1)=0.

Будем обозначать автоматные функции из PE, которые вычисляются этими автоматами через f∨(x1,x2), f&(x1,x2) и f−(x) соответственно. Канонические уравнения элемента единичной задержки имеют вид:

y(t)=q(t);

q(t+1)=x(t);

q(1)=0

соответствующая автоматная функция обозначается через f(x).

Пусть f(x1, . . . ,xn) - произвольная автоматная функция из PE, а Vq0 = (A,B,Q,F,G) - инициальный автомат, вычисляющий функцию f , где A = En = {0,1}n, B = {0,1}, Q = {q1, . . . ,qλ},q0 ∈Q, F : {0,1} nЧQ→{0,1}, G : {0,1}n ЧQ→Q. Канонические уравнения этого автомата имеют вид:

y(t)=F(x1(t), . . . ,xn(t),q(t));

q(t+1)=G(x1(t), . . . ,xn(t),q(t));

q(1)=q0.

Положим j =] log2λ[. Занумеруем состояния q1, . . . ,qλ наборами из 0 и 1 длины j, причем начальному состоянию q0 сопоставим набор (0, . . . ,0). Рассмотрим теперь новые функции, определенные на наборах из нулей и единиц:

y(t)=F1(x1(t), . . . ,xn(t),q1(t), . . . ,ql(t));

(q1(t+1), . . . ,ql(t+1))=G˜1(x1(t), . . . ,xn(t),q1(t), . . . ,ql(t));

(q1(1), . . . ,ql(1))=(0, . . . ,0),

где функция F1 и компоненты G¹₁, . . . ,G¹j вектор функции G˜¹ =

(G¹₁, . . . ,G¹j ) определены на некотором подмножестве множества E^n+j всех наборов из нулей и единиц длины ^n+j и принимают значения из {0,1}, т. е. являются частичными булевыми функциями. В покомпонентной записи эти уравнения имеют следующий вид:

y(t)=F(x1(t), . . . ,xn(t),q1(t), . . . ,qj(t));

q2(t+1)=C¹₁ (x1(t),. . . . ,xn(t),q1(t),. . . . qj(t));

ql(t+1))=G¹lj (x1(t), . . . ,xn(t),q1(t), . . . ,qj(t));

q1.(.1.)=0;

qj(1)=0.

Доопределим функции F1,G¹₁, . . . ,G¹j до всюду определенных булевых функций F2,G2₁, . . . ,G2_j соответственно. Положим G˜2 =(G2₁, . . . ,G2j ).

Таким образом, мы построили  инициальный автомат Vq˜20 =({0,1}n,{0,1},{0,1}j,F2,G˜2) с n входами, входным алфавитом {0,1}n, выходным алфавитом {0,1}, алфавитом состояний {0,1}j ,функцией выходов F2 : {0,1}nЧ{0,1}l →{0,1}, вектор-функцией G˜2 : {0,1}nЧ{0,1}l → {0,1}j и начальным состоянием переходов q˜0 =(0, . . . ,0). Легко видеть, что этот автомат вычисляет функцию f(x1, . . . ,xn).⁶

Построим схему S из функциональных элементов в базисе {∨,&, } с n + l входами, которым приписаны символы x1, . . . ,xn,q1, . . . ,qj , и 1 + j выходами y,z1, . . . ,zj ; при этом на выходе y реализуется функция F2(x1, . . . ,xn,q1, . . . ,qj), а на выходах z1, . . . ,zj - функции G²₁(x1, . . . ,xn,q1, . . . ,qj), . . . ,G²j (x1, . . . ,xn,q1, . . . ,qj) соответственно (рис. 2) .

Рис.2.

Преобразуем схему S следующим образом. Возьмем j элементов единичной задержки. Присоединим вход i-го элемента задержки к выходу zi , а выход - ко входу qi схемы S, i =1, . . . , l . Кроме того символы x1, . . . ,xn заменим на x1(t), . . . ,xn(t) соответственно а символы функциональных элементов ∨,&, - на символы f&, f∨ и f− соответственно. В результате получим "схему" S1 из автоматных элементов в базисе {f&,f∨,f−,f} (рис. 3, приложение 3) .

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

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

Индукцией по t нетрудно показать, что если в момент времени t подавать на входы схемыS1 значения x1(t), . . . ,xn(t) из {0,1}, то на ее выходе будет выдаваться значение y(t) из {0,1}, которое вычисляется в соответствии с каноническими уравнениями автомата Vq˜20. Тем самым схема S1 реализует автоматную функцию f(x1, . . . ,xn).

3.2.Использование  автоматной функции качестве  криптографического преобразования

Доступной информацией является класс криптоалгоритмов (конечно-автоматные функции); описание автоматной функции является секретным.

Конечный автомат –  это имеющее вход и выход устройство, которое в каждый момент времени находится в одном из своих состояний. Конечный автомат осуществляет преобразование информации в дискретные моменты времени 0, 1, 2, …, t, … На вход автомата поступает последовательность символов входного алфавита X = {x₁, x₂, …, x_n}; эту последовательность называют входным словом.⁷

Функционирование конечного  автомата осуществляется в соответствии с системой из ns команд, где 

s – мощность алфавита  состояний Q = {q₁, q₂, …, q_s}. В каждый момент времени значением выхода автомата является элемент выходного алфавита Y = {y₁, y₂, …, y_m}. Каждая команда имеет вид

x_iq_j → y_kq_r                     (1),

где x_i – входная буква, q_j – текущее состояние, y_k – выходная буква и q_r – состояние в следующий за текущим момент времени (следующее состояние).

Функционирование конечного  автомата задают также кортежем

<X, X, Q, V, P>,          (2),

где  V: X Ч Q → Y (функция  выхода),

P: X Ч Q →  (функция  переходов).

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

Таблица 1

время	0	1	2	3	. …….	n	n + 1
входная буква	x(0))	x(1)	x(2)		……..	x(n)
состояние	q(0)	q(1)	q(2)	q(3)	………	q(n)	q(n + 1)
выходная буква	y(0)	y(1)	y(2)		……..	y(n)

 

Здесь и далее через x^(j) (y^(j)) обозначаем j-ю букву входного (выходного) слова, а через q^(j) – состояние автомата в момент времени j (при заданном входном слове).

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

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

Как известно, применяемые  при шифровании и расшифровывании  преобразования должны быть взаимно однозначными.⁸

Конечный автомат M назовем  обратимым (ОК-автоматом), если существует конечный автомат M₁, такой, что по описанию автомата M, его начальному состоянию и произвольному выходному слову автомата M автомат M₁ однозначно определяет входное слово. В этом случае автомат M₁ будем обозначать через M^–1. Таким образом, в качестве криптографических преобразований можно использовать только автоматные функции, соответствующие ОК-автоматам.

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

Пусть V_j(x), 1 ≤ j ≤ s, – функция V(x, _qj). Нетрудно проверить, что необходимым условием того, что автомат M – это ОК-автомат, является инъективность функций V_j(x) для любого j.

Функция f(x) инъективна, если из неравенства x_i ≠ x_j следует неравенство f(x_i) ≠ f(x_j). В нашем случае (совпадение входного и выходного алфавитов) утверждение об инъективности функции V_j(x) эквивалентно утверждению о том, что она является перестановкой.

Справедливо следующее  утверждение.

Теорема. Автомат M=<X, Y, Q, V, P> является обратимым тогда  и только тогда, когда для любого j функция V_j(x) инъективна.

Известно, что число (n, s)-автоматов не превосходит nns. Нетрудно проверить, что число (n, s)-автоматов, являющихся ОК-автоматами, имеет оценку (n!)s. Отметим, что имеет место следующая (асимптотическая) формул Стирлинга:

                    (3),

 

Таким образом, доля ОК-автоматов  стремится к 0 при увеличении значений параметров автомата n и s. Однако ОК-автоматы образуют достаточно мощный класс.

При использовании ОК-автоматов  в криптографии ключи шифрования определяют описания (таблицы) функций V(x, q) и P(x, q).

Получение описаний функций V–1 (x, q) и P–1 (x, q) обратного автомата по описаниям функций V(x, q) и P(x, q) является эффективной процедурой. Следовательно, общеавтоматное шифрование является симметричным.

Задача криптоанализа  общеавтоматного шифрования – восстановление описания конечного

автомата (нахождение функций V(x, q) и P(x, q)) по наблюдению входных и выходных слов.

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

ЗАКЛЮЧЕНИЕ

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

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

К нему же ныне просто огромные претензии.

Нельзя не отметить вновь  возникший интерес к автоматным моделям. Кроме UML, SWITCH-технологии и КА-технологии можно привести еще ряд примеров использования автоматных моделей в проектировании программ. Кроме этого есть целые разделы в программировании, где уже давно и постоянно ведется разработка программ с использованием автоматов.

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

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