Prowadzący: Paweł Marczewski
Opis
If traditional languages are like prose, Prolog is like poetry.
W tym roku zapraszam na wstęp do Prologu i tym samym do fascynującego paradygmatu, jakim jest programowanie w logice. Tak jak rok temu, nauczymy się nowego, zupełnie innego sposobu myślenia o komputerze.
Będzie o tym:
- Jak mówić komputerowi, co chcemy dostać (a on sam już sobie wymyśli, jak)
- Jak cofać się w czasie i wykonywać obliczenia na wszystkie sposoby naraz
- Jak używać zmiennych, które się nie zmieniają
- Jak wyciągnąć z listy element, którego tam jeszcze nie dodaliśmy
i takie różne.
Skupimy się przede wszystkim na programowaniu, nie na części teoretycznej.
Wymagania
Powinieneś:
- Umieć programować (w C/Pascalu/Javie/… - nie chodzi o język, ale o doświadczenie): wiedzieć, co to procedura, zmienna, rekurencja, drzewo.
- Znać trochę rachunku zdań - wiedzieć, co to alternatywa, koniunkcja, implikacja, kwantyfikatory, prawa de Morgana.
- (Styczność z programowaniem funkcyjnym nie zaszkodzi, ale nie jest wymagana).
Jeśli bierzesz ze sobą laptopa (mile widziany, ale nieobowiązkowy - szczególnie, że na miejscu chyba będą komputery), zainstaluj na nim SWI-Prolog.
Zadania kwalifikacyjne
Nie trzeba zrobić wszystkiego, żeby się zakwalifikować.
Zadanie 1 wymaga umiejętności programowania i myślenia. Zadania 2 i 3 wymagają tylko umiejętności myślenia.
Na rozwiązania czekam pod adresem moc.liamg|celopmuh#moc.liamg|celopmuh.
Zadanie 1
Dana jest następująca definicja listy:
type
PList = ^List; { pusta lista to nil }
List = record
n: Integer;
next: PList;
end;
lub w C:
struct list {
int n;
struct list *next; /* pusta lista to NULL */
}
Listę reprezentuje oczywiście wskaźnik do danej struktury.
Napisz (w Pascalu lub w C) funkcję, która dla danej listy
1a. zwraca sumę jej elementów,
1b. zwraca listę, składającą się z elementów danej listy podzielnych przez 3,
1c. zwraca listę, składającą się z elementów danej listy podzielonych przez 3,
1d*. zwraca odwróconą wersję danej listy
1e**. zwraca posortowaną wersję danej listy
(najlepiej, jeśli pierwotna lista nie ulegnie przy tym modyfikacji).
Nie wolno ci korzystać z pętli (while, for, repeat, goto, …).
Zadanie 2
Załóżmy prawdziwość następujących formuł:
- $e(a)$
- $\forall x. (e(x) \Rightarrow e(s(s(x))))$
- $\forall x. (\neg e(x) \Rightarrow o(x))$
- $l(nil,a)$
- $\forall xyz. (l(y,z) \Rightarrow l(x.y,s(z)))$
gdzie
- $p, o, e, l$ to predykaty mogące być prawdziwe dla pewnych termów (np. wiemy, że e jest prawdziwe dla termu a, co zapisujemy $e(a)$)
- termy to napisy postaci $a, nil, s(x), x.y$, gdzie x, y to termy - na przykład termem może być $a.(s(a).nil)$
- $\forall x.$ czytamy "dla każdego termu x zachodzi…"
- $\exists x.$ czytamy "istnieje taki term x, że zachodzi…"
- (x, y, z… nazywamy po prostu zmiennymi)
- $a \Rightarrow b$ czytamy "jeśli a, to b"
- $\vee, \wedge, \neg$ oznaczają alternatywę, koniunkcję, negację ("lub", "i", "nie").
Dla każdej z poniższych formuł napisz (i, jeśli potrafisz, uzasadnij), czy:
- musi być prawdziwa (dla każdych termów x,y,z),
- musi być fałszywa (dla każdych x,y,z),
- nie musi być ani prawdziwa, ani fałszywa.
- $e(a)$
- $o(x) \wedge e(x)$
- $o(x) \vee e(x)$
- $l(nil, s(s(s(a))))$
- $l(x.(y.(z.nil)),s(s(s(a))))$
FAQ
Widzę, że mój niezbyt dokładny opis tego, czym są termy, a czym predykaty, spowodował wiele wątpliwości.
Co robią kropka, s()? Nic nie robią, po prostu są. Jeśli za x przypiszemy $a$, za y przypiszemy $b$, to x.y oznacza po prostu $a.b$.
Czy na przykład a.b jest prawdziwe albo fałszywe? Nie, termy nie mają wartości logicznej. Można powiedzieć, że (na przykład) predykat e nie zachodzi dla $a.b$, czyli nie zachodzi $e(a.b)$.
Co to jest a, nil? To takie napisy. Stałe. Nie mają wartości i nic pod nie nie podstawiamy. (W przeciwieństwie do x,y,z… które są zmiennymi.)
W razie dalszych wątpliwości polecam drugi i trzeci rozdział tego kursu (szczególnie początek trzeciego) (ale nie przerażajcie się - nasze zadania powinny być sporo prostsze od tych rozdziałów.)
Zadanie 3*
Co mogą opisywać termy z poprzedniego zadania? Co mogą oznaczać predykaty? Czy ich definicja jest jednoznaczna?