Declaratieve Talen

Ga naar: navigatie, zoeken
GerdaJanssens.jpg

Inhoud

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 er in 2006-2007 5 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 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

Kleine vraagjes

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 kan je 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)

Prolog

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 gebeurt zijn. Als er 1 soort is produceert de mijn die dag 1 ton, als er 2 soorten voedsel geleverd werd 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

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

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

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
abcd acbd cabd abdc

Main> berekenorde 132 123
132 312 321

Zet in commentaar hoe je dit probleem aanpakt. Geef duidelijk aan welke typejs 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