Министерство образования и науки Украины

Севастопольский национальный технический университет

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к выполнению лабораторных работ и контрольных заданий

по дисциплине «Системы искусственного интеллекта»

для студентов дневного и заочного отделения

специальности 07.080401

«Информационные управляющие системы и технологии»

часть 2 Севастополь 2002 УДК 004.8 Методические указания к лабораторному практикуму по дисциплине «Системы искусственного интеллекта» /Сост. А. В. Крицкий, В.Н. Бондарев – Севастополь: Изд-во СевНТУ, 2003. – 44с.

Методические указания предназначены для проведения лабораторных занятий по дисциплине «Системы искусственного интеллекта». Целью настоящих методических указаний является обучение студентов практическим навыкам разработки программ, использующих принципы искусственного интеллекта.

Методические указания составлены в соответствии с требованиями программы дисциплины «Системы искусственного интеллекта» для студентов специальности 7.080401 и утверждены на заседании кафедры информационных систем, протокол № от 2002 года.

Допущено учебно-методическим центром СевНТУ в качестве методических указаний.

Рецензент Цуканов А.В., д-р.техн.наук., профессор кафедры экономики и менеджмента.

ОБЩИЕ ТРЕБОВАНИЯ

К ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ РАБОТ

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

Задачами выполнения лабораторных работ являются:

углубленное изучение основных теоретических положений дисциплины «Системы искусственного интеллекта»;

получение практических навыков разработки программ на языках систем искусственного интеллекта - ЛИСП и Пролог.

2. Описание лабораторной установки Объектом исследования в лабораторных работах являются методы и алгоритмы, применяемые в системах искусственного интеллекта, а также сами языки ЛИСП и ПРОЛОГ, представляющие программные системы и реализующие две различные парадигмы программирования систем искусственного интеллекта.

Инструментом исследования указанных программных систем является ЭВМ. В качестве операционной системы могут использоваться ОС MS-DOS или Windows. Программные системы ЛИСП и ПРОЛОГ представлены реализациями соответственно Common Lisp и Visual Prolog. Описание системы Common Lisp и системы логического программирования Visual Prolog приведено ниже в лабораторных работах.

3. Порядок выполнения лабораторных работ Варианты заданий студенты выбирают самостоятельно по номеру зачетной книжки. Номер варианта определяется как остаток от деления двух последних цифр номера зачетки на 30. Например, две последние цифры зачетки 23. Остаток от деления 23 на 30 равен 23. Следовательно, номер варианта задания 23.

Все работы, приведенные в методических указаниях, выполняются за лабораторных часа. Исключение составляет работа №1, которая выполняется за 2 часа.

При выполнении каждой лабораторной работы необходимо:

- разработать алгоритм решения задачи;

- запрограммировать его средствами соответствующего языка, применяемого в лабораторной работе;

- ввести программу в ЭВМ и отладить ее;

- получить результаты обработки исходных данных в различных режимах работы программы;

- получить распечатки текстов, разработанных программ и результатов обработки.

Студенты заочной формы обучения выполняют данные лабораторные в два этапа.

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

- вариант задания;

- краткое теоретическое описание метода решения задачи;

- программу на языке Лисп, решающую поставленную задачу;

- подробное описание программы.

Сроки сдачи контрольных работ:

- контрольная работа N1 и N2 - 5-ая неделя семестра;

- контрольная работа N3 и N4 - 10-ая неделя семестра;

- контрольная работа N5 - 13-ая неделя семестра;

- контрольная работа N6 – 15-ая неделя семестра.

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

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

Исследование простейших средств вывода систем логического программирования. Изучение средств представления фактов и запросов на языке Пролог.

Разработать и представить реляционную базу данных по указанной тематике на языке Пролог. Реализовать полученную БД, составить и выполнить около десяти различных запросов к ней, используя данные 1) студентах;

2) предприятиях;

3) кораблях;

4) телефонах;

5) футболистах;

6) компьютерах;

7) животных;

8) магазинах;

9) холодильниках;

10) программном обеспечении;

11) журналах;

12) работниках предприятия;

13) склада готовой продукции;

14) автомобилях;

15) зданиях;

16) принтерах;

17) самолетах;

18) мебели;

19) родственных отношениях;

20) модемах;

21) оборудовании предприятия;

22) вертолетах;

23) книгах;

24) продуктах питания;

25) растениях;

26) одежде;

27) телевизорах;

28) сканерах;

3.1. Общие сведения о языке Пролог Язык Пролог был разработан в начале семидесятых годов. Само название этого языка определяет его суть - язык логического программирования.

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

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

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

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

Существует много различных версий языка Пролог, такие как Turbo и Arity Prolog, Visual Prolog. В настоящее время наиболее широкое применение получил Visual Prolog. Язык Пролог был разработан в начале семидесятых годов. Само название этого языка определяет его суть - язык логического программирования. Пролог является уникальным языком программирования, хотя некоторые его возможности присущи и другим языкам программирования. Так механизм работы со списками Пролог унаследовал от Лиспа, но он обеспечивает новый уровень абстракции: если Лисп скрывает от программиста организацию памяти, то Пролог, кроме того, позволяет не заботиться о потоке управления. Это объясняется тем,что программа на Прологе интерпретируется двояко: как декларативное описание некоторых закономерностей, составляющих спецификацию задачи, и как описание процедур, определяющих ход решения задачи.

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

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

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

3.2. Объекты данных языка Пролог Все объекты данных в Прологе представляют собой термы. На рисунке 3.1 приведена классификация объектов данных языка Пролог.

Рисунок 3.1 - Объекты данных языка Пролог Атом представляет собой некоторый статический объект данных (минимальную неделимую единицу языка) и описывается с помощью цепочки символов, либо состоящей из букв латинского алфавита, цифр и символа подчеркивания, и начинающуюся со строчной буквы, либо с помощью последовательности любых символов, заключенной в двойные кавычки. Например, Числа в Прологе могут быть целыми или вещественными.

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

Для того, чтобы объединить объекты в структуру, необходим функтор. Например в структуре, date(month, day, Year), функтор date объединяет атомы month и day, а также переменную Year.

3.3. Структура программы на языке Пролог Программа на языке Пролог представляет собой совокупность утверждений, являющихся дизъюнктами Хорна. В конце утверждения ставится точка. Утверждения в языке Пролог бывают двух видов: факты и правила.

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

Правило представляет собой утверждение, истинность которого зависит от некоторых условий. Например, если существует отношение родитель (parent), то всегда можно определить отношение потомок (decendant) "X является потомком Y, если Y является родителем X". Символ :- обозначает импликацию. Когда определена совокупность фактов и правил, представляющих собой базу данных, к Пролог системе можно обращаться с вопросами. В качестве ответа на вопрос выдается либо ответ «Да» или «Нет», либо выдаются все возможные значения переменных, используемых в вопросе. Например, на вопрос Пролог выдаст ответ: Х=petya.

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

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

Программа на Visual Prolog представляет собой совокупность нескольких разделов. В раздел PREDICATES объявляются факты и правила, которые будут использоваться в программе. При этом необходимо указать количество параметров и их тип. Тип данных в Visual Prolog такие же, как и в языке Common Lisp. Если перед объявлением предложения указывается одно из ключевых слов determ и nondeterm, то это означает, что предложение представляет собой детерминированное и недетерминированное правило соответственно. Детерминированное правило позволяет находить только одно решение, недетерминированное – много.

Описание фактов и правил осуществляется в разделе CLAUSES. При описании фактов и правил необходимо соблюдать количество и тип переменных или констант, используемых в правиле. Вопрос задается в разделе GOAL в виде факта. Ниже приведен пример программы на Visual Prolog.

PREDICATES

likes(symbol,symbol)

CLAUSES

likes(ellen,tennis).

likes(john,football).

likes(tom,baseball).

likes(eric,swimming).

likes(mark,tennis).

GOAL likes(tom, baseball).

1) На чем базируется язык Пролог.

2) Назовите основные объекты данных языка Пролог.

3) Что представляют собой константы языка Пролог.

4) Какие имена могут принимать переменные в Прологе.

5) Что такое структура, функтор, терм языка Пролог.

6) Что называется предложением, фактом, правилом, процедурой и вопросом в терминах языка Пролог.

7) Как обозначаются импликация и конъюнкция в Прологе.

8) Каким образом описываются реляционные базы данных в языке Пролог.

9) Объясните механизм вывода, реализованный в Пролог-системе.

10)Что называют дизъюнктами Хорна.

11)Что такое резолюция.

12)Объясните принцип резолюций.

Исследование и разработка простейшей экспертной системы. Изучение понятий сопоставления и конкретизации переменных в Прологе. Декларативная и процедурная семантика.

Представить приведенную ниже логическую задачу в виде предикатов на языке Visual Prolog, составить целевое утверждение и ответить на вопрос задачи.

1. Известно, что Единорог лжет по понедельникам, вторникам и средам и говорит правду во все остальные дни недели. Он может сказать: "Вчера я лгал. После завтрашнего дня я буду лгать два дня подряд":

В какой день Единорог произнес эту фразу.

2. Три друга - Петр, Роман и Сергей - учатся на математическом, физическом и химическом факультетах. Если Петр - математик, то Сергей не физик. Если Роман не физик, то Петр - математик. Если Сергей не математик, то Роман - химик. Какая специальность у Сергея.

3. Четыре юных филателиста: Митя, Толя, Петя и Саша - купили почтовые марки. Каждый из них покупал марки только одной страны, причем двое из них купили российские марки, один - болгарские и один - чеш- ские.

Известно, что Митя и Толя купили марки двух разных стран. Марки разных стран купили Митя с Сашей, Петя с Сашей, Петя с Митей и Толя с Сашей.

Кроме того, известно, что Митя купил не болгарские марки. Кто купил болгарские марки?

4. В чашке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в чашке; сосуд с лимонадом стоит между кувшином и сосудом с квасом; в банке не лимонад и не вода; а стакан стоит между банкой и сосудом с молоком. Где находится вода.

5. В студенческой группе возникла следующая ситуация: каждый студент или умеет играть в шахматы, или имеет спортивный разряд, или хорошо учиться (но не то и другое вместе); если студент имеет спортивный разряды, то он не умеет играть в шахматы. Следует ли отсюда, что в группе нет студентов, которые имеют спортивный разряд и в то же время хорошо учатся?

6. Боря, Витя, Гриша и Егор встретились на олимпиаде. Ребята приехали из разных городов: один - из Твери, другой - из Омска, третий - из Томска, а четвертый - из Казани. Известно, что Боря жил в одной комнате с мальчиком из Казани и ни один из них никогда не был ни в Твери, ни в Томске.

Гриша играл в одной команде с мальчиком из Твери, а против них обычно сражался приятель из Казани. Егор и мальчик из Твери увлекались игрой в шахматы. Определить город, из которого приехал Егор.

7. Проверьте правильность следующего рассуждения полицейского детектива: "Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей, либо Джонс лжёт. Если Смит был убийцей, то Джонс не встречал Смита этой ночью, и убийство имело место после полуночи. Если убийство имело место после полуночи, то либо Смит был убийцей, либо Джонс лжёт.

Следовательно, Смит был убийцей.

8. Квадрат, круг, ромб и треугольник вырезаны из белой, синей, красной и зеленой бумаги. Известно, что: круг не белый и не зеленый; синяя фигура лежит между ромбом и красной фигурой; треугольник не синий и не зеленый; квадрат лежит между треугольником и белой фигурой. Из бумаги какого цвета вырезан ромб?

9. На предприятии есть три цеха А,В,С, которые договорились о следующем порядке утверждения проектов; a) если цех В не участвует в утверждении проекта, то в этом утверждении не участвует и цех А; б) если цех В принимает участие в утверждении проекта, то в нём принимает участие цеха А и С. Обязан ли при этих условиях цех С принимать участие в утверждении проекта, когда в нём принимает участие цех А?

10. Пятеро школьников из пяти различных городов приехали в Смоленск для участия в олимпиаде по математике. "Откуда вы, ребята?" - спросили их. Вот что они ответили: Андреев: "Я приехал из Ярославля, а Григорьев живет в Гагарине". Борисов: "В Гагарине живет Васильев, я прибыл из Вязьмы". Васильев: "Из Ярославля приехал я, а Борисов - из Ельни". Григорьев: Я приехал из Гагарина, а Данилов из Ярцева". Данилов: "Да, я действительно из Ярцева, Андреев живет в Вязьме". В каждом из высказываний одно утверждение правильное, а другое ложное. Откуда приехал Данилов?

11. Три девушки Аня, Варя и Клава ходили на демонстрацию. Одна из них была в красном платье, другая - в белом, третья - в синем. На вопрос, какое было платье на каждой из девушек они дали ответ: Аня была в красном, Варя - не в красном, Клава - не в синем. В этом ответе из трёх частей одна верна, две неверны. В каком платье была каждая из девушек ?

12. Четыре марсианки, оказавшиеся на Земле в 2222 году, на вопрос об их возрасте дали ответы: а) Ми - 22 года, Ме - 21 год; б) Мо - 19 лет, Ми - год; в) Ма - 21 год, Мо - 18 лет. Все марсианки - разных возрастов, притом только таких - 18, 19, 21 и 22. В каждом ответе одна часть истинна, а другая ложна. Сколько лет каждой из марсианок?

13. В велогонках приняли участие 5 школьников. После гонок 5 болельщиков заявили: 1) Коля занял 1-е место, а Ваня - 4; 2) Сережа занял 2-е место, а Ваня - 4; 3) Сережа занял 2-е место, а Коля - 3; 4) Толя занял 1-е место, а Надя - 4; 5) Надя заняла 3-е место, а Толя - 5. Зная, что одно из показаний каждого болельщика верное, а другое – ложное. Определить какое место занял Толя.

14. Профессор Икс Игрекович Зет был так учен, как и рассеян. У него была большая библиотека, которая помещалась в трёх комнатах. В первой были справочники, во второй - труды по специальности, в третьей - научные журналы. Когда он писал свой знаменитый труд "О бессмертии майских жуков", у него на столе царил невероятный хаос, и он не мог найти трёх вещей:

словарь эскимосского языка, учебник жукологии и памфлет своего противника профессора Болтунова. Профессор очень волновался и обвинил лаборанта, что тот, по-видимому, поставил словарь где-то среди трудов, а учебник и памфлет среди журналов. Лаборант отрицал это и говорил, что профессор, как всегда, бросил все эти три вещи в первой комнате. Супруга профессора высказала предположение, что словарь, вероятно, находится среди журналов, а учебник и памфлет - среди трудов. В начавшейся перебранке каждый настаивал на своём. Дочь профессора, слушавшая всё это, сказала: "Всё, что вы утверждаете, неверно". Если она права, то куда задевались эти вещи?

15. Шестеро юношей наблюдали прохожего, затем каждый из них ответил на вопрос, какого цвета его волосы, глаза и костюм, сколько ему лет. Андрей: рыжий, глаза голубые, костюм серый,34. Вова: блондин, глаза карие, костюм синий, 30. Борис: рыжий, глаза карие, костюм коричневый,32. Григорий: брюнет, глаза голубые, костюм во всяком случае не коричневый, 30.

Дмитрий: шатен, глаза чёрные, костюм серый, 28. Евгений: блондин, глаза карие, костюм синий, 32. Каждый из них трижды ошибся. Но из шести ответов на каждый из вопросов, по меньшей мере, один был верен. Каковы приметы прохожего?

16. Семья, состоящая из отца, матери, сына, младшей и старшей дочери, купили телевизор. Условились, что в первый вечер будут смотреть передачи и в каком порядке: а) когда отец смотрит передачу, мать тоже смотрит передачу; б) дочери, обе или одна из них, смотрят передачу; в) из двух членов семьи - мать и сын - смотрят передачу либо только мать, либо только сын; г) сын смотрит передачу тогда и только тогда, когда её смотрит старшая дочь;

д) если младшая смотрит передачу, то отец и старшая дочь делают тоже. Кто из членов семьи смотрел в этот вечер передачу?

17. Во время перемены в классе были Аня, Борис, Ваня и Маня. Один из них разбил окно. Учитель спросил их и получил три ответа.

Аня: 1. Я его не разбивала; 2. Я сидела и читала; 3. Маня знает, кто разбил.

Борис: 1. Я этого не делал 2. С Маней я давно не разговариваю; 3. Это сделал Ваня;

Ваня: 1. Я невиновен; 2. Разбила Маня; 3. Борис лжёт, говоря, что разбил я.

Маня: 1. Я не разбивала окна; 2. Это вина Ани; 3. Борис знает, что я не виновата, потому что мы с ним беседовали во время перемены.

В конце концов, каждый из них признался, что из трёх ответов, которые он дал, два истинны, один ложен. Кто разбил окно?

18. Четыре юных филателиста: Митя, Толя, Петя и Саша - купили почтовые марки. Каждый из них покупал марки только одной страны, причем двое из них купили российские марки, один - болгарские и один - чеш- ские.

Известно, что Митя и Толя купили марки двух разных стран. Марки разных стран купили Митя с Сашей, Петя с Сашей, Петя с Митей и Толя с Сашей.

Кроме того, известно, что Митя купил не болгарские марки. Кто купли чешские марки?

19. В велогонках приняли участие 5 школьников. После гонок 5 болельщиков заявили: 1) Коля занял 1-е место, а Ваня - 4; 2) Сережа занял 2-е место, а Ваня - 4; 3) Сережа занял 2-е место, а Коля - 3; 4) Толя занял 1-е место, а Надя - 4; 5) Надя заняла 3-е место, а Толя - 5. Зная, что одно из показаний каждого болельщика верное, а другое – ложное. Определить какое место занял Коля.

20. В чашке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в чашке; сосуд с лимонадом стоит между кувшином и сосудом с квасом; в банке не лимонад и не вода; а стакан стоит между банкой и сосудом с молоком. Где находится квас.

21. Пятеро школьников из пяти различных городов приехали в Смоленск для участия в олимпиаде по математике. "Откуда вы, ребята?" - спросили их. Вот что они ответили: Андреев: "Я приехал из Ярославля, а Григорьев живет в Гагарине". Борисов: "В Гагарине живет Васильев, я прибыл из Вязьмы". Васильев: "Из Ярославля приехал я, а Борисов - из Ельни". Григорьев: Я приехал из Гагарина, а Данилов из Ярцева". Данилов: "Да, я действительно из Ярцева, Андреев живет в Вязьме". В каждом из высказываний одно утверждение правильное, а другое ложное. Откуда приехал Андреев?

22. Квадрат, круг, ромб и треугольник вырезаны из белой, синей, красной и зеленой бумаги. Известно, что: круг не белый и не зеленый; синяя фигура лежит между ромбом и красной фигурой; треугольник не синий и не зеленый; квадрат лежит между треугольником и белой фигурой. Какая фигура вырезана из зеленой бумаги?

23. Три друга - Петр, Роман и Сергей - учатся на математическом, физическом и химическом факультетах. Если Петр - математик, то Сергей не физик. Если Роман не физик, то Петр - математик. Если Сергей не математик, то Роман - химик. Какая специальность у Петра.

24. Боря, Витя, Гриша и Егор встретились на олимпиаде. Ребята приехали из разных городов: один - из Твери, другой - из Омска, третий - из Томска, а четвертый - из Казани. Известно, что Боря жил в одной комнате с мальчиком из Казани и ни один из них никогда не был ни в Твери, ни в Томске.

Гриша играл в одной команде с мальчиком из Твери, а против них обычно сражался приятель из Казани. Егор и мальчик из Твери увлекались игрой в шахматы. Определить город, из которого приехал Витя.

25. Известно, что Лев лжет по понедельникам, вторникам и средам и в остальные дни говорит правду, а Единорог лжет по четвергам, пятницам и субботам и говорит правду в остальные дни. Однажды Лев сказал: "Вчера был один из дней, когда я лгу", на что Единорог заметил "Вчера был один из дней, когда я тоже лгу". Когда произошла беседа.

26. В чашке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в чашке; сосуд с лимонадом стоит между кувшином и сосудом с квасом; в банке не лимонад и не вода; а стакан стоит между банкой и сосудом с молоком. Где находится лимонад.

27. Четыре юных филателиста: Митя, Толя, Петя и Саша - купили почтовые марки. Каждый из них покупал марки только одной страны, причем двое из них купили российские марки, один - болгарские и один - чеш- ские.

Известно, что Митя и Толя купили марки двух разных стран. Марки разных стран купили Митя с Сашей, Петя с Сашей, Петя с Митей и Толя с Сашей.

Кроме того, известно, что Митя купил не болгарские марки. Какие филателисты купили чешские марки?

28. В велогонках приняли участие 5 школьников. После гонок 5 болельщиков заявили: 1) Коля занял 1-е место, а Ваня - 4; 2) Сережа занял 2-е место, а Ваня - 4; 3) Сережа занял 2-е место, а Коля - 3; 4) Толя занял 1-е место, а Надя - 4; 5) Надя заняла 3-е место, а Толя - 5. Зная, что одно из показаний каждого болельщика верное, а другое – ложное. Определить какое место занял Надя.

29. Пятеро школьников из пяти различных городов приехали в Смоленск для участия в олимпиаде по математике. "Откуда вы, ребята?" - спросили их. Вот что они ответили: Андреев: "Я приехал из Ярославля, а Григорьев живет в Гагарине". Борисов: "В Гагарине живет Васильев, я прибыл из Вязьмы". Васильев: "Из Ярославля приехал я, а Борисов - из Ельни". Григорьев: Я приехал из Гагарина, а Данилов из Ярцева". Данилов: "Да, я действительно из Ярцева, Андреев живет в Вязьме". В каждом из высказываний одно утверждение правильное, а другое ложное. Откуда приехал Борисов?

30. Квадрат, круг, ромб и треугольник вырезаны из белой, синей, красной и зеленой бумаги. Известно, что: круг не белый и не зеленый; синяя фигура лежит между ромбом и красной фигурой; треугольник не синий и не зеленый; квадрат лежит между треугольником и белой фигурой. Из бумаги какого цвета вырезан квадрат?

3.1. Сопоставление Наиболее важной операцией над термами является сопоставление. Сопоставление - это процесс, на вход которого подаются два терма, и проверяется, соответствуют ли эти термы друг другу. Два терма сопоставимы, если:

2) переменным в обоих термах можно приписать в качестве значений объекты таким образом, чтобы после подстановки этих объектов в термы вместо переменных, последние стали идентичными.

Рассмотрим сопоставление двух дат. Запрос для осуществления такой операции можно составить с использованием оператора ‘=’:

?- date(D,M,1998)=date(25,may,Y).

В качестве результата Пролог-система выдаст:

По мере вычисления последовательности целей, переменным приписываются обычно все более и более конкретные значения. Сопоставление в Прологе всегда дает наиболее общую конкретизацию (см. далее).

Общие правила сопоставления двух термов S и Т таковы:

1. Если S и Т - константы, то S и Т сопоставимы в том случае, когда они являются одним и тем же объектом.

2. Если S- переменная, а Т - произвольный объект, то они сопоставимы и S приписывается значение Т и наоборот, если Т - переменная, а S произвольный объект, то они сопоставимы и Т приписывается значение S.

3. Если S и Т - структуры, то они сопоставимы, только если а) S и Т имеют одинаковый главный функтор и b) все их соответствующие компоненты сопоставимы.

3.2. Декларативная и процедурная семантика Имеет смысл различать два уровня понимания программы на языке Пролог, а именно декларативный и процедурный. Декларативный смысл касается только отношений, определенных в программе, т.е. определяет, что должно быть результатом работы программы. С другой стороны, процедурный смысл определяет еще и как этот результат был получен, т.е. как эти отношения реально обрабатывались Пролог-системой. Рассмотрим предложение где P,Q и R имеют синтаксис термов (напомним, что запятая между целями обозначает конъюнкцию, а точка с запятой - дизъюнкцию). Приведем некоторые способы декларативной интерпретации этого предложения:

С точки зрения процедурной семантики, это предложение можно прочесть следующим образом:

Чтобы решить задачу Р, сначала реши подзадачу Q, а затем подзадачу R.

Декларативный смысл программы определяет, является ли данная цель истинной (достижимой) и, если да, то при каких значениях переменных она достигается. Конкретизацией предложения С называется результат подстановки в него на место каждой переменной некоторого терма. Вариантом предложения С называется такая конкретизация С, при которой каждая переменная заменена на другую переменную. Например, рассмотрим предложение:

havechild(Х):-parent (X,Y).

‘Х имеет ребенка, если он является родителем какого-либо Y’.

Приведем два варианта этого предложения:

havechild(A):-parent(A,B).

havechild(X):-parent(X,X1).

Пример конкретизации этого же предложения:

havechild(Petya):-parent(Petya, Vasya).

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

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

3.3. Простейшая модель экспертной системы Экспертная система - это программа, которая ведет себя подобно эксперту в некоторой, обычно узкой, прикладной области. При разработке экспертной системы принято делить ее на три основных модуля:

2) машина логического вывода, и 3) интерфейс с пользователем.

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

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

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

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

Ваша база знаний будет состоять из фактов и правил. Факты в Прологе позволяют выражать произвольные отношения между объектами предметной области. Например:

population (china,1500).

population(ukraine, 50).

population(russia, 99).

Каждому факту соответствует возможная интерпретация на естественном языке. Например: "В Китае 1.5 млрд. жителей".

Если необходимо сказать, что некоторый факт зависит от групп других фактов, то в языке Пролог используются правила. Правило, применительно к описанию предметной области, представляет некоторое утверждение об объектах и отношениях между ними. Например, я не хочу жить в большой стране. Тогда описав следующее правило live(X,Y):- population(X,Z), Z=;

X=russia.

3.4.Пример решения логической задачи на языке Пролог % Произошло убийство. Четыре подозреваемых дали показания.

% Показания Конномэна: Маггит был убит из автомата в 10 часов вечера на набережной. Труп сброшен в реку. Убийца - Пиклок. Показания Пиклока: Маггит был убит из кольта 45 калибра в 9 часов вечера в Чесли. Труп сброшен в реку. Убийца - Дженнисон. Показания % Дженнисона: Маггит был убит из кольта 45 калибра в 11 часов вечера на набережной. Труп был спрятан в багажник автомашины.

Убийца - Спивенс. Показания Спивенса : Маггит был убит из автомата в % полночь в Патни. Труп спрятан в мусорном ящике. Убийца - Конномэн. Показания Маггита:...

% Было установлено, что каждый из допрошенных только дважды % говорил правду.

% Какое оружие было использовано, где и когда был убит Маггит, куда девался его труп, кто убил его ?

% отношение свидетель witness(name,weapon,time,place,corpse,killer) witness(konnoman,automat,10,embankment,river,piklok ).

witness(piklok,kolt,9,chesli,river,dgekson ).

witness(dgekson,kolt,11,embankment,car,spivens ).

witness(spivens,automat,00,patni,box,konnoman).

% отношение, описывающее тот факт, что каждый из допрошенных только % дважды говорил правду two_out_of_five(Name,Weapon,Time,Place,Corpse,Killer):witness(Name,Weapon,Time,_,_,_ );

witness(Name,Weapon,_,Place,_,_ );

witness(Name,Weapon,_,_,Corpse,_ );

witness(Name,Weapon,_,_,_,Killer);

witness(Name,_,Time,Place,_,_ );

witness(Name,_,Time,_,Corpse,_ );

witness(Name,_,Time,_,_,Killer);

witness(Name,_,_,Place,Corpse,_ );

witness(Name,_,_,Place,_,Killer);

witness(Name,_,_,_,Corpse,Killer).

% основная процедура truth:-two_out_of_five(konnoman,Weapon,Time,Place,Corpse,Killer), two_out_of_five(piklok,Weapon,Time,Place,Corpse,Killer), two_out_of_five(dgekson,Weapon,Time,Place,Corpse,Killer), two_out_of_five(spivens,Weapon,Time,Place,Corpse,Killer), %печать результатов nl,write('Maggit was killed by '),write(Killer),write(' at '), write(Time),write(' o''clock, near the '),write(Place),write(','), nl,write('with the help of a '),write(Weapon), write('. His corpse was thrown into the '),write(Corpse),write('.'),nl.

1) Что такое сопоставление.

2) Сделайте обзор общих правил сопоставления двух термов.

3) Приведите пример правила на языке Пролог и объясните его с точки зрения процедурной и декларативной семантик.

4) Объясните понятия конкретизации и варианта предложения.

5) Что входит в состав простейшей экспертной системы.

6) Объясните понятие продукция.

7) Приведите пример правила и факта на языке Пролог, описывающих некоторые знания.

8) Определите на языке Пролог предикат member.

9) Определите на языке Пролог предикат append.

ЛАБОРАТОНАЯ РАБОТА N

Работа с бинарными деревьями в языке Пролог Исследование способов организации вычислительных процессов при обработке двоичных деревьев в системах логического программирования.

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

1. печатает все листья дерева;

2. добавляет элемент в качестве корня дерева;

3. находит среднее арифметическое всех элементов дерева (элементы дерева - числа);

4. печатает все элементы дерева, начинающиеся с введенной пользователем 5. печатает дерево вертикально, сверху вниз;

6. удаляет все элементы дерева, начинающиеся с введенной пользователем 7. подсчитывает количество вершин заданного пользователем уровня;

8. определяет глубину дерева;

9. формирует дерево, которое может содержать повторяющиеся элементы;

10. определяет уровень элемента дерева;

11. печатает перевернутое дерево (снизу вверх).

12. преобразует дерево в список и выводит его на печать.

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

Древовидной называется такая структура данных, в которой отношения подчиненности между элементами могут быть описаны с помощью графа типа ‘дерево’. Наиболее широкое распространение для представления данных получили бинарные или двоичные деревья. Любая вершина такого бинарного дерева связана только с одной ближайшей вершиной высшего уровня и с двумя вершинами низшего уровня, т.е. каждый узел дерева имеет два поддерева. Число поддеревьев данного узла называется степенью узла. Узел с нулевой степенью называется листом.

Поиск по бинарному дереву приобретает наибольшую эффективность в том случае, когда дерево упорядочено. Для того, чтобы упорядочить дерево, все его элементы снабжают ключевыми признаками. Считается, что дерево упорядочено слева направо, если каждый его элемент имеет на своей левой ветви элемент с меньшим, чем у него значением ключа, а на правой - с большим. Упорядоченное бинарное дерево называется двоичным справочником.

3.2. Представление бинарных деревьев в языке Пролог.

С точки зрения языка Пролог бинарное дерево представляет собой структуру, которая либо пуста, либо состоит из трех частей: корень, левое поддерево и правое поддерево. Корень может являться любой структурой, а поддеревья обязательно должны быть двоичными деревьями. Пусть атом nil символизирует пустое дерево, а структура tree(L,X,R) описывает дерево с корнем Х, левым поддеревом L и правым поддеревом R. Можно говорить об упорядоченности такого дерева слева направо, если все вершины левого поддерева L меньше Х и все вершины правого поддерева R больше Х, причем поддеревья L и R упорядочены.

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

Правила добавления элемента дерева таковы:

• Результат добавления элемента Х к пустому дереву есть дерево вида tree(nil,X,nil).

• Если Х совпадает с корнем дерева Т, то результатом добавления элемента будет являться само дерево (если дублирование не допускается).

• Если корень дерева Т больше Х, то Х следует добавить в левое поддерево;

если корень дерева Т меньше Х. То элемент добавляется в левое поддерево.

Обратите внимание, что в этом случае добавление элемента осуществляется на уровне листа (добавление элемента на уровне корня реализуется сложнее).

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

• Если правое поддерево удаляемого элемента Х пустое, то результатом удаления будет служить его левое поддерево.

• Если удаляемый элемент Х совпадает с корнем дерева tree(L,X,R), то результатом удаления будет являться дерево tree(L,Y,R1), где Y - самая левая вершина правого поддерева, а R1 - поддерево R, из которого удалена вершина Y.

• Если удаляемый элемент Х меньше корня дерева tree(L,K,R), то удалить элемент Х из левого поддерева L.

• Если удаляемый элемент Х больше корня дерева tree(L,K,R), то удалить элемент Х из правого поддерева R.

Поиск элемента дерева осуществляется следующим образом:

• Если элемент Х является корнем дерева, то считается, что он уже найден.

• Если элемент Х меньше корня, то искать его в левом поддереве.

• Если элемент Х больше корня, то искать его в правом поддереве.

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

• отобразить правое поддерево дерева Т с отступом вправо на расстояние Н;

• напечатать корень дерева Т;

• отобразить левое поддерево Т с отступом на расстояние Н.

1. Осветите понятия нелинейные структуры данных, деревья, лист дерева, степень узла дерева.

Что такое двоичные справочники.

Напишите предикат формирования упорядоченного бинарного дерева.

Напишите предикат удаления элемента из двоичного справочника.

Напишите предикат поиска элемента дерева.

Напишите предикат печати дерева.

Напишите предикат, преобразующий список в дерево.

Напишите предикат, преобразующий дерево в список.