Логическое программирование

Министерство образования Российской Федерации Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”

РАБОЧАЯ ПРОГРАММА дисциплины ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Для подготовки дипломированных специалистов по направлению 654600 – “Информатика и вычислительная техника” по специальности 220400 -“Программное обеспечение вычислительной техники и автоматизированных систем”

Санкт-Петербург 2001

Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”

“УТВЕРЖДАЮ” Проректор по учебной работе проф. ___________ Ушаков В.Н. “_____”_______________2001 г.

РАБОЧАЯ ПРОГРАММА дисциплины ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Для подготовки дипломированных специалистов по направлению 654600 – “Информатика и вычислительная техника” по специальности 220400 -“Программное обеспечение вычислительной техники и автоматизированных систем”. Факультет компьютерных технологий и информатики Кафедра математического обеспечения и применения ЭВМ Курс – 3 Семестр – 6 Лекции

30 ч.

Экзамен

Лабораторные занятия

Текущий контроль

Курсовая работа

15 ч.

Аудиторные занятия Самостоятельные занятия Всего часов

45 ч. 43 ч. 88 ч.

2001

2

6 семестр

Рабочая программа обсуждена на заседании кафедры Математического обеспечения и применения ЭВМ “____”_______________2001 г., протокол №______. Рабочая программа составлена в соответствии с государственным образовательным стандартом по направлению 654600 –“Информатика и вычислительная техника” и специальности 220400 -“Программное обеспечение вычислительной техники и автоматизированных систем”. Рабочая программа согласована с рабочими программами изученных ранее дисциплин: 1) Программирование; 2) Структуры и алгоритмы обработки данных; Рабочая программа одобрена методической комиссией факультета компьютерных технологий и информатики “____”_____________2001 г.

3

Цели и задачи дисциплины 1. Целью дисциплины является изучение и практическое освоение средств логического программирования для решения научных и прикладных задач. В качестве инструментальных средств изучается язык ПРОЛОГ. 2. Рассматриваются теоретические и прикладные аспекты использования данных программных средств для решения задач искусственного интеллекта. Требования к уровню освоения дисциплины В результате изучения дисциплины студенты должны: 1. Знать и уметь использовать теоретические основы и прикладные средства логического программирования в решении задач искусственного интеллекта; 2. Иметь опыт использования языка ПРОЛОГ при решении практических задач; 3. Иметь представление о тенденциях и перспективах развития инструментальных средств логического программирования. Содержание рабочей программы Введение в проблематику логического программирования. Применение логического программирования в системах искусственного интеллекта: Задачи искусственного интеллекта. Современные парадигмы решения задач искусственного интеллекта. Роль логики в решении задач ИИ. Логика предикатов первого порядка. Клаузы Хорна. Соотношение между клаузальной и стандартной формой логики. Доказательство теорем в исчислении предикатов первого порядка. Алгоритм унификации и принцип резолюции Робинсона. Использование логики как языка программирования. Тема 1. Основные понятия логического программирования Основные понятия логического программирования: понятие логической программы. Основные конструкции. Факты, правила, вопросы. Логические переменные, подстановки и примеры. Абстрактный интерпретатор. Значение логической программы. Вычислительная модель логических программ. Концепция языков "нового принципа". Ретроспективный обзор создания средств логического программирования. ПРОЛОГ как система, реализующая логический вывод в исчислении предикатов первого порядка Тема 2. Основные элементы языка Основные элементы языка: алфавит языка. Термы. Виды термов: константы, переменные, структуры. Литеры и их типы. Интерпретация литер. Операторы. Свойства операторов (позиция, приоритет, ассоциативность). Инфиксные, префиксные, постфиксные операторы. Запись фактов и правил. Предикат. Цели, конъюнкция целей. Общая схема доказательства целевого утверждения Тема 3. Арифметика Встроенные предикаты для сравнения чисел: =, \=, >, <, >=, =<. Вычисление арифметических выражений: операторы +, -, *, /, ^. Предикат is. Примеры программ с выполнением арифметических операций. 4

Тема 4. Согласование целевых утверждений Диаграмма успешного доказательства целевых утверждений. Доказательство целевых утверждений при использовании механизма возврата. Правила установления соответствия. Недетерминизм первого и второго рода. Понятие "связанной" переменной. Примеры программ с использованием механизма возврата. Операционная модель вычисления ПРОЛОГ-программ. ПРОЛОГ и математическая логика. Тема 5. Рекурсивное представление данных и программ Построение рекурсивных программ. Граничные условия и способы использования рекурсии. Структуры и деревья. Список как частный вид структуры. Формы записи списков. Работа со списками. Примеры программ с рекурсивными определениями. Тема 6. Отсечение и способы его использования Модели Причины использования отсечения. Предикат !. Диаграмма работы программы с использованием отсечения. Общие случаи использования отсечения. Тема 7. Ввод и вывод Ввод и вывод термов (предикаты read, write, display). Ввод и вывод литер (предикаты get, get0, put). Примеры программ с использованием ввода и вывода. Тема 8. Встроенные предикаты Предикаты: добавление и исключение утверждений, классификация термов, изменение и анализ утверждений, работа со структурами произвольного вида, воздействие на процесс возврата, реализация сложных способов выражения целевых утверждений, объявление операторов, обработка файлов, наблюдение за выполнением программы на ПРОЛОГе. Примеры использования встроенных предикатов. Тема 9. Дополнительные возможности Программирование второго порядка. Множественные выражения. Предикаты "univ", findall, bagof, setof. Интерфейсные и графические возможности версий ПРОЛОГа. Тема 10. Отладка ПРОЛОГ-программы Рекомендации по расположению текста программ. Типичные ошибки при работе с ПРОЛОГом. Использование трассировки и контрольных точек в ПРОЛОГ-системе. Фиксация ошибок. Тема 11. Примеры использования ПРОЛОГа для решения задач искусственного интеллекта Реализация на ПРОЛОГе простейшей экспертной системы. Использование языка ПРОЛОГ п ри планировании действий. Реализация на ПРОЛОГе нечеткого логического вывода. Тема 12. Метапрограммирование на языке Пролог Метапрограммирование на языке Пролог – программирование языка Пролог на языке Пролог. Особенности реализации дополнительных функций. Возможности управления ходом доказательства. Не линейный выбор правил при доказательстве. Тема 13. Вероятностные интерпретаторы Вероятностные интерпретаторы – наличие или отсутствие правила в программе задается вероятностью. Особенности доказательства в условиях неопределенности.

5

Тема 14. Разработка игровых программ, оптимизационные задачи Разработка игровых программ, оптимизационные задачи – особенности разработки некоторых игровых программ. Оптимизация и алгоритмы на языке Пролог. Тема 15. Экспертные системы и базы знаний в Прологе Экспертные системы и базы знаний в Прологе – программа на языке Пролог рассматривается как база знаний, особенности манипуляции знаниями в Прологе. Тема 16. Планирование, решение NP-трудных задач Планирование, решение NP-трудных задач на Прологе – реализация программ планирования. Решение задачи коммивояжера, о раскрашивании графа и других. Тема 17. Constraint-технология в логическом программировании Constraint-технология в логическом программировании: обобщение механизма унификации, понятие constraint'а. Операционная модель Constraint-ПРОЛОГа. Инструментальные средства Constraint-ПРОЛОГа; Применение Constraint-ПРОЛОГА в задачах исследования операций. Заключение Тенденции и перспективы развития методов и средств логического программирования. Параллелизм в ПРОЛОГЕ. Логическое программирование как перспективная методология разработки интеллектуальных систем. Цели и содержание курсовой работы и его ориентировочная трудоемкость Цель: получение умений и навыков по применению методов проектирования и разработки программ на языке программирования Пролог. Содержание: решение задачи с использованием логического программирования, реализация в виде программы на языке Пролог и трассировка. Ориентировочная трудоемкость: 15 ч.

6

Распределение учебных часов по темам и видам занятий № темы

1 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 2.16 2.17 2.18

Объем учебных часов Название разделов и тем

Лекции

Введение в проблематику логического программирования Основные понятия логического программирования Основные элементы языка Арифметика Согласование целевых утверждений Рекурсивное представление данных в программе Отсечение и способы его использования Ввод и вывод Встроенные предикаты Дополнительные возможности Отладка ПРОЛОГ-программ Примеры использования ПРОЛОГа для решения задач искусственного интеллекта Метапрограммирование на языке Пролог Вероятностные интерпретаторы Разработка игровых программ, оптимизационные задачи Экспертные системы и базы знаний в Прологе Планирование, решение NPтрудных задач на Прологе Constraint-технология в логическом программировании. Заключение Курсовое проектирование ИТОГО:

1

Лабор. занятия

Практ. занятия

Аудит. занятия

Самост. работа

1

1

Всего

Семестр

6 2

2 2 2 1

2 2 2 1

4 3 3 1

6 6 5 5

6 6 6

2 1

1

1

6 2

1 1 1 2 2 2

1 1 1 2 2 2

3 2 1 2 2 2

6 4 3 2 4 4

6 6 6 6 6

4 2

2

3

1 3

1 3

2 3

2

2

3

1

1

3

2

2

3

6 5 3

6 6

6 6 5 6 4 1 30

7

1 15 45

6

1

5 2

43

88

6

ЛИТЕРАТУРА Основная №

Название, библиографическое описание

1

Лорьер Ж.-Л. Системы искусственного интеллекта. М.: Мир, 1991. Л.Стерлинг, Э.Шапиро. Искусство программирования на языке ПРОЛОГ. М. Мир, 1990. И.Братко. Программирование на языке ПРОЛОГ для искусственного интеллекта. М.Мир,1990 Хювенен Э., Сеппянен И. Мир ЛИСПа. В 2 т. - М.: Мир, 1990 Филд А., Харрисон П. Функциональное программирование. - М.: Мир, 1993 Хендерсон П. Функциональное программирование. Применение и реализация. - М.: Мир, 1983

2 3 4 5 6

Л

Пр зан

К-во экз. в библ. (на каф.)

Гриф

5

Уч 34

ГК СССР по нар.обр.

5

Уч 154

ГК СССР по нар.обр.

5

Уч 4

ГК СССР по нар.обр.

5

5

Т1-54 Т2-58

ГК СССР по нар.обр.

5

5

Уч 8

5

Уч 29

Ком. по ВШ Мин. науки МВ и ССО СССР

Дополнительная №

Название, библиографическое описание

1 2

Уинстон П. Искусственный интеллект. М.,Мир, 1990. Бердж В. Методы рекурсивного программирования. М., Машиностроение, 1983 J.Cohen. Constraint Logic Programming Languages. Communication of the ACM, 1990, Vol.33, No.7 J.Jaffar, S.Michaylov, P.J.Stuckey, R.H.C.Yap. The CLP(R) Language and System. ACM Transactions on Programming Languages and Systems, Vol.14, No.3, July 1992 Тей А. и др. Логический подход к искусственному интеллекту: от классической логики к логическому программированию. - М.: Мир, 1990. Ковальский Р. Логика в решении проблем. - М.: Наука, 1990. Нильсон Н. Принципы искусственного интеллекта. /Пер. с англ. Р.М. Абдусаматова, Ю.И. Крюкова; Под. ред. Стефанюка В.Л. - М.: Радио и связь, 1985. Абилов В.Г., Зинченко Н.И. Turbo и Arity: два подхода к логическому программированию. //Мир ПК No.2,3, 1990. Язык Пролог в пятом поколении ЭВМ. - М.: Мир, 1988.

3 4 5 6 7 8 9

8

К-во экз. в библ. (на каф.)

Уч 0 Уч 0 Уч 0 Уч 0 Уч 0 Уч 0 Уч 9 Уч 0 Уч 0

Авторы: ассистент

Беляев С.А.

Рецензент

Казак А.Ф.

к.т.н., доцент Зав. кафедрой математического обеспечения и применения ЭВМ д.т.н., профессор

Лисс А.Р.

Декан факультета КТИ д.т.н., профессор

Герасимов И.В.

Зав. отделом учебной литературы

Смирнова О.Н.

Программа согласована: Председатель методической комиссии факультета КТИ к.т.н., доцент

Михалков В.А.

Руководитель методического отдела к.т.н., доцент

Марасина Л.А.

9

Авторы: ассистент

Беляев С.А.

Рецензент

Казак А.Ф.

к.т.н., доцент Зав. кафедрой математического обеспечения и применения ЭВМ д.т.н., профессор

Лисс А.Р.

Декан факультета КТИ д.т.н., профессор

Герасимов И.В.

Программа согласована: Зав. отделом учебной литературы

Смирнова О.Н.

Председатель методической комиссии факультета КТИ

Михалков В.А.

к.т.н., доцент Руководитель методического отдела к.т.н., доцент

Марасина Л.А.

10