Масленникова О.Е., Попова И.В. Основы искусственного интеллекта
Подождите немного. Документ загружается.
- 191 -
Фрагмент программы будет следующим:
str_list("",[]). /* пустой строке соответствует пустой список */
str_list(S,[H|T]):–
frontchar(S,H,S1), /* H — первый символ строки S, S1
– остаток строки */
str_list(S1,T). /* T — список, состоящий из символов, входящих
в строку S1*/
Предикаты преобразования типов
Ниже представлены наиболее часто используемые предикаты
преобразования типов.
Предикат char_int
Преобразует символ в целое число или целое в символ.
Формат:
char_int(Char, Integer) % (i,o), (o,i), (i,i)
Если оба аргумента связаны, то char_int проверяет, соответствуют ли
значения аргументов. Если один аргумент связан, а другой свободен, char_int
выполняет преобразование и связывает выходной параметр с
преобразованной формой входного параметра.
Замечание. Предикат char_int оставлен для совместимости со старыми
версиями.
Предикат str_char
Предикат str_char преобразует строку, содержащую один и только один
символ, в символ или символ в строку из одного символа.
Формат:
str_char(String, Char) % (i,o), (o,i), (i,i)
(i,i) – успех, если String связан со строкой из одного символа - char.
Если длина строки — не единица, то str_char завершается неуспешно.
Предикат str_int
Преобразует строку, содержащую целое число, в его представление
Формат:
Str_int(String, Integer) % (i,o), (o,i), (i,i)
В случае если поток параметров— (i,i), то str_int завершается успешно
при условии, что integer связан с целым эквивалентом числа,
представленного с помощью string.
Предикат str_real
преобразует строку в вещественное число или вещественное число в
строку.
Формат:
str_real(String, Real) % (i,o), (o,i), (i,i)
- 192 -
(i,i) – успех, если Real связан с вещественным числом, равным числу,
представленному в string.
Предикат upper_lower
Преобразует строку, все символы (или часть символов) которые
являются символами верхнего регистра, в строку соответствующих символов
нижнего регистра, и наоборот.
Формат:
Upper_lower (Upper, Lower) % (i,o), (o,i), (i,i)
Если оба параметра связаны, то upper_lower завершается успешно, если
Upper и Lower связаны со строками, которые являются конвертируемыми
друг в друга.
Предикат term_str
Предикат term_str является универсальным предикатом для
преобразований, он cовершает преобразование терма заданного домена в его
строковое представление.
Формат:
term_str (Domain, Term, String) % (i, i,o) , (i,_, i)
Domain задает, какому домену принадлежит терм. Тerm_str может
заменить все представленные выше предикаты str_*, например, str_real может
быть реализован как str_real(s,R) :- term_str(real,r,s). Однако term_str имеет
более сложную реализацию.
Динамические базы данных
Для модификации фактов в процессе работы программы используется
динамическая или внутренняя база данных. Для работы с базой данных
применяется секция DATABASE.
Пример
DOMAINS
name, capital=string
population=integer
DATABASE
country (name, capital)
PREDICATES
town (name, population)
CLAUSES
country (―Japan‖, ―Tokio‖).
country (―France‖, ―Paris‖).
country (―Germany‖, ―Berlin‖).
town (―Tokio‖, 17).
town (―Paris‖, 12).
town (―Berlin‖, 11).
- 193 -
В процессе выполнения программы факты, описанные с помощью
предикатов в секции DATABASE, можно добавлять в базу данных, удалять
из базы данных, сохранять факты базы данных в файле, загружать факты из
файла в базу данных.
В базе данных могут содержаться только факты, а не правила вывода,
факты базы данных не могут содержать свободных переменных.
Существует три основных способа помещения фактов в базу данных:
− включение фактов в секцию CLAUSES;
− во время выполнения программы с помощью предикатов assert,
asserta, assertz;
− загрузка из файла с помощью предиката consult.
Пролог поддерживает различные стандартные предикаты для работы с
базами данных.
asserta
Назначение: включает факт в начало базы данных.
Обращение: asserta(Fact, DDBName) Fact – добавляемый факт,
DDBName – имя динамической базы данных (необязательно).
Домены: (DDBdomain, string)
Шаблоны аргументов: (i,i)
assert или assertz
Назначение: включает факт в конец базы данных.
Обращение: assert(Fact, DDBName) Fact – добавляемый факт, DDBName
– имя динамической базы данных (необязательно).
Домены: (DDBdomain, string)
Шаблоны аргументов: (i,i)
retract
Назначение: удаляет факт из базы данных.
Обращение: retract(Fact, DDBName) Fact – удаляемый факт,
DDBName – имя динамической базы данных (необязательно).
Домены: (DDBdomain, string)
Шаблоны аргументов: (*,i)
retractall
Назначение: удаляет все сравниваемые факты из базы данных.
Обращение: retractall(Fact, DDBName) Fact – удаляемый факт,
DDBName – имя динамической базы данных (необязательно).
Домены: (DDBdomain, string)
Шаблоны аргументов: (*,i)
save
Назначение: сохраняет факты из базы данных в файле.
- 194 -
Обращение: save(FileName, DDBName) FileName– имя файла,
DDBName – имя динамической базы данных (необязательно).
Домены: (string, string)
Шаблоны аргументов: (i,i)
consult
Назначение: загружает факты из файла в базу данных.
Обращение: consult(FileName, DDBName) FileName– имя файла,
DDBName – имя динамической базы данных (необязательно).
Домены: (string, string)
Шаблоны аргументов: (i,i)
Пример
В файле in.txt хранятся следующие факты:
number (1).
number (2).
number (3).
DATABASE
number (integer)
PREDICATES
start
CLAUSES
start:- consult (―in.txt‖), asserta (number(0)), retract (number (3)), save
(―out.txt‖).
GOAL
start.
В результате работы программы будет создан файл out.txt,
содержащий следующие факты:
number (0).
number (1).
number (2).
Упражнения
1. Разработайте факты для описания предметной области.
а) Библиотека, где хранится информация о книгах: автор, название.
Количество страниц.
б) Агентство по продаже автомобилей, имеющее сведения о марке
автомобиля, его цене и цвете.
в) Прокат дисков с ПО, располагающий информацией о программном
обеспечении, имеющимся в наличии: название ПО, тип ПО, цена
лицензионной версии, фирма производитель ПО.
2. Разработайте для каждой группы фактов правило (а), позволяющее
(ие) реализовать представленную ниже цель.
- 195 -
а) Вывести названия романов, которые можно считать большими
(больше 300 страниц).
б) Необходимо купить яркий автомобиль по цене не выше 25000.
в) Подобрать программное обеспечение определѐнного типа и
фирмы производителя без относительно его цены.
3. Постройте 3-4 запроса к базе данных заданной предметной области.
Музыка
predicates
songster (symbol, symbol)
clauses
songster ("sadness", "enigma").
songster ("mea culpa", "enigma").
songster ("principles of lust", "enigma").
songster ("white dove", "scorpions").
songster ("still loving you", "scorpions").
songster ("nothing else matters",
"metallica").
География
predicates
city (symbol, symbol).
clauses
city (" Ryazan "," Russia").
city (" Moscow"," Russia").
city ("Vologda "," Russia ").
city (" New York "," USA").
city (" Chicago "," USA").
city (" London ", " Great
Britain ").
Жанры кино
predicates
movie(symboi, symbol).
clauses
movie ("man in black", "comedy").
movie ("man in black - 2", "comedy").
movie ("King Kong", "Adventure").
movie ("Indiana Jones", "Adventure").
movie ("The Lion King", "Cartoon").
movie ("Ice Age", "Cartoon").
Цвета
predicates
color (symbol, symbol).
clauses
color ("Corn", "Yellow").
color ("Banana", "Yellow").
color ("Cheese", "Yellow").
color ("Apple", "Red").
color ("Raspberry", "Red").
color ("Kiwi", "Green").
4. Разработайте справочную систему для указанной предметной области
а) Написать программу, реализующую телефонный справочник. В
справочнике содержится следующая информация о каждом абоненте:
имя и телефон. Реализовать вывод всей информации из справочника,
поиск телефона по имени, поиск имени по телефону. Для удобства
работы реализовать меню с соответствующими пунктами.
б) Написать программу, реализующую географический справочник.
В справочнике содержится следующая информация: названия страны и
площади страны, названия рек и длины рек, названия озер и глубины
озер. Реализовать вывод всей информации из справочника, поиск по
названию. Реализовать поиск по площади, длине или глубине, при этом
должна быть возможность ввести некоторое пороговое значение
(например, вывести названия всех рек, длина которых не менее 3000
км). Для удобства работы реализовать меню с соответствующими
пунктами.
- 196 -
в) Написать программу, реализующую калькулятор на четыре
арифметических действия (без скобок).
г) Написать программу, реализующую словарь. В словаре
содержится следующая информация: слово и его несколько переводов.
Реализовать вывод всего словаря, перевод с русского на английский, с
английского на русский. Для удобства работы реализовать меню с
соответствующими пунктами.
д) Написать программу, реализующую авиасправочник. В
справочнике содержится следующая информация о каждом рейсе:
номер рейса, пункт назначения, цена билета. Реализовать вывод всей
информации из справочника, поиск пункта назначения по номеру
рейса. Реализовать поиск по пункту назначения с указанием
максимально возможной цены билета (должны быть выведены все
рейсы, цена билета на которые ниже указанного значения) Для
удобства работы реализовать меню с соответствующими пунктами.
5. Напишите алгоритм решения следующей задачи.
а) Подсчитать, сколько раз встречается некоторая буква в строке.
Строка и буква должны вводиться с клавиатуры. Для разделения
строки на символы использовать стандартный предикат
frontchar (String, Char, StringRest), позволяющий разделять строку String
на первый символ Char и остаток строки StringRest.
б) Вычислить значение n-го члена ряда Фибоначчи: f(0)=0, f(1)=1,
f(n)=f(n-1)+f(n-2).
в) Вычислить произведение двух целых положительных чисел
(используя суммирование).
г) Подсчитать, сколько раз встречается некоторое слово в строке.
Строка и слово должны вводиться с клавиатуры. Для разделения
строки на слова использовать стандартный предикат fronttoken (String,
Lexeme, StringRest), позволяющий разделить строку String на первое
слово Lexeme и остаток строки StringRest.
д) Вычислить сумму ряда целых нечетных чисел от 1 до n.
6. Выполните следующие задания.
а) Написать программу для реверса списка. Например: список [1, 2, 3]
преобразуется в список [3, 2, 1].
б) Написать программу для получения значения n-го элемента списка.
Например: в списке [one, two, three] второй элемент равен two.
в) Написать программу для удаления из списка всех элементов,
равных 0. Например: список [1, 0, 2, 0, 0, 3] преобразуется в список [1,
2, 3].
г) Написать программу для циклического сдвига списка вправо на
заданное число элементов. Например: список [6, 5, 4, 3, 2, 1],
- 197 -
циклически сдвинутый вправо на 2 элемента, преобразуется в список
[2, 1, 6, 5, 4, 3].
д) Написать программу для удаления из списка 2-ого, 4-ого и т.д.
элементов. Например: список [6, 5, 4, 3, 2, 1] преобразуется в список [6,
4, 2].
е) Написать программу для нахождения среднего арифметического
листьевых вершин бинарного дерева.
ж) Написать программу для проверки упорядоченности бинарного
дерева.
з) Вывести бинарное дерево на экран в виде дерева.
и) Написать программу для вычисления глубины бинарного дерева
(глубина пустого дерева равна 0, глубина одноузлового дерева равна 1).
к) Написать программу для подсчета количества вершин бинарного
дерева, значения которых лежат в определенном диапазоне.
7. Выполните следующие задания
а) Создать базу данных. База содержит факты вида number(integer).
Переместить факты с отрицательными числами в другую базу данных
(исходная и полученная базы данных находятся в файле).
б) Создать базу данных. База содержит факты произвольного вида.
Удалить все дублирующиеся факты с выводом соответствующих
сообщений (исходная и полученная базы данных находятся в файле).
в) Создать базу данных. База содержит факты произвольного вида.
Переместить часть фактов в другую базу данных. Перемещение
выполняется при ответе на запрос пользователя (исходная и
полученная базы данных находятся в файле).
г) Создать базу данных. База содержит факты вида count(name, sum).
Написать программу, позволяющую изменять значение суммы для
указанного имени. Предусмотреть сообщение об отсутствии
запрошенного имени в базе данных (исходная и полученная базы
данных находятся в файле).
д) Создать базу данных. База содержит факты произвольного вида.
Написать программу, организующую просмотр всех фактов и
позволяющую добавлять новые факты с проверкой дублирования и
удалять существующие с сообщением об отсутствии (исходная и
полученная базы данных находятся в файле).
Литература
1. Адаменко, А. Логическое программирование и Visual Prolog /
А.Адаменко. – СПб.: БХВ – Петербург, 2003. – 992 с.
2. Братко, И. Программирование на языке Пролог для искусственного
интеллекта / И Братко. – М. : Мир,1990. - 560 с.
3. Основы искусственного интеллекта / Б.В. Костров, В.Н. Ручкин,
В.А. Фулин. – М.: «ДЕСС», «ТехБук», 2007. – 192 с.
- 198 -
4. Шрайнер, П.А. Основы программирования на языке Пролог /
П.А. Шрайнер. – Режим доступа: http://www.intuit.ru/department/pl/plprolog/
5. Visual Prolog. Tutorials. – Режим доступа: http://wiki.visual-
prolog.com/index.php?title=Category:Tutorials
- 199 -
ГЛАВА 5. ПРЕДСТАВЛЕНИЕ О ФУНКЦИОНАЛЬНОМ
ПРОГРАММИРОВАНИИ
Функциональное программирование – метод программирования,
основанный на разбиении алгоритма на отдельные функциональные модули
и описания их связей и взаимодействия; метод построения программы как
последовательности вложенных друг в друга вызовов функций.
Рис. 75. Методы программирования систем искусственного интеллекта
Функциональное программирование называется так, потому что
программа полностью состоит из функций. Сама программа тоже является
функцией, которая получает исходные данные в качестве аргумента, а
выходные данные выдаѐт как результат. Как правило, основная функция
определена в терминах других функций, которые в свою очередь определены
в терминах еще большего количества функций, вплоть до функций -
примитивов языка на самом нижнем уровне, похожих на обычные
математические функции.
Краеугольным камнем в парадигме функционального
программирования является функция. Отталкиваясь от истории математики,
можно сделать вывод, что понятию «функция» уже около четырѐхсот лет. На
текущий момент разработано бесчисленное множество теоретических и
практических аппаратов для оперирования функциями, начиная от
обыкновенных операций дифференцирования и интегрирования, заканчивая
заумными функциональными анализами, теориями нечѐтких множеств и
функций комплексных переменных.
Математические функции выражают связь между параметрами
(входом) и результатом (выходом) некоторого процесса. Так как вычисление
- это тоже процесс, имеющий вход и выход, функция является вполне
подходящим и адекватным средством описания вычислений. Именно этот
простой принцип положен в основу функциональной парадигмы и
- 200 -
функционального стиля программирования. Функциональная программа
представляет собой набор определений функций. Функции определяются
через другие функции или рекурсивно — через самих себя. В процессе
выполнения программы функции получают параметры, вычисляют и
возвращают результат, в случае необходимости вычисляя значения других
функций. Программируя на функциональном языке, программист не должен
описывать порядок вычислений. Ему необходимо просто описать желаемый
результат в виде системы функций.
5.1. История функционального программирования
Теоретические основы императивного программирования были
заложены в 30-х годах XX века Аланом Тьюрингом и Джоном фон
Нейманом. Теория, положенная в основу функционального подхода,
родилась в 20-х — 30-х годах. В числе разработчиков математических основ
функционального программирования можно назвать Мозеса Шѐнфинкеля
(Германия и Россия) и Хаскелла Карри (Англия), разработавших
комбинаторную логику, а также Алонзо Чѐрча (США), создателя -
исчисления.
Теория оставалась таковой до начала 50-х г. прошлого века, когда
Джон МакКарти разработал язык Lisp, который стал первым почти
функциональным языком программирования. Хотя Lisp всѐ ещѐ
используется, он уже не удовлетворяет некоторым современным запросам.
В конце 70-х — начале 80-х годов XX века интенсивно
разрабатываются модели типизации, подходящие для функциональных
языков. Большинство этих моделей включали в себя поддержку таких
мощных механизмов, как абстракция данных и полиморфизм. Появляется
множество типизированных функциональных языков и их диалектов: ML,
Scheme, Hope, Miranda, Clean и мн. др.
В результате получилось, что практически каждая группа,
занимающаяся функциональным программированием, использовала
собственный язык. Это препятствовало дальнейшему распространению этих
языков и порождало многочисленные более мелкие проблемы. Чтобы
исправить ситуацию, объединенная группа ведущих исследователей в
области функционального программирования решила воссоздать
достоинства различных языков в новом универсальном функциональном
языке. Первая реализация этого языка, названного Haskell в честь Хаскелла
Карри, была создана в начале 90-х годов. В настоящее время действителен
стандарт Haskell-98.
В первую очередь большинство функциональных языков
программирования реализуются как интерпретаторы, следуя традициям
Lisp'а, хотя существуют и компиляторы, генерирующие неплохой машинный
код (например, Objective Caml) или код на C/C++ (например, Glasgow Haskell