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

Vše co není uvedeno jinde
Vin
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 22. 6. 2009 23:58
Typ studia: Informatika Bc.

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

Příspěvek od Vin »

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]].)
Uživatelský avatar
mifeet
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 27. 1. 2010 14:37
Typ studia: Informatika Ph.D.

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

Příspěvek od mifeet »

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. Kód: Vybrat vše

    rotace(X-X,X-X) :- var(X).
    rotace([X|Xs]-Y,Xs-Z) :- var(Y),Y=[X|Z].
    
  2. Kód: Vybrat vše

    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).
    
  3. Kód: Vybrat vše

    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).
    
  4. Kód: Vybrat vše

    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).
    
Odpovědět

Zpět na „Ostatní“