Введение к работе
Актуальность темы исследования. Разработка компьютерных решателей математических задач является важным направлением в математической кибернетике и теории интеллектуальных систем. Такие решатели составляют основу самых различных экспертных и интеллектуальных систем, используемых для автоматизации инженерных расчетов в технике, управления сложными технологическими и динамическими процессами, технической диагностики, обработки информации при проведении научных исследований, а также систем компьютерного обучения [3, 24, 25, 26, 39, 40, 41, 42, 43]. Создание решателей стимулировало проведение как исследований в конкретных предметных областях (компьютерная алгебра, вычислительная геометрия, дискретная оптимизация и др.), ориентированных на развитие используемого при решении задач математического аппарата, так и исследований математических моделей процесса решения задач в целом [1, 13, 14, 15, 17, 19, 32].
Можно выделить три основных подхода, получивших наиболее широкое распространение при разработке математических моделей процессов решения задач. Первый из этих подходов, лежащий в основе организации систем компьютерной алгебры [5, 16], связан с рассмотрением древовидной классификации типов поддающихся алгоритмизации задач в соответствующей предметной области и создании библиотеки процедур для решения таких задач. Процесс решения представляется здесь как последовательное применение процедуры грамматического разбора формулировки задачи, определение ее типа согласно древовидной классификации и применение соответствующего найденному типу алгоритма. Используемые в системе процедуры представляют собой, по существу, блок-схемного типа иерархические конструкции, составляющие готовый план действий и гарантирующие получение ответа для любой задачи из явным образом
формулируемого класса допустимых задач. Вместе с тем, для математики характерна ситуация, когда многообразие решаемых человеком задач из некоторого ее раздела не охватывается сколь-нибудь обозримой совокупностью готовых планов решения, а требует проведения планирования непосредственно в процессе решения. Эта ситуация особенно наглядно демонстрируется на примере таких базисных разделов математики, как элементарная алгебра, тригонометрия и элементарная геометрия, где системы указанного типа оказываются весьма малоэффективны. Так, широко распространенные системы компьютерной алгебры DERIVE, MATHEMATICA, MATHCAD, AXIOM, располагая мощной базой процедур для специализированных (в основном полиномиальных) символьных вычислений, решают лишь незначительную долю неполиномиальных уравнений и неравенств из стандартных сборников задач по элементарной математике.
Второй подход, развиваемый при математическом моделировании процессов решения задач, примыкает к исследованиям по математической логике [6, 7, 22, 23, 33, 35, 36, 38] и основан на применении баз знаний декларативного (теоремного либо продукционного) характера. Планирование решения задачи осуществляется здесь алгоритмическим ядром, при разработке которого учитываются лишь самые общие особенности предметной области (как правило, заложенные в эвристические оценочные функции). Объем знаний, используемых при планировании, оказывается в таких системах несопоставимо малым в сравнении с объемом основной, декларативной, базы знаний, а планирующее ядро превращается, по существу, всего лишь в оболочку логической компоненты системы. Обширный перечень систем, основанных на указанном принципе планирования, можно найти, например, в работах [12, 18, 26, 28, 29, 34, 36, 37, 41]. Как следствие недостаточной адаптации алгоритмической, планирующей составляющей механизмов логического вывода к предметной области, системы
данного типа демонстрируют плохо управляемое поведение, порождая экспоненциально ветвящиеся деревья прямого либо обратного вывода. Область применимости указанного подхода ограничивается, таким образом, лишь теми сравнительно простыми задачами, решение которых возможно получить на основе практически приемлемого перебора.
В настоящей работе развивается третий подход к моделированию процессов решения задач, основанный на создании таких крупномасштабных баз алгоритмов планирования, которые позволили бы за счет детального анализа конкретной ситуации практически исключить из процесса решения явление перебора и сделать этот процесс "квазиградиентным". Логическая составляющая извлекаемой из предметной области информации оказывается здесь рассредоточена в алгоритмических конструкциях основной, планирующей, базы знаний. Продиктованное особенностями предметной области качественное разнообразие таких конструкций делает нецелесообразной разработку сколь-нибудь развитого управляющего ядра системы (как это имело место при втором подходе), ограничивая роль этого ядра лишь организацией сканирования задачи для активизации содержащихся в базе знаний алгоритмов планирования. Фактически, указанное ядро даже не осуществляет сколь-нибудь содержательного отбора либо принятия решений, выполняемых исключительно самими алгоритмами планирования.
В то время как первый и второй подходы основаны на исследованиях по математической формализации, соответственно, алгоритмов и теорем, накопленных в предметной области, третий подход инициирует исследования по математической формализации приемов решения задач. Используемое в математической практике понятие приема приблизительно соответствует алгоритму планирования, определяющему один или несколько ближайших шагов решения задачи для
улучшения сложностной оценки ситуации. Эта оценка определяется, вообще говоря, не только задачей, но и используемой для решения базой приемов, и явное ее нахождение представляется чрезвычайно затруднительным. Фактически реализуется лишь эвристическая аппроксимация такой оценки, заложенная в решающие правила приема и формирующаяся в процессе итеративной адаптации.
Как и алгоритмы решения задач, приемы имеют программную реализацию, и оптимальное их проектирование может быть отнесено к области теории сложности вычислений. Вместе с тем, здесь возникает ряд принципиальных отличий, существенно изменяющих подход к математической постановке задачи на синтез приема от подхода к постановке задачи на синтез алгоритма. Задание на синтез алгоритма имеет замкнутый характер, сводясь к явной формулировке того класса задач, которые он должен решать, и критерия оптимизации. Это позволяет рассматривать различные задачи на синтез алгоритмов обособленным друг от друга образом. В то же время, приемы представляют собой лишь внутренние, промежуточные средства решения задачи, и какая-либо обособленная их качественная либо количественная характеризация без учета всей используемой базы приемов является невозможной. Это обстоятельство существенным образом затормозило процесс формализации используемых в математике приемов решения задач, и накопленное в ней многообразие таких приемов представлено преимущественно в неявной форме, посредством тех учебных задач, где они применяются. Хотя необходимость уделе-кия более пристального внимания формализации приемов ясно осознавалась математиками (см., например, [30, 31]), адекватное их воспроизведение требовало разработки действующих моделей решателей задач и было невозможно вне компьютерного эксперимента. Развитие логического подхода также привело к осознанию необходимости глубокой алгоритмизации механизмов логического вывода.
Здесь возник целый ряд работ [2, 8, 9, 10, 15, 17, 26 и др.], закладывающих основы такой алгоритмизации в различных предметных областях. Так как синтез алгоритмов планирования решения задач является в сильной степени предметно-ориентированным, создание высокоэффективных решателей математических задач предполагает систематическую проработку основных разделов математики, и указанные исследования представляют собой лишь первые шаги в этом направлении. В настоящей работе предпринята попытка формализации приемов решения задач, накопленных в таких разделах математики, как элементарная алгебра, тригонометрия и дифференциальное исчисление. Результатом явилась компьютерная система решения математических задач в перечисленных разделах, демонстрирующая достаточно высокий (80-90%) процент решаемых задач средней сложности и целенаправленное поведение, практически лишенное элементов перебора. Система является обучаемой и допускает развитие на другие разделы математики; быстродействие ее в десятки раз превосходит скорость решения задач человеком.
Цель работы. Разработка математической модели целенаправленных ("квазиградиентных") процессов решения математических задач, основанных на применении крупномасштабных баз алгоритмов планирования. Создание языка высокого уровня, ориентированного на ускоренную запись таких алгоритмов планирования (приемов решения задач). Формализация в рамках предложенной модели многообразия приемов решения задач из таких базисных разделов математики, как элементарная алгебра, тригонометрия и дифференциальное исчисление. Разработка общей методики обучения компьютерных решателей математических задач, ориентированного на придание их поведению высокой степени целенаправленности.
Методы исследований. В работе используются методы математической логики, дискретной математики, математической кибернетики и теории интеллектуальных систем.
Научная новизна. Все основные результаты диссертации являются новыми и опубликованы в работах автора. В диссертации предлагается математическая модель системы автоматического решения задач, планирующей свои действия в процессе решения задачи на основе энциклопедическим образом организованной базы процедур ("приемов"), осуществляющих преобразования квазиградиентного характера. Создан алгоритмический язык высокого уровня для записи приемов, ориентированный на компактную логическую формулировку сложных структурных образов. Разработан интерфейс обучения системы, позволяющий выполнять трассировку процесса решения задачи на семантическом уровне и осуществлять необходимую коррекцию программ приемов в интенсивном диалоговом режиме. Реализован процесс обучения системы решению задач по основным разделам элементарной алгебры, тригонометрии и дифференциальному исчислению. Создана эффективная версия решателя для этих разделов, обеспечивающая высокий (порядка 80-90%) процент решаемых задач и позволяющая прослеживать последовательность рассуждений, приводящих к ответу. Разработана методика обучения системы, обеспечивающая последовательные приближения ее поведения к целенаправленной деятельности человека и позволившая добиться беспереборного, практически "линейного" характера действий решателя.
Практическая и теоретическая ценность. В диссертации развивается новое научное направление, связанное с моделированием процессов решения математических задач и допускающее распространение на широкий класс хорошо и слабо формализованных задач. Результаты проведенных исследований могут найти применение при разработке компьютерных решателей математических задач
для символьных инженерных расчетов, проведения теоретических исследований в опирающихся на математический аппарат разделах естествознания, а также при создании компьютерных обучающих систем. Предложенные в диссертации общая схема процесса решения задач с формированием панов действий непосредственно при решении и методика обучения решателя, позволяющая преодолевать эффект перебора, могут найти применение также в целом ряде других важных прикладных направлений, таких, как анализ изображений, восприятие естественного языка, автоматизация проектирования, разработка интеллектуальных систем управления, техническая диагностика и др.
Апробация работы. Результаты диссертации излагались на Международной конференции "Интеллектуальные системы" (Крас-новидово, 1990 и 1992 г.г.), на Всероссийском семинаре по дискретной математике (Москва, 1993 г.), на Международной конференции по прикладной математике (Мадрид, 1993 г.), на Общемосковском семинаре по программированию под руководством чл.-корр. РАН Л.Н. Королева (1993 г.); на Общемосковском семинаре по искусственному интеллекту под руководством акад. АТН РФ В.Б. Кудрявцева, чл.-корр. АТН РФ А.В. Чечкина и проф. М.Г. Мальковского (1993 г.); на семинарах по интеллектуальным системам и теории автоматов под руководством акад. АТН РФ В.Б. Кудрявцева; на семинаре по математической теории управляющих систем под руководством чл.-корр. РАН СВ. Яблонского (1992 г.) и на семинаре по распознаванию образов под руководством акад. РАН Ю.И. Журавлева. Компьютерная система решения математических задач, описываемая в диссертации, демонстрировалась на Всемирной выставке вычислительной техники и программных продуктов СеВГГ-92 в г. Ганновере (Германия).
Публикации. Основные результаты диссертации опубликованы в работах автора [1-6], список которых приводится в конце автореферата. Среди них нет работ, написанных в соавторстве.
Структура и объем работы. Диссертация состоит из введения, шести глав и списка литературы. Первая глава разбита на 3 параграфа, вторая - на 3, третья - на 2, четвертая - на 4, пятая - на 3 и шестая - на 2. Объем работы 304 страницы. Список литературы содержит 49 наименований.