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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ г ~ 0 д

--• ■ ; г,. -1 '/'ТП

На правах рукописи

Пономарева Александра Юрьевна

ПРОБЛЕМЫ ОПТИМИЗАЦИИ ОБОБЩЕННЫХ КОНЕЧНО-АВТОМАТНЫХ МОДЕЛЕЙ С ПЕРИОДИЧЕСКИ МЕНЯЮЩЕЙСЯ СТРУКТУРОЙ

Специальность: 05.13.18 - Теоретические основы математического моделирования, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 1999 г.

Работа выполнена на кафедре статистического моделирования мате-матико-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель: доктор физико-математических наук, профессор

ЧИРКОВ Михаил Константинович

Официальные оппоненты: доктор технических наук, профессор

ФРАДКОВ Александр Львович, доктор физико-математических наук, доцент

МЕЛАС Вячеслав Борисович

Ведущая организация:

Санкт-Петербургский государственный электротехнический университет (ЛЭТИ)

Защита состоится " ^ " ЬШРкЛ. 2000 г. в час. ¿^¿Яшн. на заседании диссертационного совета Д 063.57.52 по защите диссертаций на соискание ученой степени доктора наук в Санкт-Петербургском государственном университете по адресу: 198904, г. Санкт-Петербург, Старый Петергоф, Библиотечная пл., дом 2, матсматико-механичсский факультет.

С диссертацией можно ознакомиться в Научной библиотеке им. М.Горького Санкт-Петербургского государственного университета по адресу: 199034, г. Санкт-Петербург, Университетская набережная, дом 7/9.

Автореферат разослан СЪьША 2000 г.

Ученый секретарь диссертационного Совета Д 063.57.52, доктор физико-математических наук, профессор

И.К.Даугавет

Ш.о

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Исследование проблем теории математических моделей конечно-автоматного типа продолжается в мировой науке уже несколько десятилетий, что нашло свое отражение в целом ряде монографий (Айзерман М.А. и др., Баранов С.И., Бардзинь Я.М. и Трахтенброт Б.А., Брауэр В., Бухараев Р.Г., Варшавский В.И., Глуш-ков В.М., Кудрявцев В.Б. и др., Плоткин Б.И. и др., Поспелов Д.А., Цетлин M.JL, Чирков М.К., Шестаков A.A., Яблонский C.B., Eilenberg S., Gécseg F., Gill A., Ginsburg A., Kandell А. и Lee S.C., Paz A., Salomaa A., Starke P.H. и другие) и обусловлено как чисто теоретическим интересом к решению новых задач дискретной математики, так и тем, что различные математические модели конечно-автоматного типа достаточно широко и успешно используются для описания и изучения на абстрактном уровне структуры и поведения дискретных систем, устройств и процессов, допускающих соответствующее адекватное конечно-автоматное представление. При этом к настоящему времени наиболее полная абстрактная теория и достаточно эффективные методы решения классических проблем абстрактного анализа, синтеза и оптимизации разработаны для широкого спектра стационарных конечно-автоматных моделей, начиная с детерминированных автоматов и кончал обобщенными автоматами, задаваемыми над различными алгебраическими системами. В то же время, аналогичная абстрактная теория нестационарных конечно-автоматных моделей, то есть таких автоматов, абстрактная структура которых меняется во времени, еще находится в стадии разработки, хотя очевидно, что дальнейшее существенное расширение класса дискретных систем, устройств и процессов, описываемых и изучаемых с помощью математических моделей конечно-автоматного типа, может быть достигнуто только в том случае, если отказаться уже на абстрактном уровне от условия стационарности модели и перейти к исследованию математической теории нестационарных конечно-автоматных моделей. При этом, соответственно, может расширяться и класс проблем, решаемых с помощью таких моделей, за счет тех задач абстрактного анализа, синтеза и оптимизации, которые непосредственно связаны с динамикой изменения их абстрактной структуры.

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

и построением приведенных и минимальных форм модели. В частности, при решении проблем оптимизации для наиболее общего случая стационарных обобщенных конечных автоматов, задаваемых над полями, Чирковым М.К. и Шестаковым A.A. были разработаны эффективные матричные методы построения их приведенных и минимальных форм. Естественно, что решение подобных задач оптимизации абстрактной структуры остается одной из основных и важнейших проблем и в теории нестационарных конечно-автоматных моделей. Таким образом представляется весьма актуальным исследование новых, по возможности наиболее обобщенных, нестационарных моделей конечно-автоматного типа, теоретическое обоснование и разработка методики их оптимизации и построения различных минимальных форм.

Данная диссертация выполнена в рамках проведения научно-исследовательских работ по теме плана фундаментальных госбюджетных исследований СПбГУ (N гос. per. 01960005947) и при поддержке гранта РФФИ 98-01-01008.

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

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

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

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

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

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

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

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

5. Введено понятие специальных минимальных форм для автоматов исследуемого типа и предложен метод их построения.

6. Разработана программа на языке С++, реализующая предложенные методы и алгоритмы оптимизации автоматов рассматриваемого типа.

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

Аппробация работы. Основные результаты диссертации были опубликованы в работах [1-7], представлены на международной научной конференции "The Third St.Petersburg Workshop on Simulation, June 28 - JuJу 3, 1998", докладывались и обсуждались на семинарах лаборатории математических проблем информатики НИИММ СПбГУ и кафедры статистического моделирования математико-механического

факультета СПбГУ.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и приложения. Основной текст диссертации занимает 120 страниц. Библиография составляет 58 наименований. Приложение содержит 53 страницы.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Пусть задано любое поле Т. Нестационарным обобщенным конечным автоматом с периодически меняющейся структурой AgV) заданным над полем !F, будем называть систему:

= (XWIAW,yM>f,{RW(í,0},qW,í1„r)> (1)

где tp - длина предпериода; Т - период повторения параметров структуры автомата; г = r(í) - структурный номер такта, который определяется через текущий номер такта t — 0,1,2,... следующим образом:

т = т1Л = i есЛИ 1 - tp ■ (9)

{ ) \(t-tp- l)(mod Т) + tp + 1, если t > tp ' K '

- алфавиты входных и выходных символов, допустимых в г-ом такте, = nr, = kr, т = 1 ,íp +Т; АМ - алфавит состо-

яний автомата в т-ом такте, = mT, r — Q,tp + T, А^"^ — г - матрица, размера (£о X то), строки которой задают базис в пространстве £(г) допустимых начальных распределений весов состояний в момент t — 0; (■?,/)}, xs G y¡ € - совокупность nTkT

прямоугольных (mr_j X тг)-матриц весов переходов с элементами из Т в г-ом такте, т = 1, tp + Т; q^ - финальный вектор-столбец весов состояний с тпт элементами из Т в г-ом такте, г = 0,tp +Т, причем Заметим, что в частном случае при tp = 0 и Т = 1 автомат Agv становится стационарным обобщенным конечным автоматом Agen (с частично определенными начальными условиями).

Пара слов (w,v), w = xSíxS2...xSi, v = yi1y¡2---yii, одной длины допустима для автомата Asv, если для всех t = l,d выполняется: xs, G € yit 6 . Пусть Ддоп есть множество всех пар слов (и:, v)

б

любой длины (1 = 0,1,2,..., допустимых для автомата Л(считается что "пустые" слова е, не содержащие ни одной буквы, всегда допустимы, то есть (е, е) £ ^доп)- Тогда множество Ф — {Фл|г £ £(?)} обобщенных отображений Ф^д : доп,Т, индуцируемых автоматом Лдп при различных г 6 £(г), определяется выражением: Фд(и/, у) =

Автоматы

Л„ = (хМ.АМ.уМ.г,,,^^,')},^,^^) , (3)

также как и автоматы

Л« = <*, ^{К-Аг)(*, 0}> «&1\ Т), (5)

В3„ - , (6)

называются эквивалентными ~ если Ф_д = <1>в, то есть, если для каждого Гд £ £(?л) найдется такой г/у € £(г д) (и, обратно, для каждого гв € £(?в) найдется такой Гд € £(?л)), что автоматы и В311 индуцируют одно и то же обобщенное отображение.

Рассмотрим структурный такт г € 0, ¡р + Т в автомате (1) и всевозможные моменты времени £ = такие, что т(с^) = г. Обозначим через векторное пространство, порожденное вектором-столбцом и всеми векторами-столбцами

ЬМ(«>2,г*)= П ВР^НаМ™ (7)

при всевозможных (и^шг,^!^) £ -^доп таких, что |г«1| = ¡к^ — ¡Ш1Ш2| = 1 — Л, Л — ¿1 +^2; = 1,2,... . Любую матрицу Н^ размера (тТ х т]г), где цт = , столбцы которой обра-

зуют базис в пространстве назовем правосторонней ба-

зисной матрицей автомата Аду в г-ом такте. Совокупность матриц НМ г = 0, ¿р Ч- Г, где НМ = Нназовем семейством правосторонних базисных матриц автомата Лд1!.

Аналогично, обозначим через С(гА$) векторное пространство, порожденное при заданном г £ 4-Т всеми векторами-строками

ЪР^у^^гПК^М), г £ £(?), (и/1,«О е £доп, (8)

4=1

а при т = 0 строками матрицы г и, в случае, если ¿р = 0, всеми векторами вида (8) для т = Т. Любую матрицу Н[г' размера (£г хтпт), где (г = сИт С{гЛ^т,)), строки которой образуют базис в пространстве назовем левосторонней базисной матрицей автомата Лв„ в г-ом такте. Совокупность матриц т = О, + Т, где Н[1р) = назовем семейством левосторонних базисных матриц автомата

Согласно определениям базисных матриц автомата Лди, они имеют бесконечное множество форм представления

ЙМ = н<г)а, н'т! = /ЗН<Т>; (9)

где а,/3 - любые невырожденные квадратные матрицы размера (??тхт;г) и (Сг х £г) с элементами из Т. Выделяя в матрице любые г/Т линейно независимых строк Ь^, и — 1,т]г, а в матрице любые £т линейно независимых столбцов Ь-'", а = образуя матрицы

а"1 = /3~1 = и, находя обратные им матрицы

а, /3, можно с помощью преобразования (9) найти нормализованные формы представления базисных матриц Н[т\ такие, что в ма-

трице Н^ строки с номерами V = 1, цт, имеют вид Ь^ = Ь(г/) = = (0,...0,1,0,...0), где элемент "1" стоит в м-ой позиции, а в матрице нм столбцы с номерами ]а. а — 1,£г, имеют вид

Любые матрицы Н^' и Н^' такие, что Н^'Н^ = 1(т?г), Н^НМ1 = где I(г/т), 1(£г) ~ единичные матрицы размера

(т)г х г/т), (£т х £г), будем называть матрицами, псевдообратными матрицам НМ. Для находящихся в нормализованной форме базисных матриц НМ, Н<г> матрицы

определяются тривиальным способом: Н^ есть (г]Т х шг)-матрица, у которой столбцы с номерами г ф г„, V = 1, г/т, нулевые, а столбцы с номерами V = 1, г/т, имеют вид Ь7Я(г/), и = I,?/,, и, соответственно, Н<.г' есть (тт х £Г)-матрица, у которой строки с номерами ] ф з^, а = 1,£г, нулевые, а строки с номерами о — \,£Т) имеют вид Ь(о-), а = 1,£г. Обозначим

через векторные пространства над полем . со-

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

Лемма 1.1. Пусть Л3„ есть автомат (1), Н^"' - базисная матрица любого пространства С^ Э и Н^' - псевдообратная к ней

матрица, тогда для всех q £ ¿(Л^)(1кТ)) вылолняется Н^Н^'я = я . Лемма 1.2. Пусть Лд1! есть автомат (1), - базисная матрица

любого пространства Э С{тА$) и Н£т'7 - псевдообратная к ней матрица, тогда для всех г £ С(гЛ$) выполняется гНИ'ЙИ - г .

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

Сначала строятся матрицы Н^, г — + 1, ¿р + Т, для периодически повторяющейся части автомата Адк, следующим образом:

1) Нулевое приближение - все Н^, т =Ьр + 1,1р+Т, есть "пустые" матрицы, не содержащие ни одного столбца. Первое приближение -каждая матрица Н^ есть матрица из одного столбца НМ = (ч{т]).

2) Если построены (и — 1)-е и ¡/-е приближения матриц Н'7"', т = = ¿р + 1, Ц -+- Т, и в и-ом приближении матрицы Н^, по сравнению с ее (у — 1)-м приближением, добавились новые базисные векторы-столбцы Ь^,...,^-^, то + 1)-е приближение матрицы Н^-1' (здесь при т = — + 1 Н-'^ — ) получается добавлением к ее г^-му приближению таких столбцов, чтобы столбцы + 1)-го приближения матрицы образовывали базис в пространстве, порожденном столбцами ее г/-го приближения и всевозможными векторами-столбцами вида

= у = ТЛ, X, € У1 € у(г). Выполнение

этого правила последовательно для всех г = + 1, £р + Т приводит к построению (V + 1)-го приближения семейства правосторонних базисных матриц периодически повторяющейся части автомата.

3) Рекуррентная процедура, описанная в п.2, последовательно повторяется (при начальных условиях, заданных в п.1) до тех пор, пока при очередном выполнении п.2 полученное для какой-либо матрицы

г £ + 1, + Т, (р + 1)-е приближение совпадет с ее р-м приближением. На этом построение семейства правосторонних базисных матриц периодически повторяющейся части автомата Ад„ заканчивается.

Далее строятся матрицы Н^, г — 0,£р, для начальной непериодической части автомата Ад», для чего выполняются следующие действия:

4) Н^ есть найденная на предыдущем этапе матрица Если найдена матрица т € 1,ЬР, то матрица находится как базис пространства, порожденного вектором и всевозможными векторами-столбцами (в, I) 3 = 1,7/т, х8 6

У1 е

ум , где - столбцы матрицы Щт\ После нахождения матриц Нг> для всех т £ 0, Ьр построение семейства правосторонних базисных матриц автомата Аду заканчивается.

Аналогичная процедура предложена и для построения семейства левосторонних базисных матриц автомата Л,,,, но в ней сначала строятся

матрицы Hjj) для начальной непериодической части автомата, а далее - для периодически повторяющейся части автомата.

Автомат Agv левосторонне (тгравосторонне) приведен (находится в левосторонне (тгравосторонне) приведенной форме), если семейство его левосторонних (правосторонних) базисных матриц в нормализованной форме имеет вид = I(mr), Н^ = I(тТ), т = 0,íp + Т. Любой левосторонне (правосторонне) приведенный автомат Bgv (4), эквивалентный автомату Agv (3), условимся называть левосторонне (правосторонне) приведенной формой этого автомата Agv.

Автомат (3) находится в минимальной форме (при заданных tp и Т), если не существует эквивалентного ему автомата (4) с теми же tv и Г, такого, что = |В<Т>| < = т = 0,tp+T- 1, и

т[П> < Er=QT_1 • Минимальной формой автомата Agv (3) назовем любой эквивалентный ему автомат Bgv (4) с теми же tp и Т, находящийся в минимальной форме.

Будем говорить, что автомат Agv (5) находится в специальной минимальной форме, если он находится в минимальной форме и не существует находящегося в минимальной форме эквивалентного ему автомата Bgv (6), такого, что 1 т^тт+\ < т!г=о '1 г'гтА1 w'+i . Специальной минимальной формой автомата (5) назовем любой эквивалентный ему автомат (6), находящийся в специальной минимальной форме.

В диссертации решены следующие задачи оптимизации конечно-автоматных моделей:

1. Задан автомат Agv (3), требуется построить автомат Bgv (4), который: а) является правосторонне приведенной формой автомата Agv] б) является левосторонне приведенной формой автомата Agv\ в) является минимальной формой автомата Agv-

2. Задан нестационарный автомат Agv (5). Требуется, если возможно, построить эквивалентный ему стационарный обобщенный конечный автомат, находящийся в минимальной форме.

3. Задан стационарный обобщенный автомат Agen — (A', A, Y, гу!, {R/t(.5,¿)},q/i}. Требуется построить нестационарный обобщенный автомат Bgv (6), являющийся специальной минимальной формой стационарного автомата Адеп.

4. Задан автомат Agv (5), требуется построить автомат Bgv (С), являющийся специальной минимальной формой автомата Agv.

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

ю

Теорема 2.1. Пусть Ад„ есть автомат (3) и — Н^',

г = 0, + Т, есть семейство его левосторонних базисных матриц, находящихся в нормализованной форме, а т = О, Ьр + У, есть совокупность псевдообратных к ним матриц, где ' = Н|М"Г'/ = = Пусть Вдю есть автомат (4), полученный из автомата Лд„ с помощью преобразования

гв = ?ЛЩ0)/, и£>(,,о = <&> = (Ю)

для всех е у/ € т — 1, ¿р 4- Т. Тогда Вду ~ Лду и автомат

Вдь левостороннс приведен.

Матричный метод построения левосторонне приведенной формы автомата Ад„, основанный на доказанной теореме, состоит в выполнении следующей процедуры:

1. Найти для автомата Лду семейство его левосторонних базисных матриц Н<.г), г = (Цр+Т.

2. Привести каждую из этих матриц к одной из нормализованных форм Н£т), г = 0,£р + Т, и найти псевдообратные к ним матрицы Н^'.

3. Используя матричные преобразования (10), построить автомат Вдъ., являющийся левосторонне приведенной формой автомата Лд„.

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

Теорема 2.2. Пусть Л,„ есть автомат (3) и кЦтЦЛд1!) = Н-т), т = 0, + Т, есть семейство его правосторонних базисных матриц, находящихся в нормализованной форме, а Н^', т — 0,1Р + Т, есть совокупность псевдообратных к ним матриц, где = , = — Н^''. Пусть Вдг, есть автомат (4), полученный из автомата АЯм с помощью преобразования

гв =глЙ£0\ в£>(М) (И)

для всех х$ 6 у! е У(т\ т = 1,£р + Т. Тогда Вд„ ~ АЯУ и автомат Вя„ правосторонне приведен.

Доказаны следующие важные свойства преобразований (10) и (11).

Теорема 2.3. Пусть выполняются условия теоремы 2.1, тогда для любого такта г 6 0,1р +- Т правосторонняя базисная .матрица автомата Вд1, может быть построена из системы линейно независимых столбцов матрицы Н^Л^Н^Д,,,).

Следствие. Пусть выполняются условия теоремы 2.1, тогда если автомат Адг, правосторонне приведен, то и автомат Вду правосторонне приведен.

Теорема 2.4. Пусть выполняются условия теоремы 2.2, тогда для любого такта г 6 0, ¿р + Т левосторонняя базисная матрица автомата Вду может быть построена из системы линейно независимых строк матрицы Щг\Аду)Щг\Адь).

Следствие. Пусть выполняются условия теоремы 2.2, тогда если автомат Аду левосторонне приведен, то и автомат Вдх1 левосторонне приведен.

В заключение главы 2 доказаны следующие два интересных свойства приведенных форм автомата Пусть Ауъ = (А^7"', Л^, У}г>, г л,

= {Х(в\ В(»\ у", гв, (а, /)}, Г), 3, < {р + Т, где = — если й < и ^ = 0, если с/ > и — 0, 4- Г. При этом га = 1(т,), Х^ = Х*^, 1р = В^ - Л^+Ч

= Чв' = Рассмотрим произвольный такт

й, й £ О, Ьр + Т, и пусть, г, г' £ •7ГГП<' есть два начальных распределения весов состояний для автомата Назовем гиг1 эквивалентными начальными распределениями в автомате Адъ е такте с1, если при этих г, г' автомат индуцирует одно и то же обобщенное отображение.

Теорема 2.5. Автомат Адъ. находится в правосторонне приведенной форме в том и только в том случае, когда в каждом такте ё — + Т он не имеет ни одной пары эквивалентных начальных распределений весов состояний.

Рассмотрим все пары слов (ад,и) £ 2доп длины <1 = т + кТ, т £

6 О, + Т, к = О,1,2,... Финальные вектора-столбцы £ Тгп'

называются эквивалентными для автомата Ад11 в такте г, если для каждого Гу) £ С(тА) при этих финальных векторах этот автомат для слов длины д. индуцирует одно и то же обобщенное отображение.

Теорема 2.6. Автомат Ади находится в левосторонне приведенной форме в том и только в том случае, когда в каждом такте т = О, ¿р + Т он не имеет ни одной пары эквивалентных финальных векторов весов состояний.

Теоремы 2.5 и 2.6 фактически дают новые, отличные от введенных в главе 1, определения понятий о приведенных формах автомата Аду.

В главе 3 решена задача построения минимальных форм автомата Ад„. В §1 доказаны следующие утверждения.

Теорема 3.1. Автомат Адь находится в минимальной форме в том и только в том случае, когда он левосторонне и правосторонне приведен.

Теорема 3.2. Пусть Аду есть автомат (3) и г = 0, £р + Т,

есть семейство его левосторонних базисных матриц, находящихся в

нормализованной форме, а H^\Agv), т — 0,tp + Т, есть совокупность псевдообратных к ним матриц. Пусть Bgv есть автомат (4), полученный из автомата Agv с помощью преобразований (10), и Н'Т)(Д,„), г — 0, tp + Т, есть семейство его праврсторонних базисных матриц, находящихся в нормализованной форме, а Н^'(Bgv), т = 0,tp+T, есть совокупность псевдообратных к ним матриц. Тогда, если автомат Vgv = {X(T\DlT\Y(T\fD,{R$(s,l)},q$,tp,T) получен из автомата Bgv с помощью преобразования (аналогичного преобразованию (11))

(12)

для всех xs €_Х{т\ Vi G У{т\ т = l,tp+T, где при г = tp + Т )(Bgv) = HW(ßJt). то автомат Vgv есть минимальная форма автомата Ад„, Vgv — Min Agv.

Теорема 3.3 формулируется аналогично теореме 3.2, но с обратным порядком преобразований - сначала преобразование типа (11), а затем преобразование типа (10)..

В §2 главы 3 на основании теорем 3.2 и 3.3 сформулированы две эквивалентных процедуры построения минимальных форм автомата Agv Первая процедура включает следующие действия:

1. Найти семейство левосторонних базисных матриц автомата Asv, привести каждую из них к одной из нормализованных форм

т — 0, tp + Т, и найти псевдообратные матрицы Hj.r'7(Ла«), т — 0, tp 4- Т.

2. С помощью формул (10) преобразовать автомат Agv в автомат Bgv, являющийся левосторонне приведенной формой автомата Agv.

3. Найти семейство правосторонних базисных матриц автомата Bsv, привести каждую из них к одной из нормализованных форм H^(ßJV), т = Q,tp + Т, и найти псевдообратные матрицы (£>,„), т = 0, tp + Т.

4. С помощью формул (12) преобразовать автомат Bgv в автомат Vgv, являющийся правосторонне приведенной формой автомата Bgv.

В результате получим Vgv = Min Agv. Вторая процедура отличается фактически только порядком действий. Даны примеры построения двух различных минимальных форм для заданного автомата Agv-

В §3 главы 3 исследуются некоторые свойства автоматов (3) и (4), связанные с понятием их подобия. Будем говорить, что эти автоматы AgV и Bgv подобны, если существует такое семейство неособенных квадратных матриц а^ размера (шг х тпг), т = Q,tp + Т, с элементами из

Т (где = оЛ+т>), что выполняются соотношения

Теорема 3.4. Если автоматы А¿v (3) и Bgv (4) подобны, то они эквивалентны и имеют одинаковые (с точностью до преобразования (9)) семейства левосторонних и правосторонних базисных матриц.

Следствие 1. Если автомат Agv (3) находится в левосторонне (пра-восторонне) приведенной форме, то и любой подобный ему автомат Bgv (4) также находится в левосторонне (правосторонне) приведенной форме.

Следствие 2. Если автомат Agv (3) находится в минимальной форме, то и любой подобный ему автомат Bgv (4) также находится в минимальной форме.

В §4 главы 3 исследуется вопрос о множестве всех минимальных форм автомата Agv. Доказано следующее утверждение.

Теорема 3.5. Пусть A'gv = (X«, AM',yM,f,{RW(s,Z)},qM,^,T} и автомат Ад,, (3) есть одна из его минимальных форм. Тогда любой автомат Bgv (4) есть минимальная форма автомата A'gv в том и только в том случае, если он подобен автомату Agv.

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

В главе 4 исследованы проблемы, связанные с построением специальных минимальных форм автоматов. В §1 главы 4 решена задача эквивалентного представления нестационарного автомата Agv стационарным автоматом В'деп, находящимся в минимальной форме.

Теорема 4.1. Пусть Agv есть нестационарный автомат (5), и пусть

нм,

т = 0,tp + Т, есть семейство его левосторонних базисных матриц, тогда может быть построен стационарный обобщенный автомат с постоянной структурой Вдеп такой, что

t -Ь-Т—1

1) Вдеп ~ Ад„ и Вдеп имеет m = £т=о тт состояний;

2) левостороняя базисная матрица Нг автомата Вдсп имеет вид блочно-диагональной матрицы, диагональными блоками которой являются матрицы НМ, т = 0, tp + Т — 1, а остальные элементы равны 0;

3) если автомат Agv левосторонне приведен, то и автомат Вдеп также левосторонне приведен.

Таким образом, если исходный автомат (5) находится в минимальной форме, то для получения искомого автомата В'деп достаточно найти любую правосторонне приведенную форму построенного согласно теореме 4.1 автомата Вдеп.

Следствие. Для любого стационарного автомата В'деп, находящегося в минимальной форме и имеющего т! состояний, не существует эквивалентного ему нестационарного автомата (5) с числом состояний тТ, г = 0, tp + Т - 1, такого, что E^JíT-1 mT < m'.

В §2 главы 4 решается задача оптимального представления стационарного автомата _Дзег1 эквивалентным ему нестационарным автоматом Agv, представляющим собой специальную минимальную форму автомата Адеп■ Рассмотрены различные специальные критерии оценки оптимальности Agv.¡ являющиеся функциями числа состояний автомата в различных тактах, и связанные с такими важными характеристиками конечно-автоматной модели, как объем памяти, необходимой для ее компьютерной реализации и время (количество операций), затрачиваемое на подсчет значений обобщенных отображений для слов большой длины. Предложен метод решения данной задачи, сформулированный, исходя из требования минимальности для автомата Agv величины M{Agv) — Ег=о 1 тг'"г+ь числа элементов в матрицах весов переходов для каждой пары букв (x„yi), xs £ X, y¡ £ Y, но в принципе модифицируемый под любой из рассмотренных в §2 специальных критериев оптимальности. Приведены два примера.

В §3 главы 4 решается общая задала построения для автомата Agv его специальной минимальной формы. Предложена следующая процедура построения этой минимальной формы:

1. Построение минимальной формы A'gv автомата Agv (в том случае, если автомат Agv не находится в минимальной форме).

2. Построение для автомата A'gv эквивалентного ему стационарного автомата Вдеп согласно теореме 4.1, находящегося в левосторонне приведенной форме.

3. Построение правосторонне приведенной формы В'деп стационарного автомата Вдеп, которая будет его минимальной формой.

4. Нахождение для стационарного автомата В'деп его нестационарной специальной минимальной формы Bgv, которая и будет специальной минимальной формой исходного автомата Agv.

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

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

В заключении работы кратко перечислены основные ее результаты. Приложение содержит текст программы GVAutOpt с комментариями и результаты решения примеров.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ:

[1] Пономарева А.Ю., Чирков М.К. О матричном методе редукции состояний обобщенного автомата с периодически меняющейся структурой // Вестник С.-Петербургского университета. Серия 1. 1998. Вып.З (N 15), с. 66-69.

[2] Пономарева А.Ю., Чирков М.К. Обобщенные конечно-автоматные модели с периодически меняющимися параметрами и проблемы их оптимизации // Дискретные модели. Анализ, синтез и оптимизация. СПб., изд. СПбГУ, 1998, с. 3-26.

[3] Пономарева А.Ю., Чирков М.К. Оптимизация обобщенных конечно-автоматных моделей с частично определенными начальными и финальными условиями // Дискретные модели. Анализ, синтез и оптимизация. СПб., изд. СПбГУ, 1998, с. 34-40.

[4] Ponomareva A.Yu., Tchirkov М.К. On a Special Method for States Minimization of Generalized Automata with the Periodically Varying Parameters // Proceeding of the 3rd St.Peterburg Workshop on Simulation. St.Petersburg University Press, 1998, p. 444-448.

[5] Пономарева А.Ю. О минимальных формах автоматных моделей с периодически меняющейся структурой // Вестник молодых ученых. Прикладная математика и механика. СПб., 1999. N 1, с. 33-39.

[6] Пономарева А.Ю., Чирков М.К. О множестве минимальных форм обобщенных автоматов с периодически меняющейся структурой // Статистические модели с приложениями в эконометрике и смежных областях. СПб., изд. НИИХ СПбГУ, 1999, с. 128-137.

[7] Пономарева А.Ю., Чирков М.К. Об оптимальном эквивалентном представлении стационарного автомата нестационарным с периодически меняющейся структурой // Статистические модели с приложениями в эконометрике и смежных областях. СПб., изд. НИИХ СПбГУ, 1999, с. 138-147.

Введение

Глава 1. Основные определения и формулировка задач

§1. Обобщенные автоматы с периодически меняющейся И структурой

1.1.Понятие об обобщенном автомате с периодически меняющейся структурой(11);

1.2.Обобщенное отображение (12); 1.3.Эквивалентность автоматов (12).

§2. Семейства базисных матриц обобщенного автомата с периодически меняющейся структурой 2.1 .Понятие о семействах правосторонних и левосторонних базисных матриц (14);

2.2.Нормализованные формы базисных матриц (15);

2.3.Свойства базисных матриц автомата (15).

§3. Методы построения семейств базисных матриц I

3.1.Построение семейства правосторонних базисных матриц автомата (18); . ^^

3.2.Построение семейства^евосторс^ни^базисных матриц автомата (19).

§4. Приведенные и минимальные формы обобщенного автомата с периодически меняющейся структурой

4.1.Приведенные формы автомата (21);

4.2.Минимальные формы автомата (21); 4.3.Задачи оптимизации автомата (22).

Глава 2. Методы построения приведенных форм обобщенного автомата с периодически меняющейся структурой

§1. Построение левосторонне приведенных форм

1.1 .Формулировка задачи (22);

1.2.Матричный метод построения левосторонне приведенной формы (23);

1.3.Процедура построения левосторонне приведенной формы (25);

1.4.Пример (25).

§2. Построение правосторонне приведенных форм

2.1.Формулировка задачи (31);

2.2.Матричный метод построения правосторонне приведенной формы (31);

2.3.Процедура построения правосторонне приведенной формы (33);

2.4.Пример (33).

§3. Некоторые свойства приведенных форм

3.1.Базисные матрицы левосторонне приведенной формы (37);

3.2.Базисные матрицы правосторонне приведенной формы (39);

3.3.Свойства начальных и финальных векторов в приведенных формах автомата (41).

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

§1. Обоснование метода построения минимальных форм

1.1 .Формулировка задачи (45);

1.2.Необходимое и достаточное условие минимальности автомата (45);

1.3.Теоремы о построении минимальных форм (47).

§2. Метод построения минимальных форм

2.1.Процедура построения минимальной формы (49);

2.2.Пример 1 (50);

2.3.Пример 2 (53).

§3. Подобие обобщенных автоматов с периодически меняющейся структурой

3.1.Понятие подобия автоматов (57);

3.2.Теорема о подобии автоматов (57).

§4. Множество минимальных форм обобщенных автоматов с 60 периодически меняющейся структурой

4.1.Формулировка задачи (60);

4.2.Теорема о множестве минимальных форм (60);

4.3.Пример (63).

Глава 4. Специальные минимальные формы обобщенных автоматов с периодически меняющейся структурой

§1. Представление нестационарного обобщенного автомата с периодически меняющейся структурой стационарным автоматом

1.1.Формулировка задачи (65);

1.2.Теорема об эквивалентности автоматов (65).

§2. Оптимальное представление стационарного автомата нестационарным с периодически меняющейся структурой

2.1.Формулировка задачи (71);

2.2.Критерии оценки оптимальности (71); 2.3.Общий метод решения задачи (74);

2.4.Процедура решения задачи (76);

2.5.Пример 1 (79);

2.6.Пример 2 (83).

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

3.1.Формулировка задачи (89);

3.2.Метод построения специальной минимальной формы (89);

3.3.Пример построения специальной минимальной формы (90).

Глава 5. Программная реализация алгоритмов оптимизации обобщенного автомата с периодически меняющейся структурой

§1. Общая структура программы построения приведенных и минимальных форм 1.1.Основные части программы (99); 1.2.Особенности реализации алгоритмов (99);

1.3.Входные данные (101);

1.4.Выходные данные (102);

1.5.Структура программы (102).

§2. Описание классов CMatrix и CNormal - 2.1.Методы класса CMatrix (103); 2.2.Бинарные операторы класса CMatrix (103); 2.3.Описание класса CNormal. Методы (104); 2.4.Бинарные операторы класса CNormal (105).

§3. Описание классов CStep, CAuto, CFraction и CReal ЗЛ.Методы класса CStep (107); 3.2.Бинарные операторы класса CStep (108); 3.3.Описание класса CAuto (108);

3.4. Описание класса CFraction (109);

3.5. Описание класса CReal (111).

§4. Основные характеристики программной реализации алгоритмов оптимизации 4.1 .Результаты (112);

4.2.Взаимодействие с пользователем (112); 4.3.Объем требуемой памяти (112);

4.4.Точность вычислений (113);

4.5.Границы применения программы минимизации (114).

Исследование проблем теории математических моделей конечно-автоматного типа продолжается в мировой науке уже несколько десятилетий, что нашло свое отражение в целом ряде монографий (см., например, монографии [1-3, 5-8, И, 13, 14, 20, 27, 29-32, 43, 44, 46-51, 54, 55]) и обусловлено как чисто теоретическим интересом к решению новых задач дискретной математики, так и тем, что различные математические модели конечно-автоматного типа достаточно широко и успешно используются для описания и изучения на абстрактном уровне структуры и поведения дискретных систем, устройств и процессов, допускающих соответствующее адекватное конечно-автоматное представление.

При этом к настоящему времени наиболее подробно и детально изучены стационарные математические модели конечно-автоматного типа - конечные автоматы различного вида, абстрактная структура которых (алфавиты входов, состояний и выходов, начальные и финальные условия, правила функционирования) не меняется во времени. Среди таких стационарных конечно-автоматных моделей одними из наиболее общих и сложных, включающих в себя многие самостоятельно изучавшиеся частные случаи, являются так называемые обобщенные конечные автоматы, задаваемые над различными алгебраическими системами, [18, 32, 33, 43, 45, 50, 56-58]. Фактически для всего широкого спектра стационарных конечно-автоматных моделей, начиная с детерминированных автоматов и кончая обобщенными, к настоящему времени разработана достаточно полная абстрактная теория и математические методы решения классических задач их абстрактного анализа, синтеза и оптимизации.

В то же время, аналогичная абстрактная теория нестационарных конечно-автоматных моделей, то есть таких автоматов, абстрактная структура которых меняется во времени, еще находится в стадии разработки, хотя очевидно, что дальнейшее существенное расширение класса дискретных систем, устройств и процессов, описываемых и изучаемых с помощью математических моделей конечно-автоматного типа, может быть достигнуто только в том случае, если отказаться уже на абстрактном уровне от условия стационарности модели и перейти к исследованию математической теории нестационарных конечно-автоматных моделей. При этом, соответственно, может расширяться и класс проблем, решаемых с помощью таких моделей, за счет тех задач абстрактного анализа, синтеза и оптимизации, которые непосредственно связаны с динамикой изменения их абстрактной структуры. Следует, однако, отметить, что теория таких нестационарных конечно-автоматных моделей (главным образом стохастических автоматов с переменной структурой) в течение многих лет развивалась в основном в направлении постановки и решения весьма важных, но специфических задач, связанных с поиском таких методов и алгоритмов изменения параметров структуры автомата во времени, которые бы обеспечивали по возможности оптимальное поведение автомата в тех или иных условиях его взаимодействия с окружающей средой, в игровых задачах, в задачах автоматического управления и т. п. (см., например, монографии [8, 30]). При этом упомянутые выше классические для абстрактной теории стационарных автоматов задачи анализа, синтеза и оптимизации, не связанные с понятием оптимального поведения автомата, для нестационарных автоматов оказались мало исследованными, а сам спектр рассматривавшихся нестационарных конечно-автоматных моделей недостаточно широким.

В математической теории конечно-автоматных моделей любого вида одними из важнейших являются проблемы поиска оптимальных форм их представления, в основном связанные с минимизацией числа состояний и построением приведенных и минимальных форм модели [7, 11, 12, 17, 19, 31-43, 45, 52, 54-56]. В частности, для наиболее общего случая стационарных обобщенных конечных автоматов, задаваемых над полями, при решении проблем оптимизации Чирковым М.К. и Шестаковым A.A. были разработаны эффективные матричные методы построения их приведенных и минимальных форм, не выходящих за рамки класса стационарных обобщенных автоматов [33, 35-43, 45]. Естественно, что решение подобных задач оптимизации абстрактной структуры остается одной из основных проблем и в теории нестационарных конечно-автоматных моделей.

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

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

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

Кратко остановимся на распределении материала по главам.

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

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

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

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

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

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

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

Методика исследования в основном базируется на использовании математических методов общей теории автоматов, в том числе матричных методов их эквивалентного преобразования (см. уже упоминавшиеся монографии и статьи), методов линейной алгебры и теории матриц [4, 9, 10, 15, 16], языка программирования С++ [28].

Основные результаты диссертации были опубликованы в работах [21-26,53], представлены на международной научной конференции "The Third St.Petersburg Workshop on Simulation, June 28 - July 3, 1998", докладывались и обсуждались на семинарах лаборатории математических проблем информатики НИИММ СПбГУ и кафедры статистического моделирования математико-механического факультета СПбГУ.

Диссертация выполнена в рамках проведения научно-исследовательских работ по теме плана фундаментальных госбюджетных исследований СПбГУ "Исследование фундаментальных проблем математической теории обобщенных автоматов с изменяемой структурой" (N гос. per. 01960005947) и при поддержке гранта РФФИ 98-01-01008.

Автор считает своим приятным долгом выразить глубокую благодарность научному руководителю М.К.Чиркову, а также сотрудникам кафедры статистического моделирования математико-механического факультета и лаборатории математических проблем информатики НИИММ СПбГУ за всестороннюю поддержку и постоянное внимание к работе.

Заключение.

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

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

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

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

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

5. Введено понятие специальных минимальных форм для автоматов исследуемого типа и предложен метод их построения.

6. Разработана программа СУАиЮр1 на языке С++, реализующая предложенные методы и алгоритмы оптимизации автоматов рассматриваемого типа.

1. Айзерман М.А., Гусев J1.A., Розоноэр Л.И., Смирнов И.М., Таль A.A. Логика, автоматы, алгоритмы. М., Физ-матгиз, 1963.

2. Алгебраическая теория автоматов, языков, полугрупп / под ред. М. Арбиба. М., Статистика, 1975. 335 с.

3. Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). JL, Энергия, 1979. 232 с.

4. Боревич З.И. Определители и матрицы. М., Наука, 1988.

5. Брауэр В. Введение в теорию конечных автоматов. М., Радио и связь, 1987. 392 с.

6. Бухараев Р.Г. Вероятностные автоматы. Казань, Изд. КГУ. 1977. 248 с.

7. Бухараев Р.Г. Основы теории вероятностных автоматов. М., Наука, 1985. 288 с.

8. Варшавский В.И. Коллективное поведение автоматов. М., Наука, 1973. 407 с.

9. Воеводин В.В. Вычислительные основы линейной алгебры. М., Наука, 1977. 304 с.

10. Гантмахер Ф.Р. Теория матриц. М., Наука, 1967. 576 с.

11. Глушков В.М. Синтез цифровых автоматов. М., Физматгиз, 1962. 476 с.

12. Карлайл Е.У. Приведенные формы для стохастических последова-тельностных машин // Кибернетический сборник. Новая серия. М., 1966. Вып. 3. С. 101-110.

13. Кудрявцев В.Б., Алешин C.B., Подколзин A.C. Элементы теории автоматов. М., Изд. МГУ, 1978. 216 с.

14. Кудрявцев В.Б., Алешин C.B., Подколзин A.C. Введение в теорию автоматов. М., Наука, 1985. 320 с.

15. Мальцев А.И. Алгебраические системы. М., Наука, 1970. 392 с.

16. Мальцев А.И. Основы линейной алгебры. М., Наука, 1975. 400 с.

17. Мирошниченко И.Д., Чирков М.К. Минимизация обобщенных конечных автоматов с периодически меняющейся структурой // Проблемы оптимизации дискретных систем. Д., Изд. ЛГУ, 1990. С. 7-21.

18. Мучник A.A. Общие линейные автоматы // Проблемы кибернетики. М., Наука, 1970. Вып. 23. С. 171-208.

19. Наср Я., Чирков М.К. О матричном методе оптимизации стохастических автоматов // Вестник С.-Петербургского университета. Серия 1. 1992. Вып. 3. (N 15). С. 44-49.

20. Плоткин Б.И., Гринлаз Л.Я., Гварамия A.A. Элементы алгебраической теории автоматов. М., Высшая школа, 1994. 191 с.

21. Пономарева А.Ю. О минимальных формах автоматных моделей с периодически меняющейся структурой // Вестник молодых ученых. Прикладная математика и механика. СПб., 1999, вып. 1. С. 33-39.

22. Пономарева А.Ю., Чирков М.К. О матричном методе редукции состояний обобщенного автомата с периодически меняющейся структурой // Вестник С.-Петербургского университета, СПб., Изд. СПбГУ, серия 1, 1998, вып. 3, (N 15). С. 66-69.

23. Пономарева А.Ю., Чирков М.К. Обобщенные конечно-автоматные модели с периодически меняющимися параметрами и проблемы их оптимизации // Дискретные модели. Анализ, синтез и оптимизация. СПб., Изд. СПбГУ, 1998. С. 3-26.

24. Пономарева А.Ю., Чирков М.К. Оптимизация обобщенных конечно-автоматных моделей с частично определенными начальными и финальными условиями // Дискретные модели. Анализ, синтез и оптимизация. СПб., Изд. СПбГУ, 1998. С. 34-40.

25. Пономарева А.Ю., Чирков М.К. О множестве минимальных форм обобщенных автоматов с периодически меняющейся структурой / / Статистические модели с приложениями в эконометрике и смежных областях. СПб., Изд. НИИХ СПбГУ, 1999. С. 128-137.

26. Поспелов Д.А. Вероятностные автоматы. М., Энергия, 1970. 88 с.

27. Страуструп Б. Язык программирования С++. СПб, М.; "Невский диалект" "Издательство БИНОМ", 1999. 991 с.

28. Трахтенброт Б.А., Бардзинь Я.М. Конечные автоматы. Поведение и синтез. М., Наука, 1970. 400 с.

29. Цетлин М.Л. Исследования по теории автоматов и моделированию биологических систем. М., Наука, 1969.

30. Чирков М.К. Основы общей теории конечных автоматов. JL, Изд. ЛГУ, 1975. 280 с.

31. Чирков М.К. Частичные автоматы. Л., Изд. ЛГУ, 1983. 260 с.

32. Чирков М.К. О матричных методах оптимизации обобщенных автоматов // Дискретные системы и их программное обеспечение. Л., Изд. ЛГУ, 1990. С. 3-18.

33. Чирков М.К., Наср Я. О стахостических и нестохастических минимальных формах стохастических автоматов // Теория и приложения дискретных систем. СПб, Изд. СПбГУ, 1995. С. 37-67.

34. Чирков М.К., Шестаков A.A. Оптимизация внутренней структуры обобщенных автоматов // Роботы и робототехнические системы. Иркутск, Изд. ИПИ, 1986. С. 128-135.

35. Чирков М.К., Шестаков A.A. Подобие частичных обобщенных автоматов // Роботы и робототехнические системы. Иркутск, Изд. ИПИ, 1985. С. 95-101.

36. Чирков М.К., Шестаков A.A. Подобие и минимизация обобщенных конечных автоматов // Математические проблемы информатики. Л., Изд. ЛГУ, 1987. С. 158-173.

37. Шестаков A.A. Матричные методы оптимизации обобщенных конечных автоматов // Синтез систем вычислительного эксперимента. Ч. 1. Апатиты, Изд. КНЦ РАН, 1995. С. 7-19.

38. Шестаков А. А. Эквивалентные преобразования конечных автоматов, заданных над ассоциативными телами // Вопросы анализа и синтеза сложных систем. Иркутск, Изд. ИПИ, 1989. С. 65-75.

39. Шестаков А.А. Эквивалентность и оптимизация обобщенных конечных автоматов // Вопросы анализа и синтеза сложных систем. Иркутск, Изд. ИПИ, 1989. С. 73-81.

40. Шестаков А.А. Алгоритм матричной оптимизации обобщенных конечных автоматов // Синтез систем вычислительного эксперимента. Ч. 1. Апатиты, Изд. КНЦ РАН, 1995. С. 20-26.

41. Шестаков А.А., Чирков М.К. Эффективный алгоритм оптимизации конечных автоматов // Автоматизация физического эксперимента. Иркутск, Изд. Иркут. ун-та, 1988. С. 37-39.

42. Шестаков А.А., Чирков М.К. Обобщенные конечные автоматы: поведенческая эквивалентность и проблемы оптимизации. Апатиты, Изд. КНЦ РАН, 1992. 160 с.

43. Яблонский С.В. Введение в дискретную математику. М., Наука, 1979. 272 с.

44. Chirkov М.К. On Matrix Methods for Optimization of Generalized Automata // Annales Universitatis Scientiarum Budapestinensis de Rolando Eotvos Nominatae. Sectio Computatorica. Budapest, 1991, Tomus 11, p. 175-191.

45. Eilenberg S. Automata, languages and mashines. N.Y., Academic Press, 1976.

46. Gecseg F. Algebraic theory of automata. Budapest, Akademi ai Kiado, 1972.

47. Gill A. Linear sequentional circuits: analysis, synthesis and applications. N.Y., McGraw-Hill Book Company. 1966. 216 p.

48. Ginzburg A. Algebraic theory of automata. New York, Academic Press. 1968. 165 p.

49. Kandel A., Lee S.C. Fuzzy switching and automata: theory and applications. New York, London, Russak and Company, 1979. 300 p.

50. Paz A. Introduction to Probabilistic Automata. N.-Y., Academic Press. 1971. 22 p.

51. Paz A. Minimization theorems and techniques for sequential stochastic machines // Inform, a. Control. 1967, Vol. 11, N 1-2. P. 155-166.

52. Salomaa A. Automata theory. Oxford, Pergamon Press. 1969.

53. Starke P.H. Abstrakte Automaten. Berlin, VEB Deutscher Verlag der Wissenschaften, 1969. 392 s.

54. Topencarov V.V., Peeva K.G. Equivalence, reduction and minimization of finite fuzzy-automata // Jorn. Math. Anal, and Appl. 1981. Vol. 84. N 1. P. 270-281.

55. Turakainen P. Generalized automata and stochastic languages // Proc. Amer. Math. Soc. 1969. Vol. 21. N 2. P. 303-309

56. Wechler W., Dimitrov V. R-fuzzy automata // Inform. Process. 74 (Proceedings of the IFIP Congress 74). Amsterdam; London, 1974. P. 657660.

57. Файл "Fraction.h" с описанием класса CFraction.ifhdefFRACTIONH #define FRACTIONHclass CFraction {числитель дробиint64 mnNum; // знаменатель дробиint64 m nDen;сокращение дроби void Reduce();public:создает дробь с числителем 0 и знаменателем 1

58. CFraction(int64 Num=0,int64 Den=l);присваивает дроби целое число

59. CFraction operator=(int64 nSource);оператор сложения дробей CFraction& operator+=(CFraction Source);оператор сложения дроби и целого числа

60. CFraction& operator+=(int64 nSource);оператор вычитания дробей CFraction& operator-=(CFraction Source);оператор вычитания дроби и целого числа

61. CFraction& operator-=(int64 nSource);оператор умножения дробей CFraction& operator*=(CFraction Source);оператор умножения дроби и целого числа

62. CFraction& operator*=(int64 nSource);оператор деления дробей CFraction& operator/=(CFraction Source);оператор деления дроби и целого числа

63. CFraction operator+(CFraction, CFraction);

64. CFraction operator-(CFraction, CFraction);

65. CFraction operator* (CFraction, CFraction);

66. CFraction operator/(CFraction, CFraction);endif

67. Файл "Fraction.cpp" реализации операторов, описанных в классе CFraction.include "stdafx.h" #include "fraction.h" include "util.h"

68. CFraction: :CFraction(int64 Num,int64 Den):mnNum(Num), mnDen(Den)1. Reduce();void CFraction: :Reduce() {int64 nGCD=GCD(mnNum, mnDen); mnNum/=nGCD; mnDen/=nGCD; if (mnDen<0) {mnNum*=-l; mnDen*=-l;if (mnNum= =0) mnDen=l;z*=b; return z;

69. CFraction operator/(CFraction a, CFraction b)

70. CReal operator+(CReal, CReal);

71. CReal operator-(CReal, CReal);

72. CReal operator*(CReal, CReal);

73. CReal operator/(CReal, CReal);endif

74. CReal: :CReal(double dNum) {mdNum=dNum;

75. CReal: :CRealCint64 nNum) {

76. CReal operator+(CReal a, CReal b)

77. CReal z=a; z+=b; return z;

78. CReal operator-(CReal a, CReal b) {

79. CReal z=a; z-=b; return z;

80. CReal operator* (CReal a, CReal b)

81. CReal z=a; z*=b; return z;

82. CReal operator/(CReal a, CReal b)

83. CReal z=a; z/=b; return z;

84. CMatrix<ElemType> operator* (const ElemType&, const CMatrix<ElemType>&);оператор умножения матрицы на константу template <typename ElemType>

85. CMatrix<ElemType> operator*(const CMatrix<ElemType>&, const ElemType&);оператор деления матрицы на константу template <typename ElemType>

86. CMatrix<ElemType> operator/(const CMatrix<ElemType>&, const ElemType&);оператор умножения матрицы на матриц template <typename ElemType>

87. CMatrix<ElemType> operator*(const CMatrix<ElemType>&, const CMatrix<ElemType>&);оператор сложения матриц template <typename ElemType>

88. CMatrix<ElemType> operator+(const CMatrix<ElemType>&, const CMatrix<ElemType>&);оператор вычитания матриц template <typename ElemType>

89. CMatrix<ElemType>: :~CMatrix() {if (mpMatrix) delete. mjpMatrix;template <typename ElemType>void CMatrix<ElemType>::Resize(unsigned n, unsigned m, bool bCopy) {

90. ElemType& CMatrix<ElemType>::Elem(unsigned i, unsigned j) {if ((l>i) || (i>mnRows) ||l^j) II (j>ninColumns)) throw -1;return mpMatrix(i-1) *mnColumns+j -1 .;template <typename ElemType>

91. ElemType CMatrix<ElemType>::GetElem(unsigned i, unsigned j) const {if ((l>i) || (i>mnRows) ||

92. II (j>mnColumns)) throw -1;return mpMatrix(i-1) *mnColumns+j -1 .;template <typename ElemType>

93. CMatrix<ElemType> CMatrix<ElemType>::Row(unsigned i) const {if ((l>i) || (i>mnRows)) throw -1; CMatrix<ElemType> objRow(l, mnColumns); for (unsigned j=1; j<=mnColumns; j++) objRow.Elem(l, j)=GetElem(i, j);return objRow;template <typename ElemType>

94. Elem(i, mnColumns)=objColumn.GetElem(i, 1); return mnColumns;template <typename ElemType>

95. CMatrix<ElemType>& CMatrix<ElemType>:: operator *=(const ElemType& c)for (unsigned i=l; i<-mnRows; i++)for (unsigned j=l; j<=mnColumns; j++) Elem(i,j)*=c;return *this;template <typename ElemType>

96. CMatrix<ElemType>& CMatrix<ElemType>:: operator /=(const ElemType& c)return operator *=(l/c);template <typename ElemType>

97. CMatrix<ElemType> operator*(const ElemType& c, const CMatrix<ElemType>& M) {

98. CMatrix<ElemType> R=M; return R*=c;template <typename ElemType>

99. CMatrix<ElemType> operator*(const CMatrix<ElemType>& M, const ElemType& c) {

100. CMatrix<ElemType> R=M; return R*=c;template <typename ElemType>

101. CMatrix<ElemType> operator/(const CMatrix<ElemType>& M, const ElemType& c) {

102. CMatrix<ElemType> R=M; return R/=c;template <typename ElemType>

103. CMatrix<ElemType>operator+(const CMatrix<ElemType>&A, const CMatrix<ElemType>&1. B)template <typename ElemType>

104. CNormal<ElemType>::CNormal(const CNormal& Source) : CMatrix<ElemType>(Source)1. Copy(Source);template <typename ElemType>

105. CNormal<ElemType> CNormal<ElemType>::operator=(const CNormal& Source) {

106. Min(n,mnRows)*sizeof(unsigned)); deletef. pOldColumns;if (pOldRows) {if (bCopy) memcpy(mpOneRows, pOldRows, Min(m,mnColumns)*sizeof(unsigned)); delete. pOldRows;

107. CMatrix<ElemType>: :Resize(n,m);template <typename ElemType>

108. CNormal<ElemType>: :~CNormal() {if (mpOneRows) delete. mpOneRows; if (mpOneColumns) delete[] mpOneColumns;template <typename ElemType>unsigned CNormal<ElemType>::AddRow(const CMatrix<ElemType>& objRow)

109. ASSERTE(objRow.RowCount()==l);

110. Elem(i,j)-=c*GetElem(mnRows,j); }строка была линейно независимой return mnRows;// строка не была линейно независимой return 0;template <typename ElemType>unsigned CNormal<ElemType>::AddColumn(const CMatrix<ElemType>& obj Column)

111. Elem(ij)-=c*GetElem(i,mnColumns); } // строка была линейно независимой return mnColumns;// строка не была линейно независимой return 0;template <typename ElemType>

112. CMatrix<ElemType> CNormal<ElemType>::Inv() const {

113. Файл "Step.h" с описанием класса CStep и методов, описанных в классе CStep.ifndefSTEPHdefineSTEPHinclude "Normal.h" #include "Util.h"template <typename NumType>class CStep {

114. AS SERTE(objMatrixH. ColumnCount()==mnRows); bool bAdded=false;for (unsigned nRow=l; nRow<=objMatrixH.RowCount(); nRow++) {

115. CNormal<NumType>& objNormalH)bool bAdded=false;unsigned nColumns=mpMatrixH->ColumnCount();for (unsigned nColumn=l; nColumn<=nColumns; nColumn++) {

116. CMatrix<NumType>& CStep<NumType>::MatrixH() {return *mpMatrixH;template <typename NumType>

117. CMatrix<NumType>& CStep<NumType>::MatrixR(unsigned i)if (i>=mnMatrices) throw -2; return mpMatricesR1.;template <typename NumType>void CStep<NumType>::SetNumber(unsigned nNumber)mnNumber=nNumber;endif

118. Файл "Auto.h" с описанием класса CAuto и методов, описанных в классе CAuto.ifndefAUTOH #define AUTOHinclude "Step.h"template <typename NumType>class CAuto {

119. CAuto<NumType>: :CAuto() : mnPred(0), mnSteps(O), mpSteps(NULL), mnRows(0), mnColumns(O), mszFile("tmp")

120. С Auto<NumType>: :~CAuto()if (mjpSteps) delete. mpSteps;template <typename NumType>istream& operator»(istream& is, CAuto<NumType>& a) {