Declaratieve Talen

Ga naar: navigatie, zoeken
GerdaJanssens.jpg

Inhoud

Samenvattingen

Klik hier om de samenvattingen te bekijken

Het examen zelf

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

Het examen DT 2011-2012 is formeel gezien schriftelijk; het gaat door tijdens de zittijden in de vorm van een sessie in het computerlabo die 4 uur duurt. Het examen bestaat enerzijds uit enkele kleine vragen over de leerstof en anderzijds "schrijf" je (emacs, vim, kate ...) een programma in Prolog en Haskell. De programmeeromgeving is dezelfde als tijdens de begeleide practica: Linux, met Prolog en Haskell. Een deel van de punten staat op aanwezigheid op en werkzaamheid tijdens de (verplichte) practicumsessies en op het indienen van een oplossing van de opgaves (inclusief practicum) binnen de 24 uur na de zitting. Op die permanente evaluatie staan 5 van de 20 punten.

Vanaf ten laatste academiejaar 2016-2017 lijken de begeleide practica/gequoteerde oefenzittingen meer op kleine examens: je krijgt 2u en je moet je oplossing indienen op het einde van de sessie. Wel is er geen theorie.

Niet tolereerbare tekorten: het schriftelijk examen tijdens de zittijd. 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 de gebruikte Prolog en Haskell systemen mag alles (inclusief de manual) gebruikt worden - maar niets daarbuiten. Vragen over het examen richt je best niet tot de assistenten.

  • In de slides van 2017-2018: Meebrengen: enkel slides van de lessen en de Haskell tekst (eventueel met handgeschreven nota’s erop).
  • Uit de omgevingen van GHC en SWI-Prolog mag alles gebruikt worden - maar niets daarbuiten.
  • Er is geen internet-toegang.
  • Welke manuals zijn er juist beschikbaar tijdens het examen van declaratieve talen?
    • Een offline versie van de SWI prolog manual, en de zvon.org documentatie van de prelude.
    • Hoogle is niet beschikbaar.
  • Op de computers staat een bestandje met daarop een uitgebreide specificatie van de opgave, en testwaarden en hun resultaten.

Extra informatie

  • Zeer handig in swi-prolog: 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

Gequoteerde oefenzittingen

Officieel zijn deze van een beetje makkelijker niveau dan de examenvragen, in de praktijk kan dit wel eens variëren. Het is aangeraden om concepten die niet of zelden in de oefeningen aan bod komen (Just, Maybe, Either, definiëren eigen typeclasses ...) goed theoretisch te bekijken, dit betekent namelijk niet dat ze niet gevraagd kunnen worden.


Media:Oefz_Prolog_2018_1.zip

Media:Oefz_Prolog_2018_2.zip

Media:Oefz_prolog_2017_1.zip

Media:Oefz_prolog_2017_2.zip

Media:Haskell-15-12-2016.zip

Media:Haskell-14-12-2016.zip

Media:Prolog-10-11-2016.pdf

Media:Prolog-09-11-2016.pdf

Bestand:Gequoteerde-Oefenzitting-prolog-2016.tar.gz

Media:Haskell-2014-(MOPL).zip

Vakevaluatie

Elk puntje hieronder is iemands mening. Verander aub geen puntjes. Als je een andere mening hebt, gelieve ze onderaan toe te voegen.

Kwaliteit cursus (prijs, duidelijkheid, overeenkomst met les, ...)

  • 2017: De slides van Prolog zijn nogal beknopt. Voor Haskell is er een goed boek.

Studiebelasting (aantal studiepunten in verhouding met bestede tijd)

  • 2017: Doenbaar als je tijdens het jaar meebent. Je moet bijna (geen) theorie studeren, maar enkel oefeningen maken.

Plaats binnen de opleiding (nodige voorkennis, overlap met andere vakken, relevantie van het vak,...)

  • 2017: Prolog bouwt verder op logica en automatisch redeneren uit AI. Voor de rest is het gewoon een programmeervak.

Manier van lesgeven bij hoorcolleges (snelheid, verstaanbaarheid, structuur, nut, ...)

  • 2017: Gerda Janssens legt het naar mijn mening niet op een interssante manier uit. Tom Schrijvers (Haskell) vond ik beter. De oefenzittingen zijn veruit het belangrijkste voor dit vak.

Evaluatie oefenzittingen/labo's (nut, begeleiding, ...)

  • 2017: Ok. Vrij standaard.

Examen (mate waarin het een weerspiegeling is van de cursus, examenvorm, ...)

  • 2017: Twee grote vragen: 1 voor Prolog en 1 voor Haskell. Ze zijn volledig in dezelfde stijl als de gekwoteerde oefenzittingen: kleine deelopdrachten die je op weg helpen. Als je gekwoteerde oefenzitting goed was, dan zal dat voor het examen waarschijnlijk ook zo zijn.


Examenvragen

Kleine vraagjes

18 januari 2018

  • Waarom werk je in Prolog met staartrecursie?
  • Waarom is Haskell lui? Wat zijn de voordelen?
  • Waarom is pattern matching in Haskell een specifieke vorm van unificatie?

16 januari 2018

  • Geef een voorbeeld van partiële instantiatie in Prolog.
  • Wat is een accumulerende parameter?
  • Waarvoor wordt Maybe gebruikt in Haskell?

15 januari 2018

  • Wat doet backtracking in Prolog?
  • Wat is currying en hoe werkt het?
  • Wat is structurele recursie?

19 januari 2017

  • Wat is een accumulerende parameter?
  • Geef een voorbeeld van laziness in Haskell en bespreek.
  • Wat is structurele recursie?

18 januari 2017

  • Wat zijn difference lists?
  • Wat is structurele recursie?
  • Waarom gebruikt Haskell monads voor I/O?

15 januari 2015

  • Waarom gebruikt prolog clause indexing?
  • Geef het meest algemene type van >>= en leg informeel met eigen woorden uit?
  • Bespreek het verschil tussen unificatie en pattern matching.

16 januari 2014

  • Waarom werken we met failure-driven loop?
  • Welke invloed heeft prescriptieve modes op de efficiëntie in Mercury?
  • Bespreek het verschil tussen pattern matching en guards.

15 januari 2014

  • Waarom gebruiken we in Prolog de 'most general unifier' (mgu) en niet een unifier?
  • Bespreek de functie van typeklassen in Mercury.
  • Wat zijn de voor- en nadelen van laziness in Haskell?

16 januari 2013

  • Waarom gebruiken we in Prolog de 'most general unifier' (mgu) en niet een unifier?
  • Waarom werken we met failure-driven loop?
  • Wat zijn de voor- en nadelen van laziness in Haskell?

24 augustus 2012

  • Bespreek het verschil tussen open-ended lists en difference lists
  • Bespreek het verschil tussen patterns en constructors
  • Geef de definitie van een declaratieve programeertaal

19 januari 2012

  • Bespreek het verschil tussen "open-ended" lists en verschillijsten (difference lists)
  • Bespreek het verschil tussen pattern matching en guards.
  • Wat is de functie van typeklassen in Haskell (en Mercury)

19 januari 2011

  • Bespreek het verschil tussen unificatie en pattern matching.
  • Wat doet backtracking in Prolog
  • Wat zijn de voor en nadelen van luie uitvoering in Haskell?

12 januari 2009

  • Bespreek het verschil tussen unificatie en pattern matching
  • Wanneer doet prolog aan garbage collecting
  • Hoe is in Haskell sprake van generisch programmeren

13 januari 2010

  • Bespreek het verschil tussen unificatie en pattern matching.
  • Bespreek meta-programmatie in Prolog.
  • Wat zijn de voor en nadelen van luie uitvoering in Haskell?

14 januari 2010

  • Bespreek het verschil tussen unificatie en pattern matching
  • Hoe doet Prolog aan backtracking
  • Wat is de functie van typeklassen in Haskell (en Mercury)

Oplossingen

Prolog

Belichting (18 januari 2018)

Je krijgt een rooster (denk doolhof) van 7x7 vakjes, waarin enkele muren geplaatst zijn. De bedoeling is om een aantal lampen in het rooster te plaatsen zodat alle vakjes verlicht zijn. Elke lamp belicht zijn volledige rij en kolom, tenzij er een muur in de weg staat. Op een muur kun je geen lamp zetten, en een lamp kan niet door een muur schijnen. Op sommige muren staat een "hint" zoals in Minesweeper. Die geeft aan op hoeveel naburige vakjes (d.w.z. degene die een zijde gemeenschappelijk hebben) er een lamp moet staan. Verder mag geen enkele lamp op een andere schijnen.

De datastructuur wordt voorgesteld als een verzameling feiten:

wall(X,Y)
hint(X,Y,AantalLampen)

Opdrachten:

  • Schrijf een predicaat lit(X,Y, Lampen) dat aangeeft of het vakje op positie (X,Y) verlicht is door een van de meegegeven lampen. De lampen worden voorgesteld als Prolog-termen(light(X,Y))
  • Schrijf een predicaat neighbours((X1,Y2), (X2, Y2)) dat (X2,Y2) unificeert met een buur van (X1,Y2) die in het bord ligt en geen muur is.
  • Schrijf een predicaat forbidden(X,Y,Fulls) dat aangeeft of de positie (X,Y) zich naast een vakje bevindt uit de lijst Fulls. De betekenis van Fulls is een lijst met vakjes waarop een hint staat (d.i. er moeten N omringende lampen zijn) en waarbij er al N lampen rond dat vakje staan.
  • Schrijf een predicaat light(Lights) dat de puzzel oplost. Het is aangewezen om hierbij te steunen op vraag 3. Als hulpmiddel kun je eerst de volgende predicaten schrijven:
    • light_hints (ariteit zelf te bepalen) dat het correcte aantal lampen rondom de vakjes met een hint zet.
    • light_remaining (ariteit zelf te bepalen) dat met een gedeeltelijke oplossing gegeven door light_hints de rest van de puzzel oplost.

Palindromen (15 januari 2014)

Een palindroom is een woord dat in beide richtingen hetzelfde leest. Zo zijn lepel, 1221 en stormrots palindromen. We willen een programma schrijven dat in staat is elk woord om te vormen tot een palindroom. We mogen elk teken veranderen in een ander teken om ons doel te bereiken. Hiervoor gelden volgende regels:

  • Een letter veranderen kost €1
  • Als je één letter vervangt moet je onmiddellijk alle voorkomens van deze letter vervangen.

Neem als voorbeeld [r,e,d,e]. We kunnen dit oplossen als volgt:

  • Verander 'e' in 'r' -> [r,r,d,r].
  • Verander 'd' in 'r' -> [r,r,r,r].

Met totale kost €3. Het is echter makkelijk in te zien dat dit niet de goedkoopste manier is. Als je 'r' en 'd' in 'e' veranderd krijg je de palindroom [e,e,e,e] met kost €2.

Opdracht 1: Schrijf een predikaat allesgelijk(Seq1,Kost,Seq0) dat gegeven een sequentie Seq1 de goedkoopste sequentie Seq0 vindt met alle elementen gelijk, dus waarvan de Kost van de transformatie minimaal is. Indien er meerdere oplossingen met dezelfde minimale kost zijn, geef deze dan allemaal.

bv.

allesgelijk([r,e,d,e],Kost,Seq0).
  Kost = 2
  Seq0 = [e,e,e,e]

allesgelijk([a,b],Kost,Seq0).
  Kost = 1
  Seq0 = [a,a]
of
  Kost = 1
  Seq0 = [b,b]

Opdracht 2: Schrijf een predikaat palindroom(Seq1,Kost,Seq0) dat gegeven een sequentie Seq1 het goedkoopste palindroom Seq2 vindt. Merk hiervoor op dat elke sequentie kan opgedeeld worden in een aantal disjuncte sequenties die gelijk gesteld moeten worden. Bv. abyxzbzxxcb -> ab..b..cb, yx..xx en z..z. Indien er meerdere goedkoopste oplossingen zijn, geef ze dan allemaal.

bv.

palindroom([a,b,y,x,z,b,z,x,x,c,b],Kost,Seq0).
  Kost =  3
  Seq0 = [b,b,x,x,z,b,z,x,x,b,b]

Oplossing(en)

Jan heeft stenen (16 januari 2013)

Jan speelt graag met stenen. Hij heeft er een hele hoop die allemaal rechthoekig zijn. Elke steen heeft een andere kleur. Jan heeft ook een speelveld waarop hij de stenen kan leggen. Hij kan stenen op elkaar leggen. Niet alle stenen zijn evengroot. Zo kunnen we een speelveld voorstellen als volgt:

[[.,c,c,.], [a,c,c,a], [a,c,c,a]]

waarbij a en c kleuren zijn, en "." de afwezigheid van kleur aangeeft.

Hier een illustratie van het voorbeeld:

PrologJanStenen.jpg

Vraag 1: Maak een predicaat "maakrechthoeken" om de posities van alle stenen als volgt te bepalen (voor het voorbeeld): [a-rhk(1,4,2,3),c-rhk(2,3,1,4)] waarbij een de waarden corresponderen met respectievelijk Index van Leftmost occurence,Rightmost occurence, lowesttopoccurence, highestbottomoccurence. (het assenstelsen van het veld is dus een standaard 2 dimensionaal x,y-vlak waarbij de y-as ondersteboven staat).

Vraag 2: Maak een predicaat "plan" dat de volgorde bepaalt waarin de rechthoeken gelegd zijn. Indien er meerdere mogelijkheden zijn, geef dan gesorteerd met @</2.

Oplossing(en)

Contradicties (01.09.2010)

Er worden multiple choice vragen gesteld. De persoon moet zijn voorkeur duidelijk maken. Zo verkiest jan (zie gegevens) c boven antwoorden a, b, d en e. Omdat mensen niet altijd consequent zijn, kunnen er tegenstrijdige antwoorden gegeven worden. Zo wordt in het voorbeeld i verkozen boven j, maar ook j boven i!

(opnieuw verzonnen)Gegevens: 
*antwoord(jan,c,[a,b,d,e])
*antwoord(jan,i,[f,k,c,b])
*antwoord(jan,j,[i,f,h,e])
*antwoord(jan,k,[j,h,g,d])

1. Maak een predicaat meetegen(P,A) met als argumenten de persoon en een antwoordletter, dat teruggeeft of die antwoordletter in contradictie is met een andere antwoordletter. Hint: Hoe zou je in een graaf zien dat er een contradictie is?

2. Maak een predicaat tegen(P,Tegens) dat Tegens unificeert met een lijst van groepcontradicties. Zo'n groepcontradictie is een deelverzameling van alle antwoordletters, waarvan elk koppel een contradictie veroorzaakt. Zo'n deelverzameling bestaat dus uit minstens 2 elementen en zijn strikt verschillend (er mag geen antwoord in 2 groepcontradicties zitten). Voor het vb. krijg je dan:

Tegens = [[i,j,k]]

Oplossing(en)

Productie van mijnen (13 januari 2010)

Korte beschrijving: De productie van 2 mijnen hangt af van de voedsel leveringen die aan de mijn gedaan worden. Er zijn 3 soorten voedselleveringen. De productie van de mijn hangt af van hoeveel verschillende soorten er in de laatste 3 leveringen gebeurd zijn. Als er 1 soort is, produceert de mijn die dag 1 ton, als er 2 soorten voedsel geleverd werden in de laatste 3 leveringen, produceert de mijn 2 ton,...

vb:

  • [1-v,2-v,3-v]=>tijdens levering 1 wordt type v geleverd, levering 2 type v levering 3 type v dus => 1+1+1=3ton totaal
  • [1-v,2-g,3-f]=>1+2+3=6ton totaal
  • [1-v,2-g,3-f,4-g]=>1+2+3+2(alleen de laatste 3leveringen bekijken)=8ton totaal

Als een mijn strict minder dan de helft aantal leveringen van de andere mijn ontvangen heeft krijgt deze mijn voorrang.

Schrijf een predicaat dat de scenario bepaald met een maximum productie. maxproductie(Leveringen,Scenario).

vb:

  • maxproductie([1-v,2-g,3-f,4-g,5-v,6-v,7-f],toestand(15,mine([7-f,6-v,4-g,3-f,1-v]),mine([5-v,2-g])).

Er was ook een bonusvraag indien je snel genoeg was.

Oplossing(en)

Leren werken in teamverband (15 januari 2009)

De visitatiecommisie vindt het heel belangrijk dat cw studenten in hun opleiding leren werken in teams. Het is echter opvallend dat cw studenten geneigd zijn om telkens in dezelfde teams te werken. De docenten willen vermijden en besluiten dat de studenten vanaf nu hun teams anders moeten kiezen: twee studenten mogen gedurende heel hun opleiding maar 1 keer in hetzelfde team zitten.

Wij zullen een Prolog programma schrijven voor de verdeling van de studenten over de teams. We gaan ervan uit dat er T teams zijn en dat in elk team S studenten zijn. De bedoeling is om uit te vissen hoeveel groepswerken er tijdens de opleiding van een student gepland kunnen worden zodat de nieuwe regel gerespecteerd wordt. Gemakshalve wordt verondersteld dat het goede studenten zijn en dat dus de groep van studenten gedurende de opleiding hetzelfde blijft.

Deel 1

Schrijf een predikaat verdeling(T,S,Verdeling) dat in het geval van T teams en S Studenten per team een mogelijke verdeling van de studenten geeft. Bijvoorbeeld voor verdeling(2,2,V) geeft dit V = [[1,2],[3,4]]. Om dit probleem in een redeljke tijd te kunnen oplossen willen we vermijden dat dezelfde verdeling verschillende keren gegeneeerd wordt. De verdeling [1,2],[3,4]] is in feite herzelfde als [[2,1],[3,4] en [[4,3], [2,1]], maar is duidelijk verschillend van [1,3],[2,4]]. (Personal note: bedoeld wordt dat [1,2,3] en [1,2,4] dezelfde teams zijn omdat 1 en 2 al bij elkaar gezeten hebben, de opgave was hier dus licht dubbelzinnig.)

In het reultaat van verdeling zijn daarom de elementen van de teams geordend van klein naar groter en is er ook een orde opgelegd aan de teams zelf. Deze worden geordend op hun kleinste element. [1,2][3,4] is ok, maar [3,4][1,2] niet.

? - verdeling(2,2,V).
V = [[1, 2], [3, 4]];
V = [[1, 3], [2, 4]];
V = [[1, 4], [2, 3]];

No

Deel 2

Schrijf een predikaat groepeer(T,S,W, Schedule) dat gegeven het aantal teams T het aantal studenten per team S en het aantal werkjes W een geldig schedule Schedule opstelt. Als er geen oplossing is dan faalt het predikaat.

? - groepeer(2,2,3,Schedule).
Schedule = [[[1,2],[3,4]], [[1,3],[2,4]], [[1,4],[2,3]]] ;

No

