Разработка фреймово-продукционной модели синтеза цифровых автоматов на основе метода спецификации состояний и ее программная реализация средствами реляционной СУБД тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Морозов, Андрей Владимирович

• Морозов, Андрей Владимирович
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Морозов, Андрей Владимирович

ВВЕДЕНИЕ.

Глава 1. НОВЫЕ ТЕНДЕНЦИИ В ОБЛАСТИ АБСТРАКТНОГО

СНТЕЗА АВТОМАТОВ.

§1.1. Классификация основных методов.

§1.2. Формальные методы.

§1.3. Неформальные методы.

§ 1.4. Метод синтеза, основанный на спецификации состояний.

§1.5. Выводы по первой главе.

Глава 2. ФРЕЙМОВО-ПРОДУКЦИОННАЯ МОДЕЛЬ СИНТЕЗА

АВТОМАТОВ.

§2.1. Синтез автомата как задача искусственного интеллекта.

§2.2. Предлагаемая модель. Область вне лабиринтов.

§2.3. Предлагаемая модель. Области лабиринтов. Заключительный этап.

§2.4. Выводы по второй главе.

Глава 3. ВОПРОСЫ ПРОГРАММНОЙ РЕАЛИЗАЦИИ

ПРЕДЛАГАЕМОЙ МОДЕЛИ.

§3.1. Задачи исследования.

§3.2. Пример погружения модели в среду Microsoft Access.

§3.3. Язык присоединенных процедур и его реализация.

§3.4. Реализация системных процедур модели синтеза автоматов.

§3.5. Расширение функциональных возможностей системы.

§3.6. Выводы по третьей главе.

Глава 4. ИССЛЕДОВАТЕЛЬСКАЯ ВЕРСИЯ РАЗРАБОТАННОЙ

ИНТЕРАКТИВНОЙ СИСТЕМЫ СИНТЕЗА АВТОМАТОВ

§4.1. Программная система.

§4.2. Результаты тестирования.

§4.3. Руководство пользователя.

§4.4. Пример задания на синтез автомата.

Введение диссертации (часть автореферата) на тему «Разработка фреймово-продукционной модели синтеза цифровых автоматов на основе метода спецификации состояний и ее программная реализация средствами реляционной СУБД»

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

Актуальность темы.

Решение практических задач по синтезу автоматов подразумевает использование значительной доли эвристики. Одна из первых серьезных попыток была предпринята С. Колдуэллом [8] в развитие идеи Д. Хаффмэна [42]. Однако этот подход нельзя отнести к числу детерминированных. Обещающий шаг на пути детерминизации процесса синтеза автоматов сделан А.А. Талем [30]. По объективным причинам работа была прервана, и характер ее продолжения не очевиден. Предложенный в [22] подход является эффективным инструментом эвристики [25]. Но с увеличением размерности решаемых задач трудности нарастают.

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

Использование логической [31] модели применительно к синтезу автоматов не очевидно. Возможность развития предикатного метода [7] в плане автоматизации процедуры синтеза требует специальных исследований. Для рассматриваемых объектов наиболее подходят фреймовые структуры данных [21, 11], которые в настоящее время приобрели широкое применение в различных областях.

Цель работы.

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

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

1. Выбор базового метода синтеза автоматов, хорошо адаптируемого к автоматизации.

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

3. Выбор инструментального средства для реализации разработанной модели.

4. Создание интерпретатора экспертной системы синтеза автоматов. Методы исследований.

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

Научная новизна работы:

1. Разработана фреймово-продукционная модель синтеза автоматов.

2. Проведено погружение предложенной модели в среду реляционной СУБД.

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

Проведенные исследования позволяют сделать обобщающий вывод о правомерности разработанных принципов автоматизированной реализации исходной (базовой) модели синтеза автоматов. При этом дело не в названиях выбранных инструментальных средств - Access, SQL, Visual Basic. Вместо Access может быть взята и другая инструментальная СУДЕ, обладающая как минимум указанными свойствами [33]. Тогда объем необходимых программных доработок оказывается приемлемым для создания экспертной системы синтеза автоматов малыми силами и в сжатые сроки.

Практическая значимость работы.

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

Результаты использованы в учебном процессе кафедры Компьютерных систем и информационной безопасности КГТУ им. А.Н. Туполева (КАИ).

На защиту выносится:

1. Разработка фреймово-продукционной модели синтеза автоматов.

2. Обоснование возможности погружения фреймовой модели в среду реляционной СУБД, на примере Microsoft Access.

3. Разработка языка присоединенных процедур.

4. Разработка прототипа (исследовательской версии) интерпретатора экспертной системы синтеза автоматов.

Апробация результатов работы.

Основные результаты работы докладывались и обсуждались на научно-технической конференции «IX Всероссийские Туполевские чтения студентов» (Казань, 2000 г.), Казанском городском семинаре «Методы моделирования» (Казань, 2001-2005 г.), Республиканской научно-практической конференции

Интеллектуальные системы и информационные технологии» (Казань, 2001 г.), XIII Международной конференции «Проблемы теоретической кибернетики» (Казань, 2002 г.), V Международной научно-практической конференции «Новые информационные технологии и системы» (Пенза, 2002 г.), Международной научно-практической конференции IEEE AIS'03 (Геленджик, 2003 г.).

Публикации.

Основное содержание диссертации опубликовано в 9 работах, включая 4 статьи [17, 18, 27, 28], 4 тезиса докладов [13, 14, 15, 16] и 1 компьютерный практикум [26].

Структура и объем диссертации.

Диссертационная работа состоит из введения, четырех глав и заключения. Она изложена на 101 странице, содержит 25 рисунков и 57 таблиц. Библиографический список включает 42 наименования.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Морозов, Андрей Владимирович

Основные результаты диссертационной работы:

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

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

3. Проведено погружение фреймово-продукционной модели в среду реляционной СУБД. Обоснован выбор СУБД Microsoft Access для реализации погружения. Показаны особенности представления таблиц-фреймов в виде таблиц базы данных. Рассмотрена взаимосвязь фреймов с помощью встроенных средств СУБД.

4. Разработан язык присоединенных процедур - язык арифметическо-логических выражений. Описаны основные части языка: переменные, константы, операции, выражения. Выделены два вида выражений: логические и арифметические. Представлены правила записи предложенных выражений, а также алгоритм их обработки.

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

Результаты диссертации использованы в учебном процессе кафедры Компьютерных систем и информационной безопасности КГТУ им. А.Н. Туполева (КАИ).

98

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат технических наук Морозов, Андрей Владимирович, 2006 год

1. Агибалов Г.П. Синтез автоматов по конечно-определенным словарным функциям // Алгоритмы решения задач дискретной математики. -Томск: Изд-во Том. ун-та, 1979. - С. 160-164.

2. Айзерман М.А., Гусев Л.А., Розоноэр Л.И. и др. Логика. Автоматы. Алгоритмы. -М.: Физматгиз, 1963.

3. Ангер С. Асинхронные последовательностные схемы. М.: Наука, 1977.

4. Базилевский Ю.Я. Вопросы теории временных логических функций // Вопросы теории математических машин. М.: Физматгиз, 1958.

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

6. Клини С. Представление событий в нервных сетях и конечных автоматах // Автоматы. М.: Иностр. лит., 1956.

7. Кобринский Н.Е., Трахтенброт Б.А. Введение в теорию конечных автоматов. -М.: Физматгиз, 1962.

8. Колдуэлл С. Логический синтез релейных устройств. М.: Иностр. лит., 1962.

9. Кузнецов О.П. Релейные устройства и конечные автоматы // Структурная теория релейных устройств. М.: Изд-во АН СССР, 1963.

10. Мелихов А.Н. Ориентированные графы и конечные автоматы. М.: Наука, 1971.

11. Минский М. Фреймы для представления знаний. М.: Энергия, 1979.

12. Моисил Гр.К. Алгебраическая теория дискретных автоматических устройств. М.: Иностр. лит., 1963.

13. Морозов А.В. Интерпретация языка спецификаций состояний при синтезе цифровых автоматов // IX Всероссийские Туполевские чтения студентов. Тезисы докладов. Казань: Изд-во Казан, гос. техн. ун-та, 2000.-Т. II.-С. 32.

14. Морозов А.В. К реализации фреймовой модели синтеза автоматов // Труды V Международной научно-практической конференции «Новые информационные технологии и системы». Пенза: ПТУ, 2002. - С. 162-164.

15. Морозов А.В. Моделирование процесса синтеза автоматов как задача искусственного интеллекта // Интеллектуальные системы и информационные технологии: Труды республиканской научно-практической конференции. Казань: Отечество, 2001. - С. 77-78.

16. Морозов А.В. О реализуемости фреймовой модели синтеза автоматов в инструментальной среде СУБД // Вестник КГТУ им. А.Н.Туполева. -Казань: Изд-во Казан, гос. техн. ун-та, 2003. №2. - С. 63-68.

17. Морозов А.В. Реализация системных процедур модели синтеза автоматов // Эволюционное моделирование. Казань: Из-во «ФЭН» («Наука»), 2004. - С. 288-296.

18. Нейман Дж фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971.

19. Попов Э.В. Экспертные системы. М.: Наука, 1987.

20. Представление и использование знаний / Под ред. X. Уэно., М. Исидзука. М.: Мир, 1989.

21. Райхлин В.А. К синтезу автомата по неформальному заданию // Кибернетика и системный анализ, 1994. № 4. - С. 29-41.

22. Райхлин В.А. Конструктивное моделирование систем. Казань: Изд-во ФЭН (Наука), 2005. - 304 с.

23. Райхлин В.А. Неформальные модели синтеза. Базовые понятия и принципы // Вестник КГТУ им. А.Н. Туполева. Казань: Изд-во Казан, гос. техн. ун-та, 2000. - № 3. - С. 53-58.

24. Райхлин В.А. Синтез цифровых автоматов в переходном режиме. -Казань: Изд-во Изд-во Казан, гос. техн. ун-та, 1998.

25. Райхлин В.А., Морозов А.В. Интерактивная система синтеза цифровых автоматов. Компьютерный практикум. Казань: АСО (КСЮИ), 2006. -36 с.

26. Райхлин В.А., Морозов А.В. Фреймово-продукционная модель синтеза автоматов // Вестник КГТУ им. А.Н. Туполева, 2001. № 3. - С. 5-13.

27. Райхлин В.А., Морозов А.В., Вершинин И.С, Абрамов Е.В. Интеллектуальные модели синтеза // Труды конференции IEEE AIS'03, CAD-2003. М.: Физматлит, 2003. - Т.2. - С. 158-171.

28. Спивак М.А. Алгоритмы абстрактного синтеза автоматов для расширенного языка регулярных выражений // Известия АН СССР. Техническая кибернетика, 1965. -№1.

29. Таль А.А. Анкетный язык и абстрактный синтез минимальных последовательных машин // Автоматика и телемеханика, 1964. № 6. -1965. -№3-4.

30. Тей А., Грибомон П., Луи Ж. и др. Логический подход к искусственному интеллекту. М.: Мир, 1990.

31. Тоффоли Т., Марголус Н. Машина клеточных автоматов. М.: Мир, 1991.-280 с.

32. Ульман Дж. Основы систем баз данных. М.: Финансы и статистика, 1983.-336 с.

33. Шалыто А.А. Автоматное проектирование программ. Алгоритмизация и программирование задач логического управления // Теория и системы управления, 2000. № 6. - С. 63-81.

34. Burks A.W., Copy J.M. The logical design of an idealized general-purpose computer. // J. Franclin Inst, 1956. V.261. - №3-4

35. Burks A.W., Wang H. The logic of automata. Univ. Michigan, Ann. Arbor, Mich. Eng. Res. Inst, 1956.

36. Burks A.W., Wright G.B. Theory of logical nets. // Proc. IRE. V.41. -1953.-№4.

37. Chebotarev A.N. Construction of an automaton from a formula of the monadic first-order theory of the natural numbers. // Kibernetika sistemny analiz, 2001. -№ 4. P. 91-106.

38. Chebotarev A.N. Synthesizing of the procedural representation of the automaton specified in the logical language L*.II // Kibernetika sistemny analiz, 1997.-№6.-P. 115-126.

39. Chebotarev A.N. Syntnesis of the procedural representation of an automaton specified in the logical language L*.I // Kibernetika sistemny analiz, 1997. -№4.-P. 60-74.

40. Church A. Application of recursive arithmetic in the theory of computers and automata. Univ. Michigan, 1958.

41. Huffman D.A. The synthesis of sequential switching circuits // J. Franklin Inst, 1954.-V. 257.-№3-4.