FLP

Z OI wiki

Verze z 30. 5. 2012, 06:05

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

• (CZ) Stránka předmětu na CourseWare
• (EN) Stránka předmětu na CourseWare

Úkoly 2012

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

Exam 29.5.2012

---Scheme--- 1) Popište slovy, co dělá funkce foo. Napište funkci foo bez použítí lambda.

  (kod jsem psal z hlavy, takže není zcela správně, ale princip a vzhled je podobný, když tak doopravte)

(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) y))
                       ((> (car x) z) (cons z (car x)))
                       (else (cons y z)))
                  (car q) (cdr q))
                (foo (cdr x))
                ))
        ))
 )

- má vracet nejmenší a největší prvek seznamu

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.

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]

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

...