close

Вход

Забыли?

вход по аккаунту

?

Презентация

код для вставкиСкачать
Старший преподаватель каф. ВТ
Юлия Вадимовна Новицкая
email: novitskaya@vt.cs.nstu.ru
Установочная лекция по дисциплине
«ФУНКЦИОНАЛЬНОЕ И ЛОГИЧЕСКОЕ
ПРОГРАММИРОВАНИЕ»
ПРЕДМЕТ ИЗУЧЕНИЯ
Логическое программирование
язык программирования Prolog
(Programming in logic)
Функциональное программирование
язык программирования Lisp
(List processing)
СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
В зимнюю сессию
В течение семестра
установочная лекция – 2 часа
Контрольная работа, состоящая из трех частей (Prolog)
В летнюю сессию
Лекции – 6 часов
Два практических занятия (Prolog) – 4 часа
Одно практическое занятие (Lisp) – 2 часа
Экзамен
Два теоретических вопроса
Одна практическая задача
МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ
http://ermak.cs.nstu.ru/flp
ПОЛНЫЙ КОМПЛЕКТ МАТЕРИАЛОВ
Состав комплекта (архив 1,44 Mб)
Рабочая программа
(описание дисциплины, часы, экзаменационные
вопросы, примеры экзаменационных задач, список
литературы, описание балльно-рейтинговой системы)
Задания для контрольной работы
Задания для практических занятий
Дистрибутив Prolog’а
Дистрибутив Lisp’а
Учебное пособие
КЛАССИФИКАЦИЯ
Языки
программирования
Алгоритмические
(процедурные) языки
(Fortran, Pascal,
C, …)
Декларативные
(неалгоритмические)
языки
Языки
логического
программирования
(Prolog, …)
Языки
функционального
программирования
(Lisp, …)
ОБЛАСТИ ПРИМЕНЕНИЯ
Области применения декларативных языков
Создание систем искусственного интеллекта
Разработка экспертных систем и оболочек
экспертных систем
Создание систем помощи принятия решений
Разработка систем обработки естественного языка
Построение планов действий роботов
…
СОВРЕМЕННОЕ СОСТОЯНИЕ
Visual Prolog 7.2
Разработкой языка занимается фирма PDC
Prolog Development Center
http://www.pdc.dk
Версии Prolog’а
Turbo
Prolog
PDC Prolog
Visual Prolog
СОВРЕМЕННОЕ СОСТОЯНИЕ
http://www.lisp.org
Различные диалекты Lisp’а
ЯЗЫК ПРОГРАММИРОВАНИЯ PROLOG
Особенности языка
Описание
проблемы и правил ее решения
Нахождение всех возможных решений с
помощью механизма поиска с возвратом
(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).
ДЕРЕВО ЦЕЛЕЙ
factorial (N, Factorial_N)
factorial (3, Factorial_N)
factorial (3, 6)
M=N–1
M=3–1
2=3–1
factorial (M, Factorial_M)
factorial (2, Factorial_M)
factorial (2, 2)
Factorial_N=Factorial_M*N
Factorial_N=2*3
6=2*3
M’=M–1
M’=2–1
1=2–1
factorial (M’, Factorial_M’)
factorial (1, Factorial_M’)
factorial (1, 1)
Factorial_M=Factorial_M’*M
Factorial_M=1*2
1=1*2
M’’=M’–1
M’’=1–1
0=1–1
factorial (M’’, Factorial_M’’)
factorial (0, Factorial_M’’)
factorial (0, 1)
Factorial_M’=Factorial_M’’*M’
Factorial_M’=1*1
1=1*1
РЕКУРСИВНЫЕ ТИПЫ ДАННЫХ
Списки [1, 2, 3]
Деревья (бинарные, упорядоченные)
4
2
5
nil
1
nil
3
nil
nil
nil
nil
ЯЗЫК ПРОГРАММИРОВАНИЯ LISP
Особенности языка
Одинаковая
форма представления данных и
программ – в виде списка
Функциональный образ мышления
Не требуется явное описание типов данных,
используемых в программе
Основной способ решения - рекурсия
ПЕРВАЯ ПРОГРАММА
> (+ 2 3)
программа
данные
> (+ 2 3)
5
> ‘(+ 2 3)
(+ 2 3)
> (quote (+ 2 3))
(+ 2 3)
ОСНОВЫ LISP’А
Символьные выражения
Символы
Атомы
Числа
t
nil
Length=Le
ngthT+1
2=1+1
Списки
СПИСКИ
(2 a 5 str 2.5 34)
Голова списка – первый элемент списка 2
Хвост списка – все оставшиеся элементы
списка, в свою очередь являющиеся
самостоятельным списком (a 5 str 2.5 34)
Пустой список – ( ) или 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
Документ
Категория
Презентации
Просмотров
17
Размер файла
5 236 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа