====== Archiv FLP 2011: Cvičení Prolog ======

Odkazovník:
  * [[courses:a4b33flp:2015::start|Aktuální ročník předmětu]]
  * Prolog [[prolog_prednasky|přednášky]], [[prolog_cviceni|cvičení]], [[prolog_ukoly|úkoly]]

====== Harmonogram ======
   *  5.4.2010 - Základy Prologu (predikáty, fakta, pravidla, rekurze)
   * 12.4.2010 - Práce se seznamy, zadání 1. domácího úkolu
   * 19.4.2010 - Mimologický predikát řez
   * 26.4.2010 - Prohledávání stavového prostoru, zadání 2. domácího úkolu, odevzdání 1. domácího úkolu
   *  3.5.2010 - Prohledávání stavového prostoru
   * 10.5.2010 - CLP, zadání 3. domácího úkolu, odevzdání 2. domácího úkolu
   * 17.5.2010 - Dynamické klauzule, odevzdání 3. domácího úkolu, Zápočet

Domácí úkoly se odevzdávají přes upload systém.


====== Sbírka úloh ======
Sbírka jednoduchých úloh z jazyka Prolog. {{courses:a4b33flp:2011:prolog_exercises.pdf|Prolog exercises}}

====== Cvičení 1 - úvod ======
Seznámení s jazykem Prolog (fakta, predikáty, pravidla, dotazy; rekurze) a s prostředím Eclipse.

Úkoly:

  - Podle rodokmenu na obrázku napište v Prologu fakta o rodině: rodic(X,Y), muz(X) a zena(X). Znak = označuje manžele a čára potomka.\\ {{courses:y33pui:prolog:rodina.png|}}
  - Pomocí výše uvedených faktů můžeme definovat pravidlo pro otce otec(X,Y):-muz(X), rodic(X,Y). Podobně nadefinujte pravidla pro matku, syna, dceru, dědu a babičku.
  - Zapište v Prologu následující orientovaný graf jako fakta. \\ {{courses:y33pui:prolog:graf.png|}}
  - Naprogramujte program pro ověření, zda mezi uzly X a Y existuje cesta.
  - Naprogramujte v Prologu výpočet faktoriálu.
  - Vyřešte v Prologu kryptogram JA+SE=MAM.

====== Cvičení 2 - seznamy ======

  - Zadejte následující fakta: seznam([a,b,c,d,e,f]). seznam1([a]). A zkuste dotazy: ?-seznam(X). ?-seznam1([X]). ?-seznam([H|T]). ?-seznam([H1,H2|T]).
  - Napište program, který zjisti zda prvek X je prvkem seznamu. ?-prvek(a,[b,c,d,a]).
  - Napište program, který přidá nějaký prvek X na začátek seznamu L. ?-pridej_nazacatek(a,[b,c,d],V). V=[a,b,c,d]
  - Napište program, který přidá nějaký prvek X na konec seznamu L. ?-pridej_nakonec(a,[b,c,d],V). V=[b,c,d,a]
  - Napište program, který sloučí dva seznamy. ?-sluc([a,b,c],[e,f,g],X). X=[a,b,c,e,f,g]
  - Napište program, který vypočítá délku zadaného seznamu. ?-delka([b,c,d],X). X=3
  - Napište program, který vypočítá součet všech čísel v zadaném číselném seznamu. ?-suma([2,3,4],X). X=9
  - Napište program, který nalezne N-tý prvek seznamu, v případě, že prvek neexistuje, vrátí No. (SWI vraci false.) ?-nalezni([2,3,4,7],2,X). X=3
  - Napište program, který do seznamu vygeneruje posloupnost čísel N až 0. ?-gend(5,X). X=[5,4,3,2,1,0]
  - Napište program, který do seznamu vygeneruje posloupnost čísel 0 až N. ?-genn(5,X). X=[0,1,2,3,4,5]

====== Cvičení 3 - mimologický predikát řez ======
  - Napište program, který ze dvou čísel vybere to větší. ?-vetsi(5,6,X). X=6
  - Předchozí program použijte pro nalezení maxima v číselném seznamu ?-nejvetsilist([2,3,4,2,1,2],X) X=4
  - Napište program, který smaže všechny výskyty prvku ze zadaného seznamu. ?-smazvse(a,[a,b,a,d],X). X=[b,d]
  - Napište program, který smaže první výskyt prvku v seznamu. ?-smazprvni(a,[a,b,a,d],X). X=[b,a,d]
  - Napište program, který vypočítá počet výskytů prvku v zadaném seznamu. ?-kolik(a,[a,d,c,a,a,a,d,a],X). X=5
  - Napište program, který do seřazeného číselného seznamu zařadí číslo N tak, aby seznam zůstal seřazený. ?-zarad(5,[2,4,6,7],X). X=[2,4,5,6,7]
  - Napište program v Prologu, který rozdělí seznam čísel podle zadaného čísla na dva tak, aby jeden seznam obsahoval všechna čísla menší nebo rovna a druhý seznam všechna čísla větší. Příklad dotazu: ?-rozdel(4,[2,5,3,1,8,4],U,V). U=[2,3,1] V=[5,8,4]
  - Predikát rozdel/4 z předchozího příkladu použijte pro naprogramování quick sortu. Příklad dotazu: ?- quick_sort([2,5,3,1,8,4],Y). Y=[1,2,3,4,5,8]

====== Cvičení 4 - prohledávání grafů ======

Prohledávat budeme graf:

h(a,b). h(a,c). h(a,d).

h(b,e). h(b,f). h(b,g).

h(c,h). h(c,i). 

h(d,j). h(d,k). h(d,l).

h(e,m). h(e,n).

h(f,n). 

h(g,p). h(g,q). h(g,r). h(i,i).

h(i,s). h(i,t). 

h(j,t).

h(k,u). h(k,v).

h(l,w). h(l,x).

h(n,y).

h(t,z). h(t,z).

  - Nakreslete si graf.
  - Vyzkouzkoušejte si predikáty ?-setof(X, h(t,X), L) a ?-bagof(X, h(t,X), L). Jaký je mezi rozdíl?
  - Napište program v Prologu pro prohledávání grafu do hloubky s použitím predikátu setof.
  - Program pro prohledávání grafu do hloubky rozšiřte o kontrolu tak, abyste každý uzel navštívili pouze jednou. 
  - Napište program v Prologu pro prohledávání grafu do šířky.
  - Program pro prohledávání grafu do šířky rozšiřte o kontrolu tak, abyste každý uzel navštívili pouze jednou.

====== Cvičení 5 - prohledávání stavového prostoru ======
  - Vyzkoušejte program v Prologu, který řeší úlohu o farmáři, koze, vlku a zelí. {{courses:a4b33flp:2011:puiprogramkyp5.zip|puiprogramkyp5.zip}}
 
====== Cvičení 6 - Constraint Logic Programming ======
**Úloha Golfisté**

Čtyři golfisté (Franta, Jirka, Petr, Tomáš) stojí vedle sebe na odpališti.
Každý z nich má jinou barvu kalhot (bílé, modré, červené, šedé). 

1) Golfista těsně vpravo od Franty má modré kalhoty.

2) Jirka je třetí v řadě.

3) Petr má šedé kalhoty.

4) Tomáš nestojí na pozici 2 ani 4 a nemá bílé kalhoty.

V jakém pořadí golfisté stojí a jakou mají barvu jejich kalhoty?

  - Vyřešte úlohu v "klasickém" Prologu pomocí metody generuj a testuj.
  - Vyřešte úlohu pomocí CLP.