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

• Пономарева, Александра Юрьевна
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Пономарева, Александра Юрьевна

Введение

Глава 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 на языке С++, реализующая предложенные методы и алгоритмы оптимизации автоматов рассматриваемого типа.

Список литературы диссертационного исследования кандидат физико-математических наук Пономарева, Александра Юрьевна, 1999 год

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) {