FLP
Z OI wiki
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||
Info o předmětu
(CZ) A4B33FLP - Funkcionální a logické programování
- Cvičící (CZ): Ing. Ondřej Kuželka; Ing. Lenka Nováková, Ph.D.
- Přednášející (CZ): Prof. RNDr. Olga Štěpánková, CSc.; Ing. Filip Železný, Ph.D.
(EN) AE4B33FLP - Functional and Logic Programming
- Přednášející (EN): Ing. Filip Železný, Ph.D.; RNDr. Jiří Vyskočil, Ph.D.
- Cvičící (EN): Radomír Černoch, MSc.
Pravidla předmětu
Odkaz na pravidla předmětu (bude doplněno)
Studijní materiály
Úkoly 2012
Úkoly a cvičení na Google drive
Sample data pro první úkol (navigace robota) FLP/Ukol1_2012
Sample data pro druhý úkol (evaluace situací) FLP/Ukol2_2012
Sample data pro třetí úkol (evoluce programů) FLP/Ukol3_2012
Zkoušky
Zkouška 7.9. 2017
Funkcionální část
1) Určete pravdivost následujících tvrzení o uvedeném kodu ve SCHEME.
(define foo
(lambda (x)
(cond ((null? (cdr x)) (car x))
(else
((lambda (y)
(cond ((equal? y 'no) 'no)
((< (car x) y) 'no)
(else y)
)
)
(foo (cdr x)))
)
)
)
)
Měli jsme pochopit funkci a odpovídat ANO/NE na různá tvrzení. Třeba: -> Vrátí (foo '(1 4 2)) no? ANO.
(Funkce vrací minimum, ale pouze pokud je na konci seznamu. Duplicitní minima nevadí. Jinak se vrátí no.)
2) Určete pravdivost následujících tvrzení o Haskellu.
a) Výraz [1,3..10] vrátí [1,3,5,7,9] (TRUE)
b) Byla tam nějaká funkce, která obracela String. Ptali se, jestli výraz (ta_funkce "abc") je datového typu [Char]. (TRUE)
c) f 0 = 1, f 1 = 1, f n = f (n-1) + f (n-2). f 4 vrátí 7. (FALSE)
Exam 12. 6. 2017
Funkcionální část
Napsat funkci powerset, která přijímá jeden seznam (množinu) a vrací seznam všech podmnožin. Množina je reprezentovaná seznamem. Na pořadí nezáleží. (10 bodů)
> (powerset '(1 2 3))
((1) (2) (3) (1 2) (1 3) (2 3) (1 2 3) ())
Logická část
1) Bude na dotaz ?-woman(X) odpověď X = anne? Pokud ne, opravte program tak, aby byla.
person(anne). person(jeff). man(jeff). woman(X):-not(man(X)).
řešení:
ne, woman(X):-person(X),not(man(X)).
2) Máme program:
n(0). n(1). n(2). n(3). n(4).
Pomocí findall napiště dotaz, který vrátí:
L = [0+4, 1+3, 2+2, 3+1, 4+0].
3) Jak je v Prologu definován not/1?
řešení:
not(Goal) :- Goal, !, fail. not(Goal).
Exam 23. 6. 2014
Funkcionální část
1) Vlastními slovy vyjádřete chování funkce foo. (5 bodů)
(define (foo
(lambda (x)
(if (null? x)
x
((lambda y z)
(cond
((null? z) (cons y z))
((> y (car z)) (cons (car z) (foo (cons y (cdr z)))))
)
)
(car x) (foo (cdr x)))
)
)
)
2) Napište funkci woo, která má stejné chování jako foo a stejnou nebo lepší výpočetní složitost, ale bez klíčového slova lambda. (5 bodů).
3) Stejné jako 29. 5. 2012 a 21.5. 2013 - zadaný seznam a číslo n, funkce má vrátit všechny kombinace ze zadaného seznamu délky n. (5 bodů)
4) Haskell: Napište funkci matrixCenter, která na vstupu příjímá matici čísel a vrací prostřední prvek této matice. Funkce matrixCenter je definována pouze pro lichý počet řádků i sloupců. (10 bodů)
Logická část
1) Rozhodněte, které dva termy se dají unifikovat či ne a jak. (4 body)
| První term | Druhý term | Dají se unifikovat? | Unifikace |
| [H|T] | [1,2] | ano / ne | H = T = |
| [a, b, c] | [X|[Y]] | ano / ne | X = Y = |
| [a, [b, c]]| [X, Y] | ano / ne | X = Y = |
| 2 + 3 + 4 | 5 + Z | ano / ne | Z = |
Uvažujte program:
%d(X, L).
d([],0).
d([X|T], s(D)) :- d(T, D).
Jaké jsou odpovědi na následující dotazy?
2) ?- d([1,2,3],X). {1 bod)
3) ?- d(L, s(s(0))). (1 bod)
4) ?- d(L, s(s(s(1)))). (1 bod)
Uvažujte program.
cislice(0). cislice(1). cislice(2).
c_seznam([0]).
c_seznam([H|T]) :- cislice(H), !, c_seznam(T).
Jaké jsou odpovědi na následující dotazy?
5) ?- c_seznam([2,0,1]). (1 bod)
6) ?- c_seznam([2,0,1,0,3]). (1 bod)
7) ?- c_seznam(X). (2 body)
8) Mějme orientovaný graf bez cyklů popsaný seznamem jeho hran pomocí predikátu hr(Pocatecni_vrchol, Koncovy_vrchol). Některé vrcholy jsou označeny jako cílové pomocí predikátu cil(a), který značí, že vrchol a je cílový. Napište program, který uspěje, pokud se ze zadaného vrcholu lze dostat do dvou různých cílových vrcholů. (4 body)
9) Stejné zadání jako u Haskellu: Napište predikát matrixCenter(Matice, N), kde Matice je vstupní matice a N je její prostřední prvek. matrixCenter([ [a] ],X) vrátí X = a, matrixCenter([[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15]],X) vrátí X = 8. Opět je to definované pouze pro lichá čísla. (10 bodů)
Exam 29. 5. 2014
Funkcionální část
1) Scheme - to same jako minuly rok(min max) - zjistit co dela a prepsat bez lambd (10 bodu)
2) Haskel napsat determinant matice v Haskelu - obecna velikost, ctvercova (15 bodu)
Logická část
c(0).c(1).
p1([]). p1([A|T]):-c(A),p1(T).
p2([]). p2([A|T]):-c(A),p2(T),!.
p3([]). p3([A|T]):-p3(T),c(A).
1) Vypiste prvni 4 vysledky p1(L).
2) Vypiste prvni 4 vysledky p3(L).
3) Jaky bude vysledek set_of(X,p2(X),L).
II]
Predpokladejte, ze mate odladeny predikat serad(L1,L2). A chceme vyber(L,X,M), kde L je vtupni list cisel, X je horni mez a M je vystupni pole, kde jsou serazene prvky z L mensi nez X. pr.: vyber([5, 5 , 8,6,0,1,1,2],3,M). M=[0,1,2].
III]
neco podbneho jako uz bylo min. rok 3) priklad.
IV]
5 Kamaradu slavi v jeden den narozeniny. Nejstarsimu je 11. Adolfovi je o 3 roky min, nez Lukasovi, Danovi je vic, nez Adolfovi, ... nejake takovehle podminky. Napiste program v klasickem prologu, ktery zjisti, kolik let je nejmladsimu z nich.
Exam 30. 5. 2013 - EN
http://uloz.to/xNXWm6Tk/flp-30-5-2013-zip
Exam 21. 5. 2013
Funkcionální část
1) Vlastními slovy vyjádřete chování funkce foo. Ve Scheme napište funkci woo stejného chování bez použití lambda konstrukce.
Zadaná byla stejná funkce jako 29.5. 2012. Funkce vrací dvojici (min . max) ze seznamu, se kterým se volá. Přepsat se dá snadno použitím let*
2) Ve Scheme napište funkci, která akceptuje seznam prvků a číslo n a vrací seznam všech kombinací bez opakování dané délky n. Prvky v seznamu jsou vždy různé.
(stejné jako 29.5 2012)
ŘEŠENÍ
(define (kombinace a n)
(cond ((= n 0) '(()))
(else
(apply append (map
(lambda (e)
(map (lambda (x)
(cons e x))
(kombinace (remove-before e a) (- n 1)))) a))
)
)
)
(define (remove-before e a)
(cond ((null? a) a)
((eq? e (car a)) (cdr a))
(else (remove-before e (cdr a)))
)
)
3) V jazyku Haskell napište funcki rotujMatici, která zarotuje danou matici od 90° doprava.
ŘEŠENÍ: rotujMatici m = transpose (reverse m)
Logická část
1) Mějme program:
c(0). c(1). p([]). p([H|T]) :- c(H), p(T).
a) Jaká je odpověď na dotaz ?- p([1,0]).
ŘEŠENÍ: true
b) Nechme postupně generovat odpovědi na dotaz ? - p(L). Kdy dostaneme odpověď L=[1,0]? Správnou odpověď zakroužkujte.
- Bude to jedna z prvních 3 řešení. - Bude to jedna z prvních 15 řešení. - Nikdy. (správná možnost)
2) K danému kladnému číslu C, které reprezentuje částku, kterou má pokladní vyplatit, máme připravit vhodnou kombinaci bankovek, které k tomu bude pokladní potřebovat. Např pro 3475 to bude 1x2000, 1x1000, 2x200, 1x50. Máme program:
b(5000). b(2000). b(1000). b(500). b(200). b(100). b(50). r(C,Z,[C|Z]) :- C<50. r(C,Z,V) :- b(B), B<C, C1 is C-B, r(C1,[B|Z],V).
r1(C,Z,[C|Z]) :- C<50. r1(C,Z,V) :- b(B), B<C, !, C1 is C-B, r(C1,[B|Z],V).
a) Který z následujících dotazů může vygenerovat k číslu C=275 jako jedno z možných řešení L=[25,100,50,100]?
- r(275,L,[25]). - r(275.[],L) (správná možnost) - žádný - r1(275,L,[25]). - r1(275.[],L)
b) Použijte jeden z predikátu r nebo r1 pro návrh výplaty vstupní částky pomocí co nejmenšího počtu bankovek. Vysvětlete postup.
HINT : Bankovky jsou zadefinované sestupně, takže hledaný predikát je r1 (díky řezu).
3) Mějme úlohu prohledávání stavového prostoru definovýny predikáty, které potřebujeme pro samostatný popis úlohy, tj.
tah(Akce, Vychozi_stav, Nasledny_stav, Cena_akce). pocatek(Stav_start). konec(Stav_cil).
Uvažujte predikát
cc(X,X,H) :- H>0, konec(X). cc(X,Y,H) :- H>0, tah(Akce,X,Z,C), Podcil.
a) Nahraďte Podcíl jedním nebo více predikáty tak, aby výsledný program hledal (prostřednictvím dopředného prohledávání do hloubky) takové stavy vyhovující predikátu konec, do nichž jejich celková cena nemá vyšší než předem stanovené číslo H:0.
ŘEŠENÍ: H2 is H-C, cc(Z,Y,H2)
b) Nakreslete příklad jednoduchého stavového prostoru (grafu s ohodnocenými hranami) s jediným počátečním uzlem s0, pro nějž na dotaz ?- cc(s0,Z,5) postupně při hledání více řešení získáme 2x tutéž odpověd.
HINT: Stačí třeba 4 uzly, 1 z nich je start a jeden cíl. Důležité je, aby obě cesty do cíle měly stejnou cenu.
c) V jakém případě při prohledávání grafu nevystačíme s čistým Prologem a které konstrukty pak používáme?
HINT: Já jsem tam napsal něco ve stylu, že pro graf s cyklem nám čistý Prolog nestačí a budeme potřebovat closed list ( -> potřeba not nebo \+ -> cut a fail ), abychom se nevraceli do stejného uzlu. Pro hledání do šířky navíc frontu. atp. (už nvm kolik jsem za to dostal)
4) a) Napište v Prologu predikát permutace(+S1,-S2), který postupně pro seznam S1 jako hodnoty S2 generuje všechny možné permutace S1.
ŘEŠENÍ: permutace([],[]). permutace(X,[A|R]) :- pick_element(X,A,B), permutace(B,R).
pick_element([X|XS], X, XS). pick_element([X|XS] ,Y ,[X|Z]) :- pick_element(XS,Y,Z).
TIP: místo pick_element/3 lze použít v prologu zabudovaný select/3
4) b) Předpokládejte, že máže k dispozici odladěný predikát permutace. Použijte jej pro napsání programu v Prologu, který řeší následující úlohu:
Na lavičce v parku vedle sebe sedí 3 dámy. První má šatý bílé, druhá červené a třetí zelené. Dámy se představily a překvapeně zjistily, že jejich jména tvoří stejnou množinu jako barvy jejich šatů. Dále si všimly, že
- žádná z nich nemá šaty stejné barvy, jaké má jméni - paní bílá nesedí uprostřed
Napište, jak se dámy jmenujou.
ŘEŠENÍ: solve([A,B,C], [D,E,F]) :- permut([A,B,C], [D,E,F]), A\=D, B\=E, C\=F, E\=white.
dotaz by vypadal takhle ?- solve([white, red, green], Solution).
Exam 29.5.2012
Scheme
1) Popište slovy, co dělá funkce foo. Napište funkci foo bez použítí lambda.
(define foo
(lambda (x)
(cond ((null? (cdr x)) (cons (car x) (car x)))
(else ((lambda (q)
((lambda (y z)
(cond ((< (car x) y) (cons (car x) z))
((> (car x) z) (cons y (car x)))
(else (cons y z))))
(car q) (cdr q)))
(foo (cdr x)))))))
- vrací nejmenší a největší prvek seznamu
- možný přepis:
(define (foo2 x)
(if (null? (cdr x))
(cons (car x) (car x))
(let ((r (foo2 (cdr x))))
(cond ((< (car x) (car r)) (cons (car x) (cdr r)))
((> (car x) (cdr r)) (cons (car r) (car x)))
(else r)))))
2) Napište ve scheme funkci, která vytvoří všechny kombinace bez opakování k-tic.
př.: (funkce (1 2 3) 2) má vyplivnout ((1 2) (1 3) (2 3)), na pořadí čísel či dvojic nezáleží, měli by tam být akorát všechny ty kombinace.
- možné řešení:
(define (funkce l n)
(if (< n 1) '(())
(if (< (length l) n) '()
(append (map (lambda (x) (cons (car l) x))
(funkce (cdr l) (- n 1)))
(funkce (cdr l) n)))))
3) haskell - rotateMatrix o 90° doprava (stejné jako loni)
---Prolog---
1) Jednoduchá otázka. Je zadán kód a dotaz, máte rozhodnout, jestli odpověď bude True, False nebo přetečení zásobníku.
2) Napsat funkci, která bude vypisovat postupně permutace prvků v seznamu.
př.: ?- permutace([1,2,3], L).
L = [1,2,3];
L = [2,1,3]; L = [2,3,10;]..... výpisy se mohou opisovat i vícekrát
3) Napsat funkci, která vypíše číselnou hodnotu typu - př.: ?- hodnota([1,2,3],A) ... A = 123 , ?- hodnota([1,0,0,0],A] ... A = 1000
Já to udělal stylem: hodnota(A,X):- otoc(A,X1), hodnota2(X1,X). otoc ... reversovalo list z [1,2,3] -> [3,2,1] hodnota2([A|[]],X):- X is 1*A. hodnota2([A|B],X):- hodnota2(B,X1), X is 10*X1 + A.
4) Za pomoci funkcí z 2) a 3) rozdělte čísla 1..9 na tři listy po dvou, třech a čtyřech prvcích, aby platila rovnice [A,B]*[C,D,E] = [F,G,H,I]
(možná tam byla i nula a za rovná se bylo 5 prvků... ale princip je stejný)
př.: teď nevymyslím....
rovnice(A,B,C):- L = [1,2,3,4,5,6,7,8,9], permutace(L,VysledekP), VysledekP = [A1,A2,A3,A4,A5,A6,A7,A8,A9], hodnota([A1,A2],X1),
hodnota([A3,A4,A5],X2], hodnota([A6,A7,A8,A9],X3), X1*X2 = X3, A = [A1,A2], B = [A3,A4,A5], C = [A6,A7,A8,A9].
5) Jak byste našli všechny řešení?.... findall()
6) Byl definovaný prostor...
Něco ve stylu: prechod(Akce,Vychozi_stav,Nasledujici_stav,Cena).
konec(Cilovy_bod).
cc(X,X,N):- H > N, konec(X). cc(X,Y,N):- H > N, prechod(Akce,X,Z,Cena), "dopis"
Na místo dopis něco, aby to vyhledávalo všechny cílové stavy (body), které se dají dosáhnout za cenu H > 0 nebo menší. Já dopsal něco ve stylu cc(Z,Y,N+cena).
7) Nakreslete jednoduchý strom, který při volání cc(s0,Z,4) vydá 2 stejné výsledky
8) Zakroužkujte správné odpovědi.
Když volání cc(s0,Z,4) dá 2x stejnou odpověď, co vydá volání cc(0,Z,10)? * Nalezne 2x stejnou odpověď * Zahlásí chybu (false) * Nalezne minimálně 3x stejnou odpověď
- dobře je jen první
Poznámka: Vše jsem psal z hlavy, proto nemusí být přesně správně jak zadání, tak vypracování. Přeji hodně zdaru s touto nesnadnou zkouškou. Simo
Tohle mi odpovedel Vyskocil na dotaz, co bude z prvni poloviny anglicke verze FLP u zkousky (kdyby to nekoho zajimalo):
Dobry den, 1) otazky na Haskell lze jiste u zkousky ocekavat, protoze byl probiran jak na prednasce tak na cviceni. Samozrejme, ze otazky se budou tykat pouze toho, co se probiralo. 2) Lze ocekavat, ze vetsi duraz bude kladen na Scheme, protoze mu byla venovana vetsi pozornost. 3) Protoze jsem funkcionalni programovani probiral hlavne prakticky, lze ocekavat, ze u zkousky se objevi hlavne prakticke otazky typu: "co dela nasledujici kod" nebo "napiste kod funkce dle pozadavku". S pozdravem Jiri Vyskocil
Exam 22.5.2012
--- Part I - Functional programming [25p] ---
Question 1. Consider the following scheme code:
(define foo
(lambda (x)
(letrec
((h (lambda (y z)
(cond
((null? y) 'undefined)
((null? (cdr y)) (car z))
(else (h (cddr y) (cdr z)))
))))
((lambda (y) (h y y)) x))
))
1. [5p] Write down an English description of foo function behaviour/functionality.
2. [10p] Write down a Scheme code with only one function called w with the same behaviour as foo function but without using lambda keyword.
Question 2. [10p] Write down a Haskell code of unfoldMatrix function. The function unfoldMatrix outputs a single list containing all the elements of the input matrix. The result list will begin with the first column of the input matrix, then it will continue with the last row of the rest input matrix (the matrix without the first column) rotated 90° to the right. This process will continue analogicaly until the rest input matrix is empty. The input matrix is represented as a list of lists.
Haskell type of unfoldMatrix function:
unfoldMatrix :: [ [a] ] -> [a]
Example
Main> unfoldMatrix [[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
[10, 11, 12]]
[1,4,7,10,11,12,9,6,3,2,5,8]
řešení -> unfoldMatrix
--- Part II - Logic programming [25p] ---
Question 3. <same as the last year>
Question 4. <same as the last year>
Question 5. [4p] Is clause
ancestor(A,B):-parent(A,B)
the least general generalization (under theta-subsumption) of clauses
ancestor(X,Y):-parent(X,father_of(Y)) ancestor(alice,X):-parent(alice,father_of(father_of(x)))
?
Exam 24.5.2011
Je to dost strucny, klidne to nekdo rozsirte... --Ondra "Kofolák" Jelínek 25. 5. 2011, 18:50 (UTC)
Rozšířeno, upraveno --Erik 11. 6. 2011, 09:24 (UTC). Text, který je kurzívou (hinty), nebyl součástí zadání.
--- Part I - Functional programming [25p] ---
Question 1.
Consider the following Scheme code:
(define foo
(lambda (x)
(cond ((null? (cdr x)) (car x))
(else ((lambda (y)
(if (< (car x) y)
(car x)
y))
(foo (cdr x)))))))
1. [5p] Write down an English description of foo function behaviour/functionality. (hint: specify also behaviour in marginal cases - empty list, one number)
2. [10p] Write down a Scheme code with only one function called w with the same behaviour as foo function but without using lambda keyword. (hint: use accumulator or let construction)
Question 2.
[10p] Write down a Haskell code of rotateMatrix function. The function rotateMatrix rotates an input matrix 90° to the right. The input and output matrices are represented as list of lists. (hint: very similar to matrix transposition, just reverse element order on each row)
Haskell type of rotateMatrix function:
rotateMatrix :: [ [a] ] -> [ [a] ]
Example:
Main> rotateMatrix [[1,2,3],[4,5,6],[7,8,9],[10,11,12]] [[10,7,4,1],[11,8,5,2],[12,9,6,3]]
--- Part II - Logic programming [25p] ---
Question 3.
Given are the following clauses:
pass(S) :- clever(S). pass(S1) :- next_to(S1,S2), pass(S2). clever(trevor). next_to(trevor,bob). next_to(alice,carol). next_to(X,Y):- next_to(Y,X).
(a) Consider the query
?-pass(bob).
i. [2p] How many proofs are there for this query? Explain your answer.
ii. [4p] Give one of the proof trees.
(b) Consider the query
?-pass(X).
i. [3p] Indicate all answers Prolog would find, and the order in which they are returned (duplicates included).
ii. [2p] Discuss two possible adaptations to Prolog's search strategy so that it would return all answers.
(c) [3p] Show that
pass(alice)
is not a logical consequence of this set of clauses. (hint: find model of P that is not model of pass(alice))
Question 4.
Consider the following problem. There are two jugs of 7 and 5 litres, initially empty, and an unlimited supply of water. There are three ways to change the amount of water in a jug:
1. a jug can be filled completely, 2. a jug can be emptied completely, 3. water can be poured from one jug into the other, until one jug is empty or the other is full.
(a) [3p] Sketch part of the search space, starting from the initial situation (0,0) (two empty jugs) and at least containing the situation (0,2), i.e., large jug is empty, small jug contains 2 litres of water.
(b) [4p] The following Prolog clauses represent part of the search space.
arc(s(X,Y),s(7,Y)) :- X<7. arc(s(X,Y),s(X,5)) :- Y<5. arc(s(U,V),s(0,Y)) :- U>0, Y is U+V, Y=<5. arc(s(U,V),s(X,0)) :- V>0, X is U+V, X=<7.
Give the remaining 4 clauses.
Question 5. Definite Clause Grammar
Imagine you are going to write a user interface for a Prolog program, which stores information about the British Royal Family. For simplicity, there will be only two types of information stored in the database: properties of objects ("Charles is a man.") and relations between objects ("Charles is the father of William.").
The initial implementation stub is given to you in the form of Definite Clause Grammar (DCG):
person --> [william]. person --> [camilla]. person --> [charles].
(a) [2p] Using the non-terminal person above, declare a DCG capable of parsing and generating the following sentences.
[charles,is,a,man] [camilla,is,a,woman] [camilla,is,the,wife,of,charles] [charles,is,the,father,of,william] [charles,is,the,husband,of,camilla]
(b) [1p] (not complete) propagate predicates back
property(X,man(X)) --> [man]. ...
(c) [1p] (not complete) make all relations irreflexive, so that:
?-phrase(sentence(X), [camilla, is, the, wife, of, camilla]). false.
Zkouška ??.?.2011
...