?- groepeer(4,3,3, Prt). %de vele [ en ] er zelf bijdenken
Prt = [[[1 2 3] [4 5 6] 7 8 9  10 11 12
 1 4 7  2 5 10  3 8 11  6 9 12
 1 5 8  2 4 12  3 9 10  6 7 11 ;

Prt = 1 2 3  4 5 6  7 8 9  10 11 12
 1 4 7  2 5 10  3 8 11  6 9 12
 1 5 9  2 6 11  3 7 12  4 9 10 ;

...

?- groepeer(2,3,2, Prt).
No.

Merk op dat ook in het antwoord de verdelingen opnieuw geordend zijn van klein naar groot. Voor sommige queries (bijv groepeer(4,3,3, P) kan je verschillende alternateive antwoorden krijgen).

Deel 3

Uiteindelijk kan je dan het aantal werkjes gaan bepalen. Schrijf een predikaat aantalwerkjes(T,S,W) dat gegeven het aantal teams T en het aantal studenten per team S het aantal werkjes bepaalt.


Oplossing(en)

Logische gevolgen (12 januari 2009)

Opgave

De vraag bestond uit twee grote delen:

Deel 1: sluitingen

Schrijf een predicaat sluiting(S,F,Sluiting). Dit predicaat slaagt indien S een verzameling is, F een lijst van logische gevolgen ([a]>>[b,d] betekent uit a volgt b en d) en Sluiting de sluiting is van S onder F. Hiermee wordt bedoeld dat Sluiting alles is wat uit S volgt. Even enkele voorbeeldjes ter verduidelijking:

F1=[[a]>>[b,d],[b,d]>>[c]],
sluiting([a],F1,Sluiting).
--> Sluiting = [a,b,d,c]
F2=[[a]>>[b,d],[b,d]>>[c],[e]>>[f]],
sluiting([e],F2,Sluiting).
--> Sluiting = [e,f]
Deel 2: redundanties

Een implicatie wordt redundant genoemd (in een lijst van implicaties) indien ze het logisch gevolg is van een aantal andere van die implicaties. Bijvoorbeeld: als

F3=[[a]>>[b,d],[b,d]>>[c],[a]>>[c]]

dan is [a]>>[c] redundant want het gevolg van de andere twee. Schrijf een predicaat alleredundante(F,X) dat als eerste argument een lijst met implicaties krijgt en als tweede argument alle redundante uitspraken teruggeeft (samen met een minimale deelverzameling van F waaruit de redundantie volgt). Weer enkele voorbeeldjes:

F3=[[a]>>[b,d],[b,d]>>[c],[a]>>[c]],
alleredundante(F3,X).
-->X = [ redundant([a]>>[c],[[a]>>[b,d],[b,d]>>[c]]) ]
F4=[[a]>>[b],[b]>>[d],[a]>>[c],[a]>>[d],[c]>>[d]],
alleredundante(F4,X).
-->X= [redundant([a]>>[d],[[a]>>[b],[b]>>[d]]),redundant([a]>>[d],[[a]>>[c],[c]>>[d]])]

Oplossing(en)

Huffman-encodering (25 januari 2008)

Opgave

Bij een Huffman encodering krijgt elk symbool een bepaalde code toegekend. Deze code is zodanig opgesteld dat er geen enkele code een prefix is van een andere code. Bijvoorbeeld de code [0-[1,1],1-[0],2-[1,0]] is een Huffman code, de code [0-[0,1],1-[0],2-[1]] niet. Je krijgt een gecodeerd "bericht" waarvan de encoderingssleutel is verloren gegaan. De codes staan in volgorde van index, maar de 'scheidingen' tussen de codes zijn verdwenen. Zoek de mogelijke decoderingen. Bvb:

decodeer(3,[1,1,0,1,0],Res).
Res = [0-[1,1],1-[0],2-[1,0]];
No.

Immers, voor 0 kunnen we niet [1] nemen, want dan zou 1 ook moeten beginnen met [1] en dan is 0 een prefix van 1. Door analoge redeneringen blijkt dit de enige mogelijke toewijzing te zijn. Soms zijn er meerdere decoderingen mogelijk.

decodeer(2,[1,0,0],Res).
Res = [0-[1,0],1-[0]];
Res = [0-[1],1-[0,0]];
No.

Niet elke code is "even goed". Als we een bepaald symbool dikwijls gebruiken in de tekst is het beter daar een kleine encodering voor te hebben. Maak een predicaat beste/4 dat de best mogelijke encodering zoekt, gegeven de argumenten als in decodeer en een frequentietabel waarin staat hoe dikwijls een bepaald symbool voorkomt in de tekst. Voorbeeld:

Freqs = [0-1,1-5],beste(2,[1,0,0],Freqs,Res).
Res = [0-[1,0],1-[0]];

Freqs = [0-10,1-5],beste(2,[1,0,0],Freqs,Res).
Res = [0-[1],1-[0,0]];

een oplossing

alternatieve oplossing

oplossing mbv boom

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 v 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

Oplossingen

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 1 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,z]) 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 (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 keien (n > 0)
  2. je verplaatst x keien (1 <= x <= n)
  3. de bron verliest deze x keien
  4. het doel ontvangt x - 1 keien (1 keien 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.

Opgave

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] ] (Opmerking: ik denk dat hier enkele regels ontbreken? Volgens mij moeten deze er nog bij: [o, o, x, o], [x, o, o, o], [o, x, 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.

een oplossing

Haskell

E-Mailserver (18 januari 2018)

Noot: Het lijkt erop dat de focus bij Haskell tegenwoordig ligt op ADTs, het schrijven van enkele relatief eenvoudige functies, en een grote vraag in verband met I/O, dus zowat dezelfde structuur (en moeilijkheidsgraad) als bij de gequoteerde oefenzittingen. Er was ook een skelet gegeven met typesignaturen, maar dat stelde niet veel voor.

  • Definieer een datatype voor een e-mail waarbij je de afzender, ontvanger, tijd van verzending, status gelezen/ongelezen, onderwerp, en inhoud voorstelt. Maak een instantie voor Show, Eq (mails die op hetzelfde ogenblik zijn verstuurd, zijn gelijk), en Ord, die vergelijkt volgens tijd van verzending.
  • Definieer een datatype MailServer dat een lijst van e-mails bevat. Maak een instantiatie voor Show.
    • Implementeer een functie om alle mails van een bepaald tijdstip als gelezen te markeren
    • Implementeer een functie om aan een mailbox een bericht toe te voegen, tenzij er al een bericht inzit dat op hetzelfde tijdstip verstuurd is
  • Implementeer voor elk van de volgende zoekoperaties over de server een functie die de zoekopdracht uitvoert:
    • alle berichten van een gegeven afzender, gesorteerd volgens oplopende verzendtijd
    • alle berichten naar een gegeven ontvanger, gesorteerd
    • alle ongelezen berichten naar een gegeven ontvanger, gesorteerd
    • alle berichten die tussen twee gegeven tijdstippen zijn verzonden, gesorteerd
    • alle berichten waarvan het onderwerp een gegeven substring bevat (Hint: gebruik isInfixOf uit Data.List)
    • alle berichten waarvan het lichaam een gegeven substring bevat
    • alle berichten waarvan het onderwerp of het lichaam een gegeven substring bevat (zorg dat er geen dubbels voorkomen)
  • Schrijf een functie main_loop :: Time -> MailServer -> IO () die vraagt naar een commando en op basis vaan het antwoord een juiste actie kiest.
    • exit: druk "Exiting normally." af en beeindig de uitvoering van het programma.
    • send: vraag naar een zender, ontvanger, onderwerp, en inhoud, en voeg de mail toe aan de server. Die mail wordt verstuurd op het huidige tijdstip en is uiteraard nog niet gelezen. Herhaal dan de lus, met als tijdstip t+1
    • read: vraag naar een persoon en een tijdstip en print alle mails die op het gegeven tijdstip zijn gestuurd. Markeer deze als gelezen en herhaal de lus op het volgende tijdstip
    • search: vraag naar een zoekterm en druk alle mails af die die zoekterm in het onderwerp of lichaam bevatten. Herhaal de lus op het volgende tijdstip.
    • Voor andere commando's druk je een foutmelding af en herhaal je de lus zonder de tijd te verhogen.

De functie main was al gedefinieerd en riep main_loop op met als argumenten 0 (tijdstip) en een lege e-mailserver.

Foto's van ballen (16 januari 2013)

Gegeven een 1-dimensionale-ruimte met daarin een aantal ballen. Op tijdstip 0 nemen we er een foto van. Omdat we in een heel eenvoudige omgeving werken kunnen we de foto als volgt weergeven: [10,12] waarbij 10 en 12 de posities van bal 1 en bal 2 zijn. Wanneer de tijd 1 eenheid vooruitgaat, verplaatsen alle ballen precies 1 positie naar links of naar rechts. Ballen bewegen altijd in dezelfde richting. Ballen mogen nooit tegen elkaar botsen. Ook, elke keer de tijd vooruit gaat, wordt er 1 extra bal in de bak geplaatst. Vb: Foto 1 = [10,12] Foto 2 (na 1 stap) = [9,10,13]

Vraag 1: Schrijf een functie berekenMappings die als invoer 2 foto's krijgt en een int die het aantal tijdseenheden tussen het nemen van foto 1 en foto 2 voorstelt. Voor ons voorbeeld zou een mapping dus kunnen zijn [(10,9),(12,13)] omdat de bal die op positie 10 lag nu op positie 9 zou kunnen liggen, en de bal die op positie 12 lag nu op positie 13 zou kunnen liggen.

Main> berekenMappings [10,12] [9,10,13] 1
[[(10,9), (12,13)] ]

Main> berekenMappings [10,12] [9,11,13] 1
[[(10,9), (12,11)], [(10,9), (12,13)], [(10,11), (12,13)]]

Main> berekenMappings [10,11,12] [12,9,14,10,8] 2
[[(10,12), (11,9), (12,14)], [(10,12), (11,9), (12,10)], [(10,8), (11,9), (12,14)], [(10,8), (11,9), (12,10)]]

Vraag 2: Schrijf een functie die mappings tussen 2 foto's berekent voor alle tijdstippen. (ofzo)

Oplossing(en)

Winkelen (01.09.2010)

Jan en zijn vrouw Ann gaan winkelen, maar Jan doet dat niet graag. Jan mag daarom het pad kiezen. Hij zoekt het snelste pad. vb.

  _____10__________20__________30__________10_____
              |           |           |
              3           2           3
  ______5_____|____30_____|____15_____|_____8_____


Maak een functie helpJan dat als argument de informatie krijgt van de straat. In het geval van het voorbeeld is die informatie:

[Section 10 5 3, Section 20 30 2, Section 30 15 3, Section 10 8 0]

Het antwoord hiervan moet zijn:

[(Z,5),(B,3),(N,20),(B,2),(Z,15),(Z,8),(B,0)]

waar N, Z en B respectievelijk staan voor Noordkant, Zuidkant en Brug. Merk op dat het niet uitmaakt of je aan de zuidkant of de noordkant begint of eindigt. De laatste term (B,0) mag eventueel. worden weggelaten. Schrijf de nodige types.

Deze opgave is letterlijk overgenomen van Learn You A Haskell.

Oplossing(en)

Alternatieve ordes (15 januari 2009)

De Nederlande taalunie wil onze taal grondig hervormen, zelfs de klassieke alfabetische volgorde wordt overboord gegooid.

Je krijgt een lijst van woorden geordend volgens de nieuwe 'alfabetische' orde. Hieruit bepaal je het alfabet en de orde voor dat alfabet.

Schrijf hiervoor een functie berekenorde woordenlijst. Bijvoorbeeld voor de woordenlijst ab abd abc ba bd cc bereken je als mogelijke ordes a b d c en a d b c

Voor de woordenlijst 132 123 zijn de mogelijkheden 1 3 2 3 1 2 en 3 2 1.

Main> berekenorde ["ab", "abd", "abc", "ba", "bd", "cc"]
["abdc", "adbc"]

Main> berekenorde ["aa", "ba", "dc"]
["abdc","abcd","acbd","cabd"]

Main> berekenorde ["123", "132"]
["123","213","231"]

Zet in commentaar hoe je dit probleem aanpakt. Geef duidelijk aan welke types je gebruikt. Geef ook de typering van je functies.


In feite willen we een unieke orde hebben. Schrijf een functie maakuniek orde1 orde2 waarbij uitgaande van 2 mogelijke ordes we gaan detecteren wat de vrijheidsgraden nog zijn.

Main> maakuniek "abdc" "adbc"
[NogVrij 'b' 'd']

Main> maakuniek "abcd" "adbc"
Nogvrij b d, NogVrij c d

Main> maakuniek "abcd" "cabd"
Nogvrij a c, NogVrij b c

Oplossing(en)

Medicijnen (12 januari 2009)

Opgave

In deze tijd van het jaar zijn er veel zieken. De apothekers doen dus goed zaken. Nu moet er echter geleverd worden bij al die apothekers. Ook vervallen medicijnen moeten opgehaald worden. Een busje met een bepaalde capaciteit rijdt hiervoor rond. Schrijf een functie ronde die

  • Als eerste argument de capaciteit van het busje krijgt
  • Als tweede argument een lijst koppels (naam,hoeveelheid) die voorstelt hoeveel er geleverd moet worden in die bepaalde apotheek
  • Als derde argument een lijst koppels (naam,hoeveelheid) die voorstelt hoeveel er afgehaald moet worden in die bepaalde apotheek
  • Een route teruggeeft zodat:
    • Het busje in elke stad slechts 1 keer komt (je mag veronderstellen dat alle hoeveelheden kleiner zijn dan de capaciteit)
    • Het busje zo weinig mogelijk terug naar het depot moet gaan om bij te vullen (dus eigenlijk steeds zo vol mogelijk geladen is).

Je mag er hierbij steeds van uitgaan dat er eerst medicijnen in een apotheek afgeleverd worden en pas daarna de oude medicijnen ingeladen worden. Enkele voorbeelden ter illustratieac

ronde 5 [("a",3)] [("a",3)] = ["a","depot"]
ronde 5 [("a",3),("b",4),("c",2)] [("a",2),("b",4)] = ["a","c","depot","b","depot"]
ronde 10 [("a",9),("b",5)] [("a",3),("b",5),("c",7)] = ["a","c","depot","b","depot"] 

(merk bij de voorgaande op dat ["c","a","depot","b","depot"] geen goede oplossing is)

ronde 5 [("a",3),("b",2)] [("a",2),("b",2),("c",1)] = ["a","b","c","depot"]

Oplossing(en)

Stern-Brocot boom van rationale getallen (25 januari 2008)

We kunnen de rationale getallen opsommen in een Stern-Brocot boom. Dit is een boom die we als volgt opstellen. Begin met de twee "getallen" 0/1 en 1/0 en neem 1/1 als wortel van de boom met "virtuele voorouders" 0/1 en 1/0. Dan kun je aan een knoop 2 kinderen toevoegen door het tussengetal te berekenen van deze knoop en zijn meest rechtse linkervoorouder en meest linkse rechtervoorouder voor linker- en rechterkind respectievelijk. Het tussengetal van twee breuken t1/n1 en t2/n2 is gedefinieerd als (t1+t2)/(n1+n2). Meer uitleg hierover vind je op http://en.wikipedia.org/wiki/Stern-brocot_tree

Schrijf een functie die deze boom gebruikt om een rationaal getal in een interval te vinden

>vindGetal 0.0 7.0
1/1
>vindGetal 0.45 0.55
1/2

Schrijf een functie die voor een gegeven rationaal getal een encodering opstelt via de Stern-Brocot boom door het pad dat we van de wortel tot dat getal moeten volgen.

>enc (3,5)
"LRL"

een oplossing

Algoritme 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 tupel 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.

Het kortstepadalgoritme 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 definieer 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

een alternatieve oplossing

Graafisomorfie

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 (augustus 2005)

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

Formuleboom (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"

--edit: Ik denk dat je hier het net andersom bedoelt: links is "Niet a", rechts is "Wel a"

  1. 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)] --edit: Hier wordt het dan: "[(Niet a) En (Niet b)] Of [(Wel a) En (Niet 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)

Opgave

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]

een oplossing

N-queens

Opgave

N-queensin haskell. Geef 1 of alle oplossingen.

Een oplossing

Paginering (ex-examenvraag van Toledo)

Opgave

Paginering wordt gebruikt om de virtuele adresruimte van een programma x te mappen naar het fysisch werkgeheugen van onze computer. De fysische adresruimte wordt opgedeeld in n pagina’s, 0, ... n − 1. Wanneer de uitvoering van een programma toegang nodig heeft tot een fysisch adres, wordt de overeenkomstige pagina uit het virtuele werkgeheugen gehaald. Het virtuele werkgeheugen kan maximaal m pagina’s bevatten, waarbij m < n. De pagineringstabel houdt bij of een fysische pagina in het werkgeheugen zit en zo ja in welke virtuele pagina van het werkgeheugen, 0,..., m − 1.

Initieel is het virtuele werkgeheugen leeg. Wanneer het virtuele werkgeheugen vol is, moet een oude pagina plaats maken voor een nieuwe. Om te bepalen welke pagina eruit moet, bestaan er verschillende aanpakken. Wij gebruiken “least recently used” (lru): de pagina die het langst niet gebruikt is, wordt verwijderd wanneer het virtuele werkgeheugen vol is. Je kan dit implementeren door de tijd van gebruik te registeren.

