Neprocedurální programování - písemka z Prologu 15.4.2010
Napsal: 15. 4. 2010 20:03
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]].)
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]].)