Opdracht Prolog voor Praktikum Programmeertalen

(12/03/99): Cijfers

(24/11/98): preciesering opgave 2:

De formulering van opgave 2 is iets precier geworden. Van de entries in een KWIC index wordt nu expliciet vereist dat de kontekst niet alleen bestaat uit"de omliggende paar woorden", maar uit "alle andere woorden uit de titel", dwz: alle woorden uit de titel behalve het geindexeerde woord. De getoonde voorbeeld uitvoer voldeed al aan deze preciesere eis.

(10/11/98): Hint

Om je programma te testen: De oplossing van het voorbeeld bij het stabiele huwelijksprobleem.

(2/10/98): Hint

Om het inlezen van data-files te vereenvoudigen kun je gebruik maken van de procedure readln(X). Deze procedure is al voorgeladen in Prolog, maar niet gedocumenteerd. Documentatie kun je hier vinden.

Literatuur

Het boek "Programming for Artficial Intelligence" van I. Bratko (Addison-Wesley, ISBN 0.201.41606.9) is een van de beste leerboeken over Prolog. Het is in ruime mate voorhanden bij AI studenten, en bij I-studenten die het college Prolog hebben gedaan. Er zijn ook exemplaren in de bibliotheek.

Software

Voor het praktikum kun je gebruiken maken van het SWI-Prolog systeem. Een handleiding is beschikbaar met een korte uitleg over het gebruik van het systeem, verwijzingen naar uitgebreide documentatie (op papier en op 't Web), en gratis software voor thuisgebruik.

Inlever procedure

Opgaven moeten worden ingeleverd per email naar Frank van Harmelen. Stuur voor elk van de twee onderstaande opgaven een aparate email met daarin je Prolog code. Vermeld ook in elke email de namen van de auteurs van de code.

Beoordeling

Bij de beoordeling speelt niet alleen mee of een programma werkt volgens de eisen in de opgave, maar ook algemene aspecten van programmeerstijl worden meegewogen, zoals opdeling van het programma in onderdelen (modules, procedures), keuze van procedure- en variabele-namen, commentaar, layout, het vermijden van "lelijke" programma-constructies als -> ; en zogenaamde "rode cuts". Ook efficientie en elegantie tellen mee in de waardering.

Begeleiding

Begeleiding vindt plaats op twee manieren:

email: per email gestelde vragen aan Frank van Harmelen worden altijd zo spoedig mogelijk beantwoord.
bespreking: mocht email-beantwoording van vragen niet voldoen, dan kun je een afspraak maken voor een bespreking.

Opgave 1: Stabiele huwelijken

Gegeven zijn N mannen en N vrouwen die elk een partner zoeken (dit is een nogal traditionele opgave:-). Voor elke man en vrouw is een voorkeurslijst bekend van alle partners. Het probleem is om een verzameling stabiele huwelijken te vinden.

Een huwelijk is instabiel als twee mensen die niet met elkaar getrouwd zijn beiden eigenlijk liever met elkaar getrouwd zouden zijn dan met hun daadwerkelijke partner. Een voorbeeld van een verzameling instabiele huwelijken is de volgende:

Frits is met Liza getrouwd, en
Anja met Roel, maar
eigenlijk zou Anja liever met Frits getrouwd zijn dan met Roel, en
Frits zou liever met Anja getrouwd zijn dan met Liza.

In deze opgave moet je een programma schrijven dat gegeven een verzameling mannen en vrouwen met hun voorkeuren een stabiele verzameling huwelijken berekent. (Een stelling uit de grafen theorie zegt dat voor elke mogelijke voorkeurskeuze een oplossing van dit probleem bestaat).

Je programma krijgt als invoer de namen van twee files. In de eerste file staat op elke regel de naam van een man, gevolgd door de namen alle vrouwen, in volgorde van voorkeur. In de tweede file staat dezelfde informatie, maar dan voor alle vrouwen.

Schrijf een predicaat huwelijk(ManFile,VrouwFile,Huwelijken) dat de informatie uit de twee files inleest, en een stabiele partner-toekenning berekent in de variable Huwelijken, gerepresenteerd als een lijst van [Vrouw,Man] paren, bijv:

?- huwelijken(vb1man,vb1vrouw,H).

H = [[anja,frits],[lisa,roel]]

Bij backtracken moeten vervolgens telkens de andere stabiele huwelijk-configuraties berekend worden.

Test je programma op bovenstaand voorbeeld, en ook op het onderstaande:
Man file:

avraham          chana tamar zvia ruth sarah
binyamin         zvia chana ruth sarah tamar
chaim            chana ruth tamar sarah zvia
david            zvia ruth chana sarah tamar
elazar           tamar ruth chana zvia sarah

Vrouw file:

zvia             elazar avraham david binyamin chaim
chana            david elazar binyamin avraham chaim
ruth             avraham david binyamin chaim elazar
sarah            chaim binyamin david avraham elazar
tamar            david binyamin chaim elazar avraham

Na verwijdering van permutaties van gelijke huwelijks-configuraties bestaan er voor dit voorbeeld precies 4 stabiele huwelijken:

1	chana & david	ruth & avraham	sarah & binyamin	tamar & chaim	zvia & elazar
2	chana & david	ruth & avraham	sarah & chaim	tamar & binyamin	zvia & elazar
3	chana & elazar	ruth & david	sarah & binyamin	tamar & amp chaim	zvia & avraham
4	chana & elazar	ruth & david	sarah & chaim	tamar & binyamin	zvia & avraham

Opgave 2: KWIC index

Een KWIC index (Key Word In Context) is een alfabetisch geordende lijst van alle woorden uit een tekst, waarbij voor elk woord de kontekst (= de andere woorden uit de titel) wordt vermeld.

In deze opgave moet je een programma schrijven om een KWIC index te maken van een lijst boektitels.

Je programma krijgt als invoer twee files: in de eerste file staat per regel een boektitel, in de tweede file staan onbelangrijke woorden waarvoor geen entry in de KWIC index gemaakt hoeft te worden (woorden zoals "in", "de", "het", "van", etc.). Schrijf een predicaat kwic_index(TitelFile,NegeerFile,Index) dat

op de uitvoer een netjes geformateerde versie van de Index afdrukt, en
de variabele Index bindt aan een lijst van index-entries, waarbij elke index-entry de vorm heeft [KeyWord, [... Lijst van Kontekst Woorden ..]]

Voorbeeld:

De file boekenvb1:

logic for problem solving
logic programming
algorithmic program debugging
programming in prolog

De file negeervb1:
```
in for
```

Aanroep en uitvoer:

?- kwic_index(boekenvb1,negeervb1,Index).

   algorithmic    : program debugging 
   debugging      : algorithmic program 
   logic          : problem solving 
   logic          : programming 
   problem        : logic solving 
   program        : algorithmic debugging 
   programming    : logic 
   programming    : prolog 
   prolog         : programming 
   solving        : logic problem 

I = [algorithmic + [program, debugging], debugging + [algorithmic, program], 
     logic + [problem, solving], logic + [programming], 
     problem + [logic, solving], program + [algorithmic, debugging], 
     programming + [logic], programming + [prolog], prolog + [programming], 
     solving + [logic, problem]]

Frank van Harmelen