INTELLIGENCE ARTIFICIELLE Resolution de problemes par 1'Homme et la machine par Jean-Louis Lauriere Professeur a 1'Universite Pierre et Marie Curie Groupe de Recherche CNRS C. F. PICARD-PARIS TROISIEME EDITION nouveau tirage Eyrolles, Paris Ж.-Л. Лорьер СИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА Перевод с французского под редакцией канд. физ.-мат. наук В. Л. Стефанюка Москва «Мир» 1991 ББК 5.05 Л78 УДК 007.001.33 Переводчики: Евграфова С. М., Девишев Р. И., Дихтяр В. И., канд. физ.-мат. наук Чигирь С. Д. Лорьер Ж.-Л. Л78 Системы искусственного М.: Мир, 1991-568 с., ил. ISBN 5-03-001408-Х интеллекта: Пер. с франц.— Книга известного французского специалиста посвящена вопросам проектирования и применения систем искусственного интеллекта, при построении которых используются такие современные инструменталь- ные средства, как языки Лисп, Пролог и оболочки экспертных систем. В качестве применения рассмотрена область принятия решений. Для специалистов в области искусственного интеллекта и студен- тов старших курсов соответствующих специальностей вузов. _ 1402070000-281, .,- л 041(01)-91 2-90 ББК 5.05 Редакция литературы по информатике и робототехнике Научное издание ЖАН-ЛУИ ЛОРЬЕР СИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА Заведующий редакцией д-р техн. наук А. Л. Щсрс Зам. заведующего редакцией Э. Н. Вадиков Ст. научный редактор И. М. Андреева Мл. научный редактор В. Н. Соколова Художник А. Коршунов Художественные редакторы Н. М. Иванов, О. Н. Адаскина Технический редактор Л. Л. Бирюкова Корректор Н. А. Гиря ИБ № 7183 Сдано в набор 09.11.89. Подписано к печати 13.06.90. Формат 60 «88 1/16. Бумага типографская кн.-журн. Печать офсетная. Гарнитура литературная. Объем 17,75 бум. л. Усл. печ. л. 35,5. Усл. кр.-отг. 35,5. Уч.-изд. л. 33,5. Изд. № 6/6674. Тираж 20 000 экз. Зак. 205. Цена 2 р. 80 к. ИЗДАТЕЛЬСТВО «МИР. 129820, ГСП, Москва. И-110, 1-й Рижский пер., 2. Ленинградская типография №2 головное предприятие ордена Трудового Красного Знамени Ленинградского объединения «Техническая книга» им. Евгении Соколовой Государственного комитета СССР по печати. 198052, г. Ленинград, Л-52, Измайловский проспект, 29. Отпечатано в Ленинградской типографии № 4 Государственного комитета СССР по печати, 191126, Ленинград, Социалистическая ул., 14. ISBN 5-03-001408-Х (русск.) © Jean-Louis Lauriere, 1987 © перевод на русский язык, Евгра- фова С. М., Девишев Р. И., Дих- тяр В. И., Чигирь С. Д., 1991. ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА В наше время интенсивной интернационализации науки, когда идентич- ные по уровню и подходам исследования проводятся и в США, и в СССР, и в Японии, тем не менее, может быть, стоит обратить внимание на то, что говорят о японском проекте компьютеров пятого поколения, об английской реакции на японский вызов, о европейской или американской школе искус- ственного интеллекта. Оказывается, кроме сил, объединяющих мировую науку (особенно такую, как искусственный интеллект) и обусловленных при- менением однотипной вычислительной техники, стандартных языков про- граммирования, а в последнее время и созданием международных научных проектов типа ЕСПРИТ, большую роль играют «национальные» научные традиции, придающие своеобразие исследованиям, проводимым в разных странах. Известный французский ученый Жан-Клод Симон (кстати, в его лабора- тории информатики в Университете Париж-VI начинал научную деятель- ность автор данной книги Жан-Луи Лорьер) объяснил однажды, почему он очень любит научные командировки в СССР: «В Америке, посетив одну из лабораторий, можно считать, что ты побывал везде, так как все американ- ские лаборатории искусственного интеллекта делают одно и то же. Другое дело в Москве: здесь что ни человек, то своя проблема, свой подход...» Здесь не место вникать в вопросы, что лучше—концентрация усилий или широта охвата проблемы и какова истинная причина такого положения ве- щей. Важно то, что можно твердо говорить о «европейском» искусственном интеллекте, в котором в свою очередь отчетливо выделяются итальянская, французская, английская и другие школы. Одна из отличительных черт европейской научной школы состоит в по- требности поставить любую дисциплину на прочную научную основу, что, несомненно, нашло отражение в предлагаемой советскому читателю книге. В США—родине искусственного интеллекта—многие считают, что искус- ственный интеллект — это совершенно новое направление, и, чтобы им эф- фективно заниматься, нужно отказаться от таких наук, как кибернетика или распознавание образов, и начать все с самого начала. Извесгный математик и кибернетик Марвин Минский из лаборатории искусственного интеллекта Массачусетского технологического института считает, что даже математика как универсальный язык бесполезна в искусственном интеллекте. Языком искусственного интеллекта должен стать язык интеллектуальных программ. Европейская школа не придерживается столь радикальных взглядов и предполагает, что научные достижения накапливаются постепенно и смена парадигм в науке отнюдь не перечеркивает прошлого, а дает лишь новый, свежий взгляд. Данная книга отличается от большинства (американских) работ по искусственному интеллекту европейской основательностью, сдержан- ностью и деловитостью. Возможно, одной из причин этого является то, что сам автор — увлеченный программист, вдумчивый ученый, не склонный, как многие его заокеанские коллеги, к чрезмерному оптимизму. Он сторонник кропотливого накопления результатов с постоянной привязкой их к фунда- ментальным разделам науки. Эта книга будет импонировать советским чи- тателям, обычно склонным к критическому осмыслению достижений и труд- ностей. ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА Заканчивая это небольшое введение к книге, хочется отметить следую- щее: статистика говорит о том, что интерес к искусственному интеллекту нисколько не ослабевает. На последней Международной объединенной кон- ференции по искусственному интеллекту, состоявшейся в августе 1989 г. в Детройте (США), присутствовало 6500 участников (!). Хочется верить, что данная книга будет способствовать пополнению армии специалистов по искусственному интеллекту и нашими учеными, которые пока что не слиш- ком активно участвуют и в международных, и в европейских объединенных конференциях по искусственному интеллекту (следующая конференция бу- дет проходить в 1990 г. в Швеции). Перевод книги выполнен Р. И. Девишевым (гл. 1—3), С. М. Евграфовой (гл. 4, 5), С. Д. Чигирем (предисловие автора, гл. 6—8) и В. И. Дихтяром (гл. 9). В. Л. Стефанюк ПРЕДИСЛОВИЕ Основания для появления этой книги возникли еще в то время, когда я учился в лицее. Как и все остальные ученики, я жадно впитывал знания по физике и математике, постоянно спрашивая себя: а для чего все это может пригодиться? Что касается физики, то ее отношение к реальной жизни пред- ставляется очевидным, но мы тогда не могли в это поверить, настолько все было таинственным. К тому же каждый год новый преподаватель объяснял нам, что все, что мы изучали в прошлом году, было неверным... Физика представала перед нами как причудливая игра, в которую играют взрослые. С математикой же все было по-другому. В ней нас вдохновляла красота абстракции, мы получали удовольствие от поиска красивых доказательств. Однако ко всему этому часто примешивалось ощущение, что нас обманы- вают. Нам все время преподносили определения и доказательства как на- стоящую реальность, но причины явлений никогда не объяснялись. Казалось, что большую чость доказательств преподаватели получают с помощью маги- ческих манипуляций с кусочком мела у доски. Как можно было связать воедино все эти линии и не выпустить из поля зрения ни одну из них от самого начала доказательства до его чудесного конца? И над всем этим: «А для чего все это надо?» Ответ на этот вопрос пришел позже, через несколько лет «активной» жизни. На самом деле все это ни для чего не было надо, потому что предметы, которые мы изучали, вносились в школьные программы произволь- но. По правде говоря, они служили лишь поводом для перехода к более серьезным вещам, таким, как учиться понимать, учиться решать задачи, учиться познавать. Но любопытно, что эти «вещи» не признаются и почти не преподаются. Можно сказать, что существует определенный вид интеллек- туального терроризма, когда некоторых учеников называют «нуль в матема- тике», хотя их единственная вина состоит в том, что они не понимают то, о чем... никогда не говорится. Некоторым удается этого избежать, потому что они раньше сумели познакомиться с неявными правилами этой игры. Есть и такие, кто учит все наизусть... Но в настоящее время существует область исследований, в которой пер- вым желанием исследователей является стремление понять, как система об- работки информации—будь то человек или машина—способна воспринимать, анализировать, передавать и обобщать то, чему ее обучают, и с помощью этих данных исследовать конкретные ситуации и находить решения задач. Данная область исследований — искусственный интеллект, старший сын ин- форматики. Его предметом изучения является любая интеллектуальная дея- тельность человека, подчиняющаяся заранее неизвестным законам. Его мож- но также определить как «все то, что еще не сделано в информатике». Сели предметом информатики является обработка информации, то к об- ласти искусственного интеллекта относятся такие случаи этой обработки, ко- торые не могут быть выполнены с помощью простых, точных алгоритмиче- ских методов и которых великое множество. К ним относятся даже такие банальные ситуации, как чтение текста с листа, находящегося перед вами. Один и тот же символ, например вертикальная черточка, может восприни- маться визуальной системой в зависимости от контекста либо как I, либо как t, либо как знак абсолютной величины. В случае когда текст написан ПРЕДИСЛОВИЕ от руки, ситуация еще хуже. Как может выйти из этого затруднения наша распознающая система? Вот одна из главных проблем, изучаемая в искус- ственном интеллекте. К области этой науки относятся также идентификация изображения человека (являющаяся более трудной задачей, чем просто иден- тификация букв), понимание текста (а не отдельных букв), распознавание речи, доказательство теорем, решения задач, поиск хода в шахматах, состав- ление расписаний, подготовка ответов на ежедневный интеллектуальный тест, разработка планов в архитектуре, постановка медицинского диагноза, анализ журнальной статьи. В последнее время во всех этих областях до- стигнуты впечатляющие успехи. Ж.-Л. Лорьер Глава 1 ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ В области искусственного интеллекта основными пробле- мами являются поиск и представление знаний. Цель исследова- ний при этом состоит не только в разработке новых теоретиче- ских построений, но и в создании для ЭВМ соответствующих программ наиболее общего характера. В начале главы мы кратко опишем состояние области тра- диционной информатики, затем покажем, каким образом иссле- дования в области искусственного интеллекта выделились в са- мостоятельное научное направление. 1.1. Информатика и искусственный интеллект Термин «информатика» используется исследователями в двух различных значениях. Во-первых, информатика рассмат- ривается в качестве основы для моделирования и, во-вторых, как инструмент для непосредственной проверки гипотез (ЭВМ—прекрасное средство тестирования идей). Информатика и искусственный интеллект имеют тесные взаимосвязи с лингвистикой, психологией и логикой, которые изучают явления, относящиеся к познанию, пониманию и умо- заключениям. Эти связи носят взаимный характер: с одной сто- роны, сегодня лингвисты, психологи, специалисты в области математической логики переводят в программы те новые мо- дели, которые они разрабатывают (точно так же, впрочем, как математики, биологи, исследователи в области медицины), а с другой — исследователи в области искусственного интеллекта изучают эти модели и пытаются воссоздать на их основе логику эффективных методов решения задач. Особенно тесные взаимосвязи имеются между искусствен- ным интеллектом и науками о познании. Это обусловлено тем, что единственным устройством для разумных рассуждении, ко- торое нам доступно, является наш мозг, причем непосредствен- ное исследование мыслительных процессов, протекающих в нем, практически невозможно. Использование ЭВМ в качестве мате- риальной основы искусственного интеллекта позволяет как бы изнутри взглянуть на подобные процессы. Впервые после фундаментального пересмотра картины мира, связанного с именами Коперника и Дарвина, разработка 10 ГЛАВА 1 методов искусственного интеллекта возвращает нас к вопросу о месте человека в природе. По существу впервые оспаривается исключительность разума. 1.2. Искусственный интеллект как наука Искусственный интеллект как наука насчитывает уже около 30 лет. Задачей этой науки является воссоздание с помощью искусственных устройств (в основном с помощью ЭВМ) разум- ных рассуждении и действий'. .'.При этом возникают трудности двух типов: 1. В большинстве случаев, выполняя какие-то действия, мы сами не осознаем, как мы это делаем. Нам неизвестен точный способ (или алгоритм, как говорят специалисты), как именно происходит понимание текста, узнавание лица, доказательство теоремы, выработка плана действий, решение задачи и т. п. 2. ЭВМ априори далеки от человеческого уровня компетент- ности: до начала любой их работы необходимо составить соот- ветствующие программы. Однако в действительности языки программирования дают возможность выражать только весьма элементарные понятия. Следовательно, методы искусственного интеллекта представ- ляют собой экспериментальную научную дисциплину. Под экс- периментом в данном случае понимается проверка и уточнение моделей (представляющих собой программы для ЭВМ) на мно- гочисленных примерах — наблюдениях над человеком (в том числе и над самим исследователем) с целью раскрыть эти мо- дели и лучше понять функционирование человеческого разума. Ниже мы уточним определение области искусственного ин- теллекта. Затем мы поговорим об истории этой новой научной дисциплины и в заключение рассмотрим современные методы и перспективные направления исследований в области искусст- венного интеллекта. 1.3. Области применения искусственного интеллекта Всякая задача, для которой неизвестен алгоритм решения, априорно относится к искусственному интеллекту. Под алгорит- мом понимается вся последовательность заданных действий, которые хорошо определены, выполнимы на современных ЭВМ, причем решение задачи должно получаться в приемлемое вре- мя (порядка минуты или часа). Так, например, неизвестен ал- горитм для игры в шахматы. И хотя эта игра имеет конечное число ситуаций, рассмотрение их всех потребовало бы тысяче- летий. Аналогичным образом не существует общего алгоритма медицинской диагностики, составления резюме текста или пере- вода его на иностранный язык. ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ 11 К сфере искусственного интеллекта относятся те весьма различные области, где мы действуем, не имея абсолютно точ- ного метода решения проблемы, и которые обладают в общем двумя характерными особенностями: • в них используется информация в символьной форме: буквы, слова, знаки, рисунки. Это отличает область искусствен- ного интеллекта от областей, в которых традиционно компьюте- рам доверяется обработка данных, в числовой форме; • в них предполагается налйдие выбора; действительно, сказать, что не существует алгоритма, это значит сказать, по сути дела, только то, что нужно сделать выбор между многими вариантами в условиях неопределенности, и этот недетерми- низм, который носит фундаментальный характер, эта свобода действия являются существенной составляющей интеллекта. Первой проблемой, с которой сталкиваются исследователи в области искусственного интеллекта, является проблема вос- приятия информации. Возможности . сенсорных и исполнитель- ных механизмов, присущих человеку, в области зрения, мани- пулирования, восприятия вкуса и запаха, а также в понимании и воспроизведении речи еще не достигнуты в современных тех- нических системах. Рассмотрим отдельные направления, где находят применение методы искусственного интеллекта, Восприятие и распознавание образов Любая система обработки информации получает исходные данные от своих органов восприятия. Из наших пяти органов чувств несомненно самое важное место занимает зрение. Тех- ническими аналогами глаза сегодня являются телекамеры и ла- зеры, работа которых непосредственно связана с программами распознавания изображений и анализа сцен. Микрофоны пред- ставляют собой воспринимающие органы технических слуховых систем. Область обработки поступающих сигналов известна под названием "распознавание образов". Распознающая система является необходимой частью любой автономной системы обра- ботки информации. Однако этим еще не решаются задачи, воз- никающие в области искусственного интеллекта, поскольку сов- сем недостаточно того, чтобы исходная информация была зако- дирована и занесена в память. В первую очередь возникают проблемы понимания и логического рассуждения, которые яв- ляются специфическими для искусственного интеллекта. Математика и автоматическое доказательство теорем В искусственном интеллекте особое значение придается сим- вольной, а не числовой информации. Соответственно и первыми областями, в которых работали исследователи искусственного 12 ГЛАВА 1 интеллекта, стали математика и различные игры. Обе эти сферы оказались хорошими областями приложения методов искусственного интеллекта в силу того, что связанные с ними задачи и проблемы хорошо формализованы, а, кроме того, сами эти .области являются примерами высших достижений челове- ческого разума. Первые программы автоматического доказательства теорем появились в 1957 г., т. е. 10 лет спустя после появления первых ЭВМ. Вначале эти программны были достаточно просты, но за- тем все более и более усложнялись. Уровень человека средних способностей был ими быстро превзойден, однако уровень хо- рошего математика не достигнут до сих пор. В процессе созда- ния таких программ были изучены более глубоко и получили дальнейшее развитие теории доказательств и эффективных ме- тодов их построения. Более того, формальные разделы матема- тики, например такие, как математическая логика, оказались необходимыми для таких важных приложений, как робототех- ника, решение задач, поиск информации в базах данных. Ма- тематика и автоматическое доказательство теорем остаются и сейчас одним из основных направлений приложения методов искусственного интеллекта. Игры Как и формальные системы в математике, игры, характери- зующиеся конечным числом ситуаций и четко определенными правилами, являются хорошей сферой приложения дедуктивных методов. Вот почему они были и остаются до сих пор предпоч- тительными объектами исследований в искусственном интел- лекте. В этой области уровень среднего игрока также был легко превзойден, но уровень чемпиона мира еще не достигнут. Не- ожиданно оказалось, что возникшие трудности были те же, что и в математике, и во многих других областях. Эти трудности связаны с тем, что, играя, человек использует весь объем, зна- ний, который он накопил за свою жизнь. В азартных играх, по- добных покеру или нардам, где большое значение имеет расчет вероятностей, программы работают великолепно. Решение задач Отметим, что понятие "решение" в данном случае исполь- зуется в самом широком смысле. Речь идет скорее о поста- новке, анализе и представлении конкретных ситуаций, чем о самом решении. На сегодняшний день достижения в этой обла- сти носят ограниченный характер. Это обусловлено тем, что, хотя многие хорошо решаемые задачи уже решены, остается широкое поле проблем, требующих специального изучения. ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ 13 Речь идет о задачах, встречающихся в повседневной жизни, в исследовании операций или в математике, для решения кото- рых требуется изобретательность и способность к обобщению. В частности, роботы должны быть способны решать такие за- дачи, решение которых мы получаем непроизвольно, например встать на что-нибудь, чтобы достать некоторый предмет, или зажечь свет, чтобы лучше видеть. Понимание естественного языка, В области "понимания естественного языка" исследователи интересуются анализом и генерацией текстов, их внутренним представлением, выявлением знаний, необходимых для понима- ния текстов, т. е. синтаксических, семантических, прагматиче- ских знаний. Эти проблемы в данной книге не рассматриваются. (См. работу: Pitrat J. (1985): Textes, ordinateurs et comprehen- sion. Eyrolles.) Следует отметить, что результаты и социальные последст- вия исследований в области искусственного интеллекта скоро .приобретут важное значение. Многие научные дисциплины ока- жутся непосредственно взаимосвязанными: психология (челове- ческий мозг остается обязательным объектом исследования в искусственном интеллекте), логика, лингвистика, биология (модели передачи информации с помощью генов), информати- ка (самоорганизующиеся системы, поиск в базах данных, авто- матическое программирование), медицина (помощь в диагности- ке) и особенно, может быть, теория образования и обучения во всех научных дисциплинах (уровень детализации, достигаемый в программах искусственного интеллекта, выявляет недостатки традиционного образования и делает очевидными пробелы пре- подавания). 1.4. Историческая справка Электронные вычислительные машины, даже если бы они не были необходимы для создания и испытания моделей искус- ственного интеллекта, являются замечательным средством ис- следования, и именно с ними связан взлет исследований по ис- кусственному интеллекту. В 1954 г. А. Ньюэлл задумал создать программу для игры в шахматы. К. Шеннон, отец теории ин- формации, уже предложил пригодный для этого метод. А. Тью- ринг, один из первых специалистов в области информатики, уточнил этот метод и промоделировал его вручную. В корпора- ции Рэнд Дж. Шоу и Г. Саймон объединились в работе по про- екту Ньюэлла. Их поддержал коллектив психологов из Амстер- дама (руководитель А. де Гроот), который изучал стиль игры 14 ГЛАВА 1 крупных шахматистов. Язык программирования, специально со- зданный этой группой, предназначался для того, чтобы в ма- шине было легко манипулировать информацией в символьной форме, работать с системой указателей и обрабатывать списки. Это был язык программирования ИПЛ1 (1956), явившийся предшественником языка Лисп (J. Mac Carthy, I960). Первой программой искусственного интеллекта стала программа "Ло- гик—Теоретик", предназначенная для доказательства теорем в исчислении высказываний. Ее^.работа была впервые продемон- стрирована 9 августа 1956 г. Программа для игры в шахматы NSS (Newell, Shaw, Si- mon) была создана в 1957 г. Ее структура и структура програм- мы "Логик—Теоретик", представление о "желаемых ситуа- циях" и "эвристиках" (правилах, которые позволяют сделать выбор при отсутствии точных теоретических оснований) приве- ли позже к концепции Универсального Решателя Задач. Эта программа, анализируя различия между ситуациями и конст- руируя цели, хорошо решает головоломки типа "Ханойская башня" или вычисляет неопределенные интегралы. Специалисты в области информатики начинают интересо- ваться непосредственно искусственным интеллектом, и некото- рые уже пишут ставшие затем знаменитыми статьи, как, напри- мер, Дж. Маккарти, М. Минский, Г. Саймон. Создаются новые программы. Дж. Гелернтер (Gelernter, 1960) показывает, что его программа доказательства теорем из школьной геометрии может работать лучше, чем ее создатель! Чтобы доказать, что треугольник АВС, у которого два угла у основания (углы при вершинах В и С) равны, является равнобедренным, программа вместо классического доказательства из учебников, заключаю- щегося в построении высоты, опущенной из вершины А на осно- вание, просто применяет теорему о равенстве треугольников АВС и АСВ\ Результат очевиден... Программа ЕРАМ (Elementary Perceiving and Memorizing Program — элементарная программа для восприятия и запо- минания) задумана Е. Фейгенбаумом для моделирования пси- хологических ситуаций. Программы, работающие с запросами на естественном языке, были созданы давно, найдя применение при поиске ин- формации в базах данных. Например, программа БЕЙСБОЛ • (Green et al. 1961) отвечала на вопросы о результатах прошед- ших бейсбольных матчей, а программе СТЬЮДЕНТ (Bobrow, 1964) было доступно решение алгебраических задач, сформули- рованных на английском языке. Весьма большие надежды возлагались исследователями на работы в области машинного перевода. В этой сфере продол- ИСКУССТВЕННЫЙ" ИНТЕЛЛЕКТ 15 жают работать большие группы исследователей. Они ориенти- руются прежде всего на использование синтаксического ана- лиза и информацию, получаемую из словарей (метод ключевых слав). И хотя этого недостаточно, как было доказано в сообще- ниях Дрейфуса (Dreyfus, 1972) и Лайтхилла (Lighthill, 1973), тем не менее исследователи потратили годы до того, как осоз- нали, что автоматический -перевод не является изолированной проблемой и требует для успешного осуществления наличия такого необходимого этапа, как понимание. Новый подход в формальной логике, основанный на приве- дении рассуждении к противоречию, появился в 1965 г. (Дж. Робинсон). Этот подход позволяет формализовать многие задачи и дать их машинную интерпретацию. Его успешно ис- пользовали для доказательства теорем (Слейгл, Грин, Коваль- ский) и верификации программ (Кинг, Уолдингер). Этот же подход послужил отправной точкой при создании оригинального языка программирования — языка Пролог, который обладает мощностью логики первого порядка и был создан А. Колмрауе- ром в 1971 г. (гл. 3). Исследования в области искусственного интеллекта сопро- вождаются разработкой языков программирования новых поко- лений и созданием все более изощренных систем программиро- вания. Это дает возможность при разработке программ для ЭВМ использовать наши обычные методы рассуждения и обыч- ный словарный запас. Более того, языки программирования Лисп, Пролог, PLANNER, QA4 (называем здесь только наибо- лее важные из них) позволяют с помощью концепций цели и утверждения моделировать и формализовать логический вывод в решении задач; языки MACSYMA и REDUCE позволяют производить формальные манипуляции с математическими вы- ражениями; язык TMS позволяет осуществлять управление при ненадежных сведениях и проверять соответствие последних друг другу. Описанные выше результаты начинают использоваться в ро- бототехнике при управлении работой неподвижных или мобиль- ных роботов, действующих в реальном трехмерном простран- стве. При этом возникает проблема создания искусственных органов восприятия. В системах технического зрения восприни- мающим устройством служит телекамера, а при распознавании зрительных образов все большую роль играют методы анализа зрительных сцен, связанные с определением очертаний предме- тов (Гузман, Уолц, Уинстон), а также выявлением предметов, т. е. частично скрытых другими предметами, находящимися на первом плане. Качество решения подобных задач с тех пор все время повышается. 16 ГЛАВА 1 До 1968 г. исследователи работали в основном с отдельными "микропространствами": они создавали системы, пригодные для таких специфических и ограниченных сфер приложения, как игры, евклидова геометрия, интегральное исчисление, "мир ку- биков", обработка коротких фраз с небольшим словарным за- пасом. Почти во всех этих системах использовался один и тот же подход — упрощение комбинаторики, базирующееся на уменьшении необходимого перебора альтернатив на основе здравого смысла, применения числовых функций оценивания и различных эвристик. Обычно исследователь ограничивается только этими средствами, однако к настоящему времени уже реализованы десятки систем в различных областях применения, которые по уровню начинают соперничать с человеком. Приме- рами таких систем могут служить так называемые "игровые микрокомпьютеры", ориентированные на такие игры, как шах- маты, игра го и некоторые азартные карточные игры. Однако экспертам предстоит судить, насколько велики достигнутые здесь успехи. 1.5. Заключение В начале 70-х годов произошел качественный скачок в ис- следованиях по искусственному интеллекту. Это объясняется двумя причинами. Во-первых, все исследователи постепенно осознали, что всем ранее созданным программам не хватает самого важного— глубоких знаний в соответствующей области. Различие между экспертом и обыкновенным человеком состоит в том, что у экс- перта имеется опыт в данной области, т. е. годами накопленные знания. Поэтому для существенного улучшения результатов ра- боты какой-либо программы искусственного интеллекта тре- буется не просто усовершенствовать эвристики или какие-то числовые коэффициенты, с которыми работает программа, а на- против, необходимо использовать в ней методы логических рас- суждений и накопленные' в опыте знания, представленные в символьной форме. Во-вторых, возникает конкретная проблема: как передать эти знания программе, если ее непосредственный создатель ими не обладает. Ответ ясен — сама программа должна их вы- делять из данных, получаемых от эксперта. Исследователи столкнулись с необходимостью снабдить системы искусственно- го интеллекта возможностями, которых нет в обычных языках программирования, а именно: программы искусственного интел- лекта должны уметь сами собирать информацию (например, информацию такого типа: "Париж, 10 февраля, погода хоро- ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ 17 шая"), хранить эту информацию и использовать только при на- личии достаточных оснований. В данном случае имеется раз- граничение между заключением о каком-то факте и использо- ванием этого факта. В противоположность этому обычный язык программирования позволяет выражать только выполнимые задания или указания. Отмеченная особенность является существенно важной, так как эксперт обеспечивает систему отдельными изолированными фактами, не зная заранее, в какой момент она решит принять их во внимание. Исследования по решению задач и пониманию естественного языка объединяет одна основная проблема — представление знаний. К 1970 г. было создано множество программ, основанных на этих идеях. Первая из них—программа DENDRAL. Она пред- назначена для порождения структурных формул химических соединений на основе информации, поступающей от масс-спект- рометра. Программа была разработана в Станфорде при уча- стии нобелевского лауреата Д. Ледерберга. Эта программа на- биралась опыта в процессе собственного функционирования. Экспертом в нее было заложено много тысяч элементарных фактов, представленных в виде отдельных правил. Рассматри- ваемая система явилась одной из первых экспертных систем, и результаты ее работы поразительны. В настоящее время си- стема поставляется потребителям вместе со спектрометром. Разумеется, представляется идеальным, когда программа сама выводит используемые правила логических заключений, основываясь на полученном опыте, т. е. обучается. Именно это было реализовано группой DENDRAL в Станфордском исследо- вательском институте. В программе METADENDRAL исполь- зуется несколько общих правил, позволяющих отсекать неперс- пективные варианты при рассмотрении возможных фрагментов структур соединений. Кроме того, в процессе работы программа сама выводит и последовательно уточняет частные правила по- строения структурных формул. Вначале это делается для от- дельных связей химического соединения, а затем строится структура всего соединения. Это особенно удобно для малоиз- вестных групп химических соединений и позволяет использовать данную систему при редактировании соответствующих публика- ций в международных периодических изданиях в области химии. Терри Виноград разработал систему SHRDLU (1971), кото- рая моделирует робота, манипулирующего кубиками. С робо- том можно говорить по-английски. Система интересуется не только синтаксисом фраз, но и правильно понимает их смысл, благодаря семантическим и прагматическим знаниям о своем 18 ГЛАВА 1 "мире кубиков". Она умеет устранять двусмысленности, пони- мает метафоры, проверяет свои поступки и дает отчет о своих действиях. В конечном счете она показывает в реальных усло- виях, что все это стало возможным благодаря хорошей про- грамме, которая управляет действиями такого робота. Число исследователей, посвятивших себя целиком искусст- венному интеллекту, составляет во всем мире несколько сотен, но достигнутые ими результаты касаются каждого из нас. Об этих результатах много говорят средства массовой информации, и нередко можно услышать о "роботах" будущего. На самом деле необходимо хорошо представлять себе, что эти исследова- ния являются долгими и трудными, так как в отличие от иска- теля чудодейственных рецептов исследователи в области искус- ственного интеллекта пытаются постепенно воссоздать и ввести в ЭВМ опыт и знания специалистов всех областей знания. В общем случае эта информация отсутствует и нужна дли- тельная работа с экспертом, чтобы выявить все, что было неосо- знанно отобрано и запомнено им за время своего совершен- ствования в какой-то конкретной области деятельности. Для решения этой проблемы разработаны специальные языки и си- стемы представления информации. Но для ее решения необхо- димо также собрать больше информации, чем ее содержатся в каком-либо словаре или энциклопедии. Эта задача не является невыполнимой, так как уже разработаны соответствующие ме- тоды и устройства. Кроме того, она увлекательна, так как поз- воляет узнать много нового о самом человеке и его разуме — ибо в действительности именно человек является основным объ- ектом изучения, и можно быть уверенным, что когда эта зада- ча будет решена, программы искусственного интеллекта будут иметь самостоятельную ценность независимо от современных компьютеров. Глава 2 ПРЕДСТАВЛЕНИЕ ЗАДАЧИ 2.1. Введение Смысл слова задача как синоним слову проблема происхо- дит от значения греческого слова "баллейн"—бросать * (за- дача—"объект, брошенный вперед"). Это слово на француз- ском языке (ргоЫёте) родственно таким словам, как бал (bal), парабола (parabole), гипербола (hyperbole), символ (symbole), шабли (chablis). Помимо обычных задач, с которыми мы стал- киваемся ежедневно, имеется другой тип задач, с которыми мы знакомимся еще в начальной школе. Их существенной характе- ристикой является то, что они "полностью определены", т. е. четко описаны на подходящем каждому случаю языке. Чаще всего это язык математики. Способность к более или менее глу- бокому пониманию этого слова, связанных с ним "правил игры", его неявных указаний могут привести к разделению уче- ников на "физиков" и "лириков". Цель второго раздела данной главы — показать, что этот вопрос не так прост и человечество потратило тысячелетия на то, чтобы после множества попыток создать концепции, используемые сегодня, и этот процесс еще не закончен. К сожалению, большинство задач, с которыми встречаемся мы в реальной жизни после завершения школьного образова- ния, не являются полностью определенными. Чаще всего они описаны только частично и формулируются не нами, а кем-то другим, кто использует различные средства передачи информа- ции, различные представления окружающей реальности: голос и интонацию, жесты, рисунки. Основным средством передачи информации при этом служит естественный язык. Однако с точки зрения решения задач он обладает четырьмя существен- ными недостатками: естественный язык неполон, избыточен, не- однозначен и неточен. 2.2. Естественный язык Очевидно, что большая часть информации в .обычном диа- логе не выражается определенно и ясно. Обычно предпола- гается, что оба собеседника одинаково хорошо знают тему раз- говора. Однако, если эта гипотеза не подтверждается, стано- вится возможной полностью ошибочная интерпретация его 20 ГЛАВА 2 содержания. Применение так называемых технических требова- ний, в которых используются строгие спецификации; помогает устранить данный недостаток естественного языка. В естественном языке избыточность часто используется для того, чтобы отметить важность определенных моментов задачи, но при этом ничего не говорится о том, что настоящие трудно- сти при решении задачи связаны именно с этими моментами. Язык существенно неоднозначен (без этого нам было бы просто невозможно общаться). Однако неполнота и неодно- значность могут привести к полностью ошибочной интерпрета- ции. Наконец, обычный язык является грамматически некор- ректным и парадокс состоит в том, что это .самый несуществен- ный недостаток естественного языка. 2.3. Постановка задачи Поставить задачу означает прежде всего понять условия за- дачи (т. е. удалить неполноту, избыточность и неоднозначность) или, другими словами, найти соответствующее представление. На этой стадии часто используется другой тип представления, сильно отличающийся от языка, — графическое представление. Зрительная система человека является великолепным средством сбора и обработки информации. На самом деле задача понята только тогда, когда найдено такое представление, в котором все элементы задачи представлены без избыточности и много- значности. В этом случае пространство поиска решений хорошо определено и чаще всего основная трудность решения уже вы- явлена. При этом прагматика и семантика задачи представлены в основном в формализованном виде. Задача становится одно- временно и более абстрактной, и более строгой. В этом случае говорят о задаче в замкнутой форме или о замкнутой формули- ровке задачи. 2.4. Задачи в замкнутой форме В наиболее общем виде условия задачи математически мо- гут быть записаны следующим образом: Найти в заданном множестве Х точки х, удовлетворяющие множеству заданных ограничений К(х). Примером такой постановки может служить сформулирован- ная в неявном виде задача Бине: "из множества целых нату- ральных чисел х выбрать такие числа, которые удовлетворяют уравнению х3 + 84 == 37х". Примечания. 1. Задание пространства Х означает в общем случае одновременное (но неявное) задание структуры Х и раз- ПРЕДСТАВЛЕНИЕ ЗАДАЧИ 21 решенных операций над X. Знание Х является определяющим в исходных данных. 2. Первоначально полученную замкнутую формулировку за- дачи можно в общем случае снова перевести в другую форму, чтобы с учетом ограничений К.(х) уменьшить пространство Х и улучшить таким образом .представление задачи. Задача ре- шается именно в процессе последовательных изменений пред- ставлений, причем последняя замкнутая формулировка дает не- посредственно решение задачи. Существуют два, основных варианта представления задачи в замкнутой форме. Вариант 1 Пространство содержит исходное состояние 50, заданы ко- нечное состояние 51 и конечный перечень операторов Oab, кото- рые позволяют перейти от одного состояния Sa к другому со- стоянию Sb. Речь идет о том, чтобы найти путь от SO к S1. В качестве примера рассмотрим "игру в пятнадцать": 50= 2 а 6 7 12 9 10 3 15 5 1 8 4 13 14 11 51= 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 а Здесь операторы Oab имеют следующий смысл: переход из од- ного состояния в другое производится последовательным пере- мещением занумерованных фишек на пустое место. Замкнутая формулировка задачи в рассматриваемом варианте имеет вид Х == (Последовательность операторов). Решение х есть на самом деле определенная последователь- ность x=(0ab, Obc, . . ., Otu, Ouv), где Sa =SO, Sy ==S1. Множество ограничений К(х) выражается в правиле следо- вания операторов, причем конечное состояние для оператора является начальным состоянием для последующего. Вариант 2 Здесь речь идет о классической формулировке задачи на до- казательство в математике: 22 ГЛАВА 2 Получить С(х), исходя из Н(х). Примером задачи в такой постановке является следующая задача: Показать, что для всех п, п Е N •,2 п / п \2 ^ч.^о 1=1 \t"l / Этот вариант сводится к предыдущему, если положить SO = = Н (х) и 51===С(х). Существенное отличие состоит, однако, в том, что операторы перехода от одного состояния к другому не заданы. Искусство математика как раз и заключается в том, чтобы отыскать те операторы, которые окажутся полезными для данного условия задачи. Часто конечное состояние С(х) вовсе не задано. Тогда наша задача формулируется следующим образом: "Рассчитать ^ Р" и становится совсем неопределен- ной, так как критерий остановки процесса решения оказывается субъективным. Обычно ожидается, что в процессе решения за- дачи результатом будет выражение "более простое", чем на- чальное. Однако простота выражения также не является строго определенным понятием с математической точки зрения. 2.5. Общий подход к решению задачи Подход человека к решению задачи включает семь основ- ных этапов: 1. Выяснение смысла условий задачи. 2. Первые выводы из условий задачи. 3. Проигрывание ситуации. 4. Обдумывание. 5. Выбор наилучшего представления — поиск замкнутой формулировки задачи. 6. Частичное (возврат к этапу 2) или об.щее решение задачи. 7. Проверка и обобщение решения. Этап 1 существенно зависит от наших органов восприятия (слуха и зрения). Более того, поскольку человек обычно обла- дает ограниченными способностями к немедленному запомина- нию, необходимо длительное осмысление условий задачи. На этапе 2 используются накопленные человеком знания, чтобы, во-первых, восполнить недостающую в условиях задачи инфор- мацию, и во-вторых, заменить длинные словесные фразы, со- держащиеся в условиях задачи, на более подходящие и удоб- ные для преобразований представления (такие, например, как рисунки, графы, алгебраические выражения). Отметим, что уже начиная с 1962 г. простые программы, ос- нованные на использовании ключевых слов, были способны ре- ПРЕДСТАВЛЕНИЕ ЗАДАЧИ 23 шать несложные задачи из области физической кинетики (Bob- row, 1962) и теории вероятностей (Gelb, 1964). Этап 3 является по крайней мере для человека основопола- гающим. Речь идет прежде всего о том, чтобы, возвращаясь к этапам 1 и 2, удостовериться, что ничто не пропущено и нет су- щественной ошибки в интерпретации условий задачи. Во вто- рую очередь речь идет о том, чтобы определить, в чем же со- стоит сложность задачи. Этап 4 также является основным. На этом этапе необходи- мо очистить нашу память от "фактов-паразитов", связанных с первоначальной формулировкой задачи, и найти лучшие опера- торы для новой замкнутой формулировки задачи. Отметим, что на этом этапе нередко практикуется следующий прием: на вре- мя отвлекаются от задачи и занимаются чем-нибудь другим. Мы по своей природе настолько программируемы, что забыва- ние является часто единственным способом автоматически про- гнать из памяти старые идеи и создать условия для возникно- вения новых. "Отвлечение" от задачи является прекрасным ме- тодом ее решения. На этапе 5 достигается формулировка задачи в замкнутой форме, т. е. ей придается полный, однозначный и безизбыточ- ный вид. Трудность решения задачи на этом этапе можно оце- нить более точно, исходя из размера пространства поиска X, сложности ограничений К{х) и числа разрешенных операций. На этапе 6 почти всегда удается получить наилучшее представ- ление благодаря малому пространству поиска. После того как новая замкнутая формулировка задачи получена, цикл решения можно повторить снова, начиная с этапа 2. На -этапе 7 процесс решения задачи заканчивается. Затем полезно вернуться к первому этапу, чтобы обсудить решение с заказчиком, удостовериться в адекватности решения исходной формулировке, проверить, как ведет себя полученное решение в предельных точках, а также оценить степень влияния сущест- венных входных параметров на результат. Интересно исследо- вать общность использованного подхода, рассмотрев такие вопросы: • Можно ли обобщить данную задачу, сохранив используе- мый метод решения? • Существуют ли другие задачи, к которым может быть успешно применен тот же метод решения? • Существуют ли другие методы решения для той же задачи? Проиллюстрируем проблемы, типичные для первого и вто- рого этапов решедия задачи, рассмотрев ситуации, представлен- ные на рис. 2.1—2.4. 24 ГЛАВА 2 Пример с фигурой, изображенной на рис. 2.1, хорошо изве- стен. Изображенная здесь фигура может рассматриваться как Рис. 2.1. Рис. 2.2. Рис. 2.3. куб с передней гранью, расположенной внизу слева, или же, на- оборот, как куб, в качестве передней грани которого рассматри- вается грань, расположенная справа вверху (в предыдущем рассмотрении она была задней). Этот пример доказывает, что наша зрительная система постоянно осуществляет интерпрета- цию изображения. Это становится более очевидным при рас- смотрении рис. 2.2. Поворачивая рисунок, можно попеременно видеть в нем то дом, то пляжную кабинку, то брусок, срезан- ный "в угол" с одного конца. На рис. 2.3 требуется провести Рис. 2.4. Рис. 2.5. через каждую из 9 точек ломаную линию, не отрывая каранда- ша от бумаги так, чтобы получилось не более 4 линейных фраг- ментов. Если при решении этой задачи пытаются провести ло- маную прямую внутри квадрата, состоящего из девяти точек, то решения найти невозможно. Однако приведенная формули- ровка задачи на самом деле не накладывает такого ограниче- ния. (Решение задачи показано на рис. 2.5.) Что касается задачи на рис. 2.4, где требуется построить 4 равновеликих тре- угольника, используя для этого 6 спичек, то 2 лишних ограни- чения, которые мы, как правило, подразумеваем, и которых нет в условиях задачи, должны быть сняты, чтобы отыскать реше- ния. Другими словами, спички могут пересекаться и решение не обязательно должно быть плоским. Теперь легко находятся два ПРЕДСТАВЛЕНИЕ ЗАДАЧИ 25 решения задачи: одно в плоскости (рис. 2.6), другое решение— объемное (рис. 2.7). Следующий пример касается задачи, сформулированной на обычном разговорном языке. "Один жестокий король заточил в подземелье молодую де- вушку за то, что она не захотела выйти за него замуж. Истек Рис. 2.6. Рис. 2.7. год заключения, но девушка не отказалась от своего решения. Тогда король приказал вывести ее во двор замка и предложил ей следующее. Король выберет среди камешков двора два (черный и белый) и спрячет один в правой руке, а другой в ле- вой. Если девушка выберет руку, в которой окажется белый камешек, она будет освобождена, но если в руке окажется черный камешек, девушка выйдет замуж за короля. Девушка приняла эти условия с большой тревогой, которая переросла в ужас, когда девушка заметила, что король поднял с земли только черные камешки! Как же ей поступить?" При формальном подходе задача, поставленная таким обра- зом, не имеет решения. Однако на самом деле нарушение коро- лем условия задачи о выборе из двух камешков разного цвета обернулось против него. Девушка выхватила один камешек из рук короля и как бы нечаянно уронила его на землю, где его нельзя было отличить от других таких же камней. "Ах, изви- ните меня, — воскликнула девушка, — но теперь по цвету того камешка, который остался у Вас, Ваше Величество, мы опреде- лим цвет того камешка, что решит мою судьбу." И так как это был черный камешек, то девушка стала свободной. Эти простые примеры показывают, что первый и второй этапы решения задачи в общем случае частично перекрывают- ся. Отсюда, в частности, вытекает, что задача в том виде, как она "понята", не имеет решения, и только отыскивая решение, выделяют истинную задачу, устраняя лишние ограничения. 26 ГЛАВА 2 Другой, но относительно часто встречающийся случай, когда мы не можем в явном виде представить условия задачи, отно- сится к решениям типа "все или ничего". В этом случае реше- ние возникает мгновенно после внутренней подсознательной ра- боты. В качестве примера приведем следующую задачу. "Допустим Вы одни в пустой комнате, где имеются два иден- тичных железных бруска, один из которых намагничен, а дру- гой — нет. Необходимо определить, какой из брусков намагни- чен. Бруски тяжелые, твердые, прочные. Ничего другого у Вас не имеется". Такое условие является единственным в своем роде. Мы обезоружены. Число операторов, т. е. возможных действий, Рис. 2.8. Два квадрата со сторонами (а-\-Ь}, используемые при доказатель- стве теоремы Пифагора. крайне невелико. Велико искушение опустить руки и признать, что задача не имеет решения. Поразмышляйте еще немного прежде, чем прочтете следующее: решение задачи существует, и оно очень простое. Ситуация несколько похожа на предыдущую. Проблема в том, чтобы "разорвать" симметрию. Но в даяном случае ре- шение должно'основываться на знании физики и на том, что единственными предметами, доступными для манипуляций, яв- ляются эти два бруска. Магнитное притяжение проявляется со- вершенно симметрично в отношении обоих брусков, за исключе- нием единственного места, а именно середины намагниченного бруска. Этот участок не намагничен. Достаточно приставить ко- нец одного из брусков, например бруска А, к середине другого бруска В, и если притяжения не происходит, намагничен бру- сок В, а если бруски притягиваются, намагничен брусок Л. Третий этап, связанный с проигрыванием ситуации, является наиболее важным в начале решения. Прежде всего покажем на ПРЕДСТАВЛЕНИЕ ЗАДАЧИ 27 очень простом примере, как уже этот этап может помочь найти интересные решения. Например, как доказать теорему Пифагора, используя ли- нейку и экер (прямоугольный чертежный треугольник)? Есте- ственной является мысль рассматривать экер в качестве прямо- угольного треугольника из теоремы, где а и b — его катеты, а с—гипотенуза. Чтобы возникла величина (а + b) на чертеже, надо расположить экер вдоль линейки двумя различными спо- собами. Полученные в результате построения два квадрата рав- ной площади со стороной (а + b} показаны на рис. 2.8. Пло- щадь 5 большого квадрата по построению равна (а+&)2, и если Т есть площадь треугольника, то площадь 5 правого боль- шого квадрата равна 4Г + с2, а площадь 5 равного ему левого квадрата равна 4Г + а2+ b2, что доказывает теорему. 2.6. Пример полного решения задачи Рассмотрим пример, в котором охватывается весь процесс ре- шения от первых этапов до получения замкнутой формулиров- ки задачи и ее последующего решения. "Пусть имеется шахматная доска, каждая сторона которой содержит 100 клеток. Все 10000 полей доски заняты черными шашками. В нашем случае разрешенными ходами являются "модификации", т. е. операции замены в каком-то ряду (строке или столбце) всех шашек ряда черного цвета на белые и белых на черные. Спрашивается, можно ли за конечное число ходов получить 1990 белых шашек, начиная с позиции, когда все шашки были черными?" На обычном языке это условие задачи легко формулируется и понимается. Однако, во-первых, ответ на поставленный воп- рос не возникает сам по себе, а во-вторых, "проигрывание си- туации" затруднительно, так как доска размером 100 X 100 не является обычной. Чтобы уловить смысл задачи и сделать неко- торые первоначальные заключения, т. е. создать очевидные пред- ставления условий, естественно рассмотреть задачу с умень- шенными параметрами, например использовать доску размером 4Х4 или в качестве доски использовать абстрактный квадрат со стороной неопределенной длины. Первый вывод заключается в том, что как только сделан первый ход, то тут же появляются и белые шашки. Этот общий вывод устраняет странность, бросающуюся в глаза при знаком- стве с условиями задачи. Дело в том, что в них говорится о бе- лых шашках, хотя речь вести о них имеет смысл, только начи- ная со ьторого хода. Другие заключения появляются после того, как будут проведены несколько партий на модели доски. 28 ГЛАВА 2 Порядок следования этих заключений-выводов определяется индивидуальными особенностями человека, решающего задачу. 1. Если дважды подряд модифицируют один и тот же ряд, исходная позиция не изменяется. 2. Порядок ходов при модификациях безразличен. Это опре- деляется тем, что разные строки, как и столбцы, не имеют меж- ду собой общих шашек. У пересекающихся строки L; и столб- ца С; имеется только одна общая шашка на их пересечении, ко- торая и не изменит цвета при "одновременной" модификации р строки и столбца, тогда как остальные шашки этих строки и столбца изменят цвет на противоположный. Рис. 2.9. Зоны расположения белых и черных шашек на шахматной до- ске. Отметим, что данный вывод о независимости результата от порядка ходов-модификаций, являясь практически очевид- ным для взрослых, не является таковым для детей. Он соот- ветствует четвертой стадии раз- вития интеллекта (по Пиаже) и не формируется обычно ра- нее десятилетнего возраста. 3. После того как сделан ход, номер ряда не является суще- ственным, так как в задаче важным является лишь число ша- шек того или иного цвета, а не место их расположения на доске. 4. На основании двух первых заключений можно сделать вывод, что порядок ходов в задаче не является существенным и результирующее состояние ряда то же при 2п 4- 1 ходах, что и при одном ходе-модификации. Аналогичным образом, состояние ряда одинаково как при 2п ходах, так и при 0 ходах. 5. На основании третьего вывода можно строки, которые были модифицированы один раз, перенести в верхнюю часть доски, а столбцы, которые также были модифицированы один раз, перенести в левую часть доски. Таким образом, доска ока- жется разбита на четыре зоны, которые показаны на рис. 2.9. Прямоугольные зоны на доске слева вверху и справа внизу за- полнены черными шашками, причем одни из них перевернуты дважды, а другие ни разу. Прямоугольные зоны слева внизу и справа вверху заполнены белыми шашками, причем они все пе- ревернуты по одному разу. 6. Число строк L в верхних и число столбцов С в левых прямоугольниках соответствуют рядам шашек, модифицирован- ных один раз. ПРЕДСТАВЛЕНИЕ ЗАДАЧИ 29 7. Представленная на доске позиция обладает симметрией относительно строк и столбцов. Если (L, С) — решение задачи, то и (C,L), полученное вращением позиции на 90°, также будет решением. 8. Рассматриваемая позиция обладает еще и центральной симметрией. Если (L, С)—решение, то и (100—С, 100—L) также будет решением задачи. Это свойство уже менее очевид- но, чем предыдущие. Примечание. Ниже приведены некоторые рассуждения, ко- торые не являются доказательством. В данном случае формали- зация условий задачи затруднена, так как описанные на обыч- ном языке они носят неполный и неоднозначный характер. Именно поэтому необходим переход (и это общий необходимый этап для всех задач) к замкнутой форме условий задачи, где все четко определено и согласовано. Теперь сформулировать эти условия уже легко. В задаче величины L и С являются целочисленными. С их помощью под- считывается число модифицированных рядов. Так число белых шашек составит: вверху—LX (100—С) и внизу—СХ X (100—L). В результате замкнутую формулировку задачи можно записать в виде (2.1) Очевидно, что никогда нельзя получить нечетное число бе- лых шашек. На этом этапе для получения нового, более общего представления о задаче целесообразно ее несколько обобщить. Ее можно сформулировать так: путь р—середина доски и га— число, равное половине заданного числа белых шашек. Тогда, если разделить на 2 обе части равенства (2.1) и использовать для записи обозначения р и п, получим p{L+C)-LC==n. (2.2) Итак, во-первых, трудности решения задачи связаны с цело- численным характером уравнения (2.2); во-вторых, равенство (2.2) напоминает уравнение конуса: {ху—ах—by—с=0); в-третьих, решение этого уравнения затрудняется тем, что в него входят как линейные члены p(L + С), так и квадратич- ные — LC. Оба последних заключения по поводу уравнения (2.2) можно резюмировать следующим образом. Так как конус обла- дает двумя осями симметрии, используем этот факт и сделаем равенство (2.2) более компактным и удобным для последую- щего применения. В этом случае можно исключить линейный член из равенства (2.2). Сделаем замену переменных, положив 30 ГЛАВА 2 L=l + а, С = с + а. В результате получим /? (/ + с + 2а) - (/ + а) (с + а) = /г, Чар + р (I + с} — а (I + с) — 1с — а2 = п. Положив а •= р, добиваемся того, что в равенстве останутся только квадратичные члены. Такая замена, вообще говоря, не является произвольной, так как на самом деле она отражает тот факт, что распределение шашек по цвету на доске является симметричным по отношению к центру доски. Теперь замкнутая формулировка условий задачи приобретает новую форму [с=р2-п, (2.3) где I == L — р, с = С — р. Выражение (2.3) определяет представление условий задачи в трехмерном пространстве, причем слева и справа от знака равенства находятся целые числа. Целое число, стоящее в пра- вой части, на самом деле известно: pi —п= 50 X 50 — 1990/2 = 1505. Для существования решения необходимо, чтобы число 1505 было разложимо на простые множители, сопоставимые с разме- рами доски. Итак, мы имеем 1505 = 5 X 7 X 43, а так как р == = 50, то —50 sS / s$ +50, —50 ^ с ^ +50. В данном случае существуют два решения, удовлетворяю- щих этим условиям. Первое решение /=5Х7, с ==43, L==85, С =93 С" наоборот). Второе решение /=-35, с ==-43, L=15, С=7. Таким образом, имеются два варианта получения на доске 1990 белых шашек. С другой стороны, существуют такие числа для белых ша- шек, получение которых невозможно. Например, если п==1984, имеем р2— п== 2500— 992== 2 Х2Х 13Х29, и тогда одна из двух величин—либо /, либо с—превышает число 50, что недо- пустимо ни для одного решения задачи. Наконец, имеется особый случай, когда либо У, либо с равно нулю, т. е. L или С равно 50. Это вырожденный случай, и ка- ково бы ни было здесь значение другой неизвестной, единствен- ное число, которое удовлетворяет условиям задачи, будет п == = р2 = 2500. ПРЕДСТАВЛЕНИЕ ЗАДАЧИ 31 Все задачи этого класса могут быть решены одним и тем же методом (включая сюда и задачи не только на квадратной, но и на прямоугольной доске). Что касается других методов реше- ния задач с условиями типа (2.1), т. е. в целых числах, то мы найдем их в гл. 3 и 6. Следующий раздел главы взят из книги Д. Пойа "Как ре- шать задачу" (George Poiya, How to solve it, 1956). 2.7. Что нужно сделать, чтобы решить задачу? 1. Понять задачу. • Что является неизвестным? Каковы исходные данные? Каковы условия задачи? • Можно ли удовлетворить условиям задачи? Достаточно ли заданных условий для отыскания неизвестной? Являются ли условия задачи недостаточными, избыточными или противоре- чивыми? • Сделайте рисунок. Введите соответствующие обозначения. • Выделите отдельные части условия задачи. Можете ли вы их сформулировать? 2. Составить план решения. • Определите взаимосвязь между исходными данными и не- известной. • Возможно, вам следует рассмотреть какие-то дополни- тельные задачи, если не удается непосредственно найти эту взаимосвязь. • В конце концов вы должны получить план решения. • Вы уже встречали эту задачу? Или, может быть, вы встречали похожую задачу? • Может быть, вы знаете задачу, связанную с этой? Изве- стна ли вам какая-нибудь теорема, которая может быть по- лезной? • Рассмотрите искомое и попытайтесь вспомнить задачу, которая вам уже известна и в которой отыскивалось то же са- мое или нечто подобное. • Перед вами задача, которая связана с рассматриваемой и которую вы уже решали. Можете ли вы использовать резуль- таты, полученные при ее решении? Можете ли вы воспользо- ваться использованным методом решения? Может быть, следует ввести какой-то дополнительный элемент, чтобы воспользовать- ся этим методом? • Могли бы вы сформулировать задачу по-другому? Смогли бы вы дать еще одну формулировку задачи? Обратитесь мыс- ленно к определениям. 32 ГЛАВА 2 • Если вы не можете решить задачу, которая вам предло- жена, попытайтесь решить задачу, связанную с ней. Не можете ли вы припомнить задачу, которая была бы связана с вашей, но была бы разрешима? Более общая или более частная зада- ча или аналогичная вашей? Смогли бы вы решить часть за- дачи? Оставьте только часть условий, необходимых для другой части задачи. В какой мере может быть теперь определена не- известная, как можно ею варьировать? Можете ли вы извлечь из данных что-то полезное? Не приходят ли вам ,на ум другие данные, которые могли бы помочь определить неизвестную? Можете ли вы изменить неизвестную, или исходные данные, или и то и другое, если это необходимо, так, чтобы новая неиз- вестная и новые данные лучше соответствовали друг другу? • Вы использовали все исходные данные? Вы использовали условия задачи в полном объеме? Вы учли все существенные стороны задачи? 3. Выполнить план. • Выполняя принятый план решения, проверяйте каждый его этап, каждый элемент последовательно один за другим. Очевидно ля вам, что этот элемент плана корректен? Можете ли вы доказать его корректность? 4. Проверить полученное решение. • Можете ли вы проверить полученный результат? Можете ли вы проверить проведенные рассуждения? • Можете ли вы получить результат, отличающийся от уже полученного? Можете ли вы это понять с первого взгляда? • Можете ли вы воспользоваться полученным результатом или методом решения для какой-нибудь другой задачи? 2.8. Из истории развития и преподавания математики Собственно математике предшествует длительная предысто- рия порядка четырех тысяч лет. Высшие животные и совсем маленькие дети воспринимают в окружающем мире две основ- ные абстрактные сущности: число и форму. Таким образом, арифметика и геометрия длительное время были двумя отдель- ными фундаментальными науками. В древности различение чи- сел человеком не было вполне ясным и точным. В первобытных обществах челове^к не различал две совокупности, содержащие почти равные количества элементов. Он едва умел считать: один, два, много. В латыни понятие "много" обозначается словом tres, продолжающем и сейчас жить во французском языке в виде слова trois (три)! ПРЕДСТАВЛЕНИЕ ЗНАНИЙ 33 Звездные миры были замечены наблюдателями, принадле- жавшими к самым древним цивилизациям, которые постоянно наблюдали скопления звезд на небе. Мы знаем также, что шу- меры Урука и Ниппура еще три тысячи лет тому назад уже пользовались лунным календарем. Им пришла идея представ- лять числа с помощью символов. При этом Луна обозначала единицу, а другие небесные объекты — последующие числа. Необходимость делать расчеты и затем записывать их резуль- таты привела к использованию более удобных обозначений. Вертикальной или наклонной чертой стали обозначать единицу в Финикии, Сирии, Древней Греции, Южной Аравии, Индии. Совокупности из пяти, десяти или двадцати единиц стали обоз- начать специальными символами, образованными от их назва- ний. Все это были аддитивные системы счисления, т. е. закоди- рованное ими число представляло собой сумму записанных сим- волов. В Вавилонии была изобретена своя 60-ричная система счис- ления. Ее основные символы имели значения 1, 10, 60, затем 600, 3600, 36 000 и т. д. Эта система используется и в наши дни, в частности в астрономии для определения мер времени и угловых мер. Многие народы использовали идею представле- ния чисел при помощи букв своего алфавита. Стали придавать особый смысл определенным числам, что породило кабалистиче- ские вычисления. Число, соответствующее какой-либо букве, становится функцией положения буквы в слове. Стала ощу- щаться необходимость в обозначении понятия "ничего". Проис- хождение нуля до сего времени остается неясным. Можно счи- тать установленным, что в индийскиих текстах шестого века нуль обозначался точкой. В астрономических записях древних греков нуль обозначался буквой О, являвшейся начальной бук- вой греческого слова ov6ev, обозначавшего "ничего". Современное написание цифр нашей десятичной системы счисления пришло к нам из Западной Индии через арабов. Только в 13 в. эти цифры проникли в Италию через флорентий- ских купцов. Их использование стало повсеместным в 15 в. Следы истории их появления остались в словах "цифра" и "зе- ро" (нуль), которые происходят от арабского слова sifr (zero). С изобретением книгопечатания (1440 г.) цифры принимают окончательную форму. Использование запятой в вещественных числах распространяется только в XVIII в. Четыре арифмети- ческих действия знали еще египтяне, но их представление ча- сто было очень неудобным. Так, смежное расположение чисел обозначает сложение, а греческая буква ^ — вычитание. Пере- писчики в средние века выработали окончательную форму 2 Ж.-Л. Лорьер 34 ГЛАВА 2 знака 4- из слова et (и). Знак — появился из обычая отделять в счетах чистый вес от веса тары с помощью горизонтальной черты. Отметим, однако, что Марсель Коэн в своей интересной книге "Великое изобретение—письменность и ее эволюция" пишет, что знаки + и — появились как сокращения слов plus (плюс) и minus (минус). Современные знаки умножения и де- ления были введены в 17 в. Равенство обозначалось в Европе 17 в. знаком оо, который использовался астрономами для обо- значения созвездия Тельца. Одновременно для той же цели ис- пользовалось латинское слово aequalis. Оно сначала было уко- рочено до ае, а затем превратилось в знак ==. Тогда символом оо стали обозначать число 1000. Около 1660 г. Дж. Уоллес стал обозначать этим знаком бесконечность. Мы рассказываем обо всем этом по двум причинам. Во-пер- вых, чтобы показать, что человечество потратило многие ты- сячи лет для "приручения" числа, а наука и вовсе развивается только несколько веков. Математика возникла не в один день, и ее детство еще недалеко от нас. Что же удивительного в том, если у какого-то школьника встречаются трудности в овладении предметом, когда человечество затратило так много времени, чтобы выработать представление чисел и операций. Во-вторых, вопрос о представлении конкретных или абст- рактных объектов является центральным для искусственного интеллекта. Дать представление чего-то означает прежде всего умение выделить из общей массы объект, выявить его важность и практическую ценность. Отсюда следует, что его свойства должны быть определены и переведены в форму, удобную для манипулирования с ним. Таким образом, дать представление означает понять. Если сегодня биология начинает объяснять представление наследственной информации в генах живых су- ществ, то нейрологи и психологи еще далеки от того, чтобы дать объяснение тому, каким образом в нашем мозге закодиро- ваны и организованы наши знания. Не исключено, что исследо- вания в области искусственного интеллекта дадут какие-то от- веты на этот вопрос. Уже во времена Евклида (третий век до нашей эры) гео- метры умели обозначать абстрактные объекты с помощью букв. Папус Александрийский (третий век), а затем Диофант (чет- вертый век) постепенно вводят подобные обозначения для не- известных чисел. Франсуа Виет, докладчик в Государственном совете при Генрихе IV, в своем трактате "Искусство анализа" первым ввел систематическое использование такого буквенного представления и^таким образом является праотцом современной алгебры. В сочинениях Виета встречаются, например, такие вы- ПРЕДСТАВЛЕНИЕ ЗНАНИЙ 35 ражения: Я in D -\ - F in D \ aequebitur A ~F + D\ Первые буквы алфавита (Л и D) заменяют неизвестные ве- личины, слово in стоит вместо знака умножения, линейная фор- ма-записи выражений еще неизвестна. В современных обозна- чениях это выражение выглядит так ау-Ьу ^ Ь+ у Виет уже умеет оперировать с такими выражениями. Напри- мер, он выводит из предыдущего выражения следующее: " (F + D) так относится к (H—F), как D к Л". Это дает ему возможность решать уравнения. Декарт в XVII в. нормализует и расширяет этот формализм. Он ввел в обращение наши знаки операций +> —, *, I и предло- жил употреблять последние буквы алфавита для обозначения неизвестных. Символ х пришел к нам от арабов (от слова says, обозначающего какой-то предмет, нечто). Именно Декарт от- казался от использования классических обозначений, пришедших из греческого и древнееврейского письма, в пользу современных обозначений. Наконец, Декарт объединил науки о числах и фи- гурах, заложив основы аналитической геометрии, и тем самым установил глубокое единство математики, которое было еще углублено в последующие века. Индексы и показатели появляются довольно поздно. Так Эйлер (1707—1783) использует выражение х*х*х для х3, и только Эварист Галуа (1811—1832) первым начинает пользо- ваться индексами. Но еще Жордан и затем сам Гильберт в на- чале нашего века не приняли этого новшества и продолжали писать в тяжелой и неудобочитаемой манере, когда порядок букв в алфавите играл роль неявной индексации. Функциональ- ные символы были введены Лейбницем и Иоганном Бернулли. Знак суммирования ^ был введен Эйлером. Введение обозначений для функций проходило не без труд- ностей, причем единогласия в этой области не имеется еще и до сих пор. Постоянно смешиваются сама функция f и ее зна- чение в точке f(x}. Часто пишут TJt-a(f(x\)) вместо Т+а(Л. Производная почти- всегда смешивается с ее значением. Эта ошибка вызывается принятыми обозначениями. Еще более во- пиющими являются такие ошибки в случае частных производ- ных. Проблема обозначений усложняется, когда требуется 2* 36 ГЛАВА 2 рассматривать выражение как функцию от одной из его состав- ляющих. Так, в физике или механике пишут y{t), рассматривая у как функцию времени, а затем записывают у{х), рассматри- вая ее как функцию положения, и наконец, просто у как функ- цию вообще. Такие обозначения являются неприемлемыми из-за их непо- следовательности и сложности для начинающего. Но, с другой стороны, проблема усложняется тем, что невозможно ввести свой символ для каждой функциональной зависимости. Черч и Карри в 1950 г. предложили ^-запись: символы \х перед каким-либо выражением трансформируют его в функцию от х. Таким образом линейная функция от х записывается в виде 'kx(ax-{-b). Это представляет собой весьма элегантное решение проблемы. Здесь лежит начало языка программирова- ния Лисп, созданного Маккарти в 1960 г. Символическая ло- гика и язык теории множеств возникают очень поздно. В 1891 г. Пеано ввел знак принадлежности & Включение обозначается как ос или <;, и затем позже Хаусдорф вводит в 1920 г. обозна- чение ст. Именно это обозначение сегодня является предпочти- тельным. После различных попыток ввести собственные обозна- чения сегодня снова наиболее распространенными для обо- значения пересечения, объединения и импликации являются обозначения Пеано П, LL ^>. Последний символ является обрат- ным к символу включения. Так, если Е с: F, то (х & Е} =з ^з (XE.F). Гильберт пользуется стрелкой ->- для обозначения импликации. Такое обозначение совпадает с обозначением ото- бражения в теории множеств и со знаком переписывания. Шко- ла Бурбаки предпочитает для импликации знак =>, который широко используется сегодня. Что касается нас, то мы предпо- читаем, как и логики, пользоваться обозначениями Пеано. Чтобы сделать наглядными логические рассуждения, Эйлер использовал идею диаграмм типа кругов, отражающих множе- ства и получивших название диаграмм Венна (1834—1923). Льюис Кэрролл (1882—1898) предложил другой тип диаграмм, которые сохраняли свойства сопряженности между множеством и его дополнением. Это нашло применение в булевой алгебре. Под влиянием символов U и П логические ИЛИ и И стали обозначаться соответственно V и А. Отрицание иногда обозначается знаком —, иногда чертой сверху или знаком ~ (тильда). Так как все эти знаки имеют и другое значение, то Хейтинж предложил в 1937 г. использо- вать для обозначения отрицания знак ~1, который принят в этой книге. Квантор существования 3 был также введен Пеано. Рассел и Уайтхед (1903) дополнительно ввели еще квантор всеобщно- ПРЕДСТАВЛЕНИЕ ЗНАНИЙ 37 сти, для обозначения которого они просто заключали перемен- ную в скобки. Только гораздо позже (в 1920 г.) был введен для него знак V. Г. Фреге (1848—1925) ввел знак утверждения, для которого он использовал обозначение 'г-. Так, выражение "1—Л" означает "по Л". Группа французских математиков, публикующая свои труды в виде монографий "Элементы математики" под псевдонимом Никола Бурбаки, как бы "узаконила" использование значитель- ного числа таких символов и ввела в свою очередь еще ряд новых символов (среди них уже упоминавшийся знак =>, обо- значение С для дополнения множества и многочисленные обо- значения в теории групп). Эти монографии, переведенные на многие языки мира, сделали многое для стабилизации обозна- чений, манеры и стиля современной математики. Однако посте- пенно формальный язык стал сильно отличаться от обычного языка. Там, где в обычном языке встречаются "разделители" (союзы) "и", "или", "так как", математик предпочитает исполь- зовать такие группирующие символы, как круглые, квадратные или фигурные скобки и горизонтальные черточки. Символ равен- ства, обозначающий идентичность двух объектов, предпочитают использовать в качестве разделителя. В результате между обы- чным языком и языком математики образовалось определенное смешение способов выражения. Поэтому очень наивно выгля- дят некоторые математические выражения, например "для вся- кого у -== ax + Ь", в котором символ у может иметь двоякий смысл. На самом деле это выражение следовало бы записать так: Vy, у == ах + Ь, тогда как предыдущую запись, строго го- воря, надо прочитать так: каково бы ни было равенство типа у == ах + Ь. На практике часто путают обычное значение знака ==, . описанное выше, и его роль в качестве оператора присваивания. Таким рбразом, идентичность, выражаемая с помощью знака равенства, например такая, как (а—Ь)2 = а2—2аЬ + Ь2, яв- ляется таким же правилом переписывания, как х+ 0->-0 или X-I—-JC. Знак == служит также для задания определений, на- пример в выражении tg х == sin x/cos х, и, кроме того, еще и для ввода сокращенных обозначений. Например, положим и == = (ах + b) / (х2-г \) или х', х" == (— Ь ± л/А)/2, где правая часть используется в виде самостоятельного блока. Другой тип неопределенности, присущей обычному языку, встречается и в математическом языке. Например, когда опре- деляют какую-то группу G, вначале постулируют, что- для всех g из G существует е, такое, что ge = g и eg = g. И затем про- должают: Vg, g-<=G, 3g~1, g^'sG, g 'g=e, gg \==e. Тут, однако, имеется некоторая неоднозначность, математического 38 ГЛАВА 2 языка, связанная с тем, что переменная е, существование кото- рой определяется вначале, не имеет никакого отношения к пе- ременной е из второй половины определения, хотя для их обо- значения использована одна и та же буква е. Такого рода неод- нозначности не могут не вызывать определенных затруднений у тех, кто разрабатывает системы автоматического доказательст- ва теорем. В связи со сказанным выше любой перевод с обычного язы- ка на язык математики должен производиться с осторож- ностью. Например, во фразе на французском языке "Un triang- le rectangle est un triangle qui a un angle droit" (Прямоуголь- ный треугольник — это треугольник, в котором один угол прямой), трижды встречается неопределенный артикль un (в со- четаниях со словами "прямоугольный треугольник", "треуголь- ник" и "прямой угол"). Однако если в первом случае артикль имеет смысл универсальности (любой прямоугольный треуголь- ник), то в третьем случае он употреблен в смысле существова- ния (т. е. "имеется, существует именно прямой угол"). Глаголы "быть, есть, является" служат иногда признаком того, что вво- дится какое-то определение, иногда признаком какого-то свой- ства, а иногда признаком принадлежности. Союз "или" используется иногда в качестве "или исключи- тельно" (например, белое или черное), а иногда как "или вклю- чительно" (например, много или мало), что соответствует двум различным понятиям в математике. Уже на ранних этапах обучения детям говорят о таких псев- доматематических выражениях, как: "два на два дает четыре" и "больше на меньше дает меньше". Этот тип необъясняемого рискованного приравнивания часто вызывает у детей непони- мание, из которого потом возникают неожиданные следствия. Например, учитель спрашивает: "Какое целое следует после га?" И ученик отвечает: "О". "Пусть целое Г|, V, Л), а также относиться к одному объекту (унарные опе- раторы -у , log, sin). Операторы типа "если ... то, ... иначе ..." ("если да ... то, ... если нет ...") встречаются в языках програм- мирования. В общем случае правильно построенное выражение или терм представляет собой n.-арный оператор вместе с п объ- ектами. По отношению к п-арному оператору говорят также, что его вес равен п. Правильно построенное выражение само может рассматри- ваться как новый объект, который в свою очередь может быть связан с другими объектами с помощью какого-то оператора, следуя тому же закону образования выражений, что и ранее. .В результате мы получаем терм — п-арный оператор вместе с н термами. Такое определение терма через-другие термы назы- вается рекурсивным. Оно имеет смысл только тогда, когда ап- риорно существуют исходные термы, являющиеся объектами, 42 ГЛАВА 2 Среди этих исходных объектов в общем случае некоторые могут быть заменены другими объектами или даже термами (переменные), а другие—не могут быть заменены (константы). Так, в тригонометрическом выражении sin2 х + cos2 х = 1 х мо- жет быть заменен любым термом, чего нельзя сказать ни о сим- волах 1 и 2, ни о символах sin и cos. Эти понятия будут уточ- нены в гл. 3 при рассмотрении формальных систем. 2.9.2. Линейные формы записи Книгопечатание привело математиков к тому, что они стали записывать свои формулы в виде линейной строки, читаемой слева направо в европейском мире. В этой форме записи, назы- ваемой линейной, существуют три возможности расположения оператора: впереди или позади термов, которыми они управ- ляют, или же между ними. Находят применение все эти три формы записи, но они не являются равнозначными. В наиболее общей форме записи, называемой инфиксной (или нефиксированной формой), операторы расположены среди термов и, чтобы облегчить чтение, приходится добавлять новые символы—скобки: (),[],{}, которые не входят в основной набор символов. Они не очень удобны при письме, и ими поль- зуются, только чтобы устранить неоднозначность или разделить на части слишком длинное выражение. Кроме того, для устра- нения неоднозначности условились об определенной иерархии применения операторов. Например, в алгебре выражение а — Ь + с будет интерпретироваться как (а — Ь) -\- с, а не как а—{Ь +с). Свойства ассоциативности и коммутативности не- которых операторов (и особенно операторов + и «•) неявно подразумеваются в обычном математическом анализе. Напри- мер, пишут 2 * х * у, или х * 2 * у, или у* х* 2, причем чаще всего оператор умножения * при записи формул опускается. Однако фантазия математиков идет дальше, и, например, унар- ные операторы записываются на трех уровнях. Основные вари- анты записи таковы: sin Л, В, С', dDfdt, E*, F, G', \G\. Знак— является одновременно унарным и бинарным оператором. Сле- довательно, обычная нефиксированная форма записи выраже- ний далека от определенности и строгости. < В математической логике предпочтительной является пре- фиксная форма записи. Каждый оператор в этом случае запи- сывается перед термами, которыми он управляет. Таким обра- зом, обычная запись "х оператор г/" приобретает вид "оператор ху", причем запись "оператор z" не изменяется. В этой форме записи любые скобочные системы становятся ненужными, а лаконичность и определенность формы записи с ПРЕДСТАВЛЕНИЕ ЗНАНИЙ 43 расположением оператора в начале каждого терма делает ее (после некоторой тренировки) весьма удобной для использо- вания. Выражение (р =э q) =з р, записанное в инфиксной форме, по- лучает в префиксной форме вид ^>^pqp. Выражение (Г) 1°g {у + Уг/2 — Ь/sin х) будет выглядеть так tog + У Л/ —1 г/2/6 sin х. Основная теорема префиксной формы записи. Последователь- ность 5 символов является правильно построенной в форме польской префиксной записи, если и только если: 1) ранг (S)==—1; 2) ранг (подпоследовательности слева от 5)^0, причем ранг (оператора) == вес (оператора)—1, ранг (пустой последовательности) == О, ранг (га-го символа) =п—1, ранг (переменной) == ранг (константы) =—1, ранг (S\ соединенной с 52)===ранг (SI) + ранг (52). Доказательство этой теоремы проводится по индукции на множестве символов S. Важным следствием этого результата является возможность построения алгоритма для отыскания в заданном выражении места, где заканчивается терм, который начинается в заданной позиции. Так, например, для идущей ниже последовательности симво- лов (Г) (с соответствующими им рангами) имеем для терма, который начинается, стрелкой, его окончание на знаке 2: log + у V — t у 2 / & sin x О 10 0 122 0100—1 ^ 10—1 Заметим, что запись в инфиксной форме, если она дополне- на скобками, может рассматриваться как префиксная запись и поддается верификации с помощью описанной выше процедуры. При этом открывающая скобка рассматривается как бинарный оператор, а закрывающая скобка — как константа. Другие ран- ги остаются при этом неизменными. Тогда, например, выраже- ние с бинарным оператором будет выглядеть так: ( а бинарный-оператор Ъ ) 10 1 0—1 44 ГЛАВА 2 В суффиксной (или постфиксной) форме записи оператор по- мещается сразу после соответствующих термов и выражение "х оператор г/" будет записано как "ху оператор', а выражение "оператор z" запишется как "г оператор". Выражение (Г) в суффиксной форме записи выглядит так: у у 2 л Ь х sin / — V + log Эта форма записи удобна, в частности, когда хотят оценить, т. е. вычислить, представленное выражение; например, при ма- шинных вычислениях или при компиляции языков программи- рования формулы, введенные в инфиксной форме, переводят в постфиксную форму. В такой форме записи при прочтении вы- ражения слева направо удается вычислить его значение за один проход (рис. 2.10а). у у 2 t Ь х sin / - V- + log 1 1-1- 2 t - 1 80 . тт/9 -80 81 9 -> 10 Рис. 2.10а. 2.9.3. Нелинейные формы записи При типографском способе печати линейная форма записи в виде строк не дает наглядного представления о структуре вы- ражений. Все символы выглядят равнозначными, хотя известно, что некоторые из них являются терминальными (переменные и константы), а другие нет. Если быть точным, то следует отме- тить, что каждый оператор управляет заданным числом извест- ных термов. Чтобы отразить этот факт, используются представ- ления выражений в форме чертежей или диаграмм. Примеры таких графических схем (графов) представлены ниже: Бинарный оператор if t2 - п-арныи оператор it /Z .... trt Графы такого типа получили название деревьев. Они хоро шо соответствуют нашим зрительным представлениям, напри- ПРЕДСТАВЛЕНИЕ ЗНАНИЙ 45 мер, о таких выражениях, как выражение (Т), граф которого представлен на рис. 2.106. Следует отметить тот факт, что такая форма записи содер- жит и три другие формы записи: log /\, • префиксная форма выявляется при просмотре дерева сверху вниз и слева направо при записи символов в том по- рядке, в котором они при этом встречаются; • постфиксная форма об- разуется при просмотре дерева в последовательности, обрат- ной предыдущей; sin. Рис. 2.106. Представление выраже- ния (Г) в виде дерева. • инфиксная скобочная форма записи образуется при проекции дерева на горизон- тальную ось, причем симво- лы каждого последующего уровня заключаются в скобки. Как уже отмечалось выше, ценность представления опреде- ляется тем, насколько удобно его обрабатывать. В математике основными процедурами обработки являются следующие: под- становка. одного терма вместо другого, группировка {объедине- ние) двух термов, удаление терма. Все -эти операции соответствуют очень простым операциям с соответствующим деревом, построенным для данного выражения, перемещению (перестановке) какой-либо ветви, локальной модификации тер- минальных символов — листьев, удалению какой-то ветви. Вме- сто этого при обычной инфиксной записи мы переписываем вручную построчно все выражение целиком. 2.9.4. Машинное представление выражений Память ЭВМ характеризуется большим объемом и высокой скоростью обращения к ней, что позволяет избежать ограниче- ний, присущих возможностям человека, передав ЭВМ обработку структур типа дерева. При этом каждому символу какого- либо выражения соответствуют три определяющие его характе- ристики: собственно имя символа, имя символа-"сына", распо- ложенного слева от основного символа, и имя символа-"брата", расположенного справа. "Сыновьями" являются первые симво- лы соответствующих термов. Множество имен символов выра- жения последовательно образует столбец таблицы S, множе- ство имен "сыновей" дает столбец G таблицы, а множество имен "братьев"—столбец D. Все три столбца, объединенные БИБЛИОГРАФИЯ ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ. ОСНОВНЫЕ РАБОТЫ Ackotf R.L. (1978) : The art of problem solving. J. Wlley. A.I. Software (1984) : The international directory of A. I. Companies. A.I. Software. SRL. Rovlgo Italie. Allan J.J. (ed) (1976) : CAD systems. North Holland. Amarel S. (1968) : "On representations of problems of reasoning about actions". Irt M.I. 3 FIsovler. 131-1/1. Anderson J.R. (1976) : Language, memory, and thought. Lawrence Eribaum asso- ciates. Anderson J.R.. Bower Q. (1973) : Human associative memory. WInston-Wlley. Banerji R. (1980) : A.I. a theoretical approach. North Holland. Bar-Hillel Y. (1964) : Language and Informations. Reading. Mass. : Addlson-Wesley. Barr A.. Feigenbaum' E.A. (1986) : Le Manuel de Г Intelligence Artificielle (Eyrolles). Kaufmann. Barstow D. (1979) : Knowledge based program construction. Elvesler. Bartlett F. (19331 : Remembering : A study In experimental and social psychology. Cambridge University Press. Bartlett F. (1958) : Thinking. Basic Books. New York. Boden M. (1977) : Al and natural man. Basic books. Bongard N. (1970) : Pattern recognition. Spartan Books. Bonnet A. (1984) : L'lntelllgence artlflclelle, Promesses et Realltes. InteredltlortS." Brady M. (1983) : "Computational approach to Image understanding". ACM computing. surveys. 14. 1. 3-71. Bruner J.S.. Qoodnow J.J. Austin G.A. (1956) : A study of thinking. Wlley. Bundy A., Burstall R. M. . Weir S. . Young R. M. (1980) : Artificial Intelligence: An Introductory course. Edinburgh University Press. Bundy A. (1981) : Artificial Intelligence. Edinburgh University Press. Charnlak E. . RIesbeck С. К. . McOermott 0. V. (1980) : A.I. Programming. Lawrence- Eribaum. Charnlak E. . Me Dermott 0. (1984) : An Introduction to Artificial Intelligence. Addlsor» Wesley. Colllns N.. Michie D. (1968) : Machine Intelligence. Vol. 1. American Elsevler. Dale E. . Michie 0. (eds) (1968) : Machine Intelligence. Vol. 2. American Elsevler. Dreyfus H. L. (1979) : What computers cannot do. (Revised ed. Harper (1972)). Farreny H. . Prajoux R. (1982) : "Les pouvoirs des robots de la 3e generation" La science des robots. Science et Vie. Felgenbaum E. (1968) : "Artlflcal Inlelligence : Themes In the Second Decade". Information Processing 68. Vol. 2. A.J.H. Morrell. ed. . 1008-1022. North-Holland. Felgenbaum E. . Feldman J. (eds.) (1963) ; Computers and Thought. McQraw-HIII Book Company. Felgenbaum E.. Me Corduck P. (1983) : The fifth generation. Addison-Wesley. Caspar P. (1978) : Problemes m6thodes et strategies de resolution. Ed. Organisation.' Gllford J. P. (1967) : The nature of human intelligence. Me Qraw Hill. V 4C Hofstadter 0. R. (1977) : G'iodel. Escher et Bach. Basic books. Hofstadter D. R. . Oonnot О. С (1981) : The mind's I. Basic booNs, Hunt E. B. (1975) : Artificial Inlelligence. Academic Press. New York. Itzinger 0. (1976) : Methoden der maschinetlen Intelligem. Springer Vortag. Jackson P. C. (1974) : Introduction to artificial intelligence. Petrocelll/Charter. Kllx F. (ed ) (1979) : Human and artificial intelligence North Holland. Latombe J.C. (ed ) (1978) • Al and pattern recognition in CAD. North Holland. Latombe J. C. . Lux A (1979) : "Intelligence artiflcielle et robotique industrlelle". Le nouvcl automailsme. 5. 37-44 et 6. 21-29. LIghlhlll J. ( 1973) : 'Artificial Intelligence : A General Survey". Artificial Intelligence • A Paper Symposium. Science Research Council. Lindsay P.H.. Norman 0. A. (1977) : Traitement de rintormatlon et comportemenr humaln. Editions Etudes VIvantes. Montreal Marr 0. (1976) : "Early processing of visual Information". Philosophical Transactions 01 the Royal Society of London (Series B) 275 : 483-524. Marr D. (1977) : "Artificial Intelligence - A personal view". A.I. 37-48. McCarthy J. , Hayes I" .»1969), "Some Philosophical Problems from Standpoint of Artificial Intelligence". M.I. 4. Elsevler McCarthy J. (1977) : "Epistemologlcal problems in Al ' IJCAI 5. MIT - Cambridge, •I 038-1044. McCorduck P. (1979) : Machines who think. Freeman. Meltzer В.. Michie 0 .(eds) (1969) : Machine Intelligence, Vol. 4. Elsevier. Meltzer В.. Michie D .(eds) (1970) : Machine Intelligence. Vol. 5, Elsevler. Meltzer В...Michie 0. . (eds) (1971) : Machine Intelligence, Vol. 6. Elsevler. Meltzer В., Michie D . (eds) (1972) : Machine Intelligence. Vol. 7. Elsevler. Michie D. . od. (1968) : Machine Intelligence, Vol. 3. Elsevler. MInsky M.L. (1965) : "Matter, Mind. and Models". IFIP. Minsky M.L.. Paper! S. (1969) : Pgrceptrons ; an Introduction to computational geometry. Cambridge. Mass. : MIT Press. Miller. Q.A. ( 1956) : "The magical number seven, plus or minus two : Some limits of our capacity for processing information". Psychological Review 63, 81-97. Newel) A. (1973) : "Artificial Intelligence and the Concept of Mind", Computer Models , of Thought and Language. Roger Schank and Kenneth Colby. (eds). .W. H. Freeman & Co Newell A. (1982) : "The Knowledge Level". A.I. 18 (1) 87-127. Newell A.. Simon H. (1982) : Human problem solving. Prentice Halli Nllsson N.J. (19/1) : Problem solving methods in A.I. McGraw-HIII. Nllsson N.J. (1980) : Principles of A.I. Tioga Pub Co. Nivergell J. . Craig Farrar J. . Reingold E.M. (1974) : Computer approaches to mathematical problems Prentice Hall. Norman O.A. . Rumelharl D. E. and the LNR Reseaiuh Group. ( 1975) : Explorations In cognition. San Francisco : Freeman. Pa pert S. (1980) Mindstorms, Children, Computers and powerful Ideas. Basic Books. New York. Pohl I. : "Heuristic Search viewed as path finding in a graph". A.I. 1.3. 193-204. Polya G. (1954) : Mathematics and plausible reasoning, vol. 1, 2. Princeton University press. Polya G. (1954) • Induction and analogy in mathematics. Princelon el Qauthler-Vlllars (1958). Polya G. (1957) : Mathematical discovery. Double day. Polya G. (1959) : How to solve it. Princeton Univ. Press et. Dunod (1965). Raphael B. (1976) : The thinking computer. Freeman. Rich E. (1983) : Artificial Intelligence. McQraw-HIII. Shapiro S.C. (1979) • Techniques of Al. Van Nostrand. Simon H.A. (1969) : Sciences of the artificial. Cambridge. Mass.: МП Press. Simon H.A. (1973) : "The structure of III structured problems". A.I.. 81-202. Simon H.A. (1979) : Models of thought. Yale University Press. Simon H.A.. Barenfeld (1969) : "Information processing analysis of perceptual pro- cesses in problem solving". Psychological review. 5. 473. Simon H.A.. SIklossy L: (1973) : Representation and meaning. Experiments with Information processing systems. Prentice Hall. Simons G.L. (1984) : Introducy Artificial Intelligence. NCC Pub. 547 Slagle J.R.(1971) : A.I. : the heuristic programming approach. McGraw- Hill. Sussman G.J., (1975) : A computer model of skill acquisition. n°1. Elsevler. VIdat F. (1971) : Problem solving. Dunod. Von Neuman J. , Morgenstern 0, (1944) : Theory of games and economic behavior. Princeton University Press. Waterman O..Hayes Roth F/ (eds) (1978) : Pattern directed Inference systems. Academic Press. Wertz H. (1984) : Intelligence Artlflclelle. Masson. WIcKelgren W. (1974) : How to solve problems. Freeman. Winston P. H. (ed.) (1975) : The psychology of computer vision. McGraw-HIII. WInston P. H. (1977) : Artificial Intelligence. Addlson-Wesley. Wooldrldge H. (1963) : The machine o< tha brain. McGraw-HIII. ПОСТАНОВКИ ЗАДАЧ Alem J.P. (1975) : Jeux de resprit et divertissements mathematlques. Seull. Bachet de Mezlrlac (1612) : Problemes paysans et delectabtes qut se font par les nombres. Reedlte par A. Blanchard, Paris (1959). Berloquin P. (1978) : Jeux mathematlques du monde. Flammarlon. Berloquin P. (1980) : 100 leux numerlques - 100 leux geometrlques pour insom- ntaques. LIvre de Poche. Blanche! J. M. (1976) : Mathematlque en llberte. OCDL. Chuquet N. (1484) : Jeux et Esbataments. Manuscrll В1Ы. Nat.. n0 1346. Deledlcq A. (1975) : Mathematlques bulssonnleres. CEOIC. Dudeney H.E. (1967) : 536 puzzles and Curious Problems. Scrlbner's NY. Gardner M. (1977) : Les casse tete mathematlques de Sam Loyd. Ounod. Gardner M. (1979) : Les distracts. Les Jeux mathematlques du Scientific amerlcan. CEDIC. Gardner M. (1979).' L'effet haha. Pour la Science. Belln. Gerll D. , GIrard G. (1976) ; Les olymplades Internationales de mathematlques. Hachette. Kordlemskll B. (1963) : Sur /e sentler des mathematlques. 2 tomes. Dunod. Kraltchlch M. : La mathematlque des leux. Ounod. Lucas E. (1960) : Recreations mathomatlques. (Nouveau tirage) 4 tomes. A. Blanchard. Polya Q. (1965) : Comment poser et resoudre un problems. Dunod. Salnte-Lague A. de : Avec des nombres et des llgnea. Ounod. ЕСТЕСТВЕННЫЙ ЯЗЫК И ПРЕДСТАВЛЕНИЕ ИНФОРМАЦИИ Amarel S. (1968) : "On Representations ot Problems of Reasoning About Actions' M.I. 3. D. Mlchle.(ed). 131-170. Anderson J. (1977) : "Induction of augmented transition networks'. C.S. 125-157. Ballantyne M. (1975) • "Computer generation of counter examples In topology'. ATP 24. Unlv. Texas. Austin. Baner)! R. B. , Ernst G.W. (1972) : "Strategy construction using homomorphism between games". A.I. 3.4. 223-249. Berge 0. (1970) : Graphes et hypergraphea. Ounod. Bledsoe W. (1977) : "Non-resolution theorem proving". A.I. 9. 1-35. Bobrow D.Q. (1968) : "Natural Language Input tor a Computer Problem Solving System". M. MInsky (ed). Semantic Information Processing. Cambridge. MIT, 133-215. Bobrow D.J.. Winograd T. (1977) : "A knowledge representation language*. C.S- 1.1. Bonnet A. (1980) : "Analyse de textes au moyen d'une grammaire semantlque et de schemas. Application a la comprehension de resumes medlcaux en langage naturel". Tnese d'etat. Unlverslte Paris VI. Brown M.F. (1977) : "Doing arithmetic without diagrams". A.I. 8. 175-200. Bundy A. (1973) ; "Doing arithmetics, with diagrams". IJCAI. 3. 130-138. 548 Buthlon M. (1979) • "Un programme qui resout formellement des problemes de constructions geometrlques". RAIRO Ihtormatlque 13. 1. 73-106. Charnlak E. (1977) : "On the use of frame knowledge In language comprehension" A.I.. 1. 225-266. Charnlak E. Wllks Y. (1976) : Computational semantics. North-Holland. Charnlak E. (1981) : "A Common Representation for Problem-Solving and Language- Comprehension Information". A.I. 16 (3) 225-255. ChlcnetchI В. (1979) : "Comprehension du langage naturel" Traductlon paraphrasee d'exerclces sur le courant alternatif poses en persan". These. Paris 6. Chomsky N. (1957) : Syntactic structures. Mouton La Hague. Chomsky N. (1965) : Aspects of the theory of syntax. Cambridge. Mass.. MIT Press. Chomsky N. (1982) : Яи/es and representation In The behavioral and brain sciences. Clancey W.J. (1983) : "The Epistemology of a Rule-Based Expert System - a Framework tor Explanation". A.I. 20 (3) 215-251. Colmerauer A.. Kanoul H.. Pasero R. and Roussel P. (1973) : •Un systeme da communication homme-machlne en francals". In Rapport Groups d'lntel- llgence Artltlclelle, Unlverslte d'Alx-Marseille. Lumlny. France. Cordler M.O. (1979) : "Commande d'un robot en langage naturel dans un domaine necessltant des connalssances pragmatiques : les recedes de cuisine". These de 3° Cycle. Paris 6; Cordler M.O.. RoussetM.C. (1984) : "Interactive Operators In Expert Systems - TANGO". ECAI. 78-79. Davis R. . Buchanan B. et Shortllffe E. (1977) : "Production rules as a representation! for knowledge based consultation program". A.I. 8. 1. 15-45. Descles J. P. (1982) : "Langages quasi-nalurels et categories grammatlcales", Acfes du Colloque : Domaine et obiectlfs de la recherche cognitive. Erii (1983) : "SAPHIR. presentation generale". Rapport de la Sociele d'Bude et de' Recherche en LIngulstlque et Informatlque. "FIndler N.V. (1979) : Associative networks : the representation and use of knowledge by computers. Academic Press. Gelernler H. (1963) : "Realization of a geometry theorem proving machine". Computer and thought. McQraw-HIII. 135-147. Qllmore P.C. (1970) : "An examination of the goemetry theorem proving machine" - A.I. 1.3. 171-185. Qross M. (1975) : Grammaire transformatlonnelle du francals : synlaxe du verbe, Larousse. Gross M. (1977) : Grammaire transformatlonnetle du francals : syntaxe du пот. Larousse. Harris L. (1977) : "ROBOT a high performance natural language data base query system". IJCAI S. 903-904. Hayes P.F. (1973) : "The Frame Problem and Related Problems In Artificial Intelligence'. Artificial and Human Thinking, . A. Edthorn and D. Jones, (eds). Elsevier. Hendrix Q.Q. (1976) : "Partltlonned networks tor modeling natural language semantics". Dissertation. .Unlv. of Texas. HewittC.. Bishop P. and Stelger R. (1973) : "A Universal Modular Actor Formalism for Artificial Intelligence*. IJCAI 3. KortR.E. (1980) : "Toward a Model of Representation Changes". A.I. 14. (1). 41-; 78. LauriereJ.L. (1978) : "A language and a program for stating and solving combinatorial problems". A.I. 10. 1. 29-127. Lehnert W. . OyerM.G.. Johnson P. N. . YangC.J.. Harley S. (1983) : "BORIS an experiment In In-Depth Understanding of narratives'. A.I.. 20. 1. 15-62. Lopez M. (1979) : "Realisation d'un Interface de communication en langue naturelle avec le systeme TROPIC". Congres A.FCET. Toulouse. 25-35. Me Donald О. О. (1980) : "Language production as a process of decision making under constraints". Ph. D thesis. MIT Cambridge. Marcus M. H. (1980) : A theory of syntactic .recognition for natural language. MIT Press. Merlaldo B. (1979) : 'Representation des ensembles en demonstration automatlque do theoremes". These die 3° Cycle. Paris VI. 549 Nevlns. A.J. (1975) : "Plane geometry theorem proving using forward chaining'. A.I.. 6. 4. 1-23. Paatre О. (1978а) : "Automatic theorem proving in set theory'. A.I. 10. 1. 1-27. Paetre О. (19786) : •Observation du mathematlclen : aide a I'enselgnement et a ladomonstratlon automatlque de theoremes". Educational Studies In Mathematics a. 461-502. PItrat J. (1977) : 'Formalism for text analysis'. Semlnaire International sur tes systemes Intelllgenfa de questlona-reponses et grandes banques de donneea. Bonas. PItrat J. (1979) : 'Realisation d'un analyseur generateur lexicographlque general'. Rapport n" 78-? du GR22. Paris VI. PItrat J. (1980) : •L)n Interpreteur de contralntes pour la comprehension du langage naturel*. Colloque d'lntelllgence artlflclelle. Caen. Publications GR22 n" 20. PItrat J. (1985) : Texrea, ordlnateura et comprehension. Eyrolles. Polya Q. (1962) : Mathematical Discovery. Wlley. Quililan R. M. (1969) : "The teachable language comprehender : a simulation program and Iheory of language". С ACM. 12. n0 18. Sabah О. (1980) : "Contribution a la comprehension effective d'un r6clf. These d'etat- Unlverslt6 Paris VI. Sabah G.,Rudy M. (1983) : "A deterministic syntactic-semantic parser" IJCAI 8 Salkoft M. ( 1973) : Ung grammaire en chalne du trangais. Ounod. Schank R.C. (1975) : Conceptual Information Processing. North-Holland. Simmons R. F. (1973) : "Semantic nelworks : their computation and use lor under- standing english sentences". In Schank and Colby 73. 63-113. Verdejo M. F. (1975) : "Etude du langage naturel". Simulation d'un robot capable de mener un dialogue en espagnol. Jhese Paris VI. VllnatA., Sabah Q. (1984) : "How a System May be Seif-Conscious". ECAI. 227-229. Waltz D. L. (1981) : An english language question answering system for a large relational data base. McGraw-HIII. Wllks Y. (1975) : "An intelligent analyzer and understander of English". CACM. 18. 5. Winograd Т. (1972) : Understanding natural language. Edinburgh University Press. WInograd T.(1980) : "What does it mean to understand language ?" C. S. 4: 209-241 Winograd Т. (1983) : Language as a cognitive process. Addison-Wesley. Winston P.H. (1975) : "Learning structural descriptions from examples" in The psychology of Computer Vision. McGraw-HIII. Woods W. A. (1970) : "Transition networks grammars for natural language analysis". С ACM 13, 10, 591-606. Woods W.A. (1975) : "What is-a link ?". In Representation and understanding, Bobrow et Cotllns. Academic Press. ИСТОРИЯ ИСКУССТВЕННОГО ИНТЕЛЕКТА . ПЕРВЫЕ ПРОГРАММЫ Colby К.. Weber S. . Hllf F. D. (1975) : Artificial Paranoia. Pergamon Press. Ernst G. . Newell A. (1969) : GPS ; A case study In generality and problem solving.. New York Academic Press. Evens T.G- (1963) : "A heuristic program to solve geometric analogy problems", in Semantic Information Processing. M. Mlnsky(ed). MIT Press. Cambridge. Mass. Greenblatt R. 0. et coil. (1967) : "The Greenblatt chess program". Proc. AFIPS Fall Joint Computer Conference, 31, 801-810. Guzman A. (1968) : "Computer Recognition of Three-Dlmenslonal Objects in a Visual Scene". MAC Teen. Report 59, thesis. Project MAC. MIT. Cambridge MA. Moses J. (1967) : "Symbolic integration". Rapport Technique MAC-TR-47, MIT. Newell A.. Shaw J.C.. Simon H.A. (1957) : "Programming the Logic Theory Machine". Western Joint Computer Conference. 230-240. Newell A. . Simon H.A. (1956) : "The Logic Theory Machine : A Complex Information Processing System. IRE Trans. on Information Theory. IT-2. 3. 61-79. Shannon С. Е. (1950) : "Programming a computer to play Chess". Scientific American. SlagleJ.R, (1963) : "A heuristic program that solves symbolic Integration problems in freshman calculus". Feigenbaum and Feldman (eds). McGraw-HIII. 550 Turing A. M. (1950) : "Computing Machinery and Intelligence". Mind. 59, 433-460. Reprinted In Computers and Thought. 11-35. Tonge F. (1961) : A heuristic program for assembly Line balancing. Prentice Hall. Welzenbaum J. (1966) : "Ellza. a computer program for the study of natural language communication between man and machine". CACM. 9. 36-45. Winston H. . Brown R.H. (ed ) (1979) : Artificial Intelligence. An MIT perspective. Vol. I et II. MIT Press. Cayrol M. (1983) : Le langage LISP. Cepadues editions. Chailloux J (1979) : •Le modele VLISP : description, implementation et evaluation" . 7"nese de 3° Cycle. University de Vincennes. Chailloux J (1985) : t.e Lisp,. Manuei de reference. INRIA. Farreny H. (1984) : programmer en LISP. Masson. Queinnec C. (1980) : Langage d'un autre type : LISP. Eyrolles. Siklossy L. (1976) : Lets talk LISP. Prentice Hall. Steelo G.L. Jr. (1984) : Common LISP. Digital Press, Wartz H. (1985) : LISP. Une introduction a la programmatlon. Masson. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ И НЕКЛАССИЧЕСКАЯ ЛОГИКА Allio L. . Lev! G. (1984) : "1 he Usos of Metaknowledge in Al Systems'. ECAI. 705-719. Bobrow D.G.. Collins A. (1975) : Representation and und erstandlng. Ac. Press. BooseJ.H. (1984) : "Personal Construct Theory and the Transfer of Human Expertise". FCA/. 51-60. Borillo M. . VIrbel J. (1977) : Anafyse et validation dans retude des donnees textuelles. Editions du CNRS. Paris, Brachman R.J. (19/7) : "What's in a concept : Structural foundations for semantic networks". Internallonal Journal of man-machine studies 9, 2. 127-152. Bucnanan B.C.. Ouda P.O. (1982) : "Principles of rule-based systems". Stanford University technical report. HPP-BZ-14. Carbonell J.G. (1980) : "Towards a process model of uman personality traits", A.I. 15. Chouraqul E. (1982) : 'Contributions a I'etude theorlque de la representation des connalssances". Tnese dEtat. Nancy. Coelho H. (1984) : "An Introduction to the Knowledge Representation Subfleld". ECAI, 283-285. Coulon О. . Kayser 0. (1980) : "Un systeme do ralsonnement a profondeur variable". Congres AFCET-TTI. Nancy. 517-527. Davis R. (1978) : "Knowledge acquisition In rule-based systems : Knowledge about representations as a basis tor system construction and maintenance". In DA Waterman and F. Hayes-Roth (Eds.). Pattern directed Inference systems. 99-134. Oavis R. (1979) : "Interactive Transfer of Expertise : Acquisition of New Inference Rules". A.I. 12 (2) 121-157. Davis R. (1980) : "Mela-Rules : Reasoning about Control". A.I. 15 (3) 179-222. Doyle J. (1979) : "A Truth Maintenance System". A.I. 12 (3) 231-272. FerberJ. (1984) : "Menng : An Open-Ended Object Oriented Language for Knowledge Representation" ECAI. 195-204. Duda P.O.. Hart P. E. . Nilsson N.J., Sutherland G I-. (1978) : "Semantic network representations in rule-based inference systems" In Waterman et Hayes- Roth. 203-222. Fillmore C. (1968) : "The case for case". In Bach and Harms (ed.). Untversals In linguistic Iheory. Holt. RInelhart and Winston. Qallaire H. . Lasserre C. (1979) : "Controlling knowledge deduction In a declarative approach IJCAt 6 S1-S12. Ganascia J C (1984) • "Reasoning and Result In Expert Systems : Main Differences Between Diagnostic Systems and Problem-Solvers". ECAI. 31-40. Qoldstein 1. P. . Grimson E ( 1977) : "Annotated production system : A model for skill acquisition. IJCAt 5 311-317. Hnyes P. (1973) : "The frame problem and related problems In A.I." Artificial and human thinking" Elsevler. 551 Hayes P. <1977) : "In defense of logic". IJCAI 5,-S59-583. Hayes P. (1977) : 'On semanlic nets. frames and associations". IJCAI S. 99-107. Hayes-Rolh F. . Waterman DA.. Lenat 1). B. (Eds.) <1983) : Building expert systems. Addlson Wesley. de Kleer J. et al. ° 174. Computer Science Dept . Yale University. McDermolt 0 Doyle J. (1980) : •Non-monotonic logic I". A.I.. 13. 1 «i 2. 41-72. MInsky M. (1975) : "A framework for representing knowledge". In P.M. WInston. MInsky M (ed.). (1968) : Semantic information processing. Cambridge. Mass. Mil" Press. Prade H. (1983) : "A synthetic view of approxirnale reasoning techniques". IJCAI 8. 130-136 RIeger С. (1976) : "An organization of knowledge for problem solving and language- comprehension". A.I. 7. 89-127. Reiter R. (1978) : "On reasoning by default". Theoretical issues in Natural Language Processing-2. Illinois. 2)0-218. Reiter R. (1980) : -A Logic for Default Reasoning". A.I. 13 (1-2). 81-132. Rosenberg S. (1983) : "HPRL : a language for building expert systems". IJCAI 8 Karlsruhe. 215-217. Rousseau M. (1973) : "Resolution aulomatique d'exercices d'electrlclle poses en francais". These, Paris VI. Rychener M. D. ( I976) : "Production systems as a programming language for artificial Intelligence Applications". Ph. D., Carnegie Mellon. Schank R.C. (1972) : "Conceptual Dependency : a theory of natural language un- derstanding". Cognitive Psychology. 3. 552-631. Schank R.C. (1975) : Conceptual Information Processing. North Holland Schank R.C.. Abelson R. P. (1977) : Scripts, plans, goals, and understanding. Hlllsdale. N.J. Lawrence Eribaum. ShortllWe E. H. . BuchananB.G. (1975) : "A model of inexact reasoning in medicine". Mathematical Blosctencas 23. 351-379. Skolem Т. (1967) : "The foundations of elementary arithmetic established by means of the recursive mode of thought, without the use of apparent variables ranging over Infinite domains". In From Frege to GWel. Harvard University Press. Steflk M. (1979) : "An Examination of a Frame-Structured Representation System" IJCAI 6, 845-852. 552 Steflk M. . Alklns J. . Balzer R. . Benoit J. . BIrnbaum L. . Hayes-Roth F. .SacerdotI E. (1982) : The Organization of Expert Systems. A Tutorial". A.I. 18 (2) 135-173. Szolovits P.. Paukor S.Q.', (1978) : "Categorical and Probabilistic Reasoning in Medical Diagnosis'. A.I.. 11, 115-144. Tabourler Y. ( 1982) : "Probl6mes de normalisation et de decomposition dans les modules conceptuels de donnees" Inlormatlque et gestlon. n°133. 72-81 Van Melle W. (1980) : "A domain-Independent system that aids in constructing knowledge based consultation programs" flop. Л/о. 820. Compuler Science Dept . Stanford University (Doctoral dissertation). Weyhrauch R.W. (1980) : "Prolegomena to a Theory of Mechanized Formal Reasoning". A.I.. 13 : 1-2. 133-170. Wllensky R. (1978) : "Understanding goal-based stories". Research Report 140. Yale University. Winograd T. (1975) : "Frame representations and the declarative/procedural controversy". In Representation and understanding. Bobrow & Colllns: (eds).. Academic Press. Woods W. (1975) : "What's in a link ? Foundations for semantic networks", in Representation and Understanding, Bobrow & Colllns (eds). Academic Press New York. 35-82. Zadey L.A. etal. (ed.) (1975) : Fuzzy sets and their applications to cognitive and decision processes. Academic Press. Zadey L.A. (1979) : "Approximate reasoning based on fuzzy logic". IJCAI 6. 1004- 1010. ЭКСПЕРТНЫЕ СИСТЕМЫ И ИХ ПРИМЕНЕНИЯ Alklns J. (1979) : "Prototypes and production rules : and approach to knowledge representation for hypothesis formation". IJCAI 6. AbrlalJ.R. (1974) : Data semantics IFIP. TCZ. Anderson R. , Glllogly J. (1976) : "Rand Intelligent terminal agent RITA design and philosophy". R-1809-ARPA. Anderson J. . Kllne P. (1979) : "A learning system and Its psychological Implications*. IJCAI 6. Anderson J. . Kllne P. , Beasley C. (1979) :• Complex learning processes' In Aptitude Learning and Instructions, R. Snow (Ed.). Barnett J. Berstein M. (1977) : 'Knowledge-based systems : a -tutorial*. System Development Corporation. TM(L) 5903. Barslow 0. R. (1979) : 'An experiment In knowledge based automatic programming" A.I.. 12. 73-119. Bartels U. . Ottholf W. . Rawlefs P. (1981) : "APE : a system for automatic programming from abstract specifications of data types and algorithms". IJCAI 7. 1037-1013. Battani Q. . MelonI H. (1973) : •Un Interpreleur de PROLOG". Aix-Marsellle. GIA Lumtny. BennettJ.S. . Engelmore R. (1979) : "SACON : a knowledge-based consultant for Structural analysis". IJCAI в. 47-49. BennenJ.S. . Hollander С. R. (1981) : "DART : and expert system for computer fault diagnosis". IJCAI 7. 843-845. . Bobrow (Ed.) (1975) : Representation and Understanding. Academic Press. Bobrow D. . Winograd T. (1979) : "KRL another perspective". CS. 1(1). 24-79. Bonnet A. (1980) : "Analyse de texles au moyen d'una grammaire semantlque de schemas. Applications a. la comprehension de resumes medlcaux en langage naturel". 7'ftese d'Etat. Paris VI. Bonnet A. (1981) : "Applications de I'lntelllgence artlflclelle . les systemes experts" . RAIRO Inlormatlque, 15 (4). Bonnet A. . Cordler M О. . Kayser 0. (1981) : "An ICAI System for teaching Derivatives In mathematics". Proc. or 3rd World Conference on Computer Education (WCCE). Lausanne. 27-31. Bonnet A, . Harry J. . GanasclaJ.Q. (1982) : •LITHO. un systeme expert Inferant la geologle du sous-sol". TS/. 1. 5. 393-402. 553 Bonnet A. . Oahan С. (1983) 'Oil-well oate interpretation using expert system and pattern recognition technique*. IJCAI 8. 185-189. Borning A. . Bundy A (1981) : 'Using matching In algebraic equation solving". IJCAt 7. 466-471. Bourgoln 0. (1978) :'PARI. un programme heurlstlque pour resoudre des exerclces d'arlthmelique'. T/ieae de 3eme cycle. Paris VI. Brown »>. . Burlon R. . Boll A. ( 19/5) : 'SOPHIE : a step towards creating a reactive learning environment". International J. of Man-Machine Studies. 7. 675- 716. Buchanan В. . Felgenbaum F, (1978) : •OENORAL and META-DENORAL* A.I.. 11. 5-24. Buchanan В. . MItchell Г. (1979) : "Model directed learning of production rules". In: Waterman and Hayes Roth (eds). Bundy A. . Byrd L. . LugerQ. . Melllsh R. . Milne R. . Palmer M. (1979) : "MECHOa program to solve mechanics problems'. Oept. of A.I. LI. of Edinburgh, Working Papal N" SO. 1-104. Bundy A. el al. (1979) : "Solving mechanics problems using meta-level inference". IJCAI 6. 1017-1027. CarbonellJ. (1978) : "POLITICS: automated Ideological reasoning". C. S. . 2, 27-51.. CarhartR.E. (1979) : "CONGEN : on expert system aiding the structural chemist". In MIchle (ed.). Edinburgh University Press. Cayrol M. , Fades. . Farreny H. (1979) :" Objets formels et attrlbuts dans ARQOS 11" • Actes Congres AFCET. Toulouse. 256-263. Cayrol M. . Fade B. . Farreny H. (1979) : "A decision-command function for a general robot" : ARQOS-11 . Tech. Report. Unlverslte Toulouse. Charnlak E. (1978) : -On the use of framed knowledge". A.I.. 11(3). 225-266, Chomsky N. (1965) : "Aspects of the Theory of Syntax". MIT Press. ' ClanceyW.J. (1979) : "Tutoring rules fur guiding a case method dialog". Int. J. of- Man-Machine Studies. 11. 25-49. ClanceyW.J. . Letslnger R. (1981) : "NEOMYCIN : reconfiguring a rule based expert system for application to teaching". IJCAI 7, 829-836. CtockslnW.F. . Melllsh C. S. (1981) : "Programming In Prolog". Sprlnger-Verlag. Berlin. Coelho H. . CottaJ.C. . PereiraL.M. (1980) : "How to solve It with PROLOG". Lab- Nat. de Engenharia Civil. Lisbon. ColmerauerA. (1977) : Programma'tlon en loglque du premier ordre . .Acres Journees 'La comprehension'. IRIA. Corciier M.O. (1979) : "Commando d'un robot en langage nature! dans un domalne necessltant des connalssances pragmatlques : les recettes de cuisine" These de Seme cycfe. LRI. Paris XI. Co-dlerM.O. , Rousset M. C (1984) : "Propagation: another way for matching patterns. In KBS" Cyb. and Syst.Res.2 Davis R. (1979) : "Interactive transfer of expertise : acquisition of new Inference' rules'. MIT, 11. 1-36 , abridged version In IJCAI, 5. 321-328. Oavie R. . Buchanan H. ( 19/7) : •Meta-level knowledge and applications". IJCAI S, 920-927. Oavis R. , Buchanan B. . Shortime E. ( 1977) : "Production rules as a representation for a knowledge-based consultation program". A.I.. B. 15-45. Oavlf R. , King J. (1977) : "An overview of production systems". M. 1.. 8. 300-332. Oavis R. . Austin H. . Carlbow I. . Frawley B. . Pruchnik P. . Snelderman R. . QllrealhJ.A. (1981) : The DIPMETER advisor: Interpretation of geological • signals". IJCAI 7. 846-849. DavteR. . LenalD.B. (1982) : Knowledge Based Systems In Artificial Intelligence. New York. McQraw-Hlll. Oescottes Y. . Latombe J.C. (1981) : "Garl : a problem solver that plans how to machine mechanical parts 'IJCAI 7. 766-772. OIncbae M. (1979) : "PROLOQ et un exemple de programme expert ecrit en PROLOG". Doc. СЕЯГ. . 2/3122. ' OIncbae M. (1980) : "A knowledge-based expert system for automatic analysis and synthesis'. In : CAD, Proc. IFIP. Tokyo, 705-710. Oincbaa M. (1980) : •Le aysteme de resolution de problemes METALOQ*. CERT/DERI, Report N" 3t46, Convention DRET 79, 121B. Toulouse. 554 Ooumelngte Q. . Breull D. . Pun L. (1983) : La gestlon de production asslstee par ordlnateur'. Hermes Publishing. Paris. Doyle J. (1979) : "TMS : a true maintenance system" . A.I.. 12. 231-272. OudaR.O. . QaschnlngJ. . Hart P. (1980) : "Model design In the PROSPECTOR con- sultant system for mineral exploration*, in MIchle 1980. OudaR.O. (1982) : "The PROSPECTOR consultation system". Final Report SRI B1 72. Duda P.O. . Qaschning J.O. (1981) : "Knowledge based expert systems come of age". Byte. 6 (9); 238-283. Engelmore R. . Terry A. (1979) : "Structure and function of the CRYSALIS system". IJCAI в. 250-256. Erman L. . Lesser V. (1975) : "A multi-level organization for problem-solving using many diverse cooperating sources of knowledge". IJCAI 4. 483-490. Erman L. . Hayes-Roth F. , Lesser V. R. . Reddy 0. R. (1980) : "The HEARSAY-11 speech-understanding system • Integrating knowledge to resolve uncertainty". Computing Surveys 12,2 Erman L. . London P. . Fickas S. (1981) : "The design and an example use of HEARSAY 111". IJCAI 7. 409-415. Farreny H. (1980) : 'Un systeme pour I'expression el la resolution de problemes oriente vers le controle de robots" These d'Etat. Toulouse. Farreny H. (1982) : "Des puits de science qu'on peut sonder". In : La Science des Robots. Science et VIe-hors-serle. 68-75. Farreny H. (1985) : Les systemes -experts, princlpes et exemptes. Cepadues. Felgenbaum E. (1977) : "The an of artificial Intelligence". IJCAI 5. 1014-1029. Felgenbaum E. . Suchanan В. . Lederberg J. (1971) : "On generality and problem solving : a case study using the DENDRAL program". Ml 6. 165-190 Ferrand P. (1983) -SESAM": "An Explanatory Medical Aid System". ECAI. 13-20. FleschI M. (1981) : "Aide a la Decision en Medeclne : le Systeme Sphinx. Application au diagnostic d'une douleur epigastrlque". These, Medec'ne, Marseille. FleschI M. (1984) : Intelligence artltlclelle en medeclne: systemes experts. Masson. Forgy С. . McDermott J. (1977) : "OPS : a domain Independent production system". IJCAI 6. 933-939. Fouet J.M. (1982) : " Oesapprendre a programmer". Pub. OR 22. n° 30. Friedman L. (1981) : Extended plausible Infcronce . IJCAt f. 487-495. Gallaire H. . MInker J. (Eds) (1978) : Log/c and Data Bases. Plenum. Gallaire H. . Lasserre C. ( 1979) : "Controlling knowledge deduction In a declarative approach". IJCAI в. S1-S12. Gallaire H. (1981) : •Le langage PROLOG". L4. 12R. Lectures. Toulouse. Ganascia J.G .(1983) :"MlBlllHO. Validation des resultats et detection des contradictions dans les systemes de dignostic". These 3eme cycle Paris, Sud. Gascuel 0. (1981) : "Un programme general d'alde a la decision medlcale structurant automatlquemnt ses connalssances". Congres AFCET RF-IA. Nancy. Green C. (1976) : "The design of the PSI program synthesis pyslem". Proc. of the Second International Conference on software englneev'ffiy. 4-18. Georgeff M. (1979) : "A framework for control in production systems". IJCAI в. 328- 334. Germain M. ( 1981) : Journee sur les specifications. Afcet-TTI Conference. Nancy. Qhallab M. 'Decision trees for optimizing pattern-matching algorithm". IJCAI 7. 310- 3)2. Goldstein 1. . Roberts R. (1977) : "NUDGE: a knowledge-based scheduling program". IJCAI 5. 257-263. Green О. О. (1976) : "The design of the PSI program synthesis system". IJCAI 2. 4-18. Hayes-Roth F. . Waterman 0. A. . Lena! D. B. (1977) : "Principles of pattern-directed inference systems". 577-601. ' Hayes-Roth F. . Klahr P. , Mostow 0. (1981) : "Advice-taking and knowledge refinement : An Iterative view of skill acquisition". In J. R. Anderson (ed. ). Cognitive skills and their acquisition. Lawrence Eribaum. 231-253. HedrlckC.L. (1976) : learning production systems from examples. A.I.. 7(1). 21- 49. Herbrand J. (1931) ; "Uno methodo de demonstration". These. Paris. Hewin C (1972) : •Description and theoretical analysis (using schemata) of PLANNER : a language for proving theorems and manipulating models In a robot* PhD. MIT. A.I. Lab. Report 258. 555 Holt A. W. (1971) • fnrroducMon ro Occurrence Syafems. Associative Information Tec- hniques. E. Jack (od ) Fisevler. USA. Hue) 0. (1976) : Unification dans les loglques d'ordro ).2.3,om6ga. These Paris. Johnson T. (1984) : The commercial applications of expert systems technologies. OVUM Londres. Kahn K.M. (1981) : "UNIFORM : a language based upon unification*. IJCAI Л 933- 939. Kayser О. . Coulon О. (1981) : 'Variable-depth natural language understanding* . IJCAI 7. 64-66 Klitrr D. . Morris P. (1981) : "Don't be stupid'. IJCAI 7. 345-347. Konollge К. (1979) :'An Inference net compiler lor the PROSPECTOR rule-based consultation system". IJCAI 6. 487-489. Kowalski R. (1974) :'Predicate logic as a programming language". Proc. IFIP, 3. 569- 574 Kowalski R. (1979) : Logic for Problem Solving. North-Holland. New York. Kuiikowski C.A. . Weiss S. . Trigobod M. . Satir A. (1976) : "Clinical consultation and the represenllon of disease process : some A. I. approaches". Report CEM-TR 58. Rutgors University. Kuiikowski C.A. . Weiss S (1982) : "Representation of expert knowledge for consul - tatlon : the CASNET and EXPERT projects". In Artificial Intelligence In Medicine, P. Szolovlts