Компьютерный решатель задач

Главное изображение:

Название:

Краткое описание:

Компьютерный решатель задач – произвольная компьютерная программа, предназначенная для решения задач определенного типа.

Автор:

Статус:

Черновик Публикация Архив

<p><strong>Компьютерный решатель задач</strong> – произвольная компьютерная программа, предназначенная для решения задач определенного типа. Однако, на практике этот термин употребляют лишь в тех случаях, когда для рассматриваемых задач отсутствует простой общий алгоритм, и приходится использовать эвристические методы решения. Например, такая ситуация складывается при решении школьных задач по <a href="/enc/ru/encyclopedia:0152">элементарным</a> <a href="/enc/ru/encyclopedia:0161">алгебре</a> и <a href="/enc/ru/encyclopedia:0130548">геометрии</a>, при решении игровых задач, при решении задач на понимание текстов, при анализе изображений, и т.п. Можно выделить два основных подхода, применяемых для разработки компьютерных решателей. Первый из них связан с построением эвристического алгоритма на основе общих теоретических соображений, второй – с моделированием последовательности рассуждений человека.</p> <p>Первый подход позволяет создавать эффективные решатели лишь для сравнительно узких классов задач. В основном, эти классы определяются наличием в теории подходящих алгоритмов. Попытки сколь-нибудь расширить класс допустимых задач обычно наталкиваются на существенный перебор, который удается завершить лишь в простейших случаях.</p> <p>Примером данного подхода являются компьютерные решатели, основанные на методах компьютерной алгебры (Maple, Mathematica и др.). Они с легкостью решают простые стандартные "школьные" уравнения, сводя их к отысканию корней многочленов и используя методы высшей алгебры. Однако, даже небольшое отклонение от стандартов этих методов (вполне "стандартное" с точки зрения <a href="/enc/ru/encyclopedia:0130561">школьника</a>) ставит данные системы в тупик. Системы могут только выдавать ответ и не предлагают какую-либо понятную школьнику цепочку приводящих к нему выкладок.</p> <p>Хотя во многих важных разделах и были созданы достаточно эффективные решатели задач первого типа (например, в шахматах), их дальнейшее развитие и обучение приходится выполнять вручную, так как оно связано с развитием того теоретического базиса, на котором основана их алгоритмика. Создание самообучающейся интеллектуальной системы на данном направлении представляется проблематичным.</p> <p>Второй подход основан на моделировании цепочек рассуждений человека, решающего задачи. Фактически, процесс создания решателя здесь является процессом его обучения на примерах и не требует предварительной разработки каких-либо общих алгоитмов решения задач. Такой процесс, в самых общих чертах, можно представить происходящим по следующей схеме.</p> <p>Рассматривается некоторая обучающая последовательность задач, решение которых известно разработчику. Предпринимается анализ траектории решения очередной задачи из выбранной последовательности. Если эта задача не представляет собой простейший тест, для которого имеется заранее известный стандартный план действий, то процесс ее решения складывается из отдельных этапов, состоящих из локального планирования и реализации выработанного плана действий. Каждый такой этап локального планирования анализируется, и для него предлагается некоторый гипотетический алгоритм ("прием"), приводящий в рассматриваемой ситуации к тому же результату. Эти приемы накапливаются в компьютерной модели, так что в новой задаче некоторые из них могут сработать и предложить свою версию развития решения. Каждое такое срабатывание анализируется на предмет целесообразности, и в решающие правила приема вводятся необходимые коррективы. Эта процедура повторяется для многих сотен задач предметной области – до тех пор, пока сложившаяся мозаика алгоритмов локального планирования действий не обнаружит достаточно устойчивого и эффективного поведения. В целом, процесс напоминает обучение нейросистемы методом "поощрений и наказаний"; отличие состоит лишь в более сложной процедуре коррекции, которая не сводится к изменению каких-либо числовых параметров, как у нейрокомпьютера, а требует привлечения логики для очередного перепроектирования алгоритмов планирования.</p> <p>Многообразие алгоритмов локального планирования создает своего рода "логическое векторное поле", в котором перемещается решаемая задача – от исходной формулировки к ответу. Разумеется, это лишь упрощенная аналогия; отдельные шаги в таком перемещении могут представлять собой целые иерархии вложенных логических процессов, с различными циклами ограниченного поиска и отбора. Однако, она отражает главное обстоятельство: по завершении реализации каждого локального плана предпринимается независимое рассмотрение всей текущей ситуации заново, для выработки следующего плана. К сожалению, на сегодняшний день не известно другого способа создания эффективных "логических векторных полей" автоматического решения задач, кроме весьма трудоемкого процесса их дрессировки на тысячах обучающих примеров.</p> <p>Описанная общая схема обучения компьютерных решателей легла в основу разрабатываемой на кафедре математической теории интеллектуальных систем механико-математического факультета МГУ компьютерной логической системы, которой мы и посвятим оставшуюся часть статьи. Было проработано около 10 тысяч задач из таких разделов, как элементарные алгебра и геометрия, <a href="/enc/ru/encyclopedia:0154">математический анализ</a>, аналитическая геометрия, линейная алгебра, <a href="/enc/ru/encyclopedia:0130215">дифференциальные</a> уравнения, <a href="/enc/ru/encyclopedia:0168">теория вероятностей</a>, комплексный анализ, общая алгебра. На основе этого обучающего материала сформирована база приемов решателя задач, насчитывающая в настоящее время примерно 30 тысяч приемов. Фактически, возникла мощная система символьной компьютерной математики нового типа, позволяющая не только получать ответы, но и прослеживать ход решения по шагам, а при необходимости вмешиваться в процесс решения. В отличие от традиционных систем компьютерной математики, где накапливались тысячи функций для пользователя, который должен был вручную находить их в каталоге системы и применять к текущей задаче, новая система накапливает тысячи приемов, которые самостоятельно анализируют задачу и принимают решение о выполнении преобразований. Пользователь здесь может вообще не интересоваться содержимым базы приемов. Разумеется, это более высокая степень автоматизации, и как следствие, системе становятся доступны значительно более сложные задачи. Преимущества новой системы особенно заметны в тех разделах, где велика роль логического вывода, например, в <a href="/enc/ru/encyclopedia:0157">геометрии</a>. Аппарат, созданный для моделирования логических процессов в <a href="/enc/ru/encyclopedia:0151">математике</a>, позволил перейти также к рассмотрению и других областей – таких, как элементарная <a href="/enc/ru/encyclopedia:01124">физика</a>, понимание текстов (на материале текстовых задач по математике), анализ рисунков, принятие решений в игровых ситуациях.</p> <p>Работа над моделированием процессов решения математических задач потребовала создания специального технологического комплекса.</p> <p>Чтобы при обучении решателя легко распознавались отклонения его реального поведения от желаемого, необходима хорошая визуализация процесса решения. В частности, при отображении на экране математических утверждений, сформулированных на внутреннем логическом языке решателя, необходим перевод этих утверждений на язык общепринятой математической символики. Обратный перевод также является весьма существенным, так как ускоряет ввод нового обучающего материала и новых приемов. В системе реализован редактор математических формул, обеспечивающий быстрый ввод математических утверждений и выражений, а также осуществляющий перевод во внутреннее логическое представление и обратно.</p> <p>Следующий шаг на пути к моделированию логических процессов – формализация <a href="/enc/ru/encyclopedia:0128244">понятия</a> задачи. Предварительная классификация "логических типов" задач, возникшая при анализе математических предметных областей, привела к рассмотрению 4 основных типов задач: на доказательство, на преобразование, на описание, и на исследование. Любая такая задача имеет, прежде всего, некоторый (возможно, пустой) список утверждений относительно встречающихся в ней "известных" объектов, истинность которых считается априори данной. Эти утверждения будем называть посылками задачи. Типичные примеры списков посылок – перечисление условий на известные параметры в системе уравнений; логическое описание чертежа в геометрической задаче на вычисление; список "данных" утверждений в задаче на доказательство. В зависимости от типа задачи, список посылок сопровождается рядом дополнительных элементов.</p> <p>В случае задачи на доказательство добавляется то утверждение, относительно которого требуется установить, что оно является следствием посылок; называем такое утверждение условием задачи на доказательство.</p> <p>В случае задачи на преобразование добавляется то выражение (называемое ее условием), которое должно быть преобразовано к некоторому специальному виду в предположении истинности посылок. В отличие от задачи на доказательство, здесь возникает необходимость сформулировать целевую установку, уточняющую желаемые вид и оптимизацию ответа (упростить; разложить на множители; проинтегрировать, и т.п.). Эта формулировка уже не относится к тому логическому языку "предметного уровня", на котором задаются посылки и условие. Хотя ее можно было бы задавать на некотором логическом языке, предназначенном для записи утверждений о логических структурах данных, на практике оказалось более удобным представлять целевую установку задачи как список специальных технических "пометок", называемых целями задачи. Это объясняется тем, что учетом целевых "пометок" занимается автоматика, управляющая логическим процессом и, как всякая автоматика, использующая свои специализированные нелогические структуры данных.</p> <p>Задача на описание – это обобщение таких типов задач, как решение системы уравнений или неравенств. У нее, кроме списка посылок, имеется также некоторый список утверждений с неизвестными – они называются условиями задачи. Требуется дать описание всех или части значений неизвестных, при которых выполнены условия. Как и в случае задачи на преобразование, списки посылок и условий задачи на описание приходится сопровождать целевой установкой. Она уточняет вид искомого описания; определяет, нужно ли получить полное описание или достаточно лишь частичного (например, единственного примера значений неизвестных). Ответ задачи на описание обычно достигается в процессе последовательных преобразований ее списка условий. Однако, во многих случаях для получения ответа бывает необходимо накапливать некоторое многообразие следствий объединенного списка ее условий и посылок. В таком режиме решаются системы уравнений: извлекая следствия из исходных уравнений, иногда удается получить равенства, указывающие значения неизвестных. Этот же режим определения значений неизвестных путем вывода следствий типичен для геометрических задач на вычисление. Занесение следствий непосредственно в список условий задачи нежелательно, так как впоследствии пришлось бы расчищать этот список, исключая все избыточные его элементы, что потребовало бы дополнительных вычислительных затрат на проверку избыточности. Поэтому в структуре данных задачи на описание предусмотрен специальный накопитель следствий условий и посылок. Роль такого накопителя играет вспомогательная задача на исследование (см.ниже), вводимая в процессе решения задачи на описание. Изначально она имеет своими посылками все посылки и условия задачи на описание.</p> <p>Задача на исследование, в дополнение к списку посылок, имеет лишь целевую установку, уточняющую направленность логического вывода в этом списке. При решении ее исходное логическое описание некоторой ситуации в том или ином смысле "упрощается" и пополняется утверждениями, представляющими интерес в контексте целевой установки. Этот процесс обрывается либо по исчерпании возможностей добавления к имеющейся "картине" каких-либо ценных новых фактов, либо при получении следствий, требующих немедленного возвращения к внешней задаче, для которой предпринимается исследование.</p> <p>Кроме логических структур данных, задача содержит также некоторые вспомогательные технические структуры данных, вводимые в процессе работы самим решателем и используемые для сохранения <a href="/enc/ru/encyclopedia:0127910">информации</a>, направляющей его действия. Прежде всего, это пометки, указывающие на различные ранее предпринимавшиеся неудачные попытки, блокирующие их повторение, а также сообщения управляющего характера, которыми обмениваются между собой приемы. Для ускорения поиска в задаче объектов, связанных определенным образом с заданным объектом, создаются древовидные адресные конструкции. Работа приемов сопровождается потоком многократных обращений к различным вспомогательным процедурам, осуществляющим быстрые логические вычисления. Результаты таких обращений сохраняются в специальных буферах, что существенно ускоряет работу системы и упрощает организацию взаимодействия между приемами. Фактически эти буферы создают что-то типа самоорганизующейся сетевой структуры данных, позволяющей быстро определять свойства объектов и связи между ними. Их применение оказалось особенно эффективным в геометрических задачах, насчитывающих сотни посылок.</p> <p>Преобразования задачи, а также ввод и рассмотрение различных вспомогательных задач в процессе решения обеспечиваются приемами – процедурами локального анализа ситуации, способными усматривать целесообразность определенных действий и выполнять эти действия. Таких приемов в процессе обучения накапливаются многие тысячи, и для обеспечения быстрого поиска нужного приема необходима специальная организация базы приемов. В принципе, здесь возможны два подхода.</p> <p>Первый из них состоит в использовании древовидной поисковой системы, охватывающей все многообразие приемов. Вершины такого древовидного каталога определяют некоторые проверки, выполняемые для текущего состояния задачи, и в зависимости от результатов этих проверок осуществляется отсечение отдельных ветвей каталога, заведомо не содержащих нужного приема. Если после отсечения осталось более одной ветви рассматриваемой вершины, то далее поиск предпринимается независимо в каждой из оставшихся ветвей. После того, как нужный прием найден, он реализуется, и далее цикл поиска повторяется заново. Недостатком этого подхода оказалось в первую очередь то, что в реальном многообразии приемов не удалось найти сколь-нибудь хороших принципов отсечения, ввиду слабой зависимости между условиями применимости различных приемов. Кроме того, по мере обучения и увеличения числа приемов время поиска очередного приема будет при данном подходе увеличиваться. Это, безусловно, создаст (а при плохом отсечении – достаточно скоро) сильные ограничения на объем базы приемов, при котором возможна эффективная работа решателя. Первый подход представляет собой, по существу, цикл просмотра базы приемов на каждом шаге работы системы.</p> <p>В противоположность этому, второй подход основан на цикле просмотра задачи. Большинство приемов, используемых при решении задач, допускает явное указание такого понятия, что для возможности применения приема необходимо появление этого понятия в задаче. Это позволяет организовать базу приемов по принципу энциклопедии: за каждым понятием логического языка закрепляется сравнительно небольшая группа его приемов. Как показывает опыт, исключение составляет лишь крайне незначительная группа приемов, для которых не выделяется какого-либо естественного "инициализирующего" понятия. Очередной шаг решения задачи при втором подходе состоит в последовательном, понятие за понятием, просмотре всего текста задачи, с обращением для каждого текущего понятия к поиску внутри группы его приемов. Эта группа невелика, и во многих случаях ее можно организовать по древовидному принципу, получая таким образом дополнительное ускорение поиска. Преимуществом данного подхода является то, что при обучении системы новым разделам мы практически не уменьшаем скорости ее работы на ранее проработанных разделах. Так получается потому, что "новые" понятия не встречаются в "старых" задачах, и наличие даже очень большого числа "новых" приемов никак не сказывается на времени поиска "старых", связанных с другими понятиями. Фактически, здесь снимаются сколь-нибудь сильные ограничения на рост числа приемов и появляется принципиальная возможность создавать гигантские логические системы, имеющие фундаментальное разностороннее образование.</p> <p>Таким образом, рабочий цикл решателя состоит в сканировании текста задачи – последовательном просмотре встречающихся в задаче понятий и обращении для текущего понятия к его программе, объединяющей в себе все закрепленные за понятием приемы. Эта процедура представляет собой что-то типа внутреннего "логического зрения", обеспечивающего контроль за развитием событий. Как и человек, в процессе решения система предпринимает мысленное "рассмотрение" объектов задачи и связей между ними для выработки плана ближайших действий. Чтобы выбрать из всех возможных действий наилучшее, необходимо каким-то образом сравнивать между собой результаты применения различных приемов в текущем контексте. Для этого естественно ввести числовые оценки приоритетности, выбирая каждый раз, например, прием с наименьшей такой оценкой. Вообще говоря, нерационально при сканировании задачи находить все возможные варианты применения приемов и лишь по окончании сканирования отбирать лучший – это может потребовать рассмотрения слишком большого числа вариантов, причем по своей априорной ценности анализируемые варианты тоже будут сильно различаться. К меньшим вычислительным затратам можно прийти, если разбить все приемы на группы или уровни, объединяя более-менее равноценные, и поиск нужного приема вести с последовательным увеличением номера уровня, обрывая его, как только найден применимый в текущей ситуации прием. Фактически, здесь оценкой приоритетности приема становится номер уровня. Так как обработка каждого уровня приемов требует своего цикла сканирования задачи, то число уровней целесообразно сделать не очень большим; в решателе это число равно 16, причем как правило срабатывание приема происходит на первых 5-6 уровнях. В действительности, один и тот же прием может в различных ситуациях относиться к различным уровням – номер уровня определяется, в зависимости от контекста, самой программой приема. Если этот уровень не соответствует тому, для которого выполняется текущее сканирование задачи, то дальнейшие действия по рассмотрению приема обрываются, и система переходит к другим приемам.</p> <p>Важную роль при сканировании задачи играет управление переключением внимания. Вообще говоря, различные элементы описания задачи неравноценны при поиске очередного приема. Одни из них находятся в задаче давно, другие – только что занесены либо изменены. Вероятность обнаружить при рассмотрении первых ситуацию, требующую немедленных действий, обычно значительно ниже, чем для вторых. Чтобы учесть такую статистическую неоднородность элементов задачи и уменьшить среднее время поиска приема, элементы задачи (посылки и условия) снабжаются весами – целыми неотрицательными числами, указывающими номер того уровня сканирования, до которого ранее доходило рассмотрение элемента. Как только элемент изменяется, его вес уменьшается до 0; веса новых элементов также полагаются равными 0. При сканировании, связанном с приемами i- го уровня, игнорируются все посылки и условия, веса которых больше – они образуют "теневую" часть задачи. По мере прохождения i- го уровня веса тех элементов задачи, для которых не произошло срабатывание приема, автоматически увеличиваются до i+1. Как только срабатывает какой-либо прием и возникают элементы задачи с весом 0, сканирование задачи возобновляется начиная с нулевого уровня. При этом в "зону внимания" попадут только те элементы задачи, которые имеют вес 0, т.е. только что были изменены либо введены. Данная простая автоматика уже обеспечивает в большинстве случаев разумную стратегию переключения внимания и значительно увеличивает быстродействие системы. В особенности это ощутимо для задач геометрического типа, имеющих сотни посылок и условий. Конечно, необходим ряд дополнительных средств, обеспечивающих переключение внимания в специальных случаях. Некоторые из этих средств включены в "общую автоматику" решателя; другие – реализованы непосредственно в приемах, которые могут избирательно изменять веса различных элементов задачи и таким образом управлять зоной внимания.</p> <p>Следующий важный вопрос, возникающий после выбора механизма сканирования задачи как диспетчера, организующего работу базы приемов, – это вопрос о языке для записи приемов. В приеме выделяются такие основные части, как описание ситуации, в которой логически допустимы реализуемые им действия; описание ситуации, в которой эти действия целесообразны, и описание процедуры, собственно реализующей действия приема. Первые две части предполагают использование некоторого логического языка, на котором формулируются соответствующие условия. Эти условия относятся не к объектам предметной области, рассматриваемым в задаче (числам, точкам, векторам и т.п.), а к тем структурам данных, с помощью которых задача представлена в системе: к термам логического языка, вхождениям в эти термы, к спискам термов, к различного рода техническим пометкам и конструкциям, вводимым решателем для управления процессом. Чтобы формулировать такие условия, необходимо обеспечить достаточно богатый набор понятий логического языка, ориентированных на используемые в решателе структуры данных, и прежде всего – на задачи и их элементы. Именно этот набор и составил основную часть нового языка ЛОС (Логический Описатель Ситуаций) для записи приемов; чтобы задавать те действия, которые должны быть выполнены приемом в уже "опознанной" им ситуации, оказалось достаточно присоединить к логической части языка сравнительно небольшое количество кодирующих типовые преобразования конструкций.</p> <p>После того, как на логическом языке сформулирована ситуация, в которой применение приема возможно и целесообразно, необходимо обеспечить некоторый алгоритм, реализующий в задаче поиск этой ситуации. В описании ситуации должны фигурировать объекты, идентифицированные еще до начала поиска – сама задача; выделенное в ней при сканировании вхождение понятия; текущий уровень сканирования, и т.п. Описание представляет собой последовательность утверждений P₁, ..., P_n. Некоторые P_i определяют условия на ранее идентифицированные объекты. Так как все эти объекты относятся к текущим структурам данных решателя, истинность условий проверяется непосредственно и не требует какого-либо логического вывода. Для проверки этой истинности в интерпретаторе языка имеются специальные подпрограммы. Другие P_i вводят в рассмотрение новые объекты, связанные заданным образом с уже введенными до этого объектами. Если такие объекты определяются неоднозначно, то при поиске ситуации необходимо перечислять все возможные варианты. При программировании на обычном алгоритмическом языке "процедурного" типа здесь нужно было бы использовать операторы цикла, причем вложенность циклов была бы равна числу неоднозначно определенных переходов к "новым" объектам в цепочке P₁, ..., P_n. Чтобы избежать таких громоздких конструкций, в языке выделен ряд специальных отношений между объектами, для которых перечисление реализуется автоматически. При обработке "перечисляющего" утверждения сначала рассматривается первая версия выбора новых объектов, и предпринимается попытка для выбранных объектов продвиуться вправо по цепочке . Если в некоторый момент дальнейшее продвижение, ввиду ложности условия, становится невозможным, то происходит откат к последнему "перечисляющему" утверждению и определение очередной версии выбора объектов. Этот принцип "перечисления по умолчанию" позволяет в качестве исполняемого текста программы ЛОСа использовать само логическое описание искомой ситуации и таким образом существенно упростить понимание текста программы.</p> <p>Заметим, что из совсем других соображений принцип реализации операторов с перечислением значений их выходных переменных возник в известном алгоритмическом языке ПРОЛОГ. В отличие от ЛОСа, ПРОЛОГ изначально ориентирован на работу с объектами предметного, а не структурного уровня. Поэтому центральное место в ПРОЛОГе занимает логический вывод, основанный на процедуре унификации. Этот логический вывод становится совершенно излишним при работе с элементами структуры данных, допускающими непосредственную проверку условий, и какого-либо аналога его в ЛОСе не предусмотрено. С другой строны, в ПРОЛОГе отсутствует целый ряд важных возможностей, предусмотренных в ЛОСе для эффективной работы со сложными логическими описаниями образов "структурного" уровня и для использования режима сканирования задачи. ЛОС ориентирован на создание автоматики, управляющей логическими процессами, в то время как при разработке ПРОЛОГа эта автоматика осталась почти "за кадром".</p> <p>Впрочем, оба языка – и ЛОС, и ПРОЛОГ, в общем, относятся примерно к одному уровню, и оба обладают настолько существенными недостатками, что работу над созданием языка для записи приемов пришлось продолжить уже после того, как на ЛОСе был создан весьма эффективный решатель задач по элементатной алгебре. Как правило, значительную часть программы приема на ЛОСе составляет описание вида тех утверждений или выражений, которые могут быть идентифицированы с фрагментами заданной теоремы предметной области. На практике редко бывает так, чтобы идентифицируемые логические конструкции в точности совпадали с теми, которые имеются в теореме. Например, при идентификации квадратного трехчлена ax²+bx+c коэффициент a может оказаться равным единице, и тогда в задаче вместо произведения ax² будет записана степень; сама эта степень может не иметь в точности вида квадрата, а лишь иметь четный коэффициент показателя степени, и т.д. Чтобы, несмотря на эти различия, идентифицировать теорему, приходится фактически в программе приема описывать не ее вид, а вид некоторого класса теорем, получающихся из нее различными вариациями. Текст программы в результате оказывается, во-первых, весьма громоздким, и, во-вторых, достаточно удаленным от исходной записи теоремы. Еще большую громоздкось этому тексту придают различные вставки, связанные с решающими правилами приема. Поэтому, несмотря на все предоставляемые ЛОСом и интерфейсом его редактора возможности для быстрого чтения и понимания логических описаний ситуаций, все же в сколь-нибудь невырожденных случаях описания приемов оказываются трудночитаемыми. Заметим, что хотя ПРОЛОГ, казалось бы, и ориентирован на запись программы в виде совокупности теорем предметной области, однако он тоже не позволяет преодолеть указанной трудности. Если теоремы идентифицируются без учета возможных вариаций, то программа оказывется заведомо слабой; если начинается их учет, то и на ПРОЛОГе, для задания общего вида некоторого класса теорем, придется от предметного уровня перейти к структурному (к которому ЛОС более приспособлен), и таким образом полностью утратить наглядность исходного текста теоремы.</p> <p>Чтобы восстановить утерянную при погоне за эффективностью работы программы приема наглядность и компактность записи, был создан новый язык, уровень которого существенно выше, чем у ЛОСа или ПРОЛОГа. Прием на этом языке задается как теорема предметной области, снабженная некоторой "алгоритмизирующей" разметкой. На основе разметки компилятор осуществляет необходимое обобщение вида теоремы, формулирует описание на ЛОСе ситуаций, в которых она должна быть применена, и добавляет к нему операторы ЛОСа, реализующие применение. Фактически этот язык имеет два независимых логических уровня: предметный уровень, на котором представлена теорема, и структурный уровень, на котором формулируются условия целесообразности применения теоремы. Оба эти уровня предполагают использование полноценного логического языка, однако логические записи структурного уровня, в отличие от записей уровня предметного, не участвуют в каком-либо логическом выводе – они используются только для проверки условий при принятии решения. Роль "алгоритмизирующей" разметки приема весьма разнообразна – это и указание способа применения теоремы, и определение необходимых правил ее обобщения, и указание условий целесообразности применения, и уточнение алгоритмических средств, используемых для обработки посылок теоремы, и указание на "технические" сообщения, передаваемые при срабатывании данного приема другим приемам, и указатели переключения внимания, и многое другое. Эта разметка представляет собой что-то вроде генотипа приема, элементы которого допускают независимое варьирование в достаточно широких пределах и по которому компилятор создает фактически реализуемую программу приема на ЛОСе. Такая аналогия позволила назвать новый язык ГЕНОЛОГом (ГЕНетический язык ЛОГического программирования).</p> <p>Описание приема на ГЕНОЛОГе оказалось значительно более компактным и понятным, чем на ЛОСе. На экране изображается в стандартной математической записи теорема приема, под которой размещается в нескольких окнах сопровождающая теорему информация. Во многих случаях эта информация занимает всего несколько строчек, в то время как текст создаваемой компилятором программы на ЛОСе составляет несколько полных экранов. Трудоемкость чтения приема и его коррекции, по сравнению с ЛОСом, уменьшилась на порядок.</p> <p>В отличие от обычных языков программирования, ГЕНОЛОГ не представляет собой сколь-нибудь завершенного явления. По существу, он является коллекцией типовых алгоритмических конструкций, используемых при переходе от теоремы к программе. Эта коллекция, достаточно богатая на текущий момент, продолжает (хотя все реже и реже) пополняться при рассмотрении новых предметных областей. Соответственно, при переходе к новой предметной области обычно приходится затрачивать некоторые усилия на развитие компилятора ГЕНОЛОГа. Как показывает опыт, эти затраты несопоставимо малы в сравнении с той последующей экономией, которую дает применение ГЕНОЛОГа при обучении решателя в данной области.</p> <p>Главным доводом в пользу применения и развития ГЕНОЛОГа является, впрочем, даже не наглядность представления приема и проистекающие из нее преимущества для ручной "дрессировки" решателя на тысячах задач из различных разделов, а возможность приблизиться вплотную к тому источнику, из которого приемы возникают – к логическому языку предметной области. Фактически, ГЕНОЛОГ – это язык пограничного уровня между теоремами и алгоритмами. Выше этого уровня кончается программирование и начинается логический вывод в теории. Любая экспертная система, претендующая на сколь-нибудь серьезное саморазвитие, должна будет обеспечивать для создания своих новых программ прохождение через указанный пограничный слой, и таким образом, хотя бы на промежуточных этапах, программироваться на языке типа ГЕНОЛОГа. Это обстоятельство полностью оправдывает предпринимаемую попытку развития универсальной решающей системы, охватывающей сразу многие (перечисленные выше) предметные области. Даже обычное вычислительное программирование, в своих истоках, восходит к многообразию имеющихся в математике теорем, и должны развиваться его версии, базирующиеся на ГЕНОЛОГе. Эксперименты с решателем показывают, что при определенном развитии компилятора ГЕНОЛОГа удается программировать "на уровне теорем" вполне эффективные традиционные вычислительные процедуры.</p> <p>Огромный запас накопленных в решателе приемов позволяет предпринять определенную их классификацию и выделить систему "стандартных шаблонов" использования теорем, позволяющую во многих случаях создавать по теореме новые приемы автоматически. Для поддержания устойчивости функционирования решателя необходима последующая адаптация на задачах, позволяющая отбирать ценные приемы, уточнять уровни их срабатывания и необходимую степень мотивированности срабатываний. Развитие реально работающего генератора приемов, основанного на стандартизации их типов, означает повторный цикл обучения решателя, с переработкой малоубедительных приемов и более детальным анализом целесообразности действий. Такая работа является весьма трудоемкой, однако в результате может быть создана система, способная, как и человек, получать в качестве исходной информации список теоретических фактов и затем обучаться решению задач по соответствующему задачнику.</p> <p>Разумеется, подлинные истоки программирования и самообучения лежат выше пограничного слоя между теоремами и приемами – они находятся в области теоретических исследований, приводящих к получению новых теорем. Чтобы обучить систему решению таких исследовательских задач, анализируются теоремы, на которых основаны ее приемы. Предлагаются некоторые версии исходных постановок задач, при решении которых могли бы быть "открыты" эти теоремы, и решатель обучается приемам решения данных задач. Здесь возникает интересное явление "программирующего" логического вывода, направленного на получение теорем для приемов заданного типа. Такой вывод базируется на сравнительно простых "классических" формулировках теорем, обогащая их множеством обобщающих параметров для последующего практического применения. Развитие аппарата программирующего логического вывода в сочетании с развитием генератора приемов могло бы позволить перейти в будущем к режиму обучения решателей путем загрузки в них лишь теоретических сведений из обычных учебников. Это во много раз ускорило бы процесс обучения и дало возможность создавать эффективные решатели для многих практически важных задач.</p> <h2>Рекомендуемая литература</h2> <p>А.С.Подколзин. Компьютерное моделирование логических процессов. Том 1. Москва, Физматлит, 2008.</p>

Описание изменения: