wykłady.pdf

(1064 KB) Pobierz
Programowanie deklaratywne
__________________________________________________________________________________________
PROGRAMOWANIE DEKLARATYWNE
INFORMATYKA, SEM.5
WYKŁAD:
30 GODZIN
ĆWICZENIA LAB. : 30 GODZIN
________________________________________________________________________
LITERATURA
1. W.F. Clocksin, C.S. Mellish
Prolog. Programowanie.
Wydawnictwo Helion, Gliwice, 2003
2. Eugeniusz Gatnar, Katarzyna Stąpor
PROLOG język sztucznej inteligencji
Wydawnictwo PLJ, Warszawa 1991.
3. Jerzy Bartoszek, Jolanta Cybulko
Programowanie deklaratywne
Wydawnictwo Politechniki Poznańskiej. Poznań 1999
4. Grażyna Brzykcy, Adam Meissner
Programowanie w PROLOGu i programowanie funkcyjne.
Materiały do ćwiczeń
Wydawnictwo Politechniki Poznańskiej. Poznań 1999
5. J. W. Lloyd
Foundations of Logic Programming.
Springer Ferlag, wyd.2, 1987
6. Kees Doets
From Logic to Logic Programming
The MIT Press, 1994
7. Ulf Nilsson, Jan Małuszyński
Logic, Progamming and Prolog
http://www.ida.liu.se/~ulfni/lpp
__________________________________________________________________________________________
Maria Bulińska
1
Programowanie deklaratywne
__________________________________________________________________________________________
I. WPROWADZENIE
1. Programowanie deklaratywne a programowanie tradycyjne (imperatywne).
Programowanie imperatywne:
Program instruuje komputer JAK przeprowadzić obliczenia.
Zorientowane na rozwiązywanie problemów natury numerycznej, symbole posiadają tylko
jedno znaczenie – wartość liczbową.
Logika informacji (tzn. logiczne związki między danymi potrzebnymi do rozwiązania
zadania) jest powiązana ze sterowaniem tą informacją; symbolicznie:
algorytm = logika + sterowanie
gdzie
– definicja problemu do rozwiązania
(JAKI problem),
sterowanie – sposób rozwiązania problemu (JAK).
Ważny
problem weryfikacji:
sprawdzenie poprawności programu (czy wyznacza żądaną
funkcję)
Programowanie deklaratywne:
Uproszczenie zagadnienia poprawności programu przez oddzielenie logiki od sterowania:
programista – specyfikacja logicznej części algorytmu.
system
– dostarczenie mechanizmu sterowania.
Zorientowane na przetwarzanie symboliczne, o znaczeniu symboli decydują operacje, za
pomocą których są przetwarzane.
Rodzaje:
–
programowanie w logice:
wykorzystuje logikę elementarną jako język
programowania
–
programowanie funkcyjne:
sposób przetwarzania, w którym program jest
matematycznie poprawną definicją funkcji.
logika
__________________________________________________________________________________________
Maria Bulińska
2
Programowanie deklaratywne
__________________________________________________________________________________________
PROGRAMOWANIE
IMPERATYWNE
Podstawo-
wa zasada
Program
JAK rozwiązać problem
(obliczyć wynik)
Ciąg poleceń (instrukcji), z
których każda opisuje pewną
akcję, jaką ma wykonać
komputer.
PROGRAMOWANIE DEKLARATYWNE
(deskryptywne, opisowe)
Programowanie
Programowanie
w logice
funkcyjne
JAKI problem (CO ma być rozwiązane)
Zbiór zdań
traktowanych jako
zbiór aksjomatów
pewnej teorii
Zbiór definicji funkcji
Obliczenie
Wykonanie ciągu poleceń dla Dowód twierdzenia
danych wejściowych
(zapytania)
Fortran, Algol, Basic, Pascal, Prolog, Gödel, Life
C/C++, Java
ADA
Sprawne, wyspecjalizowane
programy
Wyznaczanie wartości
wskazanej funkcji dla
zadanych argumentów
LISP, Scheme. Haskell,
ML
Przykłady
języków
Zalety
Ogólne, czytelne, poprawne programy.
PRZYKŁA D
programu w języku imperatywnym (Pascal) i w języku deklaratywnym (Prolog).
ZASTOSOWANIA:
przetwarzanie języka naturalnego i formalnego
automatyczne dowodzenie twierdzeń
symboliczne rozwiązywanie równań
relacyjne bazy danych
systemy ekspertowe
analiza struktur biochemicznych
automatyzacja projektowania
planowanie akcji
__________________________________________________________________________________________
Maria Bulińska
3
Programowanie deklaratywne
__________________________________________________________________________________________
II. PROGRAMOWANIE W LOGICE.
RYS HISTORYCZNY
1965 J. Robinson: metoda rezolucji z unifikacją.
1972 Powstanie języka PROLOG (PROgrammation en LOGique) na uniwersytecie w
Marsylii w zespole pod kierunkiem Alaina’a Colmerauera i Phillipe’a Roussel’a.
1973 Powstanie (również w Marsylii) pierwszego kompilatora PROLOGu napisanego
w ALGOLu.
1974 R. Kowalski: wprowadzenie SLD-rezolucji
1977 Edinburgh Prolog (D.H.D. Warren)
1982 Wybór programowania w logice jako podstawy japońskiego projektu FGCS (Fifth
Generation Computer System)
1984 Journal of Logic Programming
1986 Constraint Logic Programming (Programowanie w logice z ograniczeniami-więzami)
1. REZOLUCJA W RACHUNKU ZDAŃ.
KLASYCZNY RACHUNEK ZDAŃ – SYNTAKTYKA
DEF. Język rachunku zdań
(i) nieskończony, ale przeliczalny zbiór
zmiennych zdaniowych
V
�½
p
,
q
,
r
,
,
p
1
,
,
p
,
�½
(ii) zbiór
stałych logicznych
LOG
=
,
,
,
,
�½
(iii) zbiór
symboli
SYM
=
V
LOG
( , )
�½
(iv) zbiór
wyrażeń
rachunku zdań –
SYM
*
,
gdzie dla dowolnego zbioru
W
,
W
oznacza zbiór wszystkich skończonych ciągów
elementów zbioru W
DEF. Formuły.
Zbiorem
FOR formuł
rachunku zdań nazywamy najmniejszy zbiór
X
SYM
*
taki, że
__________________________________________________________________________________________
Maria Bulińska
4
Programowanie deklaratywne
__________________________________________________________________________________________
(i)
V
X
,
(ii) jeżeli
A
X
, to
A
X
,
(iii) jeżeli
A
,
B
X
, to
A
B
,
A
B
,
A
B
,
A
B
X
Reguły opuszczania nawiasów:
1) opuszczamy zewnętrzne nawiasy,
2) uwzględniamy siłę wiązania spójników logicznych ;
spójniki według siły wiązania poczynając od najsilniejszego:
a)
b)
 
c)
 
PRZYKŁAD 1.1.
Opuszczanie nawiasów w formułach.
KLASYCZNY RACHUNEK ZADAŃ – SEMANTYKA
DEF. Wartościowanie.
1. Wartości logiczne : 1 (prawda), 0 (fałsz)
2.
Wartościowaniem
nazywamy funkcję
w
:
V
0,1
�½
n
3.
Funkcją logiczną
nazywamy funkcję
f
:
0,1
�½
0,1
�½
.
Określamy funkcje:
następująco:
x
0
1
f
x
f
:
0,1
�½
0,1
�½
i
f
,
f
,
f
,
f
:
0,1
�½
0,1
�½
2
1
0
x
1
1
0
0
y
1
0
1
0
f
x
,
y
1
0
0
0
f
x
,
y
1
1
1
0
f
x
,
y
f
x
,
y
1
0
1
1
1
0
0
1
ˆ
ˆ
4. Każde wartościowanie
w
:
V
0,1
�½
rozszerzamy do funkcji
w
:
FOR
0,1
�½
, (
w
A
–
wartość logiczna formuły
A
przy wartościowaniu
w)
następująco:
ˆ
ˆ
w
A
�½
f
w
A
 
Maria Bulińska
ˆ
w
p
�½
w
p
dla
p
V
__________________________________________________________________________________________
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin