Введение к работе
Актуальность темы. Уже несколько десятилетий продолжается интенсивное развитие различных аспектов теории математических моделей конечно-автоматного типа, нашедшее отражение в целом ряде монографий (Айзерман М.А. и др., Бухараев Р.Г., Глушков В.М., Кудрявцев В.Б. и др., Трахтенброт Б.А. и Бардзинь Я.М., Чирков М.К, [1-3], Яблонский СВ., Eilenberg S., Ginzburg A., Kan-dell А. и Lee S.C., Paz A., Salomaa A., Starke Р.Н. и другие). Существенное место среди таких моделей занимают различные виды обобщенных (нечетких) и стохастических (вероятностных) автоматов, которые изучали Бухараев Р.Г., Варшавский В.И., Мучник А.А., Хунядвари Л., Чирков М.К., Щестаков A.A., Carlyle J.W., Chimel К., Ginzburg A., Kandel A., Lee S.C., Paz A., Salomaa А., Starke Р.Н., Topencharov V. *'., Turakainen P., Wechler W., Dimitrov V. и многие другие. При этом существенным стимулом к развитию пового направления - математической теории обобщенных (нечетких) автоматов послужили основополагающие работы Л.А.Заде и некоторых других авторов (Kandel А. и Lee S.C., Dubois P., Prade H., Negoita C.V. и Relescu D.A. и другие) по теории нечетких множеств и ее приложениям. Однако, внимание, проявляемое к исследованию различных обобщенных и стохастических математических моделей конечно-автоматного типа, объясняется не только чисто теоретическим интересом к решению новых задач дискретной, в том числе "нечеткой", математики, но и тем, что конечные автоматы различного вида являются, как правило, весьма удобной математической моделью для описания определенного класса систем, устройств и протекающих в них процессов. В частности, понятие стохастического автомата широко используется в качестве математической модели целого ряда систем, устройств, процессов и явлений, которые содержат в себе элементы случайности (или, являясь по-существу детерминированными, подвергаются случайным воздействиям и т.п.) и допускают конечно-автоматную интерпретацию. Повышенный иятерес к изучению различного рода обобщенных (в том числе частично определенных) конечных автоматов также обусловлен возможностью их применения в качестве простых и удобных математических моделей дискретных процес-
сои, систем и явлений (например, в условиях неточности знаний о них или при неполной определенности их задания или описания фуикциопирования), когда требование адекватного описания динамики их "тонкого" поведения требует разумного усложнения (обобщения) моделирующих их автоматов. При этом исследование обобщенных коночных автоматов предполагает не только более глубокую обобщающую интепретацию уже известных результатов, но и позволяет разрабатывать новые, более эффективные приемы и методы решения традиционных классических задач анализа, синтеза, доопределения и оптимизации и для более узких, уже изученных, классов автоматов.
Данная работа является итогом многолетних исследований автора в области математической теории (в общем случае частично определенных) обобщенных и стохастических конечно-автоматных моделей, проводившихся в СПбГУ в рамках плана фундаментальных госбюджетных исследований. В 1993-1994 г.г. исследования частично выполнялись при финансовой поддержке Российского фонда фундаментальных исследований (93-012-292),
Цель работы. Главная цель работы - исследовать теоретические основы и новые методы решения фундаментальных классических проблем математической теории конечных автоматов - абстрактного анализа, синтеза и оптимизации - применительно к качественно более общему случаю частично определенных обобщенных конечных автоматов над некоторыми алгебраическими системами, а также проблемы оптимизации стохастических (в том числе частично определенных ) автоматов, разработать на этой основе методику и алгоритмы анализа, синтеза и оптимизации конечно-автоматных моделей данного типа, удобные для практической реализации на ЭВМ.
Методика исследования базируется на использовании аппарата математической теории автоматов и регулярных языков, теории алгебраических систем, теории матриц, линейной алгебры и выпуклого анализа, теории вероятностей, теории нечетких множеств, математической логики и теории графов.
Научная новизна. В работе впервые определены и исследованы
новые, классы частично определенных обобщенных конечно-автоматных моделей над полукольцами и полями, в результате чего заложены основы единой математической теории таких частично определенных моделей и существенно дополнены некоторые разделы теории стохастических конечно-автоматных моделей. Полученные в работе новые фундаментальные результаты, касающиеся основных проблем анализа, синтеза и оптимизации частично определенных обобщенных и стохастических конечно-автоматных моделей различного вида, позволили обосновать и разработать новые эффективные методы и алгоритмы решения этих задач, удобные для реализации на ЭВМ.
Практическая ценность работы. Теоретические результаты исследования послужили основой для разработки под руководством автора на кафедре статистического моделирования СПбГУ и в лаборатории математических проблем информатики НИИММ СПбГУ комплекса алгоритмов и программ для ПЭВМ IBM PC/AT, практически реализующих теоретически обоснованные в работе методы анализа, синтеза и оптимизации обобщенных и стохастических кот нечно-автоматных моделей. Теоретические результаты исследований включены также в спецкурсы "Теория автоматов", "Стохастические автоматы" и "Автоматное моделирование", читаемые автором на математико-механическом факультете СПбГУ.
Аппробация работы.
Результаты работы были представлены на тре-х всесоюзных научных конференциях: 1. "Проблемы теоретической кибернетики", Иркутск, 1985 г. [47]; 2. "Планирование и автоматизация эксперимента в научных исследованиях", Ленинград, 1986 г. [48]; 3. "Применение вычислительной техники и математических методов в научных исследованиях", Киев, 1986 г. [49]; и двух международных научных конференциях: 1. "Third International Workshop on Model Oriented Data Analysis", St.Petersburg, 1992 [57, 58]; 2. "International Workshop on Mathematical Methods and Tools in Computer Simulation", St.Petersburg, 1994(62, 63]; докладывались и обсуждались на научных семинарах в Университете им. Йожефа Аттилы (г.Сегед, Венгрия) [36] и в Будапештском университете им. Лоранда Этвеща
(г.Будапешт, Венгрия) [44,55], а также на семинарах кафедры статистического моделирования СПбГУ и лаборатории математических проблем информатики НИИММ СПбГУ.
По теме диссертации опубликовано 63 работы, в том числе 4 монографии.
