Введение к работе
Актуальность проблемы. В настоящее время одним из основных препятствий на пути дальнейшего развития информационной революции является низкая производительность процесса создания программного обеспечения по сравнению с разработкой технических средств. Программирование по-прежнему остается искусством. Для индустриализации этого вида деятельности необходимо обеспечить непосредственное участие компьютеров в процессе создания новых программ, что совершенно не возможно без высокой степени автоматизации программирования и создания легко доступных для автоматической обработки банков ранее созданных программных продуктов. В свою очередь, автоматизация программирования невозможна без создания математической модели программного продукта или его формальной спецификации.
История спецификации вычислений началась задолго до появления первых ЭВМ с теоретических работ по вычислительным моделям и теории алгоритмов - машина А.Тьюринга, система продукций А.Поста, лямбда-исчисление А.Черча, нормальные алгорифмы А.А.Маркова, машины А.Н.Колмогорова. Эти и другие работы заложили основы современной теории программирования, но не смогли выполнить роль спецификации вычислений в практике программирования. Эту функцию выполняют универсальные языки программирования высокого уровня такие как ПЛ/І, АДА, СМОЛТОК и др. Однако, как показала практика, эти языки плохо приспособлены для роли базовой математической модели вычислений, поскольку они перегружены деталями описания конкретных алгоритмов и сильно привязаны к традиционной фон-неймановской архитектуре ЭВМ.
Примером удачного компромисса между классическими моделями вычислений и алгоритмическими языками программирования являются функциональное и логическое программирование. Языки функционального программирования (ЛИСП Дж.Маккарти, РБЇАЛ В.Ф.Турчина) реализуют идеи А.Черча и Э.Поста. Логическое программирование реализует спецификацию задач на базе математической логики.
Одновременно, в рамках системного анализа разрабатывались собственные средства описания сложных систем с широким привлечением графов - агрегативше модели Н.П.Бусленко, системно-динамические диаграммы Дк.Форрестера, сети Петря и др. Эти общесистемные средства успешно использовались для спецификации программных систем определенного типа. Перспективность исполь-
І-І
_2 -
зования графов для спецификации вычислений доказана при разработке операторных схем Ю.И.Янова, графов потока данных, вычислительной модели Э.Х.Тыугу. В настоящее время наблюдается значительное расширение области применения графовых моделей в информатике: визуальное программирование, описание структуры данных (сетевая модель данных, ЕН-модель П.Чена), описание диалога графами переходов, представление знаний семантическими сетями.
Перечислешше выше разработки образуют мощный инструментарий для спецификации отдельных задач информатики. Однако индустриализация программирования невозможна без создания достаточно универсального аппарата, способного обеспечить спецификацию проектов программных систем, произвволышх вычислений, диалога, экспертных знаний, формальный анализ программных систем, их преобразование, поддеркку всего жизненного цикла. О необходимости такого аппарата неоднократно писали ведущие ученые (например, алгебра программ Дж.Бекуса и В.М.Глушкова, "лексикон программиста" А.П.Ершова), но эта проблема по-прекнему далека от решения.
Особенно актуальной проблема разработки универсальной спецификации компьютерных систем становится с широким распространением терминальных станций и персональных компьютеров. В втих условиях основной формой реализации программных слетом становятся интегрированные человеко-машинные системы (ЧМС), которые объединяют в единое целое различные подсистемы, традиционно использующие различные методы спецификации (системы моделирования, распределенные системы, системы реального времени, системы искусственного интеллекта, человеко-машинные интерфейсы). Разработке формальной спецификации именно таких систем и посвящена диссертация.
Цель работы. Разработка формальной спецификации интегрированных человеко-машинных систем и методов решения с помощью этой спецификации основных задач, решаемых компьютерными системами - произвольные вычисления, диалог, синтез программ, распределенная обработка информации в реальном времени, представление и обработка знаний.
Методы исследования. В исследовании использованы методы теории графов, математической логики, математического программирования, теории рекурсивных функций, функционального программирования и представления знаний.
Свлзь с плановими работами. Диссертационная работа выполнена п соответствии с планом научно-исследовательских работ ВИШОИ АН СССР в рамквх теми "Компыотарноэ моделирование" (N гос. регистрации 0І89О023505).
Научная новизна. В диссертации разработана новая формальная спецификация человеко-машинных систем, обобщающая преимущества функционального программирования и сетевого представления систем обработки информации, - функциональные сети (ФС) с памятью. Проведена классификация ФС-моделей, определена их семантике.
Исследованы особенности управляемой запросами и дашшми прямой интерпретации ФС. Разработан алгоритм управляемой запросами интерпретации рекурсивных ФС, реализаций управление взаимодействием сопрограмм.
Разработана новая функциональная модель интерактивных систем, обеспечивающая одновременную автоматизацию диалога и вичислений. С помощью построенного формального критерия эквивалентности ЧМС доказано преимущество функциональной модели диалога по сравнению с традиционной процедурной моделью.
Для ранее не рассматривавшихся типов систем, характеризуйтеся сочетанием переменной структуры и произвольными обратными связями, сформулирована задача синтеза оптималышх вычислительных алгоритмов и разработаны методы ее решения.
На базе ФС-модели разработан новый метод проектирования оптимальных распределенных вычислительных систем, позволяиций объодишть в одной задаче проектирование технических средств и структуры программного обеспечения.
На ФС-модели сформулирована задача оптимизации диалога для интерактивных задач. Разработаны методы решения этой задачи. Разработан алгоритм синтеза интерактивного решения на И/ИЛИ ги-порграфе поиска решений со взаимно зависимыми гипотезами. Установлено соответствие меаду ФС-моделью и этим гиперграфом. Полученные решения использованы для интеллектуализации человеко-машинного интерфейса.
Для спецификации систем искусственного интеллекта разработаны метода использования ФС-модели для представления знаний, эквивалентные традиционным системам продукций и фреймам. Показана возможность спецификации гетерогенных экспертных систем с
ПОМОЩЬЮ ФС-М0Д9Л9Й.
Совокушюсть полученных результатов можно рассматривать как теоретическое обобщение и решение крупной научной проблемы формальной спецификации интегрированных человеко-машинных систем.
Научная значимость работы. Разработанная в диссертации ФС-модель является обобщением ряда традиционных моделей вычислений и современных концепций программирования (сопрограммы, абстрактный тип данных, объектно-ориентированный подход). ФС-модель и разработанные алгоритмы ее интерпретации образуют аппарат, обеспечивающий формальную спецификацию, анализ и преобразование программных систем различного назначения, что позволяет рассматривать эти системы в качестве объектов научного исследования.
Практическая ценность работы. ФС-модель, реализованная в виде аннотированной функциональной сети, может использоваться в качестве стандарта при создании универсальных информационных банков, обеспечивающих возможности традиционных пакетов прикладных программ, систем моделирования, банков данных и банков знаний. Разработанные в диссертации конкретные алгоритмы интерпретации ФС-модели могут непосредственно использоваться при создании соответствующих интерпретаторов, трансляторов, машин логического вывода, человеко-машинных интерфейсов.
Апробация работы. Результаты диссертации докладывались на семинаре Национального исследовательского института информации и автоматики (1980 г., Франция); на заседании комиссии по применению ЭВМ в процессах управления координационного комитета АН СССР по вычислительной технике (1980 г, Цахкадзор, Армянская ССР); на международном совещании по проблемам системного обеспечения принятия решений (1980, IIASA, Лаксенбург, Австрия); на 2-й Всесоюзной конференции по проблемам управления развитием систем (Курс-2, Таллинн, 1982); на Всесоюзной конференции "Методы трансляции и конструирования программ" (Новосибирск, 1988); на Всесоюзной конференции "Теория, методология и практика системных исследований (Москва, 1984); на 10-м Всесоюзном совещании по проблемам управления (Алма-Ата, 1986); на Международной рабочей конференции "Реализм моделей" (Бад Хоннеф, ФРГ, 1982); на Всесоюзной конференции "Математическое моделирование. Нелинейные проблемы и вычислительная математика" (Звенигород, 1Э88); на 2-м советско-американском симпозиуме по общей теории
- б -
систем, кибернетике и управлению (Таллинн, 1988); на постоянно действующем научно-техническом семинаре ВНТО приборостроителей им. 0.И,Вавилова "Современная технология производства приборов, средств автоматизации и систем управления" (Ленинград, 1990).
Публикации. По теме диссертации опубликованы 22 научные работы. В работах, написанных в соавторства, В.В.Юрчвнко принадлежат все результаты, касающиеся модели функциональных сетей, алгоритмов ее интерпретации, методологии и технологии ее использования .
Структура диссертации. Диссертация состоит из введения, 7 глав, заключения, списка литературы из 106 наименований, 3-х приложений. Объем основного текста диссертации 286 страниц.
