Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50
| Вид материала | Программа |
- Согласно со ст. 5 Федерального закона от 24. 11. 1996 №132-фэ «Об основах туристской, 125.21kb.
- Классификации по причине одинакового движения мысли, 71.59kb.
- Программа курса тема классификация стран. Типы стран мира количественные и качественные, 105.41kb.
- О порядке применения бюджетной классификации, 280.27kb.
- Изменились коды бюджетной классификации на обязательное медицинское страхование, 37.09kb.
- Виды налогов и сборов, кбк, нормативный документ, 411.79kb.
- Разъяснения по применению бюджетной классификации Российской Федерации в 2009г, 95.19kb.
- Вопросы к экзамену по дисциплине «Финансовое право», 24.76kb.
- А. А. Сковородко подходЫ к классификации инновационных, 186.55kb.
- Существуют различные классификации языков программирования, 174.02kb.
Программирование на языке Пролог и Задача поиска
Оглавление
Введение 3
1.Принципы логического программирования 4
1.2. Математическая основа языка Пролог 4
1.2. Организация вычислительного процесса 5
1.2.2. Использование переменных 6
1.2.1. Синтаксис фактов и правил 7
1.3. Бэктрекинг 8
2. Основные элементы языка 9
2.1. Имена 9
2.2. Типы данных 9
2.3. Константы и переменные 9
2.4. Программные секции Пролога 10
2.4.1. Секция Domains 10
2.4.2. Секция Predicates 11
2.4.3. Секция Database 11
2.4.4. Секция Clauses 11
2.4.5. Секция Goal 12
3. Язык Пролог в задачах и примерах 12
3.1. Программирование с помощью фактов и правил 12
3.1.2. Первая формулировка задачи поиска в пространстве состояний 51 ад 16
3.1.3. Реализация на Прологе простой вопросно-ответной системы 17
3.2. Рекурсии 18
Упражнения 20
3.3. Программирование циклических процессов 21
3.4. Работа со списками 23
3.4.1. Описание списков в программе 24
3.4.11. Примеры использования списков 29
Упражнения 30
3.5. Виды рекурсии 30
3.6. Поиск в пространстве состояний 31
Упражнения 35
3.6. Использование структур 36
Упражнения 45
3.7. Динамическая база данных 45
3.7.1. Использование стандартных предикатов динамической базы данных 45
Упражнения 47
3.8. Средства управления 47
3.9. Представление множеств двоичными деревьями 48
3.9. Программы классификации 49
3.9.1. Программа классификации с обратной цепочкой рассуждений 50
3.9.2. Программы классификации с прямой цепочкой рассуждений. 52
3.9. Обработка текстов 57
Упражнения 61
4. Стандартные предикаты 62
4.1. Ввод/вывод 62
4.2. Управление экраном и оконная система 63
4.3. Обработка строк 64
4.4. Преобразование типов 64
4.5. Работа с базой данных 65
4.6. Управляющие предикаты 65
4.7. Прочие стандартные предикаты 66
4.8. Арифметические и логические предикаты 66
Приложение 67
Приложение 1. Примерные варианты лабораторных заданий 67
Рекомендуемая литература 68
Введение
Язык программирования Пролог относится к числу важнейших языков, используемых в символьной обработке и в исследованиях по искусственному интеллекту. Он составляет основу для обучения методам искусственного интеллекта, исследованиям и практическому применению в этой области. Задачи ИИ существенно рекурсивны по природе.
К системам искусственного интеллекта относятся экспертные системы, программы доказательства теорем, интеллектуальные роботы, системы машинного перевода и др. Все эти задачи, делающие использование Пролога естественным, имеют свои особенности реализации:
1. Все они используют символьное представление информации и символьные вычисления в широком смысле, включая не только операции обработки цепочки символов, но и достаточно сложные структуры вроде графов. Такого рода работа обеспечивается следующими средствами Пролога:
- сопоставлением с образцом, позволяющим идентифицировать элементы структуры с определенными (синтаксическими) свойствами;
- рекурсией, позволяющей лаконично описывать операции на структурах в терминах операций на подструктурах;
- синтаксисом, позволяющим описывать структуры данных в удобной форме выражений.
2. Это задачи, в которых требуется некоторый вид поиска. Типичная ситуация, подходящая для применения Пролога, – это наличие некоторого набора условий, которым должен удовлетворять объект. Поиск этого объекта производится с помощью механизма бэктрекинга, встроенного в Пролог. Бэктрекинг реализует недетерминированный поиск. Одно из важных применений недетерминированного поиска – логический вывод.
Пролог идеально подходит для создания баз данных и баз знаний, а также экспертных систем, основанных на базах знаний.
Название “Пролог” есть сокращение для "ПРОграммирование в терминах ЛОГики". Пролог может быть использован в различных приложениях, относящихся к искусственному интеллекту:
– общение с ЭВМ на естественном языке;
– символьные вычисления;
– написание компиляторов;
– базы данных;
– экспертные системы и т.д.
Диалект Пролога язык PDC Prolog разработан фирмой Prolog Development Center (Копенгаген, Дания) и предназначен для программирования задач из области искусственного интеллекта. Достоинства реализации:
- является компиляторно-ориентированным языком программирования высокого уровня,
- имеет средства создавать автономно компилируемые файлы.
- Включает в состав интегрированную среду для разработки, отладки и выполнения программ.
Пролог относится к так называемым декларативным языкам, требующим от автора умения составить формальное описание ситуации. Поэтому программа на Прологе не является таковой в традиционном понимании, так как не содержит управляющих конструкций типа if … then, while … do; нет даже оператора присваивания. В Прологе задействованы другие механизмы. Задача описывается в терминах фактов и правил, а поиск решения Пролог берет на себя посредством встроенного механизма логического вывода.
Перечень возможных синтаксических конструкций Пролога невелик, и в этом смысле язык прост для изучения. С другой, декларативный стиль программирования оказывается столь непривычным и новым для матерых программистов, что вызывает шок и ряде случаев оказывается тормозом для привыкших выписывать подробно указания компьютеру, как делать.
Начать изучение языка Пролог можно с разных позиций. Мы будем исходить из того, что Пролог является одним из основных языков искусственного интеллекта, а поскольку ограниченный объем издания не позволяет всецело охватить различные аспекты этого языка, будем отдавать предпочтение тем примерам, которые так или иначе затрагивают основные проблемы, возникающие при решении задач искусственного интеллекта: представлению символьных структур данных и задаче поиска.
Основная задача программирования искусственного интеллекта – сформировать представление и управляющие структуры, необходимые для решения интеллектуальной задачи. Требования к этим структурам во многом определяют необходимые свойства языка реализации. Язык представления Пролог обеспечивает реализацию требований символьного уровня.
Существенное внимание уделено возможности начать практическую работу на Прологе. Подробно раскрывается механизм программирования работы со списками с использованием рекурсий, наиболее непривычный для привыкших к алгоритмическому стилю.
Существуют различные диалекты языка Пролог и множество версий. Здесь у нас используется версия PDC Prolog, близкая к исходной версии, разработанной Уорреном.
Замечания относительно нотации. Дело в том, что в Прологе идентификаторы (имена предикатов, переменных) несут на себе значительную смысловую нагрузку, гораздо большую, чем в традиционных языках программирования. Зачастую в литературе встречаются перевод имен предикатов на русский язык, что не соответствует синтаксису языка PDC Prolog. Поэтому, чтобы не нарушать синтаксис англоязычной версии языка, в ряде случаев мы перешли на латиницу, особенно в тех случаях, когда английский эквивалент названия представляет собой малознакомое слово.
Но что все-таки самое главное – программировать на Прологе ново, непривычно и интересно!