Основные направления искусственного интеллекта

Системы искусственного интеллекта. Курс лекций для бакалавров направления 090401. 1 Основные направления искусственного интеллекта. 1.1 История развития искусственного интеллекта Термин искусственный интеллект (ИИ) является русским переводом английского термина artifical intelligence. Создателем ИИ многие ученые считают Алана Тьюринга, автора знаменитой машины Тьюринга, которая стала одним из математических определений алгоритма [1]. В 1950 году в английском журнале “ Mind” в статье “Computing Machinery and Intelligence” (в русском переводе статья называлась «Может ли машина мыслить?») Алан Тьюринг предложил критерий, позволяющий определить, обладает ли машина мыслительными способностями. Этот тест заключается в следующем: человек и машина при помощи записок ведут диалог, а судья (человек), находясь в другом месте, должен определить по запискам, кому они принадлежат, человеку или машине. Если ему это не удается, то это будет означать, что машина успешно прошла тест. Тьюринг посчитал, что к 2000 году машины будут способны ввести в заблуждение 30% собеседников при условии длительности беседы не более 5 минут. В СМИ появилось сообщение, что 7 июня 2014 года произошло эпохальное событие: тест для определения искусственного интеллекта, придуманный британским математиком Аланом Тьюрингом 64 года назад, был пройден.  Чатбот, созданный под руководством российского программиста Владимира Веселова, живущего и работающего в США, сумел преодолеть 30% барьер, установленный Тьюрингом более полувека назад. Сам Владимир рассказал про себя, команду и свой чатбот следующее: «Чатбот «Евгений Густман» был создан командой энтузаистов в 2001 году. В состав команды входили: Евгений Демченко, Сергей Уласень, Михаил Гершкович, Джон Деннинг, Андрей Адащик, Игорь Быковских, Селена Семушкина. Графический образ создан Лореном Алкир (Laurent Alquier). Основная часть команды находится в Санкт Петербурге.  После этого программа и база знаний дорабатывались, исправлялись недостатки. В 2012-м году Густман победил в соревнованиях, посвященных 100-летию со дня рождения Алана Тьюринга. В 2012 результат был 29.2 %, в 2014  — 33.3%.  Программа «Евгений Густман» состоит из базы знаний, которая имеет около трех тысяч шаблонов распознавания фраз пользователя. Это довольно немного, по сравнению с другими чатботами. Мы использовали также различные методы управления диалогом, которые позволяют имитировать именно человека, а не поисковую машину. Евгений старается направить беседу в нужное ему русло, стараясь создавать такие ситуации, когда его фраза выглядят человекоподобно. При короткой продолжительности беседы — 5 минут — такой подход часто срабатывает». Владимир Веселов закончил Военный Инженерно-Космический Институт им. А.Ф. Можайского, служил на Байконуре, закончил адъюнктуру ВИКА им. А.Ф. Можайского, работал программистом, научным сотрудником. В данный момент является разрабочиком программного обеспечения в компании Amazon Web Services. ТТ проходил следующим образом: команда ученых-организаторов теста под руководством профессора Кевина Варвика и его ассистента Хумы Шан собрала судей (30 человек, поделенных на 4 смены) и «скрытых людей», которые должны были вести диалог. В тесте участвовало также пять чатботов, которые общались на английском языке.  Каждый судья имел перед собой экран монитора, разделенный на две части. Судья должен был вести диалог одновременно с двумя «сущностями». При этом было неизвестно, кто из них компьютер, а кто — человек. Ровно, как в классическом тесте. Через пять минут окна отключались. Судья заполнял анкету и потом приступал к оценке следующей пары. Основная задача — определить, с кем шел диалог: с машиной или же с человеком.  Программа, созданная Владимиром Веселовым и его коллегами, смогла ввести в заблуждение ровно треть всех судей, присутствовавших на мероприятии. После четырёх смен оценки, оргкомитет подсчитал бюллетени.  Профессор Варвик сказал, что тест Тьюринга окончательно пройден: «Мы специально пригласили судей и независимых наблюдателей — уважаемых ученых, чтобы все было сделано правильно и никаких сомнений не оставалось. Именно так: тест Тьюринга, пройден». Чатбот убедил 33 процента судей, в том, что он является 13-летним мальчиком из Одессы. В целом, можно сказать, что для оценки искусственного интеллекта теперь надо придумывать другие тесты. Прежде всего, это означает, что проникновение информационных систем в межчеловеческое общение ускоряется. Через пять лет уже невозможно будет сказать, общаетесь вы с живым оператором контактного центра или с машиной. Разницу будет можно почувствовать лишь через 5 минут общения.  Второе — срочно необходимо решать вопрос с проведением ТТ на русском языке. Не существует единого и общепринятого определения ИИ. Это не удивительно, так как нет универсального определения человеческого интеллекта. ИИ – это область информатики, предметом которой является разработка компьютерных систем, обладающих возможностями, традиционно связываемыми со способностями естественного интеллекта. К области ИИ принято относить ряд алгоритмов и программных систем, которые могут решать некоторые задачи так, как это делает человек. Первый шаг в исследованиях по ИИ был сделан в направлении изучения естественного интеллекта. При изучении этого вопроса был сделан ряд открытий в различных областях знаний. Так, в 1962 году Фрэнком Розенблаттом были предложены модели мозга, имитирующие биофизические процессы, которые протекают в головном мозге и которые были названы персептронами. Персептроны представляют собой различного вида сети из искусственных нейронов, в основе которых лежат модели, разработанные еще в 1943 году Уорреном Маккалоком и Уолтером Питтсом. Первоначально, изучение персептронов было связано с задачей распознавания образов, однако, в настоящее время нейронные сети широко используются для решения задач аппроксимации, классификации и распознавания образов, прогнозирования, идентификации и оценивания, ассоциативного управления [5]. Нейронные сети представляют собой низкоуровневые модели мозговой деятельности человека. Другое направление моделирования естественного интеллекта связано с созданием высокоуровневых моделей деятельности мозга человека, которые позволяют моделировать процессы рассуждений и принятия решений. В целом можно сказать, что изучение разумного поведения человека привело к появлению эвристических методов, моделирующих деятельность человека в проблемной ситуации и к разработке программно-аппаратных средств, реализующих эти методы, то есть к разработке систем искусственного интеллекта, называемых решателями задач. Другим результатом этих исследований можно считать создание экспертных систем, то есть систем искусственного интеллекта, основанных на знаниях человека-эксперта. Также к специфическим особенностям деятельности человека обычно относят способности к распознаванию сложных зрительных и слуховых образов, пониманию естественных языков, способности к обучению, рассуждениям и логическим выводам. Все эти особенности стали реализовываться в системах искусственного интеллекта. В Советском союзе ИИ получил официальное признание в 1974 году, когда при президиуме АН СССР был создан научный совет по проблеме «Искусственный интеллект», хотя работы в этом направлении велись с 60-х годов Вениамином Ноевичем Пушкиным, Дмитрием Александровичем Поспеловым, Сергеем Юрьевичем Масловым, Валентином Фёдоровичем Турчиным. Первые положительные результаты были получены в области теории управления, так как в этой области имелся ряд задач, для решения которых традиционные методы не были пригодны из-за невозможности формализации цели управления объектом и невозможности установления точных количественных зависимостей между параметрами, оказывающими влияние на процесс управления [1]. В результате проведенных работ появились логико-лингвистические модели, в которых решающее значение имеют тексты на естественном языке. В таких моделях для принятия решения при управлении объектами используется семантическая информация для описания модели объекта, модели среды и блока принятия решения. Моделирование рассуждений человека, осуществление логического вывода с помощью вычислительной машины стало возможным, благодаря использованию методов поиска решений в исчислении предикатов [3]. Эти методы стали основой общей теории дедуктивных систем. При этом все «творческие задачи» решаются интеллектуальным перебором в четко очерченном множестве – в фиксированной формальной теории, которая является ветвью математической логики и в которой реализуется процесс нахождения решений. В настоящее время выделяют следующие направления развития исследований в области искусственного интеллекта [2]: 1. Разработка систем, основанных на знаниях. Целью этого направления является имитация способностей человека в области анализа неструктурированных и слабоструктурированных задач. В данной области исследований осуществляется разработка моделей представления, извлечения и структурирования знаний, а также изучаются проблемы создания баз знаний (БЗ). К данному классу систем также относятся экспертные системы (ЭС). 2. Разработка естественно-языковых интерфейсов и машинный перевод. Данные системы строятся как интеллектуальные системы, так как основаны на БЗ в определенной предметной области и сложных моделях, обеспечивающих трансляцию «исходный язык – язык смысла – язык перевода». Эти модели основаны на последовательном анализе и синтезе естественно-языковых сообщений и ассоциативном поиске аналогичных фрагментов текста и их переводов в специальных базах данных (БД). 3. Генерация и распознавание речи. Решаются задачи обработки, анализа и синтеза фонемных текстов. 4. Обработка визуальной информации. Решаются задачи обработки, анализа и синтеза изображений. В задаче анализа исходные изображения преобразуются в данные другого типа, например, текстовые описания. При синтезе изображений в качестве входной информации используются алгоритмы построения изображений, а выходными данными являются графические объекты. 5. Обучение и самообучение. Данная область ИИ включает модели, методы и алгоритмы, реализующие автоматическое накопление и генерацию знаний с использованием процедур анализа и обобщения знаний. К данному направлению относятся системы добычи данных (Data-mining) и системы поиска закономерностей в компьютерных базах данных (Knowledge Discovery). 6. Распознавание образов. Распознавание образов осуществляется на применении специальных математических моделей, обеспечивающих отнесение объектов к классам, которые описываются совокупностями определенных значений признаков. 7. Игры и машинное творчество. К данной области относятся системы сочинения компьютерной музыки, стихов, изобретения новых объектов, а также интеллектуальные компьютерные игры. 8. Программное обеспечение систем ИИ. К данной области относятся инструментальные средства для разработки интеллектуальных систем, включая специальные языки программирования, ориентирование на обработку символьной информации (LISP, SMALLTALK, РЕФАЛ), языки логического программирования (PROLOG), языки представления знаний (OPS 5, KRL, FRL), интегрирование программные среды (KE, ARTS, GURU, G2), а также оболочки экспертных систем (BUILD, EMYGIN, EXSYS Professional, ЭКСПЕРТ). 9. Новые архитектуры компьютеров. Это направление связано с созданием компьютеров не фон-неймановской архитектуры, ориентированных на обработку символьной информации. Известны удачные промышленные решения параллельных и векторных компьютеров, однако в настоящее время они имеют очень высокую стоимость и недостаточную совместимость с существующими вычислительными средствами. 10. Интеллектуальные роботы. В настоящее время данная область ИИ развивается очень бурно. Достигнуты значительные успехи в создании бытовых роботов, роботов, используемых в космических исследованиях, медицинских роботов. 1.2 Современное состояние искусственного интеллекта. В настоящее время в области ИИ активно работают военные ведомства и ведущие западные фирмы, такие как AT&T, Intel, General Electric, Sharp, Hitachi, Siemens. Военное научное агентство DARPA - крупнейший в мире финансист исследований по ИИ, особенно по робототехнике [1]. Создание современного оружия немыслимо без использования методов ИИ, особенно таких, как нейронные технологии, нечеткие экспертные системы и интеллектуальные решатели задач. Эти методы позволяют с помощью относительно малых ресурсов получать достаточно точные результаты. В этой связи состояние разработок в некоторых областях ИИ закрыто для широкого доступа. С другой стороны, в настоящее время бурно развивается рынок бытовых роботов и интеллектуальных домашних устройств, которые приносят немалую прибыль фирмам-разработчикам. Так, например, компания NEC представила модель робота Personal Robot R100, которая может передвигаться, произносить 300 фраз, понимать сотни команд и различать 10 лиц. Робот может приносить мелкие вещи, вынимать почту из ящика, включать и выключать телевизор, записывать видеосообщения и передавать их по назначению. Робот Okonomiyaki. Этот робот мастерски готовит окономияки – жареную лепешку из смеси разнообразных ингредиентов. Предназначенный для работы независимо и рядом с людьми, этот 135-сантиметровый, 220-килограммовый промышленный робот имеет 15 суставов – по 7 в каждой руке и один в туловище. Если его запрограммировать, он способен не только делать лепешки. На выставке, где был представлен этот робот, он смог собрать одноразовый фотоаппарат, состоящий из двенадцати деталей. Роботы-футболисты. Каждый год проходит международный чемпионат по футболу среди роботов – RoboCup. В этом чемпионате между собой соревнуются команды разработчиков со всего мира. Эти роботы маленькие, неповоротливые, неуклюжие. Но из года в год они становятся все более совершенными. Робот-модель. Создан первый робот-модель. Выглядит этот робот как двадцатилетняя японка ростом 155 сантиметров. Она умеет имитировать походку и позы профессиональных манекенщиц. Это достигается за счет 30 моторов, отвечающих за движения тела и еще 8, отвечающих за мимику. Альберт Эйнштейн. Робот должен быть не только красивым, но и умным. Видимо, именно так думал американец Дэвид Хенсон, когда создавал робота с лицом Альберта Эйнштейна. Этот робот умеет воспроизводить мимику великого ученого. Он может смеяться, хмуриться, подмигивать, в зависимости от реакции окружающих. Он умеет распознавать более десятка мимических движений и отвечать на них взаимностью. Самый маленький робот-гуманоид. На Тайване создали робота, который занесен в Книгу Рекордов Гиннеса как самый маленький в мире робот-гуманоид. При росте 15.3 сантиметра и весе 250 граммов он умеет ходить, танцевать и отжиматься. Он даже знает несколько движений из боевого искусства тай-чи. Робот-няня. На выставке COMPUTEX TAIPEI 2009 был представлен робот TGR-W1, созданный для того, чтобы быть ближайшим помощником человека – няней, учителем, экскурсоводом, сиделкой. Он специально настроен на коммуникацию с людьми через звук, жесты и изображения. TGR-W1 также имеет встроенную инфракрасную и ультразвуковую систему, позволяющую ему обнаруживать и избегать препятствия, как в помещении, так и на улице. Колибри. Американская компания AeroVironmen создала по заказу военных робота, маскирующегося под птицу колибри. Он даже умеет летать за счет взмахов своих крыльев. Правда, максимальная длительность полетов этого робота-птицы равна всего лишь двадцати секундам. Ведутся активные работы в области разработки и производства роботов, предназначенных для спасения людей в завалах, высадки на других планетах и астероидах и даже для проведения хирургических операций в полевых условиях. Похожие работы проводятся в российском научном центре сердечно-сосудистой хирургии имени Бакулева РАМН. Используемый там робот имеет несколько манипуляторов, способных держать различные инструменты. Он может работать в самых неудобных и недоступных для человека положениях. Врач за монитором следит за зоной операции и управляет манипуляторами, подавая через компьютер голосовые команды [1]. В частности, есть сведения о том, что один из робототехнических комплексов испытывается на радиозаводе в Ижевске. Машина с индексом МРК-002-БГ-57, как свидетельствуют некоторые публикации, обладает гусеничным ходом, может работать порядка 10 часов в автономном режиме или же управляться дистанционно с расстояния до 5 км. Данный российский боевой робот оснащен широким спектром электронной аппаратуры - дальномером, тепловизором, вычислителем. Машина неплохо вооружена: на ней стоит пулемет Калашникова, гранатомет, а также автоматическое оружие типа "Корд". Устройство, разработанное в Ижевске, весит порядка 900 кг, развивает скорость до 45 км/ч и работает на бензиновом моторе. Автономность робота - одно из ключевых отличий от зарубежных аналогов, в частности американских, которые, как отмечают некоторые эксперты, могут в полной мере эффективно функционировать только в режиме управления человеком. Также, имеются сведения о том, что еще один российский боевой робот будет создаваться на базе машины "Тигр". Соответствующий комплект будет оснащен мощным противотанковым оружием типа "Корнет". Однако публичной информации о данной разработке пока очень немного. В ближайшее время в армию РФ должны поступить небольшие роботы-разведчики, выпускаемые компанией "Созвездие". Предназначены они главным образом для работы под землей. Эти машины способны, к примеру, определять то, сколько находится на поверхности грунта боевой техники противника, ее возможный тип, а также количество солдат, находящихся на той же площади. Машина от "Созвездия" может выполнять часть программ в автономном режиме. Компания "Сервосила" также выпускает небольшие роботы, которые могут быть задействованы в разведке. Так, например, машина "Инженер" интересна тем, что может залезать по лестницам, захватывать небольшие объекты. Обладает "Инженер" системой высокоточного визуального распознавания окружающих объектов, а также модулем навигации. Суперкомпьютер IBM Watson выиграл в 2011 году у сильнейших игроков во втором матче интеллектуальной викторины Jeopardy (российский аналог - "Своя игра"), став победителем трехдневного турнира. Успех Watson в турнире Jeopardy стал подтверждением прогресса в области автоматической обработки запросов, сформулированных на естественном языке. Согласно опубликованному отчету 2011 IBM Tech Trends Report о тенденциях развития технологий, разработчики во всем мире считают, что уникальные аналитические возможности технологии IBM Watson преобразят индустрии, которые управляют огромными массивами данных. Участники опроса указали образование и здравоохранение в качестве отраслей, которые могут максимально выиграть от применения инноваций Watson – наряду со сферой финансовых услуг, науками о жизни (биологией, биохимией, иммунологией, генетикой, физиологией, экологией и т.п.) и государственным сектором. Компания IBM представила летом 2014 года дополнение к когнитивным возможностям суперкомпьютера Watson, которое позволяет исследователям ускорить темпы научных исследований путем нахождения ранее неизведанных связей при анализе больших данных. Авторы мобильных и настольных приложений теперь могут использовать в своих разработках еще пять сервисов когнитивной системы IBM Watson. Они предназначены для преобразования речи в текст и обратно, распознавания образов, концептуального поиска и сравнительного анализа вариантов с помощью принципа Парето. Сервис преобразования речи в текст даст мобильным приложениям возможность реагировать на голосовые команды — примерно так же, как это делает система Siri на устройствах Apple. В IBM утверждают, что скорость распознавания речи очень высока. Синтезатор речи говорит тем же голосом, каким говорил суперкомпьютер Watson, участвуя в телевизионной игре Jeopardy в 2011 году. Поддерживаются английский и испанский языки. Сервис распознавания образов анализирует изображение или видео и генерирует список ключевых слов, описывающих его. Он может различить на изображении предметы, определить характер происходящего и место действия. Наконец, сервис анализа помогает выбрать из нескольких вариантов с известными параметрами вариант, оптимальный с точки зрения заданных критериев. Его можно использовать, например, для выбора лучшего варианта лечения пациента или наиболее подходящего автомобиля при заданной цене. Вопросы создания кибернетических устройств, способных выполнять присущие человеку действия, все больше привлекают разработчиков. Современный подход опирается на теории адаптивных систем и эволюционного развития. В соответствии с данным подходом предполагается, что устройства управления должны самостоятельно мутировать и развиваться, менять свою форму, размеры и так далее. Так, например, DARPA финансирует проект создания системы сборки конструкций из кубиков Лего. Система состоит из манипулятора, видеокамеры и компьютера. В качестве исходных данных в систему заложены только элементарные правила стыковки кубиков и цель – конечное сооружение, после чего система начинает пробовать различные комбинации, экспериментально определяя прочность и стабильность собираемых конструкций. Пока такая система способна за один день собрать двухметровый игрушечный мост и кран, способный поднять груз 0,5 кг. Самое главное, что эти конструкции отвечают всем инженерным требованиям по надежности, о которых система и не подозревает. Следующая задача – автоматизировать сборку системой себе подобных роботов. Получило дальнейшее развитие такое традиционное направление ИИ как экспертные системы (ЭС). В современных ЭС, основной акцент делается на принятие оперативных решений в реальном масштабе времени. Это объясняется потребностями современного бизнеса. Коммерческие ЭС контролируют крупные промышленные процессы, управляют большими сетями, распределенными СУБД, подсказывая оператору, как поступить в сложной обстановке, а в критических ситуациях берут управление на себя. Экспертная система MIXER оказывает помощь программистам в написании микропрограмм для разработанной Texas Instruments СБИС TI990. По заданному описанию микропрограммы система получает оптимизированные микропрограммы для TI990. MIXER содержит знания по микропрограммированию для TI990, взятые из руководства и из анализа микропрограммы управляющего ПЗУ TI990. Сюда относятся знания о том, как преобразовывать введенные описания в наборы промежуточных операций, как выделить соответствующие регистры под переменные и как преобразовать промежуточные операции в наборы микроопераций. MIXER использует эти знания, чтобы определить, какие микрооперации являются лучшими для реализации микропрограммы. Система представляет знания в виде правил и данных, обладает унификацией, управляемой механизмом вывода, и динамическим возвратом. MIXER реализована на языке Пролог. Она была разработана в Токийском университете и доведена до уровня демонстрационного прототипа. История развития инструментальных средств (ИС) для создания ЭС реального времени началась в 1985 г., когда фирма Lisp Machine Inc. выпустила систему Picon для символьных ЭВМ Symbolics. Успех этого ИС привел к тому, что группа ведущих разработчиков Picon в 1986 г. образовала частную фирму Gensym, которая, значительно развив идеи, заложенные в Picon, в 1988 г. вышла на рынок с ИС под названием G2, версия 1.0. Основное предназначение программных продуктов фирмы Gensym (США) - помочь предприятиям сохранять и использовать знания и опыт их наиболее талантливых и квалифицированных сотрудников в интеллектуальных системах реального времени, повышающих качество продукции, надежность и безопасность производства и снижающих производственные издержки. О том, как фирме Gensym удается справиться с этой задачей, говорит хотя бы то, что сегодня ей принадлежат 50% мирового рынка экспертных систем, используемых в системах управления. В настоящее время существует множество оболочек для разработки ЭС. Малая Экспертная Система 2.0 - Программа является простой экспертной системой, использующей байесовскую систему логического вывода. Она предназначена для проведения консультации с пользователем в какой-либо прикладной области (на которую настроена загруженная база знаний) с целью определения вероятностей возможных исходов и использует для этого оценку правдоподобности некоторых предпосылок, получаемую от пользователя. Важным достоинством данной программы является возможность создания и применения собственной базы знаний. ACQUIRE - система обнаружения знаний и оболочка экспертной системы. Это - законченная среда для разработки и поддержки интеллектуальных прикладных программ. Система содержит в себя методологию пошагового представления знаний, что позволяет специалистам в проблемной области непосредственно участвовать в процессе приобретения, структурирования и кодирования знания. Особенностью оболочки является структурированный подход к приобретению знаний; модель приобретения знаний основана на распознавании образов; знания представлены как объекты, продукционные правила и системы правил в табличной форме; оболочка позволяет выполнять обработку неопределенных качественных знаний; содержит средства вывода и документацию баз знаний в среде гипертекста. ACTIVATION FRAMEWORK работает на персональных компьютерах (под управлением операционных систем DOS, Windows) и на автоматизированных рабочих станциях UNIX. Это - не традиционная оболочка экспертной системы, а скорее инструмент для формирования прикладных программ обработки данных в реальном времени. Система конкурирует с оболочкой G2 фирмы GENSYM. ActiveAgentX - может применяться в системах поддержки принятия решений, содержащих правила , которые могут быть автоматически получены по корпоративным сетям при использовании WEB-браузеров Microsoft Windows. ActiveAgentX может быть также встроен внутрь Java аплетов, которые используются браузером Microsoft Internet Explorer или автономно, как прикладная программа Java, написанная на языке Microsoft Java или Visual J ++. При использовании в сети WWW ActiveAgentX предоставляет вполне развитые средства создания экспертных систем, которые используют интерактивные средства представления интеллектуальной информации на машинах клиента или в Web-браузерах. пакет создан в Haley Corporation. ART*Enterprise - самая последняя из сред разработки, основанных на правилах, ведущих начало от систем ИИ середины 1980-ых. Это - среда разработки прикладных программ широкого применения, объединяющая в себе правила, объектно-ориентированную систему, которая содержит такие особенности, которые в настоящее время не представлены ни в C++, ни в языке Smalltalk; и содержит большую совокупность классов объектов для разработки на различных платформах (от Windows до OS/2 и Unix), поддерживает доступ к базам данных (основанный SQL- и ODBC-запросах), и мультизадачный режим доступа. ART*ENTERPRISE среда поддерживает обратный поиск решения от фактов к цели; можно также реализовать поиск решения от цели к фактам. ARITY Expert Development Package - это экспертная система, которая интегрирует продукционное и фреймовое представления знаний с различного рода коэффициентами уверенности. CAM Software содержит два инструмента для создания экспертных систем: DClass и LogicTree Система DClass - использует дерево решений, предназначена для построения прикладных программ. LogicTree - система принятия решений, разработанная для использования профессионалами - непрограммистами. COMDALE/C, COMDALE/X и ProcessVision. COMDALE/C - экспертная система реального времени, предназначенная для наблюдения и контроля над процессами в условиях производства. . + COMDALE/C позволяет вырабатывать рекомендации, заключения об управляющих воздействиях в непрерывном процессе принятия решения. Она обрабатывает неопределенные знания и данные, и имеет открытую архитектуру. Другие особенности включают: объектно-ориентированную конфигурацию; возможности организации работы в сети; обработку прерываний; хранение и обработку данных; поддерживает работу с базой данных в реальном масштабе времени, и интерфейсы с системами передачи данных, такими как PLCs и другими устройствами ввода-вывода. + COMDALE/X - консультационная экспертная система, которая работает в режиме реального времени. Для принятия решения система организует диалог с пользователем. COMDALE/X совместно с системой COMDALE/C используется как инструмент разработки экспертных систем реального времени. COMDALE/X позволяет включить гипертекст в экспертную систему, что позволяет создавать hyper-справочники с удобным интерфейсом. +PROCESS Vision - пакет программ для управления процессами в реальном времени, базируется на открытой и модульной архитектуре. ProcessVision содержит графический интерфейс оператора; объектно-ориентированный дисплей, выполняет проверку правильности показаний датчиков и поддерживает связь с неограниченным количеством производственной контрольно-измерительной аппаратурой в одной глобальной среде. C - PRS - (Процедурно - ориентированная система рассуждений, написанная на языке C) реализует процедурное представление знаний. Это позволяет пользователю выражать и представить условные последовательности комплексных действий и гарантировать их выполнение в реальном времени в среде прикладной программы. Система C - PRS полезна в процессе контроля и управления технологическими процессами. PRS технология применялась в различных задачах и запросах в реальном времени, например, для контроля над несколькими спутниковыми системами NASA, в системах диспетчерского управления сетей электросвязи (Телесвязь Австралия), при управлении подвижными роботами (SRI, LAAS), в системе контроля над полетами и в системе обнаружения самолетов (Grumman). C - PRS работает на многочисленных платформах и операционных системах, включая SPARC, DECstation, Sony News, Hewlett Packard, VxWorks, и другие. The Easy Reasoner (TM) - Поисковая система, основанная на поиске подходящих рассуждений в адаптивной ассоциативной памяти. Система отыскивает в памяти событие, подобное новому событию, используя " Запрос на пример". Поддерживает базы данных xBase, ODBC, SQL. Система автоматически фильтрует помехи для упрощения решающих деревьев; эффективно отыскивает события, подобные новому в больших базах данных; поддерживает составные индексы в базе данных; классифицирует новую информацию, используя любое решающее дерево в автоматическом или интерактивном режиме. Выполняет адаптивное, контекстно-зависимое, заданное по умолчанию рассуждение; вычисляет адаптивную оценку, используя решающие деревья; восстанавливает (отыскивает) подобные записи по контексту; различает различные формы записи английских слов; автоматически определяет объем информации в слове ECLIPSE работает на персональных компьютерах (DOS, Windows), а также имеются версии для систем V Unix и POSIX. Синтаксис языка, используемого в пакете, совместим с языком системы CLIPS, разработанной для NASA. Отличия заключаются в управлении данными путем сопоставления с образцом, использовании прямого и обратного вывода, в поддержке множества целей, объектно-ориентированном представлении знаний и интегрировании с dBase. Exsys Developer - интеллектуальная система, которая может быть использована для разработки базы знаний в любой предметной области. В систему включены средства отладки и тестирования программы,редактирования для модификации знаний и данных. Основной частью экспертной системы является база знаний, которая накапливается в процессе развития системы. База знаний содержит правила типа: IF (условие) THEN (заключение) IF (условие) THEN (заключение 1) ELSE (заключение 2) Правила могут существовать с некоторой долей вероятности, которая выражается коэффициентом уверенности. Величину этого коэффициента задает эксперт при разработки базы знаний. EXSYS-программы рассчитаны на то, что экспертные системы будут создаваться экспертами проблемной среды совместно с профессионалами в области построения инженерных знаний. Exsys Developer работает в среде MS-DOS, MS Windows, Macintosh, Sun OS, Solaris, Unix и Vax. Система поддерживает обратный вывод от фактов к цели, линейное программирование, нечеткую логику, нейронные сети, и имеет SQL интерфейс FLEX - гибридная экспертная система, работающая на различных платформах. Система предлагает фреймовое, процедурное и продукционное представление знаний. FLEX чередует прямой и обратный методы поиска решений, множественное наследование свойств, присоединенные процедуры, автоматическую систему вопросов и ответов. Правила, фреймы и вопросы написаны на естественном англо-подобном языке. Язык спецификаций (KSL) позволяет разрабатывать легко читаемые и простые в поддержке базы знаний. FLEX написан на языке Пролог. FLEX использовался в многочисленных коммерческих экспертных системах, например, в финансовых системах типа Администратор начисления пенсии. G2 - это объектно ориентированная среда для разработки и сопровождения приложений реального времени, использующих базы данных. G2 Фирмы Gensym предлагает графическую среду для создания интеллектуальных прикладных программ, которые контролируют, диагностируют, и управляют динамическими событиями в сетевых и моделируемых средах. Среда G2 для создания правил, моделей, и процедур использует структурированный естественный язык. Экспертная система G2 является основой всех прикладных программ фирмы Gensym. Программы включают в себя G2, видеоадаптер, который позволяет использовать визуальную среду программирования для создания интеллектуальных прикладных программ управления. Возможности предлагаемого инструментального средства G2 следующие: Объектно-ориентированная технология: связи между объектами; отношения между объектами; иерархия объектов. Представление знаний: правила (общие и конкретные); процедуры; динамические модели. Механизм рассуждений: от данных; от цели; сканирование; метарассуждения (события, фокусирование на классах объектов или правил); одновременное выполнение правил и/или процедур. Графическое определение объектов. Клонирование объектов и их групп. Графические пользовательские интерфейсы для различных категорий пользователей. Многопользовательская кооперативная разработка приложения. Распределенное приложение. G2 для создания правил, моделей, и процедур использует структурированный естественный язык. Экспертная система G2 является основой всех прикладных программ фирмы Gensym. Программы включают в себя G2, видеоадаптер, который позволяет использовать визуальную среду программирования для создания интеллектуальных прикладных программ управления. NeurOn-Line и другие программы фирмы позволяют пользователям легко создавать нейросетевые прикладные программы. G2 совмещает выполнение правил и процедур в текущий момент времени со способностями рассуждений спустя некоторое время. Руководство по G2 позволяет пользователям, легко создавать графические интерфейсы и системы диагностирования в реальном масштабе времени. Компания Telewindows Gensym's создала мощную более универсальную среду клиент/сервер, которая позволяет пользователям совместно использовать прикладные программы на G2. Gensym также предлагает мосты (программы) для связи с другими программам (на C и АДА) и системы передачи и обработки данных о движущихся объектах в реальном времени, включая реляционные базы данных, распределенные системы управления, и программируемые логические системы. GBB - поддерживает фреймовые рабочие области, содержит высокоэффективный транслятор, фреймовые базы данных и библиотеку, которые поддерживают многомерные алгоритмы поиска целей;KS языки представлений знаний; Универсальные оболочки управления и утилиты администрирования порядком выполнения операторов; интерактивные, графические дисплеи для контроля и исследования; компоненты управления и рабочие области. Эти компоненты составляют инфраструктуру, необходимую для формирования прикладных программ. GURU - оболочка экспертной системы, в который предлагается широкое разнообразие инструментальных средств обработки информации, объединенных с возможностями, основанными на знаниях, такими, вывод решения от фактов к цели, вывода решения от цели к фактам, смешанное формирование цепочки вывода, многозначные переменные и нечеткие рассуждения. HUGIN - пакет программ для конструирования моделей, основанных на системах экспертных оценок в областях, характеризующихся существенной неопределенностью. Hugin система содержит удобную для использования дедуктивную систему вывода, основанную на вероятностных оценках, которую можно применить к сложным сетям с причинно-следственными вероятностными связями между объектами. ILOG RULES - содержит высоко эффективный механизм логического вывода, основанный на правилах. Это - инструмент вывода от фактов к цели, написанный на языке C++ ( следовательно это объектно-ориентированный и поддерживающий передачу наследственных характеристик механизм). Система также снабжена библиотекой C++. Она выполняется фактически на любой Unix платформе, а также на персональных компьютерах, работающих в среде DOS или OS/2. Система позволяет транслировать правила в C / C ++ код, и строить объектно-ориентированную модель данных в C++. C / C ++ код может быть включен в условия правил и действия, связанные с правилами. OPERATION EXPERT - графическое программное средство для определения повреждений в Интеллектуальных сетях связи. Система создана на основе программных средств фирмы Gensym (оболочки G2). Система использует модель сети и связанные с ней прикладные программы для отображения объектов и для описания их поведения и характеристик. Систем аподдерживает архитектуру клиент-сервер, учитывает параллельную обработку данных в реальном масштабе времени. PROSPECT EXPLORER - экспертная система, использующая нейросетевые вычислительные технологии для помощи геологам в обнаружении горных аномалий. MIT - пакет программ для улучшения эффективности и снижения затрат в процессе выделения минералов. Использует различные факторы, начиная от параметров процесса выделения минерала и кончая климатическими факторами для создания нейросетевых моделей процесса. ReThink фиры Gensym - программный инструмент для графического проектирования, моделирования и оперативного управления бизнес - процессами. Опирается на пакет G2. 1.3 Классификация систем искусственного интеллекта. Для систем искусственного интеллекта характерны следующие признаки [2]: • развитые коммуникативные способности; • умение решать сложные задачи; • способность к самообучению; • адаптивность. В соответствии с данными признаками, системы искусственного интеллекта, можно разделить на классы, представленные на рис.1.1 [2]. Рис.1.1 Классификация систем искусственного интеллекта 1.3.1 Системы с интеллектуальным интерфейсом Базы знаний (БЗ) позволяют в отличии от традиционных баз данных (БД) обеспечивать выборку необходимой информации, не хранимой явно, а выводимой из совокупности хранимых данных. Естественно-языковые интерфейсы применяются для доступа к БЗ, контекстного поиска текстовой информации, голосового ввода команд, машинного перевода с иностранных языков. Гипертекстовые системы используются для реализации поиска по ключевым словам в БД с текстовой информацией. Системы контекстной помощи являются частным случаем гипертекстовых систем и естественно-языковых систем. В отличие от них пользователь сам описывает проблему, а система выполняет поиск относящихся к ситуации рекомендаций. Системы когнитивной графики ориентированы на общение с пользователем посредством графических образов, которые генерируются в соответствии с изменениями параметров моделируемых или наблюдаемых процессов. Когнитивная графика позволяет визуализировать процесс решения задачи. При достаточно продуманной системе визуализации образы, возникающие на экране, могут помочь пользователю, увидеть те закономерности или пути решения задачи, которые ранее для него не были доступны. 1.3.2 Экспертные системы Область исследования ЭС называется инженерией знаний. Экспертные системы предназначены для решения неформализованных задач, то есть задач, решаемых с помощью неточных знаний, которые являются результатом обобщения многолетнего опыта работы и интуиции специалистов. Неформализованные знания обычно представляют собой эвристические приемы и правила. ЭС обладают следующими особенностями: • алгоритм решения не известен заранее, а строится самой ЭС с помощью символических рассуждений, базирующихся на эвристических приемах; • ясность полученных решений, то есть система «осознает» в терминах пользователя, как она получает решение; • способность анализа и объяснения своих действий и знаний; • способность приобретения новых знаний от пользователя-эксперта, не знающего программирования, и изменения в соответствии с ними своего поведения; • обеспечение «дружественного», как правило, естественно-языкового интерфейса с пользователем. ЭС охватывают самые разные предметные области, среди которых преобладают медицина, бизнес, производство, проектирование и системы управления. Классифицирующие ЭС решают задачи распознавания ситуаций. Основным методом формирования решений в них является дедуктивный логический вывод. Доопределяющие ЭС используются для решения задач с не полностью определенными данными и знаниями. В качестве методов обработки неопределенных знаний могут использоваться байесовский вероятностный подход, коэффициенты уверенности, нечеткая логика. Трансформирующие ЭС реализуют преобразование знаний в процессе решения задачи. В ЭС данного класса используются различные способы обработки знаний: • генерация и проверка гипотез; • логика предположений и умолчаний; • использование метазнаний для устранения неопределенности. Мультиагентные системы – это динамические ЭС, основанные на интеграции разнородных источников знаний, которые обмениваются между собой полученными результатами в процессе решения задач. Системы данного класса имеют следующие возможности: • реализация альтернативных рассуждений; • распределённое решение проблем, разделяемое на параллельно решаемые подзадачи; • применение различных стратегий вывода заключений; • обработка больших массивов информации из БД; • использование математических моделей и внешних процедур для имитации развития ситуаций. 1.3.3 Самообучающиеся системы Системы данного класса основаны на методах автоматической классификации ситуаций из реальной практики, или на методах обучения на примерах. Примеры составляют так называемую обучающую выборку. Элементы обучающей выборки описываются множеством классификационных признаков. Стратегия обучения «с учителем» предполагает задание для каждого примера эталонных значений признаков, показывающих его принадлежность к определенному классу. При обучении «без учителя» система должна самостоятельно выделять классы объектов по степени близости значений классификационных признаков. В процессе обучения проводится автоматическое построение обобщающих правил или функций, описывающих принадлежность объекта к классам, которыми система будет впоследствии пользоваться при определении незнакомых ситуаций. При этом из обобщающих правил автоматически формируется БЗ, которая периодически корректируется. Индуктивные системы позволяют обобщать примеры на основе принципа индукции «от частного к общему». Процедура обобщения сводится к классификации примеров по значимым признакам. Нейронные сети – обобщенное название группы математических моделей и алгоритмов, обладающих способностью обучаться на примерах, «узнавая» впоследствии черты встреченных образцов и ситуаций. Нейронные сети используются для решения задач аппроксимации и идентификации функций, классификации и распознавания образов, обработки сигналов, сжатия данных, прогнозирования и адаптивного управления. Нейронная сеть – это кибернетическая модель нервной системы, которая представляет собой совокупность большого числа нейронов, топология соединения которых зависит от типа сети. Нейроны соединяются в слои. Различают сети прямого распространения и рекурентные сети (с обратными связями). Чтобы создать нейронную сеть для решения какой-либо задачи, необходимо выбрать тип сети и определить параметры сети в процессе ее обучения. В системах, основанных на прецедентах, БЗ содержит описания конкретных ситуаций (прецеденты). Поиск решений осуществляется на основе аналогий по значениям соответствующих признаков. В отличие от индуктивных систем допускается нечеткий поиск с получением множества допустимых альтернатив, каждая из которых может оцениваться некоторым коэффициентом уверенности. Информационные хранилища отличаются от БЗ. Хранилище данных – это предметно-ориентированная, интегрированная, содержащая данные, накопленные за большой интервал времени, автоматизированная система, применяемая для поддержки процессов принятия управленческих решений. Информационное хранилище данных - это совокупность программно-аппаратных средств, позволяющих предоставлять данные в целостном виде для последующего анализа и принятия управленческих решений, чаще всего в виде архива файлов (программ). Технологии извлечения знаний из хранилища данных основаны на методах статистического анализа и моделирования, ориентированных на поиск моделей и отношений, скрытых в совокупности данных. Для извлечения значимой информации используются специальные методы (OLAP – анализ, DATA Mining или Knowledge Discovery), основанные на применении методов математической статистики, нейронных сетей, индуктивных методов и других методах. 1.3.4 Адаптивные системы Адаптивные системы должны удовлетворять ряду требований: • адекватно отражать знания проблемной области в каждый момент времени; • быть пригодными для легкой и быстрой реконструкции при изменениях проблемной среды. Ядром систем данного класса является модель проблемной области, поддерживаемая в специальной БЗ – репозитории. Ядро системы управляет процессами генерации или переконфигурирования программного обеспечения. При разработке адаптивных систем используется типовое или оригинальное проектирование. Реализация оригинального проектирования основана на использовании CASE- технологий (Designer2000, SilverRun, Natural Light Strom и др.). При типовом проектировании осуществляется адаптация типовых разработок к особенностям проблемной области. При этом используются инструментальные средства компонентного (сборочного) проектирования (R/3, BAAN, Prodis и др.). При использовании CASE- технологий при изменении проблемной области каждый раз применяется генерация программного обеспечения, а при использвании сборочной технологии – конфигурирование программ или их переработка. 1.4 Характеристики знаний. Основной проблемой, решаемой во всех системах ИИ, является проблема представления знаний. Информация представляется в компьютере в процедурной и декларативной форме. В процедурной форме представлены программы, в декларативной – данные. В системах искусственного интеллекта возникла концепция новой формы представления информации – знания, которая объединила в себе черты как процедурной, так и декларативной информации. Перечислим основные характеристики знаний: 1. Внутренняя интерпретируемость. Каждая информационная единица должна иметь уникальное имя, по которому система находит ее, а также отвечает на запросы, в которых это имя упомянуто. Данные в памяти лишены имен и могут идентифицироваться только программой, извлекающей их из памяти. При переходе к знаниям в память вводится информация о некоторой протоструктуре информационных единиц и словари имен данных. Каждая единица информации будет экземпляром протоструктуры. СУБД обеспечивают реализацию внутренней интерпретируемости информации, хранимой в базе данных. 2. Структурированность. Информационные единицы должны соответствовать «принципу матрешки», то есть рекурсивной влоенности одних информационных единиц в другие. Другими словами, должна существовать возможность произвольного установления между отдельными информационными единицами отношений типа «часть – целое», «род – вид» или «элемент – класс». 3. Связность. Между информационными единицами должна быть предусмотрена возможность установления связей различного типа, характеризующих отношения между информационными единицами. Семантика отношений может носить как декларативный характер, например, в отношениях «одновременно» и «причина – следствие», так и процедурный характер, например, в отношении «аргумент – функция». Все отношения можно разделить на четыре категории: отношения структуризации (задают иерархию информационных единиц), функциональные отношения (несут процедурную информацию, позволяющую вычислять одни информационные единицы через другие), каузальные отношения (задают причинно-следственные связи) и семантические отношения (все остальные отношения). 4. Семантическая метрика. Между информационными единицами задают отношения релевантности, которые характеризуют ситуационную близость информационных единиц, то есть силу ассоциативной связи между информационными единицами (например, «покупка» или «регулирование движения на перкрестке»). Отношение релевантности позволяет находить знания, близкие к найденным ранее знаниям. 5. Активность. Выполнение программ в информационных системах должно инициализироваться не командами, а состоянием информационной базы, например, появлением в базе фактов или описаний событий или установление связей между информационными единицами. Перечисленные характеристики определяют разницу между данными и знаниями, при этом базы данных перерастают в базы знаний. 1.5 Модели представления знаний. В интеллектуальных системах используются четыре основных типа моделей знаний: 1. Логические модели. В основе моделей такого типа лежит формальная система, задаваемая четверкой вида M = . Множество T есть множество базовых элементов, например слов из некоторого словаря, или деталей из некоторого набора. Для множества T существует некоторая процедура определения принадлежности или непринадлежности произвольного элемента x к данному множеству T. Процедура такой проверки может быть любой, но она должна давать ответ на вопрос, является ли x элементом множества T за конечное число шагов. Обозначим эту процедуру P(T). Множество S есть множество синтаксических правил. С их помощью из элементов T образуют синтаксически правильные совокупности. Например, из слов словаря строятся синтаксически правильные фразы, а из деталей собираются конструкции. Существует некоторая процедура P(S), с помощью которой за конечное число шагов можно определить, является ли совокупность X синтаксически правильной. Во множестве синтаксически правильных совокупностей выделяется некоторое подмножество A. Элементы A называются аксиомами. Как и для других составляющих формальной системы, должна существовать процедура P(A) , с помощью которой для любой синтаксически правильной совокупности можно определить принадлежность ее к множеству A. Множество B есть множество правил вывода. Применяя их к элементам A, можно получать новые синтаксически правильные совокупности, к которым снова можно применять правила из B. Так формируется множество выводимых в данной формальной системе совокупностей. Если имеется процедура P(B), с помощью которой можно определить для любой синтаксически правильной совокупности, является ли она выводимой, то соответствующая формальная система называется разрешимой. Это показывает, что именно правила вывода являются наиболее сложной составляющей формальной системы. Для знаний, входящих в базу знаний, можно считать, что множество A образуют все информационные единицы, которые введены в базу знаний извне, а с помощью правил вывода из них выводятся новые производные знания. Другими словами, формальная система представляет собой генератор порождения новых знаний, образующих множество выводимых в данной системе знаний. Это свойство логических моделей позволяет хранить в базе лишь те знания, которые образуют множество A, а все остальные знания получать из них по правилам вывода. 2. Сетевые модели. Сетевые модели формально можно описать в виде H = . Здесь I есть множество информационных единиц; C1, C2,…, Cn - множество типов связей между ними. Отображение G задает связи из заданного набора на типы связей между информационными единицами, входящими в I. В зависимости от типов связей, используемых в модели, различают классифицирующие сети, функциональные сети и сценарии, нейронные сети. В классифицирующих сетях используются отношения структуризации. Такие сети позволяют в базах знаний вводить иерархические отношения между информационными единицами. Функциональные сети характеризуются наличием функциональных отношений. Их часто называют вычислительными моделями, так как они позволяют описывать процедуры «вычислений» одних информационных единиц через другие. Нейронные сети можно отнести к классу функциональных сетей, однако нечёткие продукционные нейронные сети представляют собой гибридную модель, соединяющую в себе черты логической, продукционной и сетевой моделей. В сценариях используются каузальные отношения, а также отношения типа «средство – результат». Если в сетевой модели допускаются связи различного типа, то ее называют семантической сетью. Семантическая сеть – это ориентированный граф, вершины которого – понятия, а дуги – отношения между ними. Термин семантическая означает смысловая, а сама семантика – это наука, устанавливающая отношения между символами и объектами, которые они обозначают, т.е. наука, определяющая смысл знаков. Понятиями обычно выступают абстрактные или конкретные объекты, а отношения – это связи типа: «это» («is»), «имеет частью» («has part»), «принадлежит», «любит». Характерной особенностью семантических сетей является обязательное наличие трёх типов отношений: • класс – элемент класса; • свойство – значение; • пример элемента класса. Можно ввести несколько классификаций семантических сетей. Например, по количеству типов отношений: • ·однородные (с единственным типом отношений); • ·неоднородные (с различными типами отношений). По типам отношений: • бинарные (в которых отношения связывают два объекта); • ·n-арные (в которых есть специальные отношения, связывающие более двух понятий). Наиболее часто в семантических сетях используются следующие отношения: 1. Связи типа «часть-целое» («класс-подкласс», «элемент-множество» и т.п.); 2. Функциональные связи (определяемые обычно глаголами «производит», «влияет»...); 3. Количественные (больше, меньше, равно...); 4. Пространственные (далеко от, близко от, за, под, над...); 5. Временные (раньше, позже, в течение...); 6. Атрибутивные связи (иметь свойство, иметь значение...); 7. Логические связи (и, или, не) и др. Проблема поиска решения в базе знаний типа семантической сети сводится к задаче поиска фрагмента сети, соответствующего некоторой подсети, соответствующей поставленному вопросу. Основное преимущество этой модели – соответствие современным представлениям об организации долговременной памяти человека. Недостаток модели – сложность поиска вывода на семантической сети. 3.Продукционные модели. Продукционная модель или модель, основанная на правилах, позволяет представить знания в виде предложений типа «Если (условие), то (действие)». Под условием понимается некоторое предложение — образец, по которому осуществляется поиск в базе знаний, а под действием — действия, выполняемые при успешном исходе поиска (они могут быть промежу­точными, выступающими далее как условия, и терминальными или целевыми, завершающими работу системы). При использовании продукционной модели база знаний состоит из набора правил, Программа, управляющая перебором правил, называется машиной вывода. Чаще всего вывод бывает прямой (от данных к поиску цели) или обратный (от цели для ее подтверждения – к данным). Данные — это исходные факты, на основании которых запускается машина вывода. В базе правил должны быть заданы специальные процедуры управления правилами, с помощью которых происходит актуализация правил и выполнение того или иного правила из числа актуализированных. Продукционная модель чаще всего применяется в промышленных экспертных системах. Она привлекает разработчиков своей наглядностью, высокой модульностью, лёгкостью внесения дополнений и изменений и простотой механизма логического вывода. 4.Фреймовые модели. Фреймы (англ. frame – каркас или рамка) предложены М. Минским в 1970-е гг. как структура знаний для восприятия пространственных сцен. Эта модель, как и семантическая сеть, имеет глубокое психологическое обоснование. Под фреймом понимается абстрактный образ или ситуация. В психологии и философии известно понятие абстрактного образа. Например, слово «комната» вызывает у слушающих образ комнаты: «жилое помещение с четырьмя стенами, полом, потолком, окнами и дверью, площадью 6 – 20 м2». Из этого описания ничего нельзя убрать (например, убрав окна, мы получим уже чулан, а не комнату), но в нём есть «дырки», или «слоты», – это незаполненные значения некоторых атрибутов – количество окон, цвет стен, высота потолка, покрытие пола и др. В теории фреймов такой образ называется фреймом. Фреймом называется также и формализованная модель для отображения образа. В отличие от моделей других типов во фреймовых моделях фиксируется жесткая структура информационных единиц, которая называется протофреймом. В общем виде она выглядит следующим образом: (Имя фрейма: Имя слота 1 (тип слота 1, значение слота, присоединённая процедура 1) Имя слота 2 (тип слота 2, значение слота 2, присоединённая процедура 2) . . . . . . . . . . . . . . Имя слота К (тип слота К, значение слота К, присоединённая процедура К)). Значением слота может быть все, что угодно: имя другого фрейма, числа, математические соотношения, тексты на естественном языке, программы, правила вывода, ссылки на другие слоты данного фрейма или других фреймов. В качестве значения слота может выступать набор слотов более низкого уровня, что позволяет реализовать во фреймовых представлениях «принцип матрешки». При конкретизации фрейма ему и слотам присваиваются имена, и происходит заполнение слотов. Таким образом, из протофреймов получаются фреймы-экземпляры. Переход от исходного протофрейма к фрейму-экземпляру может быть многошаговым, за счет постепенного уточнения значений слотов. Связи между фреймами задаются значениями специального слота с именем «Связь». Некоторые специалисты по ИС не выделяют фреймовые модели в отдельный класс, так как в ней объединены все основные особенности моделей остальных типов. В настоящее время понятие фрейма сливается с понятием «объекта» в объектно-ориентированных языках программирования. Модель фрейма является достаточно универсальной, поскольку позволяет отобразить всё многообразие знаний о мире через: ◦ фреймы-структуры, для обозначения объектов и понятий (заём, залог, вексель); ◦ фреймы-роли (менеджер, кассир, клиент); ◦ фреймы-сценарии (банкротство, собрание акционеров, празднование именин); ◦ фреймы-ситуации (тревога, авария, рабочий режим устройства) и др. Важнейшим свойством теории фреймов является заимствованное из теории семантических сетей наследование свойств. И во фреймах, и в семантических сетях наследование происходит по АКО-связям (A-Kind-Of = это). Слот АКО указывает на фрейм более высокого уровня иерархии, откуда неявно наследуются, т.е. переносятся значения аналогичных слотов. Основным преимуществом фреймов как модели представления знаний является способность отражать концептуальную основу организации памяти человека, а также её гибкость и наглядность. 2 Язык логического программирования ПРОЛОГ 2.1 Логическое программирование и аксиоматические системы Теория формальных систем и, в частности, математическая логика являются формализацией человеческого мышления и представления наших знаний. Если предположить, что можно аксиоматизировать наши знания и можно построить алгоритм, позволяющий реализовать процесс вывода ответов на запрос из знаний, то в результате можно получить формальный метод для получения неформальных результатов. Логическое программирование возникло в эру ЭВМ как естественное желание автоматизировать процесс логического вывода, поэтому оно является ветвью теории формальных систем. Логическое программирование (в широком смысле) представляет собой семейство таких методов решения задач, в которых используются приемы логического вывода для манипулирования знаниями, представленными в декларативной форме [1]. Как писал Джордж Робинсон в 1984 году, в основе идеи логического программирования лежит описание задачи совокупностью утверждений на некотором формальном логическом языке и получение решения с помощью вывода в некоторой формальной (аксиоматической) системе. Такой аксиоматической системой является исчисление предикатов первого порядка, поэтому в узком смысле логическое программирование понимается как использование исчисления предикатов первого порядка в качестве основы для описания предметной области и осуществления резолюционного логического вывода. 2.2 Теоретические основы языка ПРОЛОГ Программа на Прологе включает в себя постановку задачи в виде множества фраз Хорна (раздел clauses) и формулировку теоремы, которую нужно доказать, исходя из множества правил и фактов, содержащихся в этой постановке в виде описания цели (раздел goal). Процесс поиска доказательства основан на методе линейной резолюции (дизъюнкты подбираются в порядке их следования в тексте программы). Проиллюстрируем принцип логического программирования на простом примере: запишем известный метод вычисления наибольшего общего делителя двух натуральных чисел – алгоритм Евклида в виде Хорновских дизъюнктов. Предикат nod – определяет наибольший общий делитель z для натуральных чисел x и y, при этом фразы примут вид: 1. nod (X, X, X). 2. nod (X, Y, Z): - X>Y, U=X-Y, nod (U, Y, Z). 3. nod (X, Y, Z): - Y>X, U=Y-X, nod (X, U, Z). Для вычисления наибольшего общего делителя двух натуральных чисел, например 4 и 6, добавим к описанию алгоритма четвертый дизъюнкт: 4. nod (4, 6, Z). Последний дизъюнкт – это цель, которую мы будем пытаться вывести из первых трех дизъюнктов. 2.3 Основы языка программирования Пролог 2.3.1 Общие положения Язык программирования Пролог (PROgramming LOGic) предполагает получение решения задачи при помощи логического вывода из ранее известных фактов. Программа на языке Пролог не является последовательностью действий – она представляет собой набор фактов и правил, обеспечивающих получение логических заключений из данных фактов. Поэтому Пролог считается декларативным языком программирования. Одной из важнейших особенностей Пролога является то, что он ищет не только ответ на поставленный вопрос, но и все возможные альтернативные решения. Вместо обычной работы программы на процедурном языке от начала и до конца, Пролог может возвращаться назад и просматривать все остальные пути при решении всех частей задачи. Программист на Прологе описывает объекты рассуждений и отношения, а также правила, при которых эти отношения являются истинными. Объекты рассуждения в Прологе называются термами – синтаксическими объектами одной из следующих категорий: • константы, • переменные, • функции (составные термы или структуры), состоящие из имени функции и списка аргументов-термов, имена функций начинаются со строчной буквы. Константа в Прологе служит для обозначения имен собственных и начинается со строчной буквы. Переменная в Прологе служит для обозначения объекта, на который нельзя сослаться по имени. Переменные в Прологе инициализируются при сопоставлении с константами в фактах и правилах. До инициализации переменная свободна, после присвоения ей значения она становится связанной. Переменная остается связанной только то время, которое необходимо для получения решения по запросу, затем Пролог освобождает ее и ищет другое решение. Переменные в Прологе предназначены для установления соответствия между термами предикатов, действующих в пределах одной фразы (предложения), а не местом памяти для хранения данных. Переменная начинается с прописной буквы или знаков подчеркивания. В Прологе программист свободен в выборе имен констант, переменных, функций и предикатов. Исключения составляют резервированные имена и числовые константы. Переменные от констант отличаются первой буквой имени: у констант она строчная, у переменных – заглавная буква или символ подчеркивания. Область действия имени представляет собой часть программы, где это имя имеет один и тот же смысл: • для переменной областью действия является предложение (факт, правило или цель), содержащее данную переменную; • для остальных имен (констант, функций или предикатов) – вся программа. Специальным знаком «_» обозначается анонимная переменная, которая используется тогда, когда конкретное значение переменной не существенно для данного предложения. Анонимные переменные не отличаются от обычных при поиске соответствий, но не принимают значений и не появляются в ответах. Различные вхождения знака подчеркивания означают различные анонимные переменные. Отношения между объектами в Прологе называются фактами. Факт соответствует фразе Хорна, состоящей из одного положительного литерала. Факт – это простейшая разновидность предложения Пролога. Любой факт имеет значение истинности «И» и определяет отношение между термами. Факт является простым предикатом, который записывается в виде функционального терма, состоящего из имени отношения и объектов, заключенных в круглые скобки, например: мать( мария, анна). отец( иван, анна). Точка, стоящая после предиката, указывает на то, что рассматриваемое выражение является фактом. Вторым типом предложений Пролога является вопрос или цель. Цель – это средство формулировки задачи, которую должна решать программа. Простой вопрос (цель) синтаксически является разновидностью факта, например: Цель: мать (мария, юлия). В данном случае программе задан вопрос, является ли мария матерью юлии. Если необходимо задать вопрос, кто является матерью юлии, то цель будет иметь следующий вид: Цель: мать( X, юлия). Сложные цели представляют собой конъюнкцию простых целей и имеют следующий вид: Цель: Q1, Q2,…,Qn, где запятая обозначает операцию конъюнкции, а Q1, Q2,…,Qn – подцели главной цели. Конъюнкция в Прологе истинна только при истинности всех компонент, однако, в отличие от логики, в Прологе учитывается порядок оценки истинности компонент (слева направо). Пример 1. Пусть задана семейная БД при помощи перечисления родительских отношений в виде списка фактов: мать( мария, анна). мать(мария, юлия). мать( анна, петр). отец( иван, анна). отец( иван, юлия). Тогда вопрос, является ли иван дедом петра, можно задать в виде следующей цели: Цель: отец( иван, X), мать(X, петр). На самом деле БД Пролога включает не только факты, но и правила. Для получения ответа БД просматривается по порядку, то есть в порядке следования фактов и правил в тексте программы. Цель достигнута, если в БД удалось найти факт или правило, который (которое) удовлетворяет предикату цели, то есть превращает его в истинное высказывание. В нашем примере первую подцель удовлетворяют факты отец( иван, анна). и отец( иван, юлия). Вторую подцель удовлетворяет факт мать( анна, петр). Следовательно, главная цель удовлетворена, переменная X связывается с константой анна. Третьим типом предложения является правило. Правило позволяет вывести один факт из других фактов. Иными словами, правило – это заключение, для которого известно, что оно истинно, если одно или несколько других найденных заключений или фактов являются истинными. Правила – это предложения вида H: - P1, P2,…, Pn. Символ «: -» читается как «если», предикат H называется заключением, а последовательность предикатов P1, P2,…, Pn называется посылками. Приведенное правило является аналогом хорновского дизъюнкта HÚØP1ÚØP2,…,ÚØPn. Заключение истинно, если истинны все посылки. В посылках переменные связаны квантором существования, а в заключении - квантором всеобщности. Пример 2. Добавим в БД примера 18 правила, задающие отношение «дед»: мать( мария, анна). мать(мария, юлия). мать( анна, петр). отец( иван, анна). отец( иван, юлия). дед (X, Y): - отец(X, Z), мать(Z, Y). дед (X, Y): - отец(X, Z), отец(Z, Y). Тогда вопрос, является ли иван дедом петра, можно задать в виде следующей цели: Цель: дед( иван, петр). Правила - самые общие предложения Пролога, факт является частным случаем правила без правой части, а цель – правило без левой части. Все предложения для одного предиката связаны между собой отношением «или». Очень часто правила в Прологе являются рекурсивными. Например, для нашей семейной БД предикат «предок» определяется рекурсивно: предок(x, y): - мать(x, y). предок(x, y): - отец(x, y). предок(x, y): - мать(x, z), предок(z, y). предок(x, y): - отец (x, z), предок(z, y). Рекурсивное определение предиката обязательно должно содержать не рекурсивную часть, иначе оно будет логически некорректным и программа зациклится. Чтобы избежать зацикливания, следует также позаботиться о порядке выполнения предложений, поэтому практически полезно, а порой и необходимо придерживаться принципа: «сначала не рекурсивные выражения». Программа на Прологе - это конечное множество предложений. 2.3.2 Использование дизъюнкции и отрицания Чистый Пролог разрешает применять в правилах и целях только конъюнкцию, однако, язык, используемый на практике, допускает применение дизъюнкции и отрицания в телах правил и целях. Для достижения цели, содержащей дизъюнкцию, Пролог–система сначала пытается удовлетворить левую часть дизъюнкции, а если это не удается, то переходит к поиску решения для правой части дизъюнкции. Аналогичные действия производятся при выполнении тела правил, содержащих дизъюнкцию. Для обозначения дизъюнкции используется символ « ; ». В Прологе отрицание имеет имя «not» и для представления отрицания какого-либо предиката P используется запись not(P). Цель not(P) достижима тогда и только тогда, когда не выполняется предикат (цель) P. При этом переменным значения не присваиваются. В самом деле, если выполняется P, то не выполняется not(P), значит надо стереть все присваивания, приводящие к данному результату. Наоборот, если P не выполняется, то переменные не принимают никаких значений. 2.3.3 Унификация в Прологе Общий принцип выполнения программ на Прологе прост: производится поиск ответа на вопросы, задаваемые БД, состоящей из фактов и правил, то есть проверяется соответствие предикатов вопроса предложениям из БД. Это частный случай метода резолюций. Отметим, что в Прологе не проводится синтаксического различия между предикатом и функцией (составным термом), а также между нечисловой константой и функцией без аргументов. Следовательно, суть действия состоит в том, что ищется попарное соответствие между термами, один из которых является целью, а другой принадлежит БД. Установление соответствия между термами является основной операцией при вычислении цели. Она осуществляется следующим образом: на каждом шаге выбирается очередной терм и отыскивается соответствующее выражение в БД. При этом переменные получают или теряют значения. Этот процесс можно описать в терминах текстуальных подстановок: «подставить терм t вместо переменной Y». Свободными переменными в Прологе называются переменные, которым не были присвоены значения, а все остальные переменные называются связанными переменными. Переменная становится связанной только во время унификации, переменная вновь становится свободной, когда унификация оказывается неуспешной или цель оказывается успешно вычисленной. В Прологе присваивание значений переменным выполняется внутренними подпрограммами унификации. Переменные становятся свободными, как только для внутренних подпрограмм унификации отпадает необходимость связывать некоторое значение с переменной для выполнения доказательства подцели. 2.3.4 Правила унификации 1. Если x и y-константы, то они унифицируемы, только если они равны. 2. Если x- константа или функция, а Y-переменная, то они унифицируемы, при этом Y принимает значение x . 3. Если x и y -функции, то они унифицируемы тогда и только тогда, когда у них одинаковые имена функций (функторы) и набор аргументов и каждая пара аргументов функций унифицируема. Есть особый предикат «=», который используется в Прологе для отождествления двух термов. Использование предиката «=» поможет лучше понять процесс означивания переменной. В Прологе предикат «=» интерпретируется как оператор присваивания или как оператор проверки на равенство в зависимости от того, являются ли значения термов свободными или связанными. Пример 3: X=Y, если X и Y – связанные переменные, то производится проверка на равенство, например: если X=5 и Y=5, то результат ДА (истина); если X=6 а Y=5, то результат НЕТ(ложь). Если одна из переменных X или Y – свободная, то ей будет присвоено значение другой переменной. Оператор «=» ведет себя точно так, как внутренние подпрограммы унификации при сопоставлении целей или подцелей с фактами и правилами программы. 2.3.5 Вычисление цели. Механизм возврата Каноническая форма цели (вопроса) является конъюнкцией атомарных предикатов, то есть последовательностью подцелей, разделенных запятыми: Q=Q1, Q2,…, Qn. Пролог пытается вычислить цель при помощи унификации термов предикатов подцелей с соответствующими элементами в фактах и заголовках правил. Поиск ответа на вопрос напоминает поиск пути в лабиринте: следует поворачивать налево в каждой развилке лабиринта до тех пор, пока не попадете в тупик. В этом случае следует вернуться к последней развилке и повернуть направо, после чего опять следует повернуть налево и так далее. Вычисление цели выполняется слева направо, как и поиск пути в лабиринте. Некоторые подцели при вычислении цели могут оказаться неуспешными, поэтому Прологу требуется способ запоминания точек отката, в которых он может продолжить альтернативные поиски решения. Прежде чем реализовать один из возможных путей вычисления подцели, Пролог фактически помещает в программу указатель, который определяет точку, в которую может быть выполнен возврат, если текущая попытка поиска цели будет неудачной. Если некоторая подцель оказывается неуспешной, то Пролог возвращается к ближайшей точке возврата. С этой точки Пролог начинает попытку найти другое решение для неуспешной цели. До тех пор, пока следующая цель на данном уровне не будет успешной, Пролог будет повторять возврат к ближайшей точке возврата. Эти попытки выполняются внутренними подпрограммами унификации и механизмом возврата. Замечание: единственным способом освободить переменную, связанную в предложении является откат при поиске с возвратом. Алгоритм вычисления цели – частный случай правила резолюции применительно к дизъюнктам Хорна. Вопрос Q является правилом без заголовка, аналогом выражения ØQ. Пусть D – база данных (множество дизъюнктов). На вопрос Q, следует найти такую подстановку s, для которой множество s[DÈ(ØQ)] невыполнимо. Стратегия выбора очередной пары дизъюнктов для резолюции здесь очень проста: подцели и предложения просматриваются в текстуальном порядке. Пример 4: пусть есть БД семья: 1. мать( мария, анна). 2. мать(мария, юлия). 3. мать( анна, петр). 4. отец( иван, анна). 5. отец( иван, юлия). 6. дед (X, Y): - отец(X, Z), мать(Z, Y). 7. дед (X, Y): - отец(X, Z), отец(Z, Y). 8. бабка (X, Y): - мать(X, Z), мать(Z, Y). 9. бабка (X, Y): - мать(X, Z), отец(Z, Y). Зададим сложную цель: Q1, Q2 = отец(X, Y), мать(мария, Y). Подцель Q1= отец(X,Y) соответствует четвертому предложению БД :отец (иван,анна). Это дает подстановку s1={X=иван,Y=анна}. Затем найденная подстановка применяется к s1[Q2]= мать(мария, анна). Этой подцели соответствует 1 предложение БД, что дает пустую подцель по правилу резолюции, следовательно ответ найден: X= иван, Y= анна. Для получения нового ответа в БД ищется новая унификация для s1[Q2]. Так как в БД нет соответствующего предложения, то вычисления прекращаются, система вновь рассматривает последовательность Q1, Q2 и для Q1 ищется новая унификация в БД, начиная с пятого предложения. Это и есть возврат. Пятое предложение сразу же дает желаемую унификацию с подстановкой s2={X=иван,Y=юлия}. Вновь найденная подстановка применяется к s1[Q2]= мать(мария, юлия). Этой подцели соответствует второе предложение БД. Далее указанная процедура повторяется и в итоге имеем: Цель: отец(X, Y), мать(мария, Y). 2 решения: X=иван, Y=анна X=иван, Y=юлия. Это описание объясняет, как работает утилита TestGoal в Visual Prolog. При реализации механизма возврата выполняются следующие правила: 1. Подцели вычисляются слева-направо. 2. Предложения при вычислении подцели проверяются в текстуальном порядке, то есть сверху-вниз. 3. Если подцель сопоставима с заголовком правила, то должно быть вычислено тело этого правила, при этом тело правила образует новое подмножество подцелей для вычисления. 4. Цель считается успешно вычисленной, когда найден соответсвующий факт для каждой подцели. 2.3.6 Управление поиском решения Встроенный в Пролог механизм поиска с возвратом может привести к поиску ненужных решений, в результате чего снижается эффективность программы в случае, если надо найти только одно решение. В других случаях бывает необходимо продолжить поиск, даже если решение найдено. Пролог обеспечивает два встроенных предиката, которые дают возможность управлять механизмом поиска с возвратом: предикат fail – используется для инициализации поиска с возвратом и предикат отсечения ! – используется для запрета возврата. Предикат fail всегда имеет ложное значение! Пример 5: Использование предиката fail. Для примера 21 можно добавить правило для печати всех матерей, которые есть в БД: печать_матерей:-мать(X,Y), write(X,” есть мать”,Y),nl,fail. goal печать_матерей. В результате будет выдано 3 решения: X=мария, Y= анна. X=мария, Y= юлия. X=анна, Y= петр. Отсечение так же, как и fail помещается в тело правила. Однако, в отличие от fail предикат отсечения имеет всегда истинное значение. При этом выполняется обращение к другим предикатам в теле правила, следующим за отсечением. Следует иметь в виду, что невозможно произвести возврат к предикатам, расположенным в теле правила перед отсечением, а также невозможен возврат к другим правилам данного предиката. Существует только два случая применения предиката отсечения: 1. Если заранее известно, что определенные посылки никогда не приведут к осмысленным решениям – это так называемое «зеленое отсечение». 2. Если отсечения требует сама логика программы для исключения альтернативных подцелей – это так называемое «красное отсечение». 2.3.7 Процедурность Пролога Пролог – декларативный язык. Описывая задачу в терминах фактов и правил, программист предоставляет Прологу самому искать способ решения. В процедурных языках программист должен сам писать процедуры и функции, которые подробно «объясняют» компьютеру, какие шаги надо сделать для решения задачи. Тем не менее, рассмотрим Пролог с точки зрения процедурного программирования: 1. Факты и правила можно рассматривать как определения процедур. 2. Использование правил для условного ветвления программы. Правило, в отличие от процедуры, позволяет задавать множество альтернативных определений одной и той же процедуры. Поэтому, правило можно считать аналогом оператора case в Паскале. 3. В правиле может быть выполнено сравнение, как в условных операторах. 4. Отсечение можно считать аналогом go to. 5. Возврат вычисленного значения производится аналогично процедурам. В Прологе это делается путем связывания свободных переменных при сопоставлении цели с фактами и правилами. 2.3.8 Структура программ Пролога Программа, написанная на Прологе, состоит из шести основных разделов: раздел объявления доменов, раздел объявления констант, раздел объявления предикатов внутренней базы данных, раздел объявления предикатов, раздел описания предложений и раздел описания цели. Все разделы являются необязательными, кроме раздела цели, который может быть только в единственном числе. Остальные разделы могут повторяться. Ключевые слова domains, constants, facts (старое название database), predicates, clauses и goal отмечают начала соответствующих разделов. Назначение этих разделов таково: • раздел domains содержит определения доменов, которые описывают различные типы данных, используемых в программе; • раздел constants используется для объявления символических констант, используемых в программе; • раздел facts (database) содержит объявления предикатов внутренней базы данных Пролога, если программа такой базы данных не требует, то этот раздел может быть опущен; • раздел predicates служит для объявления предикатов, не принадлежащих внутренней базе данных; • в раздел clauses заносятся факты и правила самой программы; • в разделе goal на языке Пролог формулируется назначение создаваемой программы. Составными частями при этом могут являться некие подцели, из которых формируется единая цель программы. В Visual Prolog разрешает объявление разделов domains, facts, predicates, clauses как глобальных разделов, то есть с ключевым словом global. Пролог имеет следующие встроенные типы доменов: Тип данных Ключевое слово Диапазон значений Примеры использования Символы char Все возможные символы ‘a’, ’b’, ‘#’, ‘B’, ‘%’ Целые числа integer byte word dword От –32768 до 32767 От 0 до 255 От 0 до 65535 От 0 до -63, 84, 2349 Действительные числа real short ushort long ulong unsigned От +1E-307 до +1E308 16 битов со знаком 16 битов без знака 32 бита со знаком 32 бита без знака 16 или 32 бита без знака 360, - 8324, 1.25E23, 5.15E-9 Строки string Последовательность символов (не более 250) «today», «123», «school_day» Символические имена symbol 1.Последовательность букв, цифр, символов подчеркивания; первый символ – строчная буква. 2. Последовательность любых символов, заключенная в кавычки. flower, school_day «string and symbol» Ссылочный тип ref Файлы file Допустимое в DOS имя файла mail.txt, LAB.PRO Если в программе необходимо использовать новые домены данных, то они должны быть объявлены в разделе domains. Пример 6: domains number=integer name, person=symbol. Различие между symbol и string - в машинном представлении и выполнении, синтаксически они не различимы. Visual Prolog выполняет автоматическое преобразование типов между доменами string и symbol. Однако, по принятому соглашению, символическую строку в двойных кавычках нужно рассматривать как string, а без кавычек – как symbol: Visual Prolog поддерживает и другие типы стандартных доменов данных, например, для работы с внешними БД или объектами. Предикаты описываются в разделе predicates. Предикат представляет собой строку символов, первым из которых является строчная буква. Предикаты могут не иметь аргументов, например «go» или «repeat». Если предикаты имеют аргументы, то они определяются при описании предикатов в разделе predicates: Пример 7: predicates mother (symbol, symbol) father (symbol, symbol). Предикаты внутренней (динамической) базы данных пролога объявляются в разделе facts. Предикаты, объявленные в данном разделе, могут присутствовать в программе только в виде фактов. Синтаксически предикаты раздела facts не отличаются от предикатов раздела predicates. Предикаты раздела facts могут удаляться, добавляться или модифицироваться во время исполнения программы. Если есть необходимость в наличии нескольких разделов facts, то каждый раздел должен объявляться с собственным именем, например: facts – my_data. Факты и правила определяются в разделе clauses, а вопрос к программе задается в разделе goal. В Visual Prolog раздел goal в тексте программы является обязательным. Разница в режимах исполнения программы состоит в разном использовании утилиты Test Goal. Если утилита создается для запуска любой программы, то при этом ищутся все решения, если утилита создается для автономного запуска программы – то ищется одно решение. 2.3.9 Использование списков Список является составной рекурсивной структурой данных, хотя явно и не объявляется как рекурсивная структура. Список – это упорядоченный набор объектов одного и того же типа. Элементами списка могут быть целые числа, действительные числа, символы, строки, символические имена и структуры. Порядок расположения элементов в списке играет важную роль: те же самые элементы списка, упорядоченные иным способом, представляют уже совсем другой список. Совокупность элементов списка заключается в квадратные скобки ([]), элементы друг от друга отделяются запятыми. Список может содержать произвольное число элементов, единственным ограничением является объем оперативной памяти. Количество элементов в списке называется его длиной. Список может содержать один элемент и даже не содержать ни одного элемента. Список, не содержащий элементов, называется пустым или нулевым списком. Непустой список можно рассматривать как список, состоящий из двух частей: головы – первого элемента списка; и хвоста – остальной части списка. Голова является элементом списка, хвост является списком. Голова списка – это неделимое значение, хвост представляет собой список, составленный из того, что осталось от исходного списка в результате «отделения головы». Этот новый список обычно можно делить и дальше. Если список состоит из одного элемента, то его можно разделить на голову, которой будет этот самый элемент, и хвост, являющийся пустым списком. Пустой список нельзя разделить на голову и хвост! Операция деления списка на голову и хвост обозначается при помощи вертикальной черты (|): [Head | Tail]. Голова списка всегда имеет тип элемента списка, хвост списка – тип списка! Head здесь является переменной для обозначения головы списка, переменная Tail обозначает хвост списка (для имен головы и хвоста списка пригодны любые допустимые Прологом имена). Данная операция также присоединяет элемент в начало списка, например, для того, чтобы присоединить X к списку S следует написать [X|S]. В концептуальном плане, список имеет структуру дерева, как и другие составные термы. Так, например, список [a,b,c] можно представить в виде структуры: Отличительной особенностью описания списков является наличие звездочки (*) после имени домена элементов. Пример 8: объявление списков, состоящих из элементов стандартных типов доменов или типа структуры. domains list1=integer* list2=char* list3=string* list4=real* list5=symbol* personal_library = book (title, author, publisher, year) list6= personal_library* list7=list1* list8=list5* В первых пяти объявлениях списков в качестве элементов используются стандартные домены данных, в шестом типе списка в качестве элемента используется домен структуры personal_library, в седьмом и восьмом типе списка в качестве элемента используется ранее объявленный список. Пример 9: демонстрация разделения списков на голову и хвост. Список Голова Хвост [1, 2, 3, 4, 5] 1 [2, 3, 4, 5] [6.9, 4.3] 6.9 [4.3] [cat, dog, horse] Cat [dog, horse] [‘S’, ‘K’, ‘Y’] ‘S’ [‘K’, ‘Y’] [«PIG»] «PIG» [] [] Не определена Не определен Visual Prolog допускает объявление и использвание составных списков. Составной список – это список, в котром используется более чем один тип элемента. Для создания такого списка, необходимо использовать структуры, так как домен может содержать более одного типа данных только для структуры. Пример 10: объявление списка, который может содержать символы, целые числа или строки: domains llist=i(integer);c(char);s(string) list=llistl* Подобный список выглядит следующим образом: L=[i(1),i(-2),c(‘a’),string(“hello”),c(‘b’)]. Для применения списков в программах на Прологе необходимо описать домен списка в разделе domains, предикаты, работающие со списками необходимо описать в разделе predicates, задать сам список можно либо в разделе clauses либо в разделе goal. Над списками можно реализовать различные операции: поиск элемента в списке, разделение списка на два списка, присоединение одного списка к другому, удаление элементов из списка, сортировку списка, создание списка из содержимого БД и так далее. 2.3.10 Поиск элемента в списке Поиск элемента в списке является очень распространенной операцией. Поиск представляет собой просмотр списка на предмет выявления соответствия между объектом поиска и элементом списка. Если такое соответствие найдено, то поиск заканчивается успехом, в противном случае поиск заканчивается неуспехом. Стратегия поиска при этом будет состоять в рекурсивном выделении головы списка и сравнении ее с объектом поиска. Пример 11: поиск элемента в списке. domains list=integer* predicates member (integer, list) clauses member (Head, [Head |_ ]). member (Head, [_ | Tail ]):- member (Head, Tail). goal member (3, [1, 4, 3, 2]). %member (X, [1, 4, 3, 2]). Второй вариант запроса порождает перебор всех элементов списка. Правило поиска может сравнить объект поиска и голову текущего списка, эта операция записана в виде факта предиката member. Этот вариант предполагает наличие соответствия между объектом поиска и головой списка. Отметим, что хвост списка в данном случае не важен, поэтому хвост списка присваивается анонимной переменной. Если объект поиска и голова списка различны, то в результате исполнения первого предложения будет неуспех, происходит возврат и поиск другого правила или факта, с которыми можно попытаться найти соответствие. Для этой цели служит второе предложение, которое выделяет из списка следующий по порядку элемент, то есть выделяет голову текущего хвоста, поэтому текущий хвост представляется как новый список, голову которого можно сравнить с объектом поиска. В случае исполнения второго предложения, голова текущего списка ставится в соответствие анонимной переменной, так как значение головы с писка в данном случае не играет никакой роли. Процесс повторяется до тех пор, пока первое предложение даст успех, в случае установления соответствия, либо неуспех, в случае исчерпания списка. В представленном примере предикат member находит все совпадения объекта поиска с элементами списка. Для того, чтобы найти только первое совпадение следует модифицировать первое предложение следующим образом: member (Head, [Head |_ ]):- !. Отсечение отменяет действие механизма возврата, поэтому поиск альтернативных успешных решений реализован не будет. 2.3.11 Объединение двух списков Слияние двух списков и получение, таким образом, третьего списка принадлежит к числу наиболее полезных при работе со списками операций. Обозначим первый список L1, а второй список - L2. Пусть L1 = [1, 2, 3], а L2 = [4, 5]. Предикат append присоединяет L2 к L1 и создает выходной список L3, в который он должен переслать все элементы L1 и L2. Весь процесс можно представить следующим образом: 1. Список L3 вначале пуст. 2. Элементы списка L1 пересылаются в L3, теперь значением L3 будет [1, 2, 3]. 3. Элементы списка L2 пересылаются в L3, в результате чего тот принимает значение [1, 2, 3, 4, 5]. Тогда программа на языке Visual Prolog имеет следующий вид: Пример 12: объединение двух списков. domains list=integer* predicates аppend (list, list, list) clauses append ( [], L2, L2). append ([H|T1], L2, [H|T3 ]):- append (T1, L2, T3). goal append ( [1, 2, 3], [4, 5], L3). Основное использование предиката append состоит в объединении двух списков, что делается при помощи задания цели вида append ([1, 2, 3], [4, 5], L3). Поиск ответа на вопрос типа: append (L1, [3, 4, 5], [1, 2, 3, 4, 5]) – сводится к поиску такого списка L1=[1, 2], который при слиянии со списком L2 = [3, 4, 5] даст список L3 = [1, 2, 3, 4, 5]. При обработки цели append (L1, L2, [1, 2, 3, 4, 5]) ищутся такие списки L1 и L2, что их объединение даст список L3 = [1, 2, 3, 4, 5]. При обработке цели append ([1, 2], [3, 4, 5], [1, 2, 3, 4, 5]) списки [1, 2] и [3, 4, 5] объединяются и сравниваются поэлементно со списком [1, 2, 3, 4, 5]. Если равенство выполняется, то возвращается значение yes, если нет – то значение no. 2.3.12 Определение длины списка Число элементов в списке можно подсчитать при помощи рекурсивных предикатов count_list1 и count_list2. Предикат count_list1 ведёт подсчёт числа элементов в списке на прямом ходе рекурсии, начиная от головы списка, при этом первый параметр типа byte является текущим счётчиком, а второй - необходим для возвращения результата при выходе из рекурсии. Предикат count_list2 ведёт подсчёт числа элементов в списке на обратном ходе рекурсии, начиная с последнего элемента, при этом параметр типа byte является текущим счётчиком и результатом одновременно. Два варианта решения задачи приводятся в примере 39. Пример 13: определение длины списка. domains list=integer* predicates count_list1(list,byte,byte) count_list2(list,byte) clauses count_list1([],N,N). count_list1([_|T],N,M):- N1=N+1, count_list1(T,N1,M). count_list2([],0). count_list2([_|T],N):- count_list1(T,N1), N=N1+1. goal count_list1([0,-1,2,6,-9],0,N), count_list2([4,3,-8],K). 2.3.13 Поиск максимального и минимального элемента в списке Найти максимальный или минимальный элемент в списке можно при помощи рекурсивных предикатов max_list и min_list. Предикат max_list ищет максимальный элемент в списке на прямом ходе рекурсии, начиная от головы списка, при этом первый параметр типа integer является текущим максимумом, а второй - необходим для возвращения результата при выходе из рекурсии. Предикат min_list ищет минимальный элемент в списке на обратном ходе рекурсии, начиная с последнего элемента, при этом параметр типа integer является текущим минимумом и результатом одновременно. Два варианта решения задачи приводятся в примере 40. Пример 14: поиск максимального т минимального элемента в списке. domains list=integer* predicates max_list(list, integer, integer) min_list(list, integer) clauses max_list ([],M,M). max_list ([H|T],N,M):- H>N, max_list(T,H,M). max_list ([H|T],N,M):- H<=N, max_list(T,N,M). min_list ([H|[]],H). min_list ([H|T],M):- min_list(T,M1), H>=M1, M=M1. min_list ([H|T],M):- min_list(T,M1), HY. perest([Z|T],[Z|T1]):-perest(T,T1). goal puz([1,3,4,5,2],L).] Пример 16: сортировка списков методом вставки по возрастанию элементов. domains list=integer* predicates insert_sort (list, list) insert (integer, list, list) asc_order (integer, integer) clauses insert_sort ( [], []). insert_sort ([H1|T1], L2):- insert_sort (T1, T2), insert(H1, T2, L2). insert (X, [H1| T1], [H1| T2]) :- asc_order (X, H1), !, insert (X, T1, T2). insert (X, L1, [X| L1]). asc_order (X, Y):- X>Y. goal insert_sort ([4, 7, 3, 9], L). Для удовлетворения первого правила оба списка должны быть пустыми. Для того, чтобы достичь этого состояния, по второму правилу происходит рекурсивный вызов предиката insert_sort, при этом значениями H1 последовательно становятся все элементы исходного списка, которые затем помещаются в стек. В результате исходный список становится пустым и по первому правилу выходной список также становится пустым. После того, как произошло успешное завершение первого правила, Пролог пытается выполнить второй предикат insert, вызов которого содержится в теле второго правила. Переменной H1 сначала присваивается первое взятое из стека значение 9, а предикат принимает вид insert (9, [], [9]). Так как теперь удовлетворено все второе правило, то происходит возврат на один шаг рекурсии в предикате insert_sort. Из стека извлекается 3 и снова вызывается insert, а затем по третьему правилу вызывается предикат asc_order, то есть происходит попытка удовлетворения пятого правила asc_order (3, 9):- 3>9. Так как данное правило заканчивается неуспешно, то неуспешно заканчивается и третье правило, следовательно, удовлетворяется четвертое правило и 3 вставляется в выходной список слева от 9: insert (3, [9], [3, 9]). Далее происходит возврат к предикату insert_sort, который принимает следующий вид: insert_sort ([3, 9], [3, 9]). На следующем шаге рекурсии из стека извлекается 7 и по третьему правилу вызывается предикат asc_order в виде asc_order (7, 3):- 7>3. Так как данное правило заканчивается успешно, то элемент 3 убирается в стек и insert вызвается рекурсивно еще раз, но уже с хвостом списка – [9]: insert (7, [9], _). Так как правило asc_order (7, 9):- 7>9 заканчивается неуспешно, то выполняется четвертое правило, происходит возврат на предыдущие шаги рекурсии сначала insert, затем insert_sort. В результате 7 помещается в выходной список между элементами 3 и 9: insert (7, [3, 9], [3, 7, 9]). При возврате еще на один шаг рекурсии из стека извлекается 4 и по третьему правилу вызывается предикат asc_order в виде asc_order (4, 3):- 4>3. Так как данное правило заканчивается успешно, то элемент 3 убирается в стек и insert вызвается рекурсивно еще раз, но уже с хвостом списка – [7, 9]: insert (4, [7, 9], _). Так как правило asc_order (4, 7):- 4>7 заканчивается неуспешно, то выполняется четвертое правило, происходит возврат на предыдущие шаги рекурсии сначала insert, затем insert_sort. В результате 4 помещается в выходной список между элементами 3 и 7: insert (4, [3, 7, 9], [3, 4, 7, 9]). insert_sort [4, 7, 3, 9], [3, 4, 7, 9]). 2.3.15 Компоновка данных в список Иногда при программировании определенных задач возникает необходимость собрать данные из фактов БД в список для последующей их обработки. Пролог содержит встроенный предикат findall, который позволяет выполнить данную операцию. Описание предиката findall выглядит следующим образом: Findall (Var_, Predicate_, List_), где Var_ обозначает имя для терма предиката Predicate_, в соответствии с типом которого формируются элементы списка List_. Пример 17: использование предиката findall. domains d=integer predicates decimal (d) write_decimal clauses decimal (0) decimal (1) decimal (2) decimal (3) decimal (4) decimal (5) decimal (6) decimal (7) decimal (8) decimal (9) write_decimal:- findall(C, decimal (C), L), write (L). goal write_decimal. 2.3.16 Использование строк в Прологе. Строка – это набор символов. При программировании на Прологе символы могут быть «записаны» при помощи алфавитно-цифрового представления или при помощи их ASCII-кодов. Обратный слэш (\), за которым непосредственно следует ASCII-код (N) символа, интерпретируется как символ. Для представления одиночного символа выражение \N должно быть заключено в апострофы (‘\N’). Для представления строки символов ASCII-коды помещаются друг за другом и вся строка заключается в кавычки («\N\N\N»). Операции, обычно выполняемые над строками, включают: • объединение строк для образования новой строки; • разделение строки для создания двух новых строк, каждая из которых содержит некоторые из исходных символов; • поиск символа или подстроки внутри данной строки. Для удобства работы со строками Пролог имеет несколько встроенных предикатов, манипулирующих со строками: • str_len – предикат для нахождения длины строки; • concat – предикат для объединения двух строк; • frontstr – предикат для разделения строки на две подстроки; • frontchar – предикат для разделения строки на первый символ и остаток; • fronttoken – предикат для разделения строки на лексему и остаток. Синтаксис предиката str_len: str_len (Str_value, Srt_length), где первый терм имеет тип string, а второй терм имеет тип integer. Пример 18: str_len («Today», L)- в данном случае переменная L получит значение 5; str_len («Today», 5) – в данном случае будет выполнено сравнение длины строки «Today» и 5. Так как они совпали, то предикат выполнится успешно, если бы длина строки не была равна 5, то предикат вылонился бы неуспешно. Синтаксис предиката concat: concat (Str1, Str2, Str3), где все термы имеют тип string. Пример 19: concat («Today», «Tomorrow», S3)- в данном случае перменная S3 получит значение «TodayTomorrow»; concat (S1, «Tomorrow», «TodayTomorrow») – в данном случае S1 будет присвоено значение «Today»; concat («Today», S2, «TodayTomorrow») – в данном случае S2 будет присвоено значение «Tomorrow»; concat («Today», «Tomorrow», «TodayTomorrow»)- будет проверена возможность склейки строк «Today» и «Tomorrow» в строку «TodayTomorrow». Синтаксис предиката frontstr: frontstr (Number, Str1, Str2, Str3), где терм Number имеет тип integer, а остальные термы имеют тип string. Терм Number задает число символов, которые должны быть скопированы из строки Str1 в строку Str2, остальные символы будут скопированы в строку Str3. Пример 20: frontstr (6,«Expert systems», S2, S3)- в данном случае перменная S2 получит значение «Expert», а S3 получит значение ,« systems». Синтаксис предиката frontchar: frontchar (Str1, Char_, Str2), где терм Char_ имеет тип char, а остальные термы имеют тип string. Пример 21: frontchar («Today », C, S2)- в данном случае перменная C получит значение «T», а S2 получит значение ,«oday»; frontchar («Today », ‘T’, S2) – в данном случае S2 будет присвоено значение «oday»; frontchar («Today», C, «oday») – в данном случае C будет присвоено значение «T»; frontchar (S1, «T», «oday») – в данном случае S1 будет присвоено значение «Today»; frontchar («Today», «T», «oday»)- будет проверена возможность склейки строк «T» и «oday» в строку «Today». Синтаксис предиката fronttoken: fronttoken (Str1, Lex, Str2), где все термы имеют тип string. В терм Lex копируется первая лексема строки Str1, остальные символы будут скопированы в строку Str2. Лексема – это имя в соответствии с синтаксисом языка Visual Пролог или строчное представление числа или отдельный символ (кроме пробела). Пример 22: fronttoken («Expert systems», Lex, S2)- в данном случае перменная Lex получит значение «Expert», а S2 получит значение ,« systems». fronttoken («$Expert», Lex, S2)- в данном случае перменная Lex получит значение «$», а S2 получит значение ,«Expert». fronttoken («Expert systems», Lex, « systems»)- в данном случае перменная Lex получит значение «Expert»; fronttoken («Expert systems», «Expert», S2)- в данном случае перменная S2 получит значение « systems»; fronttoken (S1, «Expert», « systems»)- в данном случае перменная S1 получит значение «Expert systems»; fronttoken («Expert systems», «Expert», « systems»)- в данном случае будет проверена возможность склейки лексемы и остатка в строку «Expert systems». 2.3.17 Преобразование данных в Прологе Для преобразования данных из одного типа в другой Пролог имеет следующие встроенные предикаты: upper_lower; str_char; str_int; str_real; char_int. Все предикаты преобразования данных имеют два терма. Все предикаты имеют два направления преобразования данных в зависимости от того, какой терм является свободной или связанной переменной. Пример 23: upper_lower («STARS», S2). upper_lower (S1,«stars»). str_char («T», C). str_char (S, ’T’). str_int («123», N). str_int (S, 123). str_real («12.3», R). str_real (S, 12.3). char_int (‘A’, N). char_int (C, 61). В Прологе нет встроенных предикатов для преобразования действительных чисел в целые и наоборот, или строк в символы. На самом деле, правила преобразования данных типов очень просты и могут быть заданы в программе самими программистом. Пример 24: predicates conv_real_int (real, integer) conv_int_real (integer, real) conv_str_symb (string, symbol) clauses conv_real_int (R, N):- R=N. conv_int_real (N, R):- N=R. conv_str_symb (S, Sb):- S=Sb. goal conv_real_int (5432.765, N). (N= 5432). conv_int_real (1234, R). (R=1234). conv_str_symb («Visual Prolog», Sb). (Sb=Visual Prolog). Пример 25: преобразование строки в список символов с использованием предиката frontchar. domains list=char* predicates convert (string, list) clauses convert («», []). convert (Str, [H\T]):- frontchar(Str, H, Str1), convert(Str1, T). 2.3.18 Создание динамических баз данных В Прологе существуют специальные средства для организации внутренних и внешних баз данных. Эти средства рассчитаны на работу с реляционными базами данных. Внутренние подпрограммы унификации осуществляют автоматическую выборку фактов из внутренней (динамической) базы данных с нужными значениями известных параметров и присваивают значения неопределенным параметрам. Раздел программы facts в Visual Prolog предназначен для описания предикатов динамической (внутренней) базы данных. База данных называется динамической, так как во время работы программы из нее можно удалять любые факты, а также добавлять новые факты. В этом состоит ее отличие от статических баз данных, где факты являются частью кода программы и не могут быть изменены во время исполнения. Иногда бывает полезно иметь часть информации базы данных в виде фактов статической БД - эти данные заносятся в динамическую БД сразу после активизации программы. В общем случае, предикаты статической БД имеют другое имя, но ту же самую форму представления данных, что и предикаты динамической БД. Добавление латинской буквы d к имени предиката статической БД - обычный способ различать предикаты динамической и статической БД. Следует отметить два ограничения для предикатов, объявленных в разделе facts : • в динамической базе данных Пролога могут содержаться только факты; • факты базы данных не могут содержать свободные переменные. Допускается наличие нескольких разделов facts , тогда в описании каждого раздела facts нужно явно указать его имя, например facts – mydatabase. В двух различных разделах facts нельзя использовать одинаковые имена предикатов. Также нельзя использовать одинаковые имена предикатов в разделах facts и predicates. Если имя базы данных не указывается, то ей присваивается стандартное имя dbasedom. Программа может содержать локальные безымянные разделы фактов, если она состоит из единственного модуля, который не объявлен как часть проекта. Среда разработки компилирует программный файл как единственный модуль только при использовании утилиты TestGoal. Иначе безымянный раздел фактов должен быть объявлен глобальным, то есть как global facts. В Прологе есть специальные встроенные предикаты для работы с динамической базой данных: *0 assert; *1 asserta; *2 assertz; *3 retract; *4 retractall; *5 save; *6 consult. *7 Предикаты assert, asserta, assertz, - позволяют занести факт в БД, а предикаты retract, retractall - удалить из нее уже имеющийся факт. Предикат assert заносит новый факт в БД в произвольное место, предикат asserta добавляет новый факт перед всеми уже внесенными фактами данного предиката, assertz добавляет новый факт после всех фактов данного предиката. Предикат retract удаляет из БД первый факт, который сопоставляется с заданным фактом, предикат retractall удаляет из БД все факты, которые сопоставляются с заданным фактом. Предикат save записывает все факты динамической БД в текстовый файл на диск, причем в каждую строку файла заносится один факт. Если файл с заданным именем уже существует, то старый файл будет затерт. Предикат consult записывает в динамическую БД факты, считанные из текстового файла, при этом факты из файла дописываются в имеющуюся БД. Факты, содержащиеся в текстовом файле должны быть описаны в разделе domains. Пример 26:Написать программу, генерирующую множество 4-разрядных двоичных чисел и записывающих их в динамическую БД. facts dbin (byte, byte, byte, byte) predicates cifra (byte) bin (byte, byte, byte, byte) clauses cifra (0). cifra (1). bin (A, B, C, D):- cifra (A), cifra (B), cifra (C), cifra (D), assert (bin (A, B, C, D)). goal bin (A, B, C, D). Пример 27:Написать программу, подсчитывающую число обращений к программе. facts dcount (word) predicates modcount clauses dcount (0). modcount:- dcount (N), M=N+1, retract (dcount (N)),asserta (dcount (M)). goal modcount. 2.3.19 Использование составных термов В Прологе функциональный терм или предикат можно рассматривать как структуру данных, подобную записи в языке Паскаль. Терм, представляющий совокупность термов, называется составным термом или структурой. Составные структуры данных в Прологе объявляются в разделе domains. Использование доменной структуры упрощает структуру предиката. Аргументами составного терма данных могут быть простые типы данных, составные термы или списки. Синтаксически составной терм выглядит так же, как и предикат: у терма есть функтор и список аргументов, заключенных в круглые скобки. Составной терм может быть унифицирован с простой переменной или составным объектом (при этом переменные могут быть использованы как часть внутренней структуры терма). Это означает, что составной объект можно использовать для того, чтобы передавать целый набор значений, как единый объект, а затем применять унификацию для их разделения. Пример 29: Необходимо создать БД, содержащую сведения о книгах из личной библиотеки. Зададим составной терм с именем personal_library, имеющим следующую структуру: personal_library= book (title, author, publisher, year), и предикат collection (collector, personal_library). Терм book называется функтором структуры данных. Пример программы, использующей составные термы для описания личной библиотеки, и поиска информации о владельцах книг и книгах, напечатанных в 1990 году, а также книги, изданной позже всех остальных, выглядит следующим образом: domains collector, title, author, publisher = symbol year = integer personal_library = book (title, author, publisher, year) predicates collection (collector, personal_library) q1(year) q2 facts dq1(collector, title, year) max_year(title, author, year) clauses collection (irina, book («Using Turbo Prolog», «Yin with Solomon», «Moscow, World», 1993)). collection (irina, book («Логическое программирование и Visual Prolog», «А.Адаменко, А.Кучуков», «Санкт-Петрбург, БХВ- Петрбург», 2003)). collection (petr, book («The art of Prolog», «Sterling with Shapiro», »Moscow, World», 1990)). collection (anna, book («Prolog: a relation language and its applications», «John Malpas», »Moscow, Science», 1990)). %q1(Y):- collection (C, book( T,_, _, Y), write(C,’ ‘,T,’ ‘, Y), nl, fail. q1(Y):- dq1(C, T, Y), write(‘*’,C,’ ‘,T,’ ‘, Y), nl, fail. q1(Y):- not(dq1(_,_,Y)), collection (C, book( T,_, _, Y), assert(dq1(C,T.Y)), write(X,’ ‘,T,’ ‘, Y), nl, fail. max_year(a, b, 0). q2:- collection (_, book(T,A, _, Y), max_year(T1,A1,Y1),Y>Y1, retract(max_year(T1,A1,Y1)), assert(max_year(T,A,Y)), fail. goal %q1(1990). %q1(1990);q1(1990). q2;(max_year(T,A,Y). В данном случае переменная Y используется для унификации части составного терма. Если цель задать в виде: collection (X, Z),Z=book( Y,_, _, 1990), то простая переменная Z унифицируется с составным термом book. 2.3.20 Повторение и рекурсия в Прологе Очень часто в программах необходимо выполнить одну и ту же операцию несколько раз. В программах на Прологе повторяющиеся операции обычно выполняются при помощи правил, которые используют возврат и рекурсию. Существует четыре способа построения итеративных и рекурсивных правил: • механизм возврата; • метод возврата после неудачи; • правило повтора, использующее бесконечный цикл; • обобщенное рекурсивное правило. Правила повторений и рекурсии должны содержать средства управления их выполнением. Встроенные предикаты Пролога fail и cut (!) используются для управления возвратами, а условия завершения используются для управления рекурсией. Правила выполняющие повторения, используют возврат, а правила, выполняющие рекурсию, используют самовызов. 2.3.21 Механизм возврата Возврат является автоматически инициируемым системой процессом, если не используются специальные средства управления им. Если в предикате цели есть хотя бы одна свободная переменная, то механизм возврата переберет все возможные способы связывания этой переменной, то есть реализует итеративный цикл. Пример 31: распечатать все десятичные цифры. domains d=integer predicates decimal (d) write_decimal (d) clauses decimal (0). decimal (1). decimal (2). decimal (3). decimal (4). decimal (5). decimal (6). decimal (7). decimal (8). decimal (9). write_decimal (C):- decimal (C), write (C), nll. goal write_decimal (C). 2.3.22 Метод возврата после неудачи Метод возврата после неудачи может быть использован для управления вычислением внутренней цели при поиске всех возможных решений. Данный метод либо использует внутренний предикат Пролога fail, либо условие, которое порождает ложное значение. Пример 32: распечатать все десятичные цифры. domains d=integer predicates decimal (d) write_decimal clauses decimal (0) decimal (1). decimal (2). decimal (3). decimal (4). decimal (5). decimal (6). decimal (7). decimal (8). decimal (9). write_decimal:- decimal (C), write (C), nl, fail. goal write_decimal В программе есть 10 предикатов, каждый из которых является альтернативным предложением для предиката decimal (d). Во время попытки вычислить цель внутренние подпрогрммы унификации связывают переменную C с термом первого предложения, то есть с цифрой 0. Так как существует следующее предложение, которое может обеспечить вычисление подцели decimal (C), то помещается указатель возврата, значение 0 выводится на экран. Предикат fail вызывает неуспешное завершение правила, внутренние подпрограммы унификации выполняют возврат и процесс повторяется до тех пор, пока не будет обработано последнее предложение. Пример 34: необходимо выдать десятичные цифры до 5 включительно. domains d=integer predicates decimal (d) write_decimal make_cut (d) clauses decimal (0). decimal (1). decimal (2). decimal (3). decimal (4). decimal (5). decimal (6). decimal (7). decimal (8). decimal (9). write_decimal:- decimal (C), write (C), nl, make_cut (C),!. make_cut (C):-C=5. goal write_decimal Предикат ! используется для того, чтобы выполнить отсечение в указанном месте. Неуспешное выполнение предиката make_cut порождает предикат fail, который используется для возврата и доступа к цифрам до тех пор, пока цифра не будет равна 5. Пример 35: необходимо выдать из БД первую цифру , равную 5. domains d=integer predicates decimal (d) write_decimal clauses decimal (0). decimal (5). decimal (2). decimal (3). decimal (4). decimal (5). decimal (6). decimal (5). decimal (8). decimal (9). write_decimal:- decimal (C), С=5, write (C), nl, !. goal write_decimal Если из тела правила убрать предикат !, то будут найдены все три цифры 5, что является результатом применения метода возврата после неудачи. При внесении отсечения будет выдана единственная цифра 5. 2.3.23 Метод повтора, использующий бесконечный цикл Вид правила повторения, порождающего бесконечный цикл: repeat. repeat:- repeat. Первый repeat является предложением, объявляющим предикат repeat истинным. Однако, поскольку имеется еще один вариант для данного предложения, то указатель возврата устанавливается на первый repeat. Второй repeat – это правило, которое использует само себя как компоненту (третий repeat). Второй repeat вызывает третий repeat, и этот вызов вычисляется успешно, так как первый repeat удовлетворяет подцели repeat. Предикат repeat будет вычисляться успешно при каждой новой попытке его вызвать после возврата. Факт будет использоваться для выполнения всех подцелей. Таким образом, repeat это рекурсивное правило, которое никогда не бывает неуспешным. Предикат repeat широко используется в качестве компонента других правил, который вызывает повторное выполнение всех следующих за ним компонентов. Пример 36: ввести с клавиатуры целые числа и вывести их на экран. Программа завершается при вводе числа 0. domains d=integer predicates repeat write_decimal do_echo check (d) clauses repeat. repeat:- repeat. write_decimal:-nl, write( «Введите, пожалуйста, цифры»), nl, write(«Я повторю их»), nl, write(«Чтобы завершить ввод, введите 0»), nl, nl. do_echo:- repeat, readln (D), write(D), nl, check (D), !. check (0):- nl, write («-OK!»). check(_):- fail. goal write_decimal, do_echo. Правило do_echo – это конечное правило повтора, благодаря тому, что предикат repeat является его компонентом и вызывает повторение предикатов readln, write, и check. Предикат check описывается двумя предложениями. Первое предложение будет успешным, если вводимая цифра 0, при этом курсор сдвигается на начало следующей строки и на экране появляется сообщение «OK!» и процесс повторения завершается, так как после предиката check в теле правила следует предикат отсечения. Если введенное значение отличается от 0, то результатом выполнения предиката check будет fail в соответствии со вторым предложением. В этом случае произойдет возврат к предикату repeat. Repeat повторяет посылки в правой части правила, находящиеся правее repeat и левее условия выхода из бесконечного цикла. 2.3.24 Методы организации рекурсии Рекурсивная процедура – это процедура, которая вызывает сама себя. В рекурсивной процедуре нет проблемы запоминания результатов ее выполнения потому, что любые вычисленные значения можно передавать из одного вызова в другой, как аргументы рекурсивного предиката. Например, в приведенной ниже программе вычисления факториала (пример 37), приведен пример написания рекурсивного предиката. При этом Пролог создает новую копию предиката factorial таким образом, что он становится способным вызвать сам себя как самостоятельную процедуру. При этом не происходит копирования кода выполнения, но все аргументы и промежуточные переменные копируются в стек, который создается каждый раз при вызове рекурсивного правила. Когда выполнение правила завершается, занятая стеком память освобождается и выполнение продолжается в стеке правила-родителя. Пример 37: написать программу вычисления факториала. predicates factorial (byte, dword) clauses factorial (0, 1). factorial (1, 1):-!. factorial (N, R):- N1=N-1, factorial (N1, R1), R=N*R1. goal factorial (7, Result). Для вычисления факториала используется последовательное вычисление произведения ряда чисел. Его значение образуется после извлечения значений соответствующих переменных из стека, используемых как список параметров для последнего предиката в теле правила. Этот последний предикат вызывается после завершения рекурсии. Пример 38: написать программу, генерирующую числа Фибоначчи до заданного значения. predicates f (byte, word) clauses f (1, 1). f (2, 1). f(N, F):- N1=N-1, f (N1, F1), N2=N1-1, f (N2,F2), F=F1+F2. goal f (10, Fib). У рекурсии есть три основных преимущества: • логическая простота по сравнению с итерацией; • широкое применение при обработке списков; • возможность моделирования алгоритмов, которые нельзя эффективно выразить никаким другим способом (например, описания задач, содержащих в себе подзадачи такого же типа). У рекурсии есть один большой недостаток – использование большого объема памяти. Всякий раз, когда одна процедура вызывает другую, информация о выполнении вызывающей процедуры должна быть сохранена для того, чтобы вызывающая процедура могла, после завершения вызванной процедуры, возобновить выполнение на том месте, где остановилась. Рассмотрим специальный случай, когда процедура может вызвать себя без сохранения информации о своем состоянии. Предположим, что процедура вызывается последний раз, то есть после вызванной копии, вызывающая процедура не возобновит свою работу, то есть при этом стек вызывающей процедуры должен быть заменен стеком вызванной копии. При этом аргументам процедуры просто присваиваются новые значения, и выполнение возвращается на начало вызывающей процедуры. С процедурной точки зрения этот процесс напоминает обновление управляющих переменных в цикле. Эта операция в Visual Prolog называется оптимизацией хвостовой рекурсии или оптимизацией последнего вызова. Создание хвостовой рекурсии в программе на Прологе означает, что: • вызов рекурсивной процедуры является самой последней посылкой в правой части правила; • до вызова рекурсивной процедуры в правой части правила не было точек отката. Приведем примеры хвостовой рекурсии. Пример 39:рекурсивный счетчик с оптимизированной хвостовой рекурсией. count(100). count(N):-write(N),nl,N1=N+1,count(N1). goal nl, count(0). Модифицируем этот пример так, чтобы хвостовой рекурсии не стало. Пример 40:рекурсивный счетчик без хвостовой рекурсии. count1(100). count1(N):-write(N),N1=N+1,count1(N1),nl. goal nl, count1(0). Из-за вызова предиката nl после вызова рекурсивного предиката должен сохраняться стек. Пример 41:рекурсивный счетчик без хвостовой рекурсии. count2(100). count2(N):-write(N),nl,N1=N+1,count2(N1). count2(N):-N<0, write(“N – отрицательное число“). goal nl, count2(0). Здесь есть непроверенная альтернатива до вызова рекурсивного предиката (третье правило), которое должно проверяться, если второе правило завершится неудачно. Таким образом, стек должен быть сохранен. Пример 42:рекурсивный счетчик без хвостовой рекурсии. count3(100). count3(N):-write(N),nl,N1=N+1,check(N1),count3(N1). check(Z):-Z>=0. check(Z):-Z<0. goal nl, count3(0). Здесь тоже есть непроверенная альтернатива до вызова рекурсивного предиката (предикат check). Случаи в примерах 41 и 42 хуже, чем в примере 39, так как они генерируют точки возврата. Очень просто сделать рекурсивный вызов последним в правой части правила, но как избежать альтернатив? Для этого следует использовать предикат отсечения, который предотвращает возвраты в точки, левее предиката отсечения. Модифицируем 41 и 42 примеры так, чтобы была хвостовая рекурсия. Пример 43:рекурсивный счетчик из примера 41 с хвостовой рекурсией. count4(100). count4(N):-N>0,!,write(N),N1=N+1,count4(N1). count4(N):- write(“N – отрицательное число“). goal nl, count4(0). Пример 44:рекурсивный счетчик из примера 42 с хвостовой рекурсией. count5(100). count5(N):-write(N),N1=N+1 check(N1),!, count5(N1). check(Z):-Z>=0. check(Z):-Z<0. goal nl, count5(0). 2.3.25 Представление бинарных деревьев Одной из областей применения списков является представление множества объектов. Недостатком представления множества в виде списка является неэффективная процедура проверки принадлежности элемента множеству. Используемый для этой цели предикат member неэффективен при использовании больших списков. Для представления множеств могут использоваться различные древовидные структуры, которые обеспечивают более эффективную реализацию проверки принадлежности элемента множеству, в частности, в данном разделе для этой цели рассматриваются бинарные деревья. Представление бинарных деревьев основано на определении рекурсивной структуры данных, использующей функцию типа tree (Top, Left, Right) или tree (Left, Top, Right), где Top - вершина дерева, Left и Right - соответственно левое и правое поддерево. Пустое дерево обозначим термом nil. Объявить бинарное дерево можно следующим образом: Пример 45: domains treetype1=tree(symbol, treetype1, treetype1);nil treetype2=tree(treetype2, symbol, treetype2);nil Пример 46: Пусть дано дерево следующего вида: a b c d e Такое дерево может быть задано следующим образом: 1. левое поддерево: tree (b, tree (d, nil, nil), tree (e, nil, nil)). 2. правое поддерево: tree (c, nil, nil). 3. все дерево: tree (a, tree (b, tree (d, nil, nil), tree (e, nil, nil)), tree (c, nil, nil)). Пример 47: написать программу проверки принадлежности вершины бинарному дереву. domains treetype = tree(symbol, treetype, treetype);nil() predicates in(symbol, treetype) clauses in(X, tree(X,_,_). in(X, tree(_,L,_):-in(X, L). in(X, tree(_,_,R):-in(X, R). goal in(d,tree(a, tree(b, tree(d, nil, nil), tree(e, nil, nil)), tree(c, nil, nil))). Поиск вершины в неупорядоченном дереве также неэффективен, как и поиск элемента в списке. Если ввести отношение упорядочения между элементами множества, то процедура поиска элемента становится гораздо эффективнее. Можно ввести отношение упорядочения слева направо непустого дерева tree(X, Left, Right) следующим образом: 1. Все узлы в левом поддереве Left меньше X. 2. Все узлы в правом поддереве Right больше X. 3. Оба поддерева также являются упорядоченными. Преимуществом упорядочивания является то, что для поиска любого узла в дереве достаточно провести поиск не более, чем в одном поддереве. В результате сравнения узла и корня дерева из рассмотрения исключается одно из поддеревьев. Пример 48: написать программу проверки принадлежности вершины упорядоченному слева направо бинарному дереву. domains treetype = tree(byte, treetype, treetype);nil() predicates in(byte, treetype) clauses in(X, tree(X,_,_). in(X, tree(Root,L,R):-Root>X,in(X, L). in(X, tree(Root,L,R):-RootOc2,!; xod_max (Poz1), Oc1