автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:О моделировании процессов решения математических задач

р v б оа

- 2 а^в российская академия наук

вычислительный центр

На правах рукописи УДК 519.711

подколзин александр сергеевич

о моделировании процессов решения математических задач

Специальность: 05.13.16*- применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по физико-математическим наукам)

автореферат диссертации на соискание ученой степени доктора физико-математических наук

Москва-1994

Работа выполнена на механико-математическом факультете МГУ.

Официальные оппоненты — академик РАН, доктор

— физико-математических наук, профессор Ю.Л. Ершов

1 — чл.-корр. АН Украины, доктор

физико-математических наук, профессор В.Н. Редько

— доктор физико-математических наук, профессор Д.В. Михалев

Ведущая организация — Саратовский Гос. Университет

им. Н.Г. Чернышевского

Защита диссертации состоится в^Лъ?^ туг.

часов ОН мин. на заседании специализированного совета Д002.32.06 при Вычислительном центре РАН по адресу: 117967, Москва ГСП-1, ул. Вавилова, 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке МИ РАН.

Автореферат разослан

-¿4ту.

Ученый секретарь специализированного Совета Д002.32.06 при Вычислительном центре РАН

кандидат физико-математических наук С.М. Швартин.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. Разработка компьютерных решателей математических задач является важным направлением в математической кибернетике и теории интеллектуальных систем. Такие решатели составляют основу самых различных экспертных и интеллектуальных систем, используемых для автоматизации инженерных расчетов в технике, управления сложными технологическими и динамическими процессами, технической диагностики, обработки информации при проведении научных исследований, а также систем компьютерного обучения [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 г.), на Общемосковском семинаре по программированию под руководством чл.-корр. РАН JI.H. Королева (1993 г.); на Общемосковском семинаре по искусственному интеллекту под руководством акад. АТН РФ В.Б. Кудрявцева, чл.-корр. АТН РФ A.B. Чечкина и проф. М.Г. Мальковского (1993 г.); на семинарах по интеллектуальным системам и теории автоматов под руководством акад. АТН РФ В.Б. Кудрявцева; на семинаре по математической теории управляющих систем под руководством чл.-корр. РАН C.B. Яблонского (1992 г.) и на семинаре по распознаванию образов под руководством акад. РАН Ю.И. Журавлева. Компьютерная система решения математических задач, описываемая в диссертации, демонстрировалась на Всемирной выставке вычислительной техники и программных продуктов СеВ1Т-92 в г. Ганновере (Германия).

Публикации. Основные результаты диссертации опубликованы в работах автора [1-6], список которых приводится в конце автореферата. Среди них нет работ, написанных в соавторстве.

Структура и объем работы. Диссертация состоит из введения, шести глав и списка литературы. Первая глава разбита на 3 параграфа, вторая - на 3, третья - на 2, четвертая - на 4, пятая - на 3 и шестая - на 2. Объем работы 304 страницы. Список литературы содержит 49 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе излагается общая схема организации системы автоматического решения задач. Первый параграф этой главы посвящен описанию используемого во внутреннем представлении данных логического языка, а также принципов трансляции между внутренним и внешним представлениями данных. Возможность применения при реализации логического вывода таких развитых алгоритмических конструкций, какими являются приемы, значительно ослабляет требования к формализации логического языка, позволяет широко применять контекстно-определенную семантику языковых конструкций и расширять синтаксис языка по мере обучения системы. При определении синтаксиса языка используются алфавит /ь /г, • ■ • логических символов и алфавит Х\,Х2, ■ ■ ■ символов переменных. Синтаксические конструкции делятся на два класса — утверждения и выражения. Однобуквенные слова, составленные из элементов указанных алфавитов, объявляются выражениями; с каждым логическим

и

символом / связывается свое собственное правило образования новых утверждений либо выражений /(<1 . ..<„) из построенных ранее утверждений либо выражений <1 ...<„. Семантика терма /(<1.. .<„) также определяется независимым для каждого символа / образом, причем в особых случаях такое определение дается только в контексте вхождения данного терма в задачу и в нем могут содержаться указания на сквозную модификацию семантики других термов задачи. Фактически таким образом развивается открытая версия предикатного языка, приближенная к естественному математическому языку. Необходимость в интенсивной семантической трассировке при обучении системы потребовала использования, наряду с внутренним логическим представлением утверждений и выражений, внешнего их представления в общепринятой математической записи. Для обеспечения перехода от одного представления к другому были разработаны и реализованы соответствующие процедуры трансляции.

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

а) список утверждений /1,... , /„ , называемых посылками задачи и предполагающихся в процессе решения истинными.

б) набор (а1,... ,а„) целых неотрицательных весов посылок, используемых для переключения внимания и изначально равных 0.

в) набор (К 1,... ,Кп,Ко) , элементы К, которого суть наборы комментариев: при I > 0 — к посылке /,-, а при г = 0 — ко всему списку посылок. В виде комментариев регистрируется различная информация, накапливаемая при решении задачи и используемая для оценки целесообразности применения приемов (например, информация о ранее предпринимавшихся неудачных шагах, блокирующая их повторение).

Выделяются 4 типа задач: на доказательство, на описание, на преобразование и на исследование. Указанные выше компоненты а), б), в) являются общими для задач всех этих типов. Прочие компоненты задачи определяются в зависимости от ее типа следующим образом:

1) Задача на доказательство имеет условие /о (утверждение, которое требуется вывести из /1,... ,/„), вес условия ао и набор Ко комментариев к условию.

2) Задача на описание имеет список условий (/{,... , набор весов условий (а^,... , а^); набор (К[,... , К'т, К'0) комментариев к условиям; набор (сь... ,ср) целей и вспомогательны блок В, используемый для извлечения совместных следствий из условий и посылок. Класс утверждений, допустимых в качестве ответа задачи на описание, определяется в зависимости от набора ее целей; при этом некоторые из целей могут не накладывать явных ограничений на вид ответа, а лишь определять тенденции к оптимизации, учитываемые при решении задачи. Блок В представляет собой задачу на исследование (см. ниже), список посылок которой является объединением списков посылок и условий данной задачи на описание. Вывод следствий в блоке В используется как для нахождения неизвестных задачи, так и для получения информации эвристического характера.

3) Задача на преобразование имеет условие £ (преобразуемое выражение), вес условия ао и список комментариев Ко к условию, а также набор целей (сх,... ,ср), определяющих характер преобразований.

4) Задача на исследование, помимо компонент а)-в), имеет лишь список целей (с\,... , ср), определяющих направление логического вывода.

В третьем параграфе первой главы приводятся основные принципы организации базы приемов решателя и определяется процесс

сканирования задачи, лежащий в основе рабочего цикла системы. Для подавляющего большинства приемов локализация в задаче ситуаций, определяющих их срабатывание, начинается с обнаружения вхождения в посылку либо условие некоторого фиксированного для рассматриваемого приема логического символа. Это сделало целесообразным объединение всех приемов, соответствующих одному и тому же логическому символу /, в общую древовидную процедуру а для приемов, применение которых не связано с выделением в задаче вхождения какого-либо конкретного логического символа — в четыре процедуры Ох, Л2, Ач, £>4, соответственно типу решаемой задачи. В результате вся база приемов оказалась организована по принципу энциклопедии, а для поиска приемов предпринимается последовательный просмотр всех подряд логических символов условий и посылок задачи (сканирование задачи) и обращение для каждого такого вхождения символа / к процедуре £>/. Для отбора наиболее целесообразного приема вводится целочисленный текущий уровень {У сканирования: сначала предпринимается просмотр задачи при С/ = 0; если ни один из приемов не сработал, то сканирование повторяется при и = 1, и т. д. вплоть до некоторого максимального уровня игпат, устанавливаемого до начала решения задачи. При просмотре задачи отбрасываются все посылки и условия, вес которых не равен С/, причем временно исключенные таким образом из поля зрения утверждения, имеющие большой вес, при росте V снова попадают в поле зрения и для исключения эффекта "слепого пятна" подвергаются циклу локальных повторных просмотров, во время которых текущий уровень изменяется от О до £/. Если при просмотре терма для текущего уровня V не произошло срабатывание приема, то вес этого терма автоматически заменяется на С/ + 1; веса измененных после реализации приема

термов полагаются равными 0. Кроме того, предусмотрена возможность изменения весов приемами, используемая для избирательного переключения внимания.

Текущая ситуация, складывающаяся в процессе решения исходной задачи 2", описывается цепью задач Ъ = , , - - • »^лг, где

—вспомогательная задача, введенная для решения задачи (¿ = 1,1). При реализации приема может происходить как изменение текущей решаемой задачи ^дг, так и обращение к решению новых вспомогательных задач.

Вторая глава посвящена описанию алгоритмического языка высокого уровня, используемого для записи приемов. При обучении решателя стала очевидной необходимость создания специализированного языка для представления приемов, адаптированного к описанной схеме сканирования задачи и позволяющего быстро записывать сложные логические условия на рассматриваемую в приеме ситуацию. Задача заключалась в сохранении процедурного характера языка, дающего возможность применять широкий спектр традиционных алгоритмических конструкций, и одновременно в максимально возможном приближении его к логическому языку, обеспечивающему высокую скорость программирования, а также простоту чтения и изменения программ. В результате анализа первых программ приемов был выделен ряд необходимых языковых конструкций, на основе которых и возникла используемая версия языка. Подобно широко распространенному при проектировании интеллектуальных систем алгоритмическому языку ПРОЛОГ [3, 23], данный язык основан на реализации операторов в режиме перечисления значений выходных переменных. Это существенно сокращает число используемых в программе циклических конструкций и позволяет рассматривать кванторные записи условий

на ситуацию как разновидность алгоритмических проверочных операторов. Тенденция к алгоритмизации языка ПРОЛОГ за счет добавления реализуемых вне процесса логического вывода (" встроенных") предикатов здесь доведена до логического завершения - исключения лежащего в основе функционирования программ ПРОЛОГа механизма логического вывода, оказывающегося излишним при работе с объектами структурного уровня. Основу языка составляют около 200 реализуемых интерпретатором операторов и операторных выражений, ориентированных на работу с задачами и вспомогательными логико-сетевыми структурами данных. Атомарными типами данных являются логические символы, термы, списки, а также вхождения в термы и списки. Возможность непосредственной работы с вхождениями, отсутствовавшая в ПРОЛОГе, где базовым типом данных являются термы, оказывается чрезвычайно важной для быстрого сканирования сложных конструкций. Выполнение программы осуществляется интерпретатором, позволяющим также вести трассировку на уровне применяемых приемов, с выдачей на экран преобразуемых формул в стандартной математической записи, и таким образом получать не только ответ, но и полное решение задачи. В первом параграфе второй главы содержится описание основных структур данных языка, а также общая схема организации и функционирования программ приемов. Во втором параграфе перечисляются основные операторы языка, и в третьем- излагаются общие принципы программирования приемов, проиллюстрированные на примерах.

Описываемая в диссертации математическая модель была реализована в виде компьютерной системы решения задач, и в ее рамках осуществлена формализация приемов решения задач из следующих разделов элементарной математики и дифференциального исчисления:

а) Упрощение алгебраических выражений.

б) Алгебраические уравнения и неравенства с одной неизвестной.

в) Системы алгебраических уравнений.

г) Логарифмические и показательные уравнения, неравенства и системы.

д) Доказательство тождеств и неравенств.

е) Тригонометрические уравнения, системы уравнений и неравенства.

ж) Вычисление пределов и производных.

з) Применение пределов и производных для доказательства неравенств, нахождения локальных и глобальных экстремумов и определения интервалов монотонности.

Результаты проведенной при обучении системы формализации приемов решения задач из перечисленных разделов излагаются в главах З-б диссертации. Основной проблемой, решавшейся в процессе обучения системы, была проблема анализа средств, применяемых человеком для управления ходом логического вывода и придающих его поведению необходимую целенаправленность. Одним из центральных результатов проведенного компьютерного эксперимента явилось установление возможности обеспечения такой целенаправленности путем накопления в приеме базы логических описаний ситуаций, определяющих условия целесообразности его срабатывания. Описание ситуации формировалось в процессе обучения по принципу последовательных приближений: сначала возникало описание общего случая, затем формулировались исключения из этого случая, затем — исключения из исключений и т. д. При этом обнаружилось, что в подавляющем большинстве случаев возможно добиваться практически однозначного принятия решения на основе использования лишь логики описания ситуации, без привлечения каких-либо статистических

