Установочная лекция по дисциплине Старший преподаватель каф. ВТ Юлия Вадимовна Новицкая email: novitskaya@vt.cs.nstu.runovitskaya@vt.cs.nstu.ru. - презентация

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

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

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

4

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

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

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

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

9

10

11

12

13

14

15

16

17

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

19

20

21

22

23

24

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

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

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

28 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

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

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

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

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

33 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).

34

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

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

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

38

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

40 > (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

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