Declaratieve Talen

Fout bij het aanmaken van de miniatuurafbeelding: Bestand is zoek

Het examen zelf

• Hoe zit het examen tegenwoordig in elkaar?[1]

Het examen DT 2005-2006 is formeel gezien schriftelijk; het gaat door tijdens de zittijden en in de vorm van een sessie in het computerlabo

die 4 uur duurt; tijdens die 4 uur "schrijf" je (emacs, vim, kate ...) een programma in Prolog en Haskell. De programmeeromgeving is dezelfde als

tijdens de begeleide practica: Linux, met SWI Prolog en Hugs. Een deel van de punten staat op aanwezigheid op en werkzaamheid tijdens de

(verplichte) practicumsessies en op het indienen van een oplossing van een opgave binnen de 24 uur na de zitting.

Op die permanente evaluatie staan 6 van de 20 punten.

In de septemberzittijd tellen de punten voor practicazittingen onder het jaar enkel mee als dat in het voordeel is van de student - anders telt

alleen de prestatie in de septemberzittijd.

Tijdens het examen mag de student gebruik maken van de lokale on-line manuals en de slides van de cursus (eventueel met handgeschreven notas

erop). Handboeken, listings met opgeloste oefeningen, extra manuals en elke andere bijkomende informatiebron zijn niet toegelaten.

Uit de omgevingen van Hugs en SWI-Prolog mag alles gebruikt worden - maar niets daarbuiten.

Tijdens het examen is enkel de Hugs en SWI-Prolog omgeving ter beschikking gesteld (on-line, maar lokaal).

Vragen over het examen richt je best niet tot de assistenten.

• welke manuals zijn er juist beschikbaar tijdens het examen van declaratieve talen?

De SWI prolog manual, en de zvon.org documentatie van de prelude.

Remko

Extra informatie

• Haskell introductie

Prolog

graadafstand

opgave

Een graaf G is een stel knopen V met (niet-gerichte) bogen E ertussen - we maken dat soms expliciet door die graaf te noteren als G(V,E). De graad van een knoop v schrijven we als delta(v) en is het aantal bogen dat knoop v als eindpunt heeft.

Als G1(V1,E1) en G2(V2,E2) twee grafen zijn dan noemen we een bijectie f: V1->V2 een knoopbijectie tussen de twee grafen G1 en G2. Voor een gegeven knoopbijectie f tussen G1 en G2, definieren we de f- afstand tussen G1 en G2 als de som over alle knopen k van V1, van de absolute waarde van het verschil tussen de graad van v en de graad van f(v).

De graadafstand tussen twee grafen G1 en G2 met een gelijk aantal knopen, is dan gedefinieerd als het minimum van alle f-afstanden tussen G1 en G2. Schrijf een predicaat graadafstand/3 dat voor twee gegeven grafen G1 en G2 (als eerste en tweede argument - zie later hoe) het derde argument unificeert met de graadafstand tussen G1 en G2.

Een graaf is gegeven door een rij feiten van de vorm:

graaf(8,a,b).
graaf(8,a,c).
graaf(8,a,d).
graaf(22,aa,bb).
graaf(22,aa,cc).
graaf(22,aa,dd).
graaf(15,a,b).
graaf(15,b,c).
graaf(15,a,d).

die betekenen: in graaf 8 is er een boog tussen a en b, ...

Elke boog wordt slechts 1 maal voorgesteld en voor het gemak beschouwen we alleen grafen zonder lussen (een lus is een boog van een knoop v naar v).

Het resultaat van een paar queries:

?- graadafstand(8,22,N).
N=0
?-graadafstand(15,22,N).
N=2
?-graadafstand(8,15,N).
N=2

winkelen

opgave

Een bedrijf stelt orders op van de vorm

[zeep/10, prei/14]

met betekenis dat in deze order 10 eenheden zeep en 14 eenheden prei worden besteld. Het bedrijf heeft een aantal leveranciers, waarvan het voor elk product dat de leverancier aanbiedt de prijs kent - in de vorm:

prijs(delhaize, zeep, 8).
prijs(delhaize, prei, 10).
prijs(delhaize, zout, 6).
prijs(carrefour, prei, 9).
prijs(carrefour, soep, 19).
prijs(champion, zeep, 7).
prijs(champion, prei, 11).
prijs(champion, pinda, 6).

met betekenis: delhaize levert zeep aan 8 Euro per eenheid, enzovoort. Merk op dat niet elke leverancier dezelfde producten levert, en dat de prijzen varieren. Een order kan geplaatst worden bij 1 leverancier, en dan moet de order geplaatst worden bij de leverancier die de beste prijs heeft voor het hele order samen. Voor [zeep/10, prei/14] is dat delhaize, want carrefour kan niet alles leveren, de totaalprijs van delhaize is 10*8+14*10 == 220 en de totaalprijs van champion is 10*7+14*11 == 224.

Een order kan ook gesplitst worden over twee leveranciers (maar nooit meer dan twee) en als dat goedkoper is dan alles door 1 leverancier te laten leveren, dan moet die order gesplitst worden. In het voorbeeld is het beter om de zeep te laten leveren door champion en de prei door carrefour, want dat geeft de laagste totale kost.

Je schrijft een predicaat bestorder/2 dat als eerste argument een order krijgt en het tweede argument unificeert met een beschrijving van hoe dat order moet geplaatst worden. Voor het voorbeeld is dat:

?- bestorder([zeep/10, prei/14], Plaatsing).
Plaatsing = [zeep/champion, prei/carrefour]

De volgorde in Plaatsing is van geen belang. Als er meerdere beste orders zijn, dan geef je er maar 1. Een order kan willekeurig lang zijn.

Voor het gemak is er ook een feit dat aangeeft welke de leveranciers zijn; voor het voorbeeld:

leveranciers([delhaize,carrefour,champion]).

Je kan de gegeven feiten gebruiken om je programma te testen - je mag nieuwe feiten toevoegen voor je testen ook natuurlijk.

Bovenstaande is het eerste (en belangrijkste) stuk van je opdracht. Als je daarmee klaar bent, en je hebt nog tijd, schrijf je - gebaseerd op je predicaat bestorder/2 - een predicaat optimalorder/2, dat uit alle bestorders met dezelfde kost, het order kiest waarop de leverancier(s)s in het totaal het meeste reductie geven: een leverancier geeft reductie gebaseerd op het totaal aantal eenheden dat hij mag leveren, volgens een formule die per leverancier varieert en die gegeven wordt door feiten (voor het voorbeeld):

kortingspercentage(delhaize, E, max(0,min(10,(E-29)/10)) ).
kortingspercentage(carrefour, E, max(0,min(5,(E-10)/7)) ).
kortingspercentage(champion, E, max(0,min(11,(E-50)/9)) ).

Je roept die feiten op met tweede argument een totaal aantal eenheden dat bij die leverancier besteld wordt en als derde argument krijg je terug de formule waarmee je het kortingspercentage kan berekenen. Je programma moet een willekeurige (correcte) formule aankunnen.

• Hoe kan je die input/output omzetten naar de gebruikelijke rijen? --Beau

minimale snede

opgave

Een transportnetwerk is gegeven: het is een samenhangende gerichte gewogen graaf met vanuit knoop a (de bron) alleen vertrekkende bogen en in z (de put) komen alleen maar bogen aan. Een voorbeeldtransportnetwerk is:

boog(a,b,1).
boog(a,c,1).
boog(b,c,1).
boog(c,z,3).
boog(b,z,1).

Je schrijft een predicaat mincut/2 dat voor een gegeven transportnetwerk argument 1 met een minimale snede unificeert en argument twee met de capaciteit van die minimale snede. Een snede in een transportnetwerk wordt bepaald door een partitie in twee disjuncte deelverzamelingen A en Z van de knopen van het transportnetwerk; bovendien zit a in A en z in Z.

De capaciteit van een snede is de som van de capaciteiten van de bogen die van A naar Z lopen. De snede geef je door de term snede(<knopen van A>, <knopen van Z>)

Voor het voorbeeld:

?- mincut(X,Y).
Y = snede([a],[z,b,c])
X = 2
Yes

Als er meer dan q minimale snede is, dan mag je zelf kiezen welke je teruggeeft.

Het vervolg van deze oefening bestaat uit het teruggeven van een minimale snede met zo weinig mogelijk gesneden bogen.

boog(a,b,1).
boog(a,c,1).
boog(b,d,1).
boog(c,d,1).
boog(d,z,2).

heeft als minimale snedes snede([a],[b,c,d,e]) en snede([a,b,c,d],[z]). In de eerste worden de bogen (a,b) en (a,c) gesneden; in de tweede enkel (d,z). Bijgevolg is de tweede het antwoord voor kleinste_mincut/2:

?- kleinste_mincut(X,Y).
Y = snede([a,b,c,d],[z])
X = 2
Yes

handelsreiziger verplaatsen

opgave

feiten: predikaat dat stelt dat 2 steden buur zijn en predikaat dat stelt dat en stad een hotel heeft

buurvan(a,b)   (a is buur van b, maar ook b is buur van a)
heefthotel(a)

Bedrijf heeft handelsreizigers, die doen steden aan, 's avonds bellen ze naar bedrijf, en vragen vanuit de stad waar ze nu zijn, of er een buurstad is die een hotel heeft, en zo ja, dewelke

Maak verplaats([persoon,plaats],moves) waarbij moves moet geunificieerd worden met een mogelijke verplaatsing vanuit 'plaats' naar een buurstad met een hotel.

?- verplaats([(ik,leuven),(jij, gent)],X)
X = [(ik,leuven,brussel),(jij,leuven,ietsbuitengent)]

Maak verplaats_beste die met dezelfde argumenten, de weg geeft naar een hotel in de minste moves.

Keigrafen [Examen juni 2005]

Opgave

(Ik probeer hier de vraag te reconstrueren ...)

We werken met knopen in een ongerichte grafe. Elk knooppunt bevat geen, 1 of meer keien. Je kunt keien van knooppunt als volgt verplaatsen:

1. de bron bevat n knopen (n > 0)
2. je verplaatst x knopen (1 <= x <= n)
3. de bron verliest deze x knopen
4. het doel ontvangt x - 1 knopen (1 knoop gaat dus verloren!)

Een knoop is kei_bereikbaar als je na een eindig aantal (0 of meer) verplaatsingen van keien 1 of meer keien in de knoop hebt.

Een grafe is kei_goed als alle knopen kei_bereikbaar zijn.

Een grafe is kei_nijg als alle knopen TEGELIJK kei_bereikbaar zijn (en je met andere woorden na een eindig aantal verplaatsingen van keien in elke knoop minstens 1 kei hebt).

Opgave is simpel: schrijf prolog-code die deze eigenschappen berekent.

N-queens

Opgave

Schrijf een genereer-en-test programma voor het N-queens probleem, ttz zet N koninginnen op een NxN schaakbord, zodat geen enkele koningin door een andere geslagen kan worden. Je mag gelijk welke voorstelling van een bord gebruiken, maar je levert als resultaat een lijst van rijen waarin opeenvolgende koninginnen staan: bv. nqueens(4, L) -> L = [2, 4, 1, 3] Deze oplossing zegt dat de koningin in kolom 1 op rij 2 staat, in kolom 2 op rij 4, ...

Te vinden oplossingen: [2, 4, 1, 3] [3, 1, 4, 2] Fout bij het parsen (syntactische fout): {\displaystyle _____________ _____________ |__|K_|__|__| |__|__|K_|__| |__|__|__|K_| |K_|__|__|__| |K_|__|__|__| |__|__|__|K_| |__|__|K_|__| |__|K_|__|__| }

Haskell

graaf isomorfie

Een graaf G(V,E) wordt bepaald door zijn vertices V en bogen (edges) E. Daarbij is E een deel van VxV, de gerichte bogen van G zijn van de vorm (v,w) met v en w in V.

De gerichte graaf G1(V1,E1) is isomorf met de gerichte graaf G2(V2,E2) indien er een bijectie b bestaat van V1 naar V2, die een bijectie f induceert van E1 naar E2 als volgt:

f((v,w)) = (b(v), b(w))

Schrijf een functie iso die twee isomorfe grafen als argumenten neemt en de knopenbijectie tussen de twee (de functie b van hiervoor) aflevert. Die knopenbijectie beschrijf je door een lijst van koppels waarbij elk koppel van de vorm (v,b(v)) is, dus de eerste component zit in V1 en de tweede in V2. Je moet expliciet nagaan dat de geinduceerde f een bijectie is natuurlijk.

De grafen worden gegeven als een tuple met als eerste component een lijst van de knopen, en als tweede component een lijst van de bogen. Een boog is een tuple met de twee eindpunten van de boog als component. De grafen zijn niet gericht.

Je functie moet polymorf zijn in het type van de knopen. Dus volgende 2

iso (["a","b"],[("a","b")]) (["c","d"],[("c","d")])
iso (["a","b"],[("a","b")]) ([1,2],[(1,2)])

moet kunnen - de eerste geeft bijvoorbeeld [("a","d"), ("b","c")] als antwoord en de tweede bijvoorbeeld [("a",1), ("b",2)]

Als er verschillende isomorfismen bestaan, dan maakt het niet uit welk er als antwoord gegeven wordt.

Als je daarmee klaar bent gebruik je de essentie van wat je al schreef voor het vervolg van de opgave: je gaat een functie schrijven die het graaf-subisomorfisme probleem oplost. De functie heet subiso en ze krijgt twee grafen als invoer. subiso bepaalt of de eerste isomorf is met een subgraaf van de tweede. Een graaf is een subgraaf van een andere als ze een deel van de bogen en knopen ervan heeft. subiso heeft als resultaat True of False al naar gelang ... Twee voorbeelden:

?- subiso (["a","b"],[("a","b")]) ([1,2],[(1,2)])
True
?- subiso (["a","b"],[(["a","b")]) ([1,2,3],[(1,2),(2,3)])
True

want ([1,2,3],[(1,2),(2,3)]) bevat ([1,2],[(1,2)]) als deelgraaf en die is isomorf met (["a","b"],[(["a","b")])

?- subiso (["a","b"],[(["a","b")]) ([1,2,3],[])
False

want geen enkele deelgraaf van ([1,2,3],[]) is isomorf met (["a","b"],[(["a","b")])

Boom Betegelen [examen 2005, augustus]

Opgave

We krijgen een boom en een hoop tegels waarmee de boom moet bedekt worden. De boom is nogal heterogeen (niet elke knoop heeft hetzelfde aantal kinderen) en daarom hebben we een declaratie:

data Boom t = Knoop1 t (Boom t) | Knoop2 t (Boom t) (Boom t) | Blad t
data Tegel t = Tknoop1 t (Tegel t) | Tknoop2 t (Tegel t) (Tegel t) | Tblad t | Leeg

Om een tegel op de top van een boom te kunnen leggen:

• moeten de overeenkomstige waarden gelijk zijn
• moet een Knoop1 met een Tknoop1, Tblad of Leeg overeenkomen
• moet een Knoop2 met een Tknoop2, Tblad of Leeg overeenkomen
• moet een Blad met een Tblad of Leeg overeenkomen

Op die manier is misschien niet alles van de boom bedekt door die tegel in de top en blijven er nog stukken boom over: elk van die stukken is zelf een boom die dan misschien weer getegeld worden in zijn top. Als er geen stukken meer overblijven hebben we een tegeling van de hele oorspronkelijke boom.

Een boom heeft dus een tegeling indien de top kan bedekt worden en indien elke deelboom die dan overblijft ook bedekt kan worden met die verzameling tegels. Je schrijft een functie tegel die als argumenten een boom krijgt en een lijst met tegels. Als resultaat geeft de functie True indien er een tegeling bestaat en False indien niet. Elke tegel mag 0, 1 of meerdere keren gebruikt worden.

Min-max

Opgave

maak een algoritme minimax die een spelboom doorloopt en aanpast:

spelboom = doosboom (id, [bolbomen], winst) | bolboom (id, [doosbomen], winst)

• id is voor iedere knoop verschillend (en integer)
• winst is in het begin een integer voor de bladeren (die zonder deelbomen) en "nog niet beslist" voor de andere knopen

bedoeling is om winst in te vullen bij het doorlopen van de boom, zodat in een doosboom het maxx van de sub-bol-bomen komt en in een bolboom het min van de sub-doos-bomen.

                     ["nog niet beslist"]
("nog niet beslist") ("nog niet beslist") ("nog niet beslist")
       [1][2]              [3][4]               [5][6]

--->

        [5]
 (1)    (3)   (5)

[1][2] [3][4] [5][6]

bijvraag: maak een algoritme dat het pad teruggeeft dat moet gevolgd worden bij optimale keuze:

                                      [5]
                                      ___
                          (1)         (3)         (5)
                                                  ___
                      [1] [2]       [3][4]       [5][6]
                                                    ___

oneindige rij

Opgave

maak een oneindige rij van een datatype t.

geg: een variabele van dat type een functie die een rij van t's omzet naar een t waarbij iedere keer de functie wordt toegepast op de hele vorige rij.

bvb. infinite 1 sum (sum is een functie uit prelude, die de som neemt van alle elementen uit de rij die die meekrijgt)

[1,1,2,4,8,16,32,..]

ieder getal is de som van alle voorgaande

Formule-boom [examen juni 2005]

Opgave

(Ik probeer hier de vraag te reconstrueren ...)

Maak een datatype dat een logische formule voorstelt (En, Of, Wel, Niet)

Maak vervolgens ook een datatype dat een formule voorstelt als een boom:

1. Vertakking uit knoop 'a' naar links betekent "Wel a", vertakking naar rechts betekent "Niet a"
2. Als bladeren moet je "T" of "F" geven. T = True = "dit pad is geldig", terwijl F = False = "dit pad geldt niet"

Om dit wat visueler te maken:

                     ___a___
                    /       \
                  _b_       _c_
                 /   \     /   \
                T     F   T     F

betekent zoveel als: "[(Wel a) En (Wel b)] Of [(Niet a) En (Wel c)]

Een boom kun je dus telkens tot een logische formule omvormen. Maak nu dus een procedure die voor een gegeven boom en een gegeven logische zin nagaat of de boom de zin al dan niet beslist.

Test met volgende regels:

Main> boom_is_formule tree1 form1
True
Main> boom_is_formule tree2 form1
False