Установочная лекция по дисциплине Старший преподаватель каф. ВТ Юлия Вадимовна Новицкая

Логическое программирование язык программирования Prolog (Programming in logic) Функциональное программирование язык программирования Lisp (List processing)

В зимнюю сессию установочная лекция – 2 часа В течение семестра Контрольная работа, состоящая из трех частей (Prolog) В летнюю сессию Лекции – 6 часов Два практических занятия (Prolog) – 4 часа Одно практическое занятие (Lisp) – 2 часа Экзамен Два теоретических вопроса Одна практическая задача

Состав комплекта (архив 1,44 Mб) Рабочая программа (описание дисциплины, часы, экзаменационные вопросы, примеры экзаменационных задач, список литературы, описание балльно-рейтинговой системы) Задания для контрольной работы Задания для практических занятий Дистрибутив Prologа Дистрибутив Lispа Учебное пособие

Языки программирования Алгоритмические (процедурные) языки (Fortran, Pascal, C, …) Декларативные (неалгоритмические) языки Языки логического программирования (Prolog, …) Языки функционального программирования (Lisp, …)

Области применения декларативных языков Создание систем искусственного интеллекта Разработка экспертных систем и оболочек экспертных систем Создание систем помощи принятия решений Разработка систем обработки естественного языка Построение планов действий роботов …

Visual Prolog 7.2 Разработкой языка занимается фирма PDC Prolog Development Center Версии Prologа Turbo Prolog PDC Prolog Visual Prolog

Различные диалекты Lispа

Особенности языка Описание проблемы и правил ее решения Нахождение всех возможных решений с помощью механизма поиска с возвратом (backtracking) Простой синтаксис

Факты Воробей – это птица. Воробей – родитель птенца. Правило вывода Некто является птицей при условии, что у него есть родитель – птица. Программа птица (воробей). птица (X):–родитель (Y, X), птица (Y). родитель (воробей, птенец). Запрос птица (Z) Все возможные решения: Z = воробей Z = птенец

PREDICATES bird (symbol) parent (symbol, symbol) CLAUSES bird («воробей»). bird (X):– parent (Y, X), bird (Y). parent («воробей», «птенец»). Goal: bird (Z) Z = «воробей» Z = «птенец» Факт Правило вывода Внешняя цель

PREDICATES bird (symbol) parent (symbol, symbol) CLAUSES bird (sparrow). bird (X) :- parent (Y, X), bird (Y). parent (sparrow, nestling). Goal: bird (Z) Z = sparrow Z = nestling

Поиск с возвратом (backtracking) Рекурсия Вход

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

PREDICATES tens (string) ones (string) start CLAUSES tens («Двадцать»). tens («Тридцать»). ones («два»). ones («три»). start :- tens (X), ones (Y), write (X, « », Y), nl, fail. GOAL start. РЕШЕНИЕ Двадцать два Двадцать три Тридцать два Тридцать три

Нахождение значения факториала n! = 1 * 2 * 3 * … * (n – 1) * n 0! = 1 Рекурсивная формула для расчета факториала n! = (n – 1)! * n

PREDICATES factorial (integer, real) CLAUSES factorial (0, 1). factorial (N, FactN) :- M = N – 1, factorial (M, FactM), FactN = FactM*N. GOAL factorial (3, FactN), write («FactN=», FactN).

Списки [1, 2, 3] Деревья (бинарные, упорядоченные)

Особенности языка Одинаковая форма представления данных и программ – в виде списка Функциональный образ мышления Не требуется явное описание типов данных, используемых в программе Основной способ решения - рекурсия

> (+ 2 3) программа данные > (+ 2 3) 5 > (+ 2 3) (+ 2 3) > (quote (+ 2 3)) (+ 2 3)

(2 a 5 str ) Голова списка – первый элемент списка 2 Хвост списка – все оставшиеся элементы списка, в свою очередь являющиеся самостоятельным списком (a 5 str ) Пустой список – ( ) или nil

> (car (1 2 3);получение головы списка 1 > (cdr (1 2 3));получение хвоста списка (2 3) > (cons 1 (2 3));создание списка (1 2 3) > (atom (1 2 3));проверка на атом NIL > (equal (1 2 3) (1 2 3));проверка равенства T

>(defun factorial (n) (cond ((= n 0) 1) (t (* (factorial (– n 1)) n)) ) ) FACTORIAL >(factorial 3) 6