De her-eindopdracht staat nu online! Hertentamen datum bekend

LIX003B05
Logisch Programmeren 2007-2008

Cursusinformatie

Docenten

Jori Mur
e: j.mur(at)rug.nl

Mendel van 't Riet
e: m.van.t.riet(at)ai.rug.nl

Tijd & Plaats

Hoorcollege, wk 44-50

Maandag, 9-11u, H.13.309

Werkcollege, wk 44-50

Donderdag, 13-15u, H.12.102 (Unix-ruimte)

Hertentamen, maandag 16 juni 2008

14-17u, zaal 12.0013 (Harmoniegebouw)

Literatuur

Learn Prolog Now!
Patrick Blackburn, Johan Bos and Kristina Striegnitz

Dit boek is on-line: voor html zie de homepage. Of lokaal, in iets oudere versie lokaal [pdf] en lokaal [ps.gz].

Her-eindopdracht

De her-eindopdracht staat nu online.

Beschrijving

Het college Logisch Programmeren behandelt de programmeertaal Prolog, gebaseerd op de predikatenlogica. In tegenstelling tot procedurele programmeertalen als Pascal en C is Prolog een declaratieve taal. De onderliggende gedachte van het declarative paradigma is dat een programma niet een procedure beschrijft om een probleem op te lossen, maar juist een precieze omschrijving is van de oplossing zelf. Prolog probeert dan op basis van deze beschrijving het probleem op te lossen. Prolog is een veelgebruikte programmeertaal in natuurlijke taalverwerking en kunstmatige intelligentie.

Het college is een inleiding, en heeft als doel om inzicht te geven in logisch programmeren en bovendien vaardigheid in Prolog. Deze twee dingen gaan hand in hand en het is daarom belangrijk dat deelnemers de wekelijkse huiswerkopgaven maken. Voorbeeldantwoorden van deze opdrachten zullen ook wekelijks gegeven worden en bovendien zullen sommige opdrachten tijdens het practicum behandelt worden.

Logisch Programmeren is 5 ECTS punten, waarvoor aan de volgende voorwaarden voldaan moet worden:

Het eindcijfer is een gewogen gemiddelde tussen de eindopdracht (1x) en het tentamen (2x). Voor zowel de eindopdracht als voor het tentamen kan een herkansing gemaakt worden. Een voldoende op een eerder tentamen of een eerdere eindopdracht mag blijven staan. De huiswerkopdrachten moeten wel opnieuw gemaakt worden.

Voor deelname aan het prakticum op donderdagmiddag is een Unix-account op hagen bij Letteren nodig, die bij de heer Da Costa (kr 336, computer afdeling Harmoniegebouw) te verkrijgen is. Aanwezigheid op het practicum is niet verplicht, tenzij je door de docent uitgenodigd wordt om extra uitleg te krijgen over het huiswerk, in welk geval aanwezigheid op het practicum geldt als voorwaarde voor het halen van de huiswerkopdracht van die week. Verder is het practicum bedoeld om vragen te stellen of onder begeleiding het huiswerk te kunnen maken.

Op het Letterennetwerk draait Sicstus Prolog (sicstus om een sessie te starten). Voor thuis kan bijvoorbeeld SWI-Prolog gebruikt worden. In het huiswerk/de eindopdracht zal geen gebruik worden hoeven gemaakt van dialect-specifieke Prolog.

Het huiswerk dat moet worden ingeleverd, moet worden opgestuurd naar Mendel van 't Riet <m.van.t.riet(at)ai.rug.nl>, vóór het volgende hoorcollege. Stuur het op als platte tekst onder vermelding van naam en studentnummer

Planning

  1. Week 44, 29 oktober 2007
    Hoofdstuk 1 en 2, behalve 2.1.2

    Als inleiding kijken we naar elementen van de taal Prolog op een hoog niveau (feiten, regels en vragen) en op een laag niveau (termen: atoms, getallen, variabelen en complexe termen). Prolog kan twee termen vergelijken en proberen ze aan elkaar gelijk te maken (matchen). Gebruik makend van deze techniek zoekt Prolog op een systematische manier naar een oplossing voor een gegeven probleem. De systematische zoekmethode kan uitgebeeld worden door middel van zoekbomen, zodat ook backtracking kan worden uitgelegd.

    Opdrachten 1e college

    Maak 1.1, 1.2, 1.3, 2.1, 2.2, 2.3, 2.4, voor jezelf om bekend te raken met Prolog en de prolog interpreter.

    Lever in vóór maandag 5 november:
    Op basis van je oplossing voor opdracht 2.4, de implementatie van crosswd/6: teken de volledige zoekboom voor de query ?- crosswd(abalone,anagram,C,D,E,F). Bepaal de grootte van de zoekboom (in aantal knopen). Hoe hangt die af van je code? Kan je de zoekboom nog verkleinen door je code te veranderen? Wat voor oplossing(en) heeft de query?

    Links

  2. Week 45, 5 november 2007
    Hoofdstuk 3

    Nu hebben we al matching en backtracking gezien; een ander belangrijk punt is dat van recursie, een fenomeen dat overigens ook bij andere programmeertalen wordt aangetroffen, maar in Prolog programma's heel vaak voorkomt. Er is sprake van recursie als een regel als onderdeel van zijn definitie een verwijzing naar zichzelf bevat.

    Opdrachten 2e college

    Om te oefenen: maak 3.1, 3.2, 3.3

    Lever in vóór donderdag 15 november, het volgende:
    Ga uit van de volgende feiten: 

    % stamboom
%
%             truus
%            /     \
%       griet       trina
%      /     \        |   
% marie       klara maart
%   |                 |
% hiske             sasha
% 

% moeder/2 ?Dochter ?Moeder
moeder(hiske,marie).

moeder(marie,griet).
moeder(klara,griet).

moeder(griet,truus).
moeder(trina,truus).

moeder(maart,trina).

moeder(sasha,maart).

    Schrijf een predikaat generatiegenoot/2 dat waar is als de twee argumenten vrouwen uit dezelfde generatie zijn. De volgende antwoorden moet het programma in ieder geval goed krijgen: 

    ?- generatiegenoot(griet,trina).

yes

?- generatiegenoot(maart,marie).

yes

?- generatiegenoot(sasha,marie).

no

    Je predikaat moet recursief gedefinieerd zijn, want het moet voor elke grootte stamboom te gebruiken zijn. Begin met het definieren van je base case: het simpelste, niet recursieve geval waarin generatiegenoot/2 waar is. Bouw op basis daarvan een tweede, recursieve clause. Het is niet erg wanneer dezelfde aanroep van generatiegenoot/2 op verschillende manieren kan worden bewezen.

    Beschrijf kort wat je programma doet bij elk van de volgende vier queries: 

    ?- generatiegenoot(truus,Y).

?- generatiegenoot(klara,Y).

?- generatiegenoot(X,klara).

?- generatiegenoot(X,Y).

    Links

  3. Week 46, 12 november 2007
    Hoofdstuk 4 en paragraaf 9.2.2

    Behalve in regels kun je recursie ook aantreffen in datastructuren. De lijst in Prolog is hiervan een goed voorbeeld: hij bestaat uit een aantal elementen, gevolgd door de staart van de lijst. Deze staart is ook weer een lijst: dit maakt de lijststructuur recursief. Zo'n recursieve structuur kan worden weergegeven als een boom, waardoor ook de operaties die we op lijsten kunnen uitvoeren, zoals het zoeken naar een element binnen een lijst, wellicht makkelijker te begrijpen zijn. In combinatie met een recursieve datastructuur wordt recursief programmeren een stuk interessanter.

    Opdrachten 3e college

    Lever de volgende twee opdrachten in voor het college op donderdag 22 november:

    Eerste inleveropdracht: Schrijf een predikaat neem_uit/3, dat als eerste argument een element X neemt, als tweede argument een lijst L, en als derde argument het resultaat van het uit L halen van een voorkomen van X. Dus bijvoorbeeld: 

    ?- neem_uit(b,[a,b,c],D).

D = [a,c]

yes.

?- neem_uit(C,[a,b,c],D).

C = a, D = [b,c] ;

C = b, D = [a,c] ;

C = c, D = [a,b] ;

no.

?- neem_uit(d,B,[a,b,c]).

B = [d,a,b,c] ; 

B = [a,d,b,c] ; 

B = [a,b,d,c] ; 

B = [a,b,c,d] ; 

no.

    Tweede inleveropdracht: we kunnen twee getallen vergelijken met X > Y, X >= Y, X < Y, X =< Y, respectievelijk: X is groter dan, groter of gelijk aan, kleiner dan en kleiner of gelijk aan Y. Schrijf hiermee een predikaat voegtoe/3 dat als eerst argument een getal neemt, als tweede argument een gesorteerde lijst, en als derde argument een gesorteerde lijst, waarbij deze lijst de elementen van de eerste lijst en het extra getal bevat. Bijv.: 

    ?- voegtoe(1,[2,3],X).

X = [1,2,3]

yes.

?- voegtoe(2,[1,3],X).

X = [1,2,3]

yes.

?- voegtoe(2,[1,2,3],X).

X = [1,2,2,3]

yes.

?- voegtoe(1,[2,3],[2,3,1]).

no.
    Hint: we hebben gezien dat veel dingen die je met lijsten doet bestaan uit door de lijst heenlopen en met elk element iets doen. Nu is het feit dat het tweede argument van voegtoe/3 gesorteerd is belangrijk: m.b.v. de boven gegeven vergelijkingsoperatoren kun je bepalen hoe ver het zin heeft door de lijst te lopen, en wanneer je het extra element kan plaatsen.

    Terzijde: op voegtoe/3 is een sorteeralgoritme gebaseerd. Dat ziet er dan zo uit: 

    % sorteer/2 +Ongesorteerd ?Gesorteerd
sorteer([],[]).
sorteer([A|B],C) :- sorteer(B,D), voegtoe(A,D,C).
    Gedeeltijke bomen voor dit sorteerpredikaat dat voegtoe/3 gebruikt staan uitgewerkt op een aparte pagina.

    Link

  4. Week 47, 19 november 2007
    Hoofdstuk 5 en 6 en paragraaf 9.2.1

    Eerder zagen we hoe je met behulp van de zogenaamde successor notatie (0, s(0), s(s(0)),...) kunt tellen en rekenen in Prolog. Het is ook mogelijk om Prolog met behulp van het ingebouwde predicaat is/2 berekeningen te laten uitvoeren met normale getallen. Verder komen meer toepassingen van lijsten aan bod, zoals het predicaat append/3 waarmee je twee lijsten kunt samenvoegen tot één lijst. Iets wat in hoofdstuk 5 van het boek wordt geïntroduceerd, en de efficiëntie van programma's kan verbeteren is het gebruik van accumulators.

    Opdrachten 4e college

    Eerste inleveropdracht: de volledige code voor sorteerpredikaat sorteer/2, dat voegtoe/3 gebruikt, ziet er zo uit: 

    % sorteer/2 +Lijst ?Gesorteerde_lijst
sorteer([],[]).
sorteer([Xh|Xt],Y):- 
        sorteer(Xt,Z), 
        voegtoe(Xh,Z,Y).

% voegtoe/3 +Element +Oude_gesorteerde_lijst ?Nieuwe_gesorteerde_lijst, of evt
% voegtoe/3 +Element ?Oude_gesorteerde_lijst +Nieuwe_gesorteerde_lijst
voegtoe(X,[],[X]).
voegtoe(X,[Ah|At],[Ah|Bt]):- 
        X > Ah, 
        voegtoe(X,At,Bt). 
voegtoe(X,[Ah|At],[X,Ah|At]):- 
        X =< Ah.
    Schrijf een accumulatorversie van sorteer. Aan voegtoe/3 hoef je niets te veranderen. Lever er een wrapper-predikaat bij, zodat we geen rekening hoeven te houden met het feit dat er een accumulator gebruikt is.

    Tweede inleveropdracht: Schrijf een predikaat vierentwintig/2, dat als eerste argument een lijst van vier cijfers neemt. Het predikaat slaagt wanneer, door optellen, aftrekken, vermenigvuldigen of delen, je 24 kan maken uit de getallen. Je moet elk getal precies één keer gebruiken. In het tweede argument staat de manier waarop je tot 24 bent gekomen.

    Bijvoorbeeld: je kan met 1,3,6 & 7 tot vierentwintig komen op de volgende manier:

    • (6-3)*(1+7)

    immers:

    • 6 - 3 = 3
    • 1 + 7 = 8
    • 3 * 8 = 24

    Er zijn echter nog andere manieren. Naast triviale (het omdraaien van de volgorde, of van de volgorde van de getallen aan weerzijde van '*' en '+'), kan je bijvoorbeeld ook 24 maken door:

    • 1 * 3 = 3
    • 7 - 3 = 4
    • 4 * 6 = 24

    Schrijf je predikaat zo, dat het eerste argument een lijst getallen is, en het tweede argument een lijst rekenstapjes met resultaat. Dus: 

    ?- vierentwintig([9,8,7,2],Stappen).

Stappen = [9+7=16,16*2=32,32-8=24] ? 

yes

?- vierentwintig([8,7,4,3],P).
  
P = [7-3=4,4*4=16,16+8=24] ? ;
P = [7-3=4,4*4=16,8+16=24] ? ;
P = [7-3=4,4*4=16,16+8=24] ? ;
P = [7-3=4,4*4=16,8+16=24] ? ;
P = [3-7= -4,-4*4= -16,8- -16=24] ? ;
P = [3-7= -4,4* -4= -16,8- -16=24] ? ;

no.
    Bij de eerste query heb ik niet naar meer oplossingen gevraagd, bij de tweede wel. Je programma hoeft niet de oplossingen te geven in de volgorde hierboven, maar wel alle. Tot slot zijn er combinaties waarmee het niet kan: 
    ?- vierentwintig([8,7,6,1],P).

no.
    NB! Voel je niet gedwongen om iets met accumulators te doen in deze tweede opdracht.

    Link

  5. Week 48, 26 november 2007
    Hoofdstuk 9 (behalve 9.4), hoofdstuk 11 en hoofdstuk 12

    Hoofdstuk 9 gaat wat dieper in op termen. Veel hiervan is al eerder aan bod gekomen, maar wat nieuw is is bijvoorbeeld het ingebouwde predicaat functor/3 waarmee je een complexe prologterm kunt ontleden in de functor en de ariteit, of juist deze gegevens kunt gebruiken om een complexe term te construeren. In dit college zal ook een datastructuur geïntroduceerd worden (zoals we eerder al de lijst hebben gezien): de boom. Soms wil je wellicht niet slechts één antwoord opslaan in een variabele, maar alle mogelijke antwoorden. Prolog kent een paar ingebouwde predicaten waarmee je antwoorden kunt verzamelen in een lijst: findall/3, bagof/3 en setof/3 (hoofdstuk 11). Daarnaast kijken we naar invoer en uitvoer, zowel van en naar het scherm (practical session 9) als van en naar bestanden (hoofdstuk 12).

    Opdrachten 5e college:

    1. Formuleer de stamboom van de opdracht van week twee als binaire boom (d.w.z. in termen van tree/3). De definitie van de datastructuur is als volgt (zie ook de collegeaantekeningen): 
      bin_boom(void).
bin_boom(tree(_Label,LinkerDochter,RechterDochter)):-
         bin_boom(LinkerDochter),
         bin_boom(RechterDochter).
      Maak de stamboom beschikbaar als argument van een feit familie/1, het ziet er dus uit als (vul zelf de puntjes in): 
      familie(tree( ..., ..., ...)).
    2. Definieer een predikaat generatie/3 +Stamboom ?FamilieLid ?Generatie, dat een stamboom als eerste argument vraagt en een familielid en een lijst met alle leden van haar generatie, op basis van de stamboom, teruggeeft. Voor het instantieren van het eerste argument gebruiken we het familie/1 feit. De volgorde van de elementen in de lijst is niet belangrijk. Bijv.: 
      ?- familie(X), generatie(X,sasha,Y).

X = ...
Y = [hiske,sasha].
    3. Definieer met behulp van generatie/3 een predikaat generatie/2, dat als eerste argument een stamboom neemt, en een generatie teruggeeft. Het is belangrijk dat er geen dubbele antwoorden komen op een query. De volgende query heeft precies 4 antwoorden (de volgorde van de antwoorden is weer niet belangrijk): 
      ?- familie(X), generatie(X,Y).

X = ...
Y = [truus];

X = ...
Y = [griet,tina];

X = ...
Y = [klara, maart, marie];

X = ...
Y = [hiske,sasha];

no
      (De no betekent dus dat er niet een 5de oplossing is.)

    Link

  6. Week 49, 3 december 2007
    Hoofdstuk 10

    Prolog kan met behulp van het backtrackmechanisme alle mogelijke oplossingen voor een probleem uitproberen. Soms weet je als programmeur echter al vantevoren dat Prolog een bepaalde serie van mogelijke oplossingen niet eens hoeft te proberen: dit kun je dan aangeven met de cut: ! (uitroepteken). Dit zorgt ervoor dat een deel van de zoekboom wordt 'gesnoeid' en in de toekomst tijdens eventueel backtracken niet meer bezocht zal worden.

    Ook kijken we naar negatie in Prolog. Prolog behandelt negation as failure; de negatie van een predikaat \+ p. wordt bewezen geacht als Prolog p niet kan bewijzen.

    Voor degenen die de gedrukte versie van het boek hebben aangeschaft: deze wijkt hier qua behandelde stof en qua opzet af van de online versie en van de pdf. Bij twijfel, raadpleeg een van de laatste twee.

    Opdrachten 6e college

    Het Stable Marriage Problem. Stel dat je N mannen en N vrouwen hebt. Voor elke man weten we precies hoe leuk hij elk van de vrouwen vindt, want voor elke man hebben we een lijstje met de namen van de vrouwen op volgorde van aantrekkelijkheid. Voor de vrouwen hebben we dezelfde informatie: per vrouw een lijstje met de namen van de mannen op volgorde van aantrekkelijkheid. Het probleem is nu om N stabiele huwelijken te vinden,dat wil zeggen, om elke man aan een vrouw te koppelen zonder dat de verzameling huwelijken instabiel wordt. Een set van N huwelijken is instabiel, wanneer er een vrouw V en een man M zijn, zodanig dat V een voorkeur voor M heeft boven haar partner, en dat tegelijkertijd M een voorkeur voor V heeft boven zijn partner. Dus, als zowel M en V er belang bij hebben om vreemd te gaan (met elkaar) is de verzameling huwelijken niet stabiel.

    Bijvoorbeeld, neem de volgende voorkeuren:

    • Jan wil het liefst Marie, en daarna Sasha
    • Peer wil ook het liefst Marie en daarna Sasha
    • Sasha wil het liefst Jan, en dan Peer
    • Marie wil ook liefst Jan en dan Peer

    Als we nu Marie x Peer doen, en Sasha x Jan, dan hebben we geen stabiele verzameling huwelijken, omdat Marie en Jan meer tot elkaar zijn aangetrokken dan tot hun partners.

    Maar doen we Marie x Jan en Sasha x Peer, dan is het wel stabiel, ookal wil Sasha liever Jan dan Peer. Jan verkiest namelijk zijn vrouw Marie boven Sasha, en dus is hij niet geinteresseerd in een affaire. Voor een eventuele buitenechtelijke relatie tussen Peer en Marie gaat dezelfde redenering op in deze set huwelijken.

    Feit: voor elke N en voor alle mogelijke lijsten voorkeuren bestaat altijd een set stabiele huwelijken!

    Voor de opdracht gaan we uit van N=5. Verder mag je aannemen dat de personen en hun voorkeuren in het programma gegeven zijn als feiten. Bijvoorbeeld: 

    %% a vindt v het leukst, dan z, w, x en y; etc
preflist(a,[v,z,w,x,y]).
preflist(b,[w,v,x,y,z]).
preflist(c,[v,x,z,y,w]).
preflist(d,[w,x,v,y,z]).
preflist(e,[z,x,v,w,y]).

preflist(v,[e,a,d,b,c]).
preflist(w,[d,e,b,a,c]).
preflist(x,[a,d,b,c,e]).
preflist(y,[c,b,d,a,e]).
preflist(z,[d,b,c,e,a]).

%% alle mannen
man([a,b,c,d,e]).

%% alle vrouwen
vrouw([v,w,x,y,z]).
    Definieer de relatie stabiel/1 ?Lijst die een lijst paren p(V,M) oplevert die een stabiele set huwelijken tussen vrouw V en man M representeert. Dus, een van de oplossingen voor bovenstaande feiten is: 
    ?- stabiel(X)

X = [p(v,e),p(w,d),p(x,a),p(y,b),p(z,c)]

yes

    Hint: Een goede strategie voor wat grotere problemen is het implementeren van een generate-and-test strategie. Genereer eerst een complete toestand, d.w.z. zorg dat iedereen precies een keer getrouwd is, en test vervolgens of de toestand aan je voorwaarden voldoet, d.w.z. dat iedereen een stabiel huwelijk heeft. Laat Prolog met backtracken het harde werk doen. Door het opdelen in deze twee delen is het probleem een stuk overzichtelijker.

  7. Week 51, 17 december 2007

    Vragenuurtje, geen practicum.