Schrijf een functie lru die als argumenten m, n, en een lijst van fysische paginanummers krijgt. De lijst van pagina’s is de sequentie van pagina’s die tijdens de uitvoering van het programma gebruikt worden. Voor een werkgeheugen van grootte 3 (m gelijk aan 3) en de lijst [2,3,2,1,5,2,4,5,3,2,5,2], evolueert het virtuele werkgeheugen onder lru als volgt:


TijdLeesVirt. Pagina
012
0
1 2 2
2 3 2 3
3 2 2 3
4 1 2 3 1
5 5 2 5 1
6 2 2 5 1
7 4 2 5 4
8 5 2 5 4
9 3 3 5 4
10 2 3 5 2
11 5 3 5 2
12 2 3 5 2

Op tijdstip 5 treedt de eerste pagineringsfout op: we hebben pagina 5 nodig en het werkgeheugen bevat pagina’s 2, 3 en 1 die respectievelijk nog gebruikt werden op tijdstippen 3, 2 en 4. Pagina 3 werd het langst niet gebruikt en zal dus vervangen worden door 5. De functie lru geeft als resultaat de lijst van pagineringsfouten. Voor ons voorbeeld is dat de lijst [ ..., (5,1,3,5),(7,2,1,4),(9,0,2,3),(10,2,4,2)] waarbij ... eventueel rapporteert over de eerste pagina’s die in het lege werkgeheugen worden geladen en (5,1,3,5) de eerste echte pagineringsfout kenmerkt aan de hand van het tijdstip, de positie in het werkgeheugen, de oude en de nieuwe pagina. Definieer in Haskell de nodige types. Geef ook het type van al de functies die je schrijft.

Indien je slechts een deel van het probleem oplost, dan zorg je dat je commentaar aangeeft hoe jouw deel past in een volledige oplossing.

een oplossing