рассмотрений. Выяснилось, что эффект переключения на альтернативные пути решения задачи почти полностью устраняется по мере адаптации используемых в приемах описаний ситуаций, и поведение системы приобретает "линейный" характер: от формулировки задачи непосредственно к ответу. Таким образом, развиваемый подход действительно позволил преодолеть возникавшие в рамках второго подхода "переборные" трудности и обеспечить отсутствовавшее при первом подходе планирование действий непосредственно в процессе решения задачи.

В третьей главе диссертации описываются используемые в решателе приемы общелогического характера. Первый параграф этой главы посвящен рассмотрению приемов, закрепленных за логическими символами, обозначающими типы задач; второй параграф — рассмотрению приемов, связанных с логическими связками, кванторами и равенством. Четвертая глава посвящена изложению приемов, используемых для решения задач по элементарной алгебре. В первом параграфе данной главы рассматриваются приемы планирования действий при упрощении алгебраических выражений. Ввиду большого объема накопленного здесь материала подробно излагаются алгоритмические конструкции лишь нескольких типичных приемов и приводится краткое описание всего семейства используемых приемов. Этот стиль изложения сохраняется и в последующих разделах диссертации. Второй параграф четвертой главы посвящен описанию приемов, планирующих действия при решении уравнений и неравенств с одной неизвестной. Решение систем уравнений с несколькими неизвестными потребовало разработки общей схемы, принципиально отличающейся от случая одной неизвестной, и использованные здесь алгоритмические конструкции описываются в третьем параграфе. Наконец, в четвертом параграфе изложены приемы, применяемые решателем при доказательстве алгебраических тождеств и неравенств.

Пятая глава диссертации посвящена описанию приемов автоматического решения задач по тригонометрии. В первом параграфе этой главы рассматриваются приемы, возникающие в связи с упрощением и разложением на множители тригонометрических выражений; во втором параграфе — приемы автоматического решения уравнений и неравенств, и в третьем параграфе — приемы для задач с обратными тригонометрическими функциями. В последней, шестой, главе диссертации описано семейство приемов автоматического решения задач по дифференциальному исчислению. Первый параграф этой главы посвящен изложению используемых в решателе процедур вычисления пределов и производных; второй параграф — изложению приемов, позволяющих решателю проводить исследование функций с помощью пределов и производной (доказательство неравенств, локальные и глобальные экстремумы, интервалы монотонности).

При проработке учебного материала была развита методика синтеза приемов и обучения системы, основные положения которой могут быть сформулированы следующим образом:

1) Основным источником информации, используемым для извлечения приемов и обучения системы, являются учебные задачи. Решение каждой такой задачи анализируется и разбивается на фрагменты, требующие независимых актов планирования. В начале проработки предметной области эти действия выполняются вручную; по мере накопления базы приемов подключаются уже имеющиеся возможности решателя, самостоятельно реализующего первые шаги решения задачи вплоть до момента, когда оказывается необходимо вмешательство в его поведение. Для возможности быстрого восприятия, оценки и коррекции действий решателя создан специальный интерфейс обучения. Этот интерфейс выдает на экран последовательность предпринимаемых при решении задачи преобразований (изменение, удаление

либо добавление посылок и условий, обращение к решению вспомогательных задач и модификация управляющих комментариев) и обеспечивает на каждом шаге доступ к программе текущего реализуемого приема с возможностью просмотра значений программных переменных, а также доступ к основному стеку системы, хранящему предысторию текущей ситуации. Информация выводится на экран либо в стандартной математической записи, либо во внутреннем "скобочном" представлении, причем использование специального языка высокого уровня для записи приемов обеспечивает достаточно оперативное чтение и коррекцию программ приемов, придавая процессу обучения интенсивный диалоговый характер.

2) Для каждого выделенного фрагмента решения задачи создается заготовка приема, реализующего цепочку преобразований в рамках этого фрагмента. Такая заготовка включает в себя три основные компоненты: блок усмотрения ситуации, блок целевой фильтрации и блок реализации преобразований. Первая компонента осуществляет информационный поиск при сканировании задачи, выявляя те группы объектов, для которых в принципе возможно корректное применение определяемых приемом преобразований. Вторая компонента принимает решение о целесообразности или нецелесообразности применения приема в текущей ситуации, а в тех случаях, когда первая компонента оставляет определенные степени свободы для выбора конкретного варианта преобразования, — также отбор (синтез) наиболее целесообразного варианта. Наконец, третья компонента осуществляет фактическое изменение задачи в соответствии с выбранным планом преобразований. Программирование первых двух блоков состоит в последовательном перечислении логических условий на текущую ситуацию, накладываемых этими блоками; очередность расположения условий определяется соображениями ускорения отсева неприемлемых приемов, причем условия второго блока могут располагаться

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

3) Так как при сканировании задачи основная часть времени затрачивается не на реализацию приемов, а на их поиск, оптимизация алгоритмических конструкций направляется в первую очередь на уменьшение числа сканирований за счет максимально возможного удлинения цепочек преобразований, выполняемых отдельными приемами. Время обработки терма в режиме сканирования оказывается в среднем обратно пропорционально квадрату длины этого терма, и для ускорения решения задачи здесь используется вынесение обработки фрагментов больших термов во вспомогательные задачи, а также накопление групп приемов "эндшпильного" характера, редактирующих за один шаг громоздкую заготовку ответа (например, образовавшуюся при склейке ответов отдельно разобранных подслучаев). Обнаружилось, что выделение фрагментов преобразуемого терма лишь

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

4) Помимо логических условий, определяющих возможность и целесообразность применения преобразований, в приеме используются дополнительные логические фильтры, являющиеся следствиями из условий первых двух типов, но допускающие быструю проверку и располагаемые возможно ближе к началу программы приема для ускорения отсечения нереализуемых ситуаций. При сканировании задачи осуществляется интенсивная проверка условий, расположенных в начальных отрезках самых различных приемов базы знаний, и этот процесс можно рассматривать как модель работы подсознания, направленной на отбор очередного шага решения. Использование дополнительных логических фильтров может существенным образом уменьшить трудоемкость отбора, и разработка системы таких фильтров представляет собой, по существу, процесс оптимизации работы "подсознания" решателя.

5) При обосновании корректности выполняемых преобразований, а также при усмотрении той или иной стандартной ситуации, инициирующей анализ возможности применения приема, оказывается необходимо выполнять проверку истинности различных условий на рассматриваемые в задаче объекты. Такая проверка, в принципе, могла бы осуществляться за счет обращения к вспомогательной задаче на доказательство. Однако, в тех случаях, когда проверяемое условие не имеет места, система может "увязнуть" на попытках его доказательства с привлечением для этого все более сильных средств. Поэтому использование вспомогательной задачи для проверки условия

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

6) Принятие решения о целесообразности применения приема происходит с обязательным учетом взаимодействия приемов; во многих случаях прием блокируется не из-за того, что выполняемое им преобразование нецелесообразно, а потому, что в рассматриваемой ситуации более эффективной оказывается альтернативная цепочка преобразований. Здесь возникает сложная система ограничений и приоритетов, имеющих логический характер и ориентированных на выбор в каждом конкретном случае наиболее эффективного с точки зрения эксперта шага. Развитие этой системы происходит путем последовательных приближений при проработке учебного материала, причем основным средством упорядочения срабатывания приемов является шкала уровней их срабатывания. Важным этапом синтеза приема оказывается, таким образом, выбор допустимых для его срабатывания значений текущего уровня и формулировка условий срабатывания на каждом из этих уровней.

7) В предметной области могут выделяться группы понятий, обладающих аналогичными свойствами и похожими приемами решения задач. Преодоление дублирования, возникающего в программах

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

8) Помимо вспомогательных процедур, во многих случаях оказываются необходимы также вспомогательные базы знаний, используемые приемами. Такие базы знаний организуются по объектно-ориентированному принципу, когда для обработки однотипных запросов служит семейство процедур, закрепленных за различными логическими символами. В результате прием может предпринимать самостоятельное сканирование тех или иных фрагментов задачи, с обращением для текущего просматриваемого символа к соответствующей процедуре базы знаний. Использование такого рода конструкций оказывается особенно эффективным в тех случаях, когда принятие решения о целесообразности применения приема на основе одних лишь общих соображений затруднительно.

9) Для представления информации, возникающей при решении задачи, используется смешанная логико-сетевая структура данных. Необходимость выработки планов преобразований приводит к применению процедуры последовательного просмотра встречающихся в задаче понятий, и на этом этапе оказывается целесообразно логическое представление информации. Вместе с тем, после фиксации текущей точки в сканируемой задаче реализуется быстрый поиск различных связанных с ней объектов, и здесь уже необходимым оказывается применение сетевого представления данных. Формирование и модификация в процессе решения задачи сетевого представления информации

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

Анализ применяемой методики обучения системы, а также классификация типов и источников компонент накопленных в системе приемов, могут позволить перейти к разработке самообучающихся версий решателя. Обучение системы представляет собой процесс последовательных коррекций, основанных на решении потока задач, формулируемых в контексте текущего состояния базы приемов и связанных с объектами структурного характера. Автоматизация решения таких задач на основе уже развитой техники обучения решателя могла бы стать первым шагом на пути к созданию эффективных механизмов самообучения.

Основные результаты диссертации могут быть сформулированы следующим образом:

1) Разработана математическая модель системы автоматического решения задач, планирующей свои действия в процессе решения задачи на основе энциклопедическим образом организованной базы процедур ("приемов"), осуществляющих преобразования квазиградиентного характера.

2) Создан алгоритмический язык высокого уровня для записи приемов, ориентированный на компактную логическую формулировку сложных структурных образов.

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

4) Реализован процесс обучения системы решению задач по основным разделам элементарной алгебры, тригонометрии и дифференциального исчисления. Создана эффективная версия решателя

для этих разделов, обеспечивающая высокий (порядка 80-90%) процент решаемых задач средней сложности и позволяющая прослеживать последовательность рассуждений, приводящих к ответу.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Подколзин А.С. Об организации баз знаний, ориентированных на автоматическое решение задач // Дискретная математика. 1991. Т. 3. Вып. 3. С. 13-30.

2. Подколзин А.С. Компьютерный решатель математических задач // ДАН РФ. 1994. Т. 335. N 4.

3. Подколзин А.С. Система автоматического решения задач по элементарной алгебре // Дискретная математика. 1994. T-C.Bbin.4.

4. Подколзин А.С. О разработке процедур автоматического решения задач // Интеллектуальные системы. 1994. Т. 1. Вып. 1.

5. Podkolzin A.S. Computer solver of mathemaiical problems // Resúmenes de las conferencias plenarias, XIII C.E.D.Y.A., III Congreso de matematica aplicada, Universidad Politécnica de Madrid, 1993.

6. Подколзин А.С. Принципы синтеза приемов автоматического решения задач по тригонометрии и дифференциальному исчислению. Изд-во МГУ, 1994.

СПИСОК ЛИТЕРАТУРЫ

1. Бенерджи Р. Теория решения задач. М., Мир, 1972.

2. Бисон М. Дж. Доказательство программ и программирование доказательств // Кибернетический сборник. 1989. Вып. 26. С. 173207.

3. Богомолов A.M., Сперанский Д. В. Аналитические методы в задачах контроля и анализа дискретных устройств // Изд-во СГУ, 1986. 240с.

4. Братко Дж. Программирование на языке ПРОЛОГ для искусственного интеллекта. М., Мир, 1990. 559 с.

5. Бухбергер Б., Калме Ж., Калтофен Э. и др. Компьютерная алгебра: символьные и алгебраические вычисления. М., Мир, 1986. 391 с.

6. Ван Хао. На пути к машинной математике // Кибернетический сборник. 1963. Вып. 5. ИЛ. С. 114-165.

7. Ван Хао. Формализация и автоматическое доказательство теорем // Кибернетический сборник. М., Мир, 1970. Вып. 7, С. 180193.

8. Васильев С.Н. К автоматизации вывода теорем с аналогами функций Ляпунова и морфизмов // Computers and Artificial Intelligence. 1982. V. 1. N 6. P. 517-538.

9. Васильев С.Н. Алгоритмы вывода теорем с функциями сравнения / / Вопросы кибернетики: Неклассические логики и их применения. М., Изд-во ВИНИТИ, 1982. С. 54-74.

10. Vassilyev S.N., Martyanov V.I., Matrosov V.M. Computer Methods of theorem synthesis and proving // Proc. 8-th Int.Cong, of logic, methodology and philosophy of science. M. 1987. V 1.

11. Vassilyev S.N. Machine synthesis of mathematical theorems // J. Logic Programming, 1990. V. 9. N 2&3. P. 235-266.

12. Гелернтер Г. Реализация машины, доказывающей геометрические теоремы / В сб. "Вычислительные машины и мышление". М., Мир, 1967. С. 145-164.

13. Глушков В.М., Капитонова Ю.В. Автоматизация поиска доказательств теорем и интеллектуальные машины // Кибернетика, 1972. N 5. С. 2-5.

14. Глушков В.М. Машина доказывает. М., Знание, 1981. 63 с.

15. Гончаров С.С., Свириденко Д.Н. Е-программирование / В сб. "Логико-математические основы проблемы МОЗ". Новосибирск, ИМ СО АН СССР, 1985. Вып. 107: Вычислительные системы. С. 3-29.

16. Дэвенпорт Дж. и др. Компьютерная алгебра: системы и алгоритмы вычислений. М., Мир, 1991. 350 с.

17. Ершов Ю.Л. Е-определимость в допустимых множествах // ДАН СССР, 1985 Т. 285. N 4. С. 792-793.

18. Ефимов Е.И. Решатели интеллектуальных задач. М., Наука, 1982. 316 с.

19. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания и классификации ]/ Проблемы кибернетики. М., "Наука", 1978. Вып. 33. С. 5-68.

20. Капитонова Ю.В., Летичевский A.A. О некоторых идеях формирования математического аппарата кибернетики в работах В.М. Глушкова // Кибернетика, 1982. N 6. С. 1-5.

21. Капитонова Ю.В., Вершинин К.П., Дегтярев А.И. и др. О системе обработки математических текстов // Кибернетика, 1979. N2. С. 48.

22. Ковальски Р., Хайс П. Дж. Семантические деревья в автоматическом поиске доказательства // Кибернетический сборник, М., Мир, 1972. Вып. 9. С. 66-83.

23. Kowalski R.A. Logic for Problem Solving Elsevier-North. Holland, New York, 1979.

24. Краснощекое П.С., Петров A.A., Федоров B.B. Информатика и проектирование. М., "Знание", 1986., 46 с.

25. Краснощекое П.С., Петров A.A. Принципы построения моделей. М., МГУ, 1983., 264с.

26. Лорьер Ж.-Л. Системы искусственного интеллекта. М., Мир, 1991. 568 с.

27. Малпас Дж. Реляционный язык ПРОЛОГ и его применение. М., "Наука", 1990. 463 с.

28. Нильсон Дж. Принципы искусственного интеллекта. М., Радио и связь, 1985. 373 с.

29. Ньюэлл А., Шоу Дж., Саймон Г. Эмпирические исследования машины "Логик-Теоретик" // В сб. "Вычислительные машины и мышление". М., Мир, 1967.

30. Пойа Д. Математика и правдоподобные рассуждения. М., "Наука", 1975., 464с.

31. Пойа Д. Математическое открытие. М., "Наука", 1976. 448 с.

32. Поспелов Д.А. Моделирование рассуждений. М., Радио и связь, 1989. 182 с.

33. Правиц Д. Достижения и проблемы в развитии процедур механического доказательства [/ Кибернетический сборник. Вып. 9, М., Мир, 1972. С. 52-65.

34. Слейгл Дж. Искусственный интеллект. М., Мир, 1973. 319 с.

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

36. Тыугу Э.Х. Концептуальное программирование. М., "Наука", 1984.

37. ХантЭ. Искусственный интеллект. М., Мир, 1978. 558 с.

38. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М., "Наука", 1983.

39. Автоматизированное проектирование систем управления. М., "Машиностроение", 1989. 343 с.

40. Диалоговые системы схемотехнического проектирования. М., "Радио и связь", 1988. 285 с.