Declaratieve Talen

Ga naar: navigatie, zoeken
GerdaJanssens.jpg


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 nota's 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?


  • Op de computers staat een bestandje met daarop een uitgebreide specificatie van de opgave, en testwaarden en hun resultaten.

Extra informatie

  • Zeer handig in Hugs: het predicaat help. Deze brengt help op in een apart venster, met daarbij een index, zodat ook onbekende namen van handige predikaten gevonden kunnen worden.
  • 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

een oplossing

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.

een oplossing

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

een oplossing

handelsreiziger verplaatsen

opgave

feiten: Een predikaat dat stelt dat 2 steden buren van elkaar zijn en een predikaat dat stelt dat een stad een hotel heeft.

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

Een bedrijf heeft handelsreizigers en die doen steden aan. 's avonds bellen ze naar het bedrijf en vragen vanuit de stad waar ze nu zijn of er een buurstad is die een hotel heeft. 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.

een oplossing

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.

een oplossing

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]

__________ ** ___________

|__|K_|__|__| ** |__|__|K_|__|

|__|__|__|K_| ** |K_|__|__|__|

|K_|__|__|__| ** |__|__|__|K_|

|__|__|K_|__| ** |__|K_|__|__|

een oplossing

Celautomaat (19 juni 2006)

Ingescande versie van het examen. Klik voor volledige grote.

Een cellulaire automaat is oneindig lang en bestaat uit een rij zwarte (aangeduid door x) en witte cellen (aangeduid door o). Alle cellen voor en achter degene die we in het geheugen hebben, zijn automatisch wit.

Een cellulaire automaat kan overgaan naar een volgende generatie. Hierbij is de nieuwe toestand van een cel enkel afhankelijk van de toestand in de huidige generatie van de linker-, rechter- en huidige cel. Hierbij wordt gebruik gemaakt van regels: [X,Y,Z,N] betekent dat een cel met waarde Y de waarde N krijgt als de linker - en rechtercel respectievelijk waardes X en Z hadden.

Er bestaat de zogenaamde "javel-regel": [o,o,o,o]. Deze garandeert dat de oneindige stukken witte band voor en achter het stuk band in het geheugen wit blijven.

Voorbeeld: ... o x o ... wordt ... o x x o o ... onder de regels [ o, o, x, x ], [ o, x, o, x ], [ x, o, o, o ] en de javelregel

1. Schrijf een predicaat volgendegen( Seq, Regels, Volgende ) dat een volgende generatie berekent van Seq met de gegeven regels indien mogelijk en anders faalt. Hint: voeg 2 witte cellen toe voor en achter je invoer.

2. Schrijf een predicaat regels( Sequenties, Regels ) Hierbij is Sequenties een lijst van achtereenvolgende generaties van de automaat. Regels moet geunificeerd worden met de regels die nodig zijn voor deze transformaties indien dit mogelijk is. De overgang van o x o x o naar o o o o x o o is niet mogelijk omdat voor o x o de x zowel in een o als een x moet veranderen. De regels blijven voor elke generatie-overgang dezelfde. De lijst van regels mag geen dubbels bevatten.

  • Voorbeelden:
    • regels( [ [o, x, x], [o, o, o, x, o], [o, o, o, o, o, o, o] ], X ) geeft

[ [x, x, o, x], [o, x, x, o], [o, x, o, o], [o, o, o, o] ]

    • regels( [ [o, x, o, x, o], [o, o, o, x, o] ], X ) heeft geen geldig resultaat, omdat er geen consistente set regels voor deze overgang bestaat.

Haskell

Algorimte van Dijkstra

Definieer eerst een data type Afstand dat de gehele getallen "bevat" en ook "oneindig". Voeg dat data type toe aan de type class Ord. (zoek de class declaratie van Ord op in de Prelude, dan weet je wat je moet definieren).

I.p.v. een rij Prologfeiten voor de bogen, krijg je twee functies:

boog :: String -> String -> Afstand

die voor twee knopen (die van het datatype String zijn) de lengte van de boog geeft tussen de twee knopen. Die kan "oneindig" zijn. Je mag veronderstellen dat (boog b1 b2) altijd gelijk is aan (boog b2 b1).

De tweede functie is

knopen :: [String]

die als resultaat een lijst met knopen geeft.

Definieer de functie dijkstra::String -> String -> (Afstand,Pad) die tussen twee gegeven knopen een tuppel aflevert met als tweede component een kortste Pad en als eerste component de lengte van dat Pad.

Pad is gedefinieerd als type Pad = [String]

Je mag veronderstellen dat er een pad bestaat.

Algoritme Kortste-pad algoritme van Dijkstra

Gegeven twee verschillende knopen a en z in een samenhangende gewogen graaf G(V,E) met gewichten w voor bogen (x, y); de lengte van een kortste pad van a naar z wordt gevonden door algoritme:

  1. Initialisatie: zet T gelijk aan V en denieer de afbeelding L op V door L(a) = 0 en L(x) = oneindig, voor alle x van V die verschillend zijn van a
  2. Kies volgende: kies een v element van T met kleinste L(v) en haal v uit T
  3. Herbereken L: voor alle knopen y in T die verbonden zijn met knoop v, zet L(y) = min(L(y),L(v) + w(v, y))
  4. Test einde: indien z geen element van T stop anders ga naar Kies volgende.


een oplossing

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")])


een oplossing

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.

2 oplossingen

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]
                                                    ___

een oplossing

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


een oplossing

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

een oplossing

Buurgraden (19 juni 2006)

Ingescande versie van het examen. Klik voor volledige grote.

Een Graaf t wordt voorgesteld in dit soort notatie: Graaf [Knoop naam1, Knoop naam2, ...] [Boog naam1 naam2, Boog naam3 naam4, ...] In de graaf kunnen geen lussen voorkomen. Tussen elke 2 knopen kan hoogstens 1 boog zijn. Bogen zijn ongericht.

  • De graad van een knoop is het aantal bogen dat uit die knoop vertrekt.
  • De buurgraad van een knoop is een lijst met daarin de graden van de buren. Bijvoorbeeld [4,2,2]. De buurgraad is gesorteerd van groot naar klein.
  • De buurgraad van een graaf is een lijst koppels van de buurgraad van een knoop, en de lijst van alle knopen met die buurgraad. Het ziet er uit als dit: [([4,2,2],['a','b']), ([3,2],['c']), ([2,1],['d','e']) ]
  • De buurgraad is gesorteerd, waarbij buurgraden met meer elementen eerst komen en bij even lange buurgraden gewoon de grootste buurgraad wordt genomen (dus [x,y,z] komt voor [u,v]]', en [4,1,1] komt voor [3,2,2])
  1. Schrijf een functie om de buurgraad van een graaf terug te geven.
  2. Indien 2 grafen isomorf zijn, dan zullen er voor elke knoop-buurgraad evenveel knopen in beide grafen zijn. Schrijf een functie nooit_isomorf :: (Graaf t) -> (Graaf t) -> Bool die False teruggeeft indien dit het geval is.

Tip van de persoon die dit examen gehad heeft: zoek eens in de prelude naar sortBy

Je mag ook de module List importeren die een functie sort bevat.
sort::(Ord a) => [a] -> [a]