# Neprocedurální programování - písemka z Prologu 15.4.2010

<{ForumPost(poster="Vin", timestamp=2010-04-15 20:03:10)}>
Tak, jak si to ještě pamatuju:  
  
Celkem 4 úlohy. První dvě za 10 bodů, další dvě za 15 bodů.  
  
Zadání:  
  
==========================================================================  
10 bodů:  
  
1) Rotace seznamů. Predikát Rotace(+Seznam,-RotovanySeznam) vydá na výstup  
rotovaný seznam; rotaci provede v konstantním čase. Predikát přijímá i neúplně  
definované struktury.  
  
a) Vyjádřete seznam \[1,2,3] jako neúplnou datovou strukturu.  
b) Definujte predikát Rotace(+Seznam, -RotovanySeznam), který bude používat  
neúplně definované struktury k rotaci daného seznamu.  
  
2) Akumulátor. Predikát obsah(+SeznamVrcholu, -Obsah) spočítá obsah  
mnohoúhelníka a je definován takto:  
  
obsah(\[X],0).  
obsah(\[v(X1,Y1),v(X2,Y2) | T ], Obsah):-  
      obsah(\[v(X2,Y2) | T], Temp),  
      Obsah is Temp + (X1 * Y2 + X2 * Y1)/2.  
  
a)Definujte vlastní predikát, který bude používat akumulátor (a rekurzi použije  
na konci těla predikátu).  
  
b)Vysvětlete, proč je vaše řešení v a) efektivnější.  
  
15 bodů:  
  
3)Je zadán orientovaný ohodnocený graf pomocí seznamu vrcholů se seznami  
následníků, tj např. \[a-\[b-1,c-2],b-\[a-2]]. Definujte predikát  
obratGraf(+OhodnocGraf,-ObracGraf), který otočí orientaci jednotlivých hran v  
grafu, ale zachová jejich ohodnocení.  
  
4)Je zadán seznam kladně a záporně ohodnocených výroků, tedy např. \[a-true,  
b-false, c-false]. Úkolem je definovat predikát  
ohod2(+SeznamVyroku,-SeznamySDvemaZmenenymiVyroky), který vrátí seznam všech  
seznamů, kde byly změněny ohodnocení právě dvou výroků.  
  
==========================================================================  
  
Na vypracování písemky jsme měli 65 minut. Řešení měla být čitelná a  
strukturovaná.  
  
U první úlohy mě kdyžtak někdo opravte, jestli mám  
zadání správně... teď jsem si zpětně uvědomil, že jsem řešil úlohu jen pro  
rozdílové seznamy, a normální jsem zapomněl na rozdílové převést.  
  
U druhé úlohy si nejsem jistý ohledně seznamu.  
  
A u čtvrté úlohy si já (a pár dalších lidí) není jistý, jak znělo zadání. Jde o  
to, vrátit seznam všech možných seznamů, nebo stačí jen seznam s dvema  
zmenenymi ohodnocenimi?  
  
(Mám pocit ale, že opravdu seznam všech seznamů, protože na příkladu myslím  
bylo jako možný výsledek V =  
\[\[a-true,b-true,c-true],\[a-false,b-true,c-false],\[a-false,b-false,c-true]].)
<{/ForumPost}>

<{ForumPost(poster="mifeet", timestamp=2010-04-15 22:33:29)}>
Zadání si pamatuji stejně.  
1) U prvního úkolu jsem taky použil jenom rozdílové seznamy, větu "Predikát přijímá i neúplně definované struktury" jsem pochopil tak, že převod na normální seznam není nutný.  
2) U dvojky bylo v predikátu X1*Y2-X2*Y1 (místo X1*Y2+X2*Y1).  
3) Myslím, že ukázkový vstup byl \[a-\[b/1,c/3],b-\[a/2],c-\[]]  
4) Tady chtěli vrátit seznam všech ohodnocení, která se od původního liší v právě dvou hodnotách, tj. seznam seznamů. A ještě u toho byla poznámka, že na plný počet bodů je to třeba napsat bez bagof & spol.  
  
Moje řešení:

1. 

    rotace(X-X,X-X) :- var(X).
    rotace([X|Xs]-Y,Xs-Z) :- var(Y),Y=[X|Z].
    

1. 

    obsah(X,Y) :- obsah(X,0,Y).
    obsah([_],A,A).
    obsah([v(X1,Y1),v(X2,Y2)|Vs], A, Vysl):-A1 is A + (X1*Y2-X2*Y1)/2,obsah([v(X2,Y2)|Vs], A1, Vysl).
    

1. 

    otoc(G,TG):-bezHran(G,BG),otocHrany(G,BG,TG).
    
    bezHran([],[]).
    bezHran([V-_|Xs], [V-[]|Ys]):-bezHran(Xs,Ys).
    
    otocHrany([], A, A):-!.
    otocHrany([V-Hrany|Vs], A, Vysl) :-pridejHrany(V,Hrany,A,A1),otocHrany(Vs, A1, Vysl).
    
    pridejHrany(_,[],G,G).
    pridejHrany(Kam,[V/Vaha|Vs],A,Vysl):-select(V-Hrany,A,A1),A2 = [V-[Kam/Vaha|Hrany]|A1],pridejHrany(Kam,Vs,A2,Vysl).
    

1. 

    negace(true,false).
    negace(false,true).
    insert(X,Is,[X|Is]).
    
    ohod2([V1-H1,V2-H2],[[V1-NH1,V2-NH2]]):-negace(H1,NH1),negace(H2,NH2),!.
    ohod2([V1-H1|Vs],Vysl) :-negace(H1,NH1),ohod1(Vs,Ts1), maplist(insert(V1-NH1),Ts1,Vysl1),ohod2(Vs,Ts2), maplist(insert(V1-H1),Ts2,Vysl2),append(Vysl1,Vysl2,Vysl).
    
    ohod1([V1-H1],[[V1-NH1]]):-negace(H1,NH1),!.
    ohod1([V1-H1|Vs],Vysl):-negace(H1,NH1),Vysl1=[[V1-NH1|Vs]],ohod1(Vs,Ts), maplist(insert(V1-H1),Ts,Vysl2),append(Vysl1,Vysl2,Vysl).
    

{: style="list-style-type:decimal"}

<{/ForumPost}>