Классификация задач по логическому программированию.

Одной из дидактических задач дисциплины "Основы ИИ", как нами было выделено выше, является знакомство с приемами логического программирования. В данном пункте проводится обзорный анализ учебно-методической литературы по логическому программированию ([1],[13],[5]).

Как отмечает автор [14], большинство задач, которые считаются логическими, сводятся к задаче нахождения пути в некотором графе - графе состояний задачи. Характерными особенностями этих задач является следующее:

1) наличие неких дискретных состояний, число которых конечно; чаще всего в этих задачах имеется начальное состояние, с которых начинается поиск;

2) определены правила перехода между состояниями;

)   для каждого состояния заданы определенные условия допустимости (оценки) этого состояния.

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

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

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

1.                       Задачи на запросы к базе данных Пролог-программы.

· Пусть дана база знаний "Спортивные увлечения".

летний (бег).

летний (плавание).

зимний (лыжи).

зимний (коньки).

спорт (Иван, бег).

спорт (Семен, плавание).

спорт (Петр, Х):- спорт (Иван, Х), зимний(Х).

Не определяя новых правил, сформулируйте вопросы:

· Какими видами спорта занимается Петр?

· Существуют ли такие одинаковые виды спорта, которыми занимаются Иван и Петр?

· Занимается ли Семен каким-нибудь летним видом спорта? [6]

· Описать базу знаний "Отборочные соревнования", в которой даны результаты прохождения лыжниками дистанций длиной 5 км и 10 км (в минутах). Если лыжник прошел 5 км за время, не превышающее 17 минут, а 10 км - менее чем за 35 минут, то он допускается к участию в соревнованиях. Сформулируйте следующие вопросы:

· Кто из лыжников пробежал дистанцию 5 км не более чем за 17 минут? Каково это время?

· Кто из лыжников допущен к участию в соревнованиях?

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

· Описать базу знаний "Крупнейшие озера земного шара", используя информацию из таблицы?

 

Название	Площадь	Наибольшая глубина
Каспийское море (Европа, Азия)	394,3	980
Верхнее озеро (Сев. Америка)	82,4	308
Виктория (Африка)	68	80
Гурон (Сев. Америка)	59,6	222
Мичиган (Сев. Америка)	58	263
Танганьика (Африка)	32,9	1453
Байкал (Азия)	31,5	1742
Аральское море (Азия)	66,5	68

 

Сформулируйте цели и ответьте на них:

· Какие озера расположены в Африке и Азии?

· Существует ли в Северной Америке озера, глубина которых меньше 300 метров (неглубокие), а также озера, глубина которых больше 800 метров (глубокие)?

· Какие озера расположены в Европе и на каких материках глубина озер находится в пределах от 400 до 1500 метров? [6]

2.                       Задачи на логические связи между объектами.

· Воронов, Павлов, Левицкий и Сахаров - 4 талантливых молодых человека. Один из них - танцор, другой - художник, третий - певец, а четвертый - писатель. О них известно следующее.

1) Воронов и Левицкий сидели в зале Консерватории в тот вечер, когда певец дебютировал в сольном концерте.

2) Павлов и писатель вместе позировали художнику.

3) Писатель написал биографическую повесть о Сахарове и собирается написать о Воронове.

4) Воронов никогда не слышал о Левицком.

Кто чем занимается?

· Имеются два сосуда - на 3 и на 5 литров. Как отмерить с их помощью 4 литра воды? [6]

3. Задачи на описание базы знаний предметной области с выводом новых отношений.

· Определить базу знаний "Транспорт" по данной схеме движения транспорта.

Определить:

 

 

Можно ли доехать из города В в город Е?

В какие города можно доехать из города D?

Из каких городов можно доехать до города Е?

4) Можно ли доехать из города А в город D или в город F? [6]

· Дана база знаний "Автобусы". На схеме показано, между какими населенными пунктами курсирует автобус.

 

 

 

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

· На каком виде транспорта можно доехать из пункта В в пункт Г?

· Можно ли доехать на автобусе из К в Л?

· В какие населенные пункты придется ехать на автомобиле из пункта Б? [6]

4.                       Задачи на построение транзитивных замыканий существующих отношений.

· Некоторая авиакомпания обеспечивает прямые рейсы между некоторыми городами, сведения о которых хранятся в программе в виде фактов (для упрощения задачи обратные рейсы исключены). Запрограммируйте рекурсивный предикат perelet, который определяет, можно ли попасть из одного города в другой (может быть, с пересадками) [3].

· В районе расположено несколько сел. Есть данные о наличии дорог между ними (в одну сторону) и их длине, которые хранятся в виде фактов предиката doroga.

Напишите предикат put, определяющий, можно ли попасть из одного села в другое, и какова суммарная протяженность дороги между ними [3].

5.                       Логические задачи на поиск решения.

· Напишите программу, которая решает следующую задачу: нарисовать конверт, не отрывая карандаша от бумаги и не проводя два раза по одной и той же линии. Результатом выполнения программы будет список пройденных вершин [14].

· Задача состоит в том, чтобы такую расстановку восьми ферзей на пустой шахматной доске, в которой ни один из ферзей не находится под боем другого [1].

6. Содержательные учебные задачи ИИ

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

К классическим задачам такого типа относится задача "Обезьяна и банан":

Возле двери комнаты стоит обезьяна. В середине этой комнаты к потолку подвешен банан. Обезьяна голодна и хочет съесть банан, однако она не может дотянуться до него, находясь на полу. Около окна этой же комнаты на полу лежит ящик, которым обезьяна может воспользоваться. Обезьяна может предпринимать следующие действия: ходить по полу, залезать на ящик, двигать ящик (если она уже возле него) и схватить банан, если она стоит на ящике прямо под бананом. Может ли обезьяна добраться до банана?

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

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