Введение к работе
Актуальность темы. Исследование проблем теории математических моделей конечно-автоматного типа продолжается в мировой науке уже несколько десятилетий, что нашло свое отражение в целом ряде монографий (Айзерман М.А. и др., Баранов СИ., Бардзинь Я.М. и Трахтенброт Б.А., Брауэр В., Бухараев Р.Г., Варшавский В.И., Глуш-ков В.М., Кудрявцев В.Б. и др., Плоткин Б.И. и др., Поспелов Д.А., Цетлин М.Л., Чирков М.К., Шестаков А.А., Яблонский СВ., Eilenbcrg S., Gecseg F., Gill A., Ginsburg A., Kandell А. и Lee S.C., Paz A., Salomaa A., Starke P.H. и другие) и обусловлено как чисто теоретическим интересом к решению новых задач дискретной математики, так и тем, что различные математические модели конечно-автоматного типа достаточно широко и успешно используются для описания и изучения на абстрактном уровне структуры и поведения дискретных систем, устройств и процессов, допускающих соответствующее адекватное конечно-автоматное представление. При этом к настоящему времени наиболее полная абстрактная теория и достаточно эффективные методы решения классических проблем абстрактного анализа, синтеза и оптимизации разработаны для широкого спектра стационарных конечно-автоматных моделей, начиная с детерминированных автоматов и кончая обобщенными автоматами, задаваемыми над различными алгебраическими системами. В то же время, аналогичная абстрактная теория нестационарных конечно-автоматных моделей, то есть таких автоматов, абстрактная структура которых меняется во времени, еще находится в стадии разработки, хотя очевидно, что дальнейшее существенное расширение класса дискретных систем, устройств и процессов, описываемых и изучаемых с помощью математических моделей конечно-автоматного типа, может быть достигнуто только в том случае, если отказаться уже на абстрактном уровне от условия стационарности модели и перейти к исследованию математической теории нестационарных конечно-автоматных моделей. При этом, соответственно, может расширяться и класс проблем, решаемых с помощью таких моделей, за счет тех задач абстрактного анализа, синтеза и оптимизации, которые непосредственно связаны с динамикой изменения их абстрактной структуры.
В математической теории конечно-автоматных моделей любого вида одними из важнейших являются проблемы поиска оптимальных форм их представления, связанные с минимизацией числа состояний
и построением приведенных и минимальных форм модели. В частности, при решении проблем оптимизации для наиболее общего случая стационарных обобщенных конечных автоматов, задаваемых над полями, Чирковым М.К. и Шестаковым А.А. были разработаны эффективные матричные методы построения их приведенных и минимальных форм. Естественно, что решение подобных задач оптимизации абстрактной структуры остается одной из основных и важнейших проблем и в теории нестационарных конечно-автоматных моделей. Таким образом представляется весьма актуальным исследование новых, по возможности наиболее обобщенных, нестационарных моделей конечно-автоматного типа, теоретическое обоснование и разработка методики их оптимизации и построения различных минимальных форм.
Данная диссертация выполнена в рамках проведения научно-исследовательских работ по теме плана фундаментальных госбюджетных исследований СПбГУ (N гос. per. 01960005947) и при поддержке гранта РФФИ 98-01-01008.
Цель работы. Основная цель данной работы - детально исследовать проблемы оптимизации, теоретически обосновать и разработать математические методы и алгоритмы построения приведенных и минимальных форм применительно к новым нестационарным математическим моделям конечно-автоматного типа - нестационарным обобщенным (задаваемым над произвольным полем) конечным автоматам, абстрактная структура которых сначала последовательно меняется в течение конечного числа начальных тактов (предпериода), а затем меняется периодически с заданным периодом, решить ряд специфических задач оптимизации таких автоматов по нетрадиционным критериям, связанных с построением их специальных минимальных форм, а также разработать программу, реализующую предложенные методы и алгоритмы оптимизации.
Методика исследования базируется на использовании математических методов общей теории автоматов, в том числе специальных матричных методов их эквивалентного преобразования, методов линейной алгебры и теории матриц, языка программирования C++.
Научная новизна. Кратко можно выделить следующие, полученные в рамках данной работы, новые результаты:
1. Введено понятие о новой математической модели конечно-автоматного типа - нестационарном, обобщенном (задаваемом над произвольным полем) конечном автомате с заданным предпериодом и периодом изменения всех параметров абстрактной структуры и частично
определенными начальными условиями, введено понятие о семействах базисных матриц такого автомата и изучены их свойства, введено понятие об эквивалентности автоматов данного типа и сформулированы задачи оптимизации их абстрактной структуры.
-
Доказан ряд фундаментальных положений, позволивших теоретически обосновать и разработать оригинальные матричные методы и алгоритмы решения сформулированных задач оптимизации и построения приведенных и минимальных форм таких автоматов.
-
На автоматы исследуемого типа обобщено понятие подобия, доказано, что множество всех минимальных форм автомата совпадает с множеством всех автоматов, подобных любой из его минимальных форм, и получено выражение для преобразования подобия, связывающего различные минимальные формы автомата.
-
Разработан метод построения для нестационарного автомата исследуемого типа эквивалентного ему стационарного обобщенного автомата, находящегося в минимальной форме, и метод построения для стационарного обобщенного автомата эквивалентного ему нестационарного автомата исследуемого типа, находящегося в минимальной форме и удовлетворяющего специальному критерию оптимальности.
-
Введено понятие специальных минимальных форм для автоматов исследуемого типа и предложен метод их построения.
-
Разработана программа на языке C++, реализующая предложенные методы и алгоритмы оптимизации автоматов рассматриваемого типа.
Практическая ценность работы состоит в разработке эффективных методов, алгоритмов и программы решения задач оптимизации нестационарных обобщенных конечно-автоматных моделей с периодически меняющейся структурой, которые могут найти практическое применение при математическом моделировании, оптимизации числа состояний и построении минимальных форм тех дискретных систем, устройств и процессов, которые допускают адекватное абстрактное описание в терминах обобщенных автоматов с периодически меняющейся структурой, задаваемых над полем какого-либо вида.
Аппробация работы. Основные результаты диссертации были опубликованы в работах [1-7], представлены на международной научной конференции "The Third St.Petersburg Workshop on Simulation, June 28 - JuJy 3, 1998", докладывались и обсуждались на семинарах лаборатории математических проблем информатики НИИММ СПбГУ и кафедры статистического моделирования математико-механического
факультета СПбГУ.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и приложения. Основной текст диссертации занимает 120 страниц. Библиография составляет 58 наименований. Приложение содержит 53 страницы.
