Kunstmatige intelligentie
Het vak Kunstmatige intelligentie,
ook wel AI (van Artificial Intelligence)
genoemd, wordt verzorgd door
dr. W.A. (Walter) Kosters,
geassisteerd door
drs. Tim Cocx
en
drs. Jeroen Laros,
en wordt in het voorjaar van 2006 gegeven.
(En daarna weer in het voorjaar van 2007;
eerste college: maandagmiddag 5 februari 2007.)
Note that the course is in DUTCH.
Collegetijden:
maandagen, van 13.45 tot 15.30 uur,
in zaal 174 van het Snellius,
het gebouw van Wiskunde en Informatica, Niels Bohrweg 1, Leiden.
Data: 6 februari tot en met 8 mei 2006
(niet op 17 april 2006).
Het vak levert 6 (zes) ECTS punten op in het nieuwe systeem (vanaf 2002/2003;
voorheen waren dit 4 (vier) "oude" studiepunten).
Naast het voldoende maken van het tentamen
is het hiervoor ook nodig het
practicum
voldoende te hebben.
Het eindcijfer wordt voor 99% bepaald door het tentamencijfer,
eventueel enigszins afgerond in de richting van het gemiddelde practicumresultaat,
mits beide voldoende zijn. Ten einde het practicum voldoende
te maken, moeten de vier opgaven alle met minstens een 6
of een "OK" beoordeeld zijn.
Het college is in eerste instantie bedoeld voor tweede- en hogerejaars
studenten Informatica, maar is ook interessant voor andere
belangstellenden; voorkennis van de programmeertaal
C++
is sterk aan te raden.
Tentamendata
De tentamendata in 2006 zijn:
- dinsdag 20 juni 2006, 14.00 - 17.00 uur; zaal 174 en zaal 412
NB in het roosterboekje staat op een enkele plaats
abusievelijk 10.00 - 13.00 uur vermeld;
het is dus 14.00 - 17.00 uur!
vragenuur: vrijdag 16 juni 2006, 11.00 uur; zaal 174
- hertentamen: maandag 21 augustus 2006, 10.00 - 13.00 uur
Alle cijfers (college voorjaar 2006) zijn te zijner tijd
hier
te vinden.
Zie ook
vroeger.
Materiaal
Gebruik wordt gemaakt van het boek
Artificial intelligence, A modern approach
van Stuart J. Russell en Peter Norvig, second edition, Prentice Hall, 2003.
Het kost in de winkel circa 60 euro;
soms is de versie met slappe kaft goedkoper.
In het bijzonder worden uit dit boek
de volgende hoofdstukken behandeld:
1 (Introduction; lezen),
2 (Intelligent agents; lezen),
3 (Solving problems by searching; uitgebreid),
4 (Informed search and exploration; uitgebreid),
5 (Constraint satisfaction problems; uitgebreid),
6 (Adversarial search; uitgebreid),
7 (Logical agents; lezen, met name Wumpus),
8 (First order logic; lezen, met name Wumpus),
14 (Probabilistic reasoning; uitgebreid; lees ook 13, Uncertainty),
18 (Learning from observations; uitgebreid, met name beslissingsbomen),
19.1 (Knowledge in learning; lezen),
20.5 (Statistical learning methods; uitgebreid: neurale netwerken),
21.1,2,3 (Reinforcement learning, geillustreerd met 17.1,2;
uitgebreid, aangevuld met 4.3 Genetische algoritmen)
en
25 (Robotics; lezen, + concreet robot-programma),
grotendeels in deze volgorde.
Lees ook eens Hoofdstuk 26 (Philosophical foundations).
Daarnaast werd in voorgaande jaren nog speciaal aandacht besteed aan het onderwerp
Data mining, maar aangezien er nu een apart
derdejaars vak is met die titel ...
Overige literatuur (niet kopen — tenzij je erg veel geld hebt):
- George F. Luger,
Artificial intelligence, Structures and strategies for complex problem solving, Fifth edition,
Addison-Wesley, 2005.
- R. Callan, Artificial intelligence,
Palgrave Macmillan, 2003.
- Tom M. Mitchell,
Machine learning,
McGraw-Hill, 1997.
- Michael Negnevitsky,
Artificial intelligence, A guide to intelligent systems, Addison-Wesley, Second edition, 2004.
-
E. Alpaydin,
Introduction to machine learning,
The MIT Press, 2004.
Compilatie 2001-2005 (in PDF, 12 pagina's);
enkele antwoorden (in PDF).
Er is meer informatie te vinden over het college
de afgelopen jaren;
hier zijn onder andere nog meer oude tentamens (gefabriceerd
door andere docenten!) te bekijken,
zoals het redelijk representatieve
tentamen van 8 juni 1998
[hiervan NIET Opgave 4] met
uitwerking
[beide gezipt PostScript].
Let op: vanaf voorjaar 2005 hoort het onderwerp
Data mining niet meer bij de tentamenstof.
Voor iedere practicumopgave moeten worden ingeleverd:
een minstens drie pagina's
(laten we zeggen vijf pagina's, afgezien van de Appendix)
tellend verslag in
LaTeX
(dit is een GROTE tekst in PDF;
zie ook hier
voor een zeer korte inleiding, en
daar
voor een langere;
of een heel korte zichzelf uitleggende
voorbeeldfile;
of een leuke, uitgebreide, Vlaamse
handleiding),
en een werkend programma (digitaal (mailen aan de docent)
en uitgeprint in de Appendix
van het verslag;
stuur geen LaTeX/PS/PDF-files en ook geen executables).
Het verslag moet een duidelijke opbouw hebben, bijvoorbeeld:
- Inleiding ("dit is de tweede opdracht van het college ...")
- Uitleg probleem (plaatje; "de spelregels zijn ...", gebruikte definities)
- Theorie ("stelling zegt dat ...")
- Aanpak (plaatje; "een drielaags neuraal netwerk ...")
- Implementatie ("een dubbel array"; kort)
- Experimenten (tabel, grafiek)
- Conclusie ("ging fout als de testopstelling niet verlicht was")
- Referenties (genummerd; naar alle wordt verwezen; "handleiding Lego-robots ...", "Russell en Norvig ...")
Een fatsoenlijke referentie ziet er uit als:
[1] S.J. Russell en P. Norvig, Artificial intelligence, A modern approach,
second edition, Prentice Hall, 2003
- Appendix: het programma;
tip: vervang tabs door spaties,
kies kleiner lettertype, en zet het tussen \begin{verbatim}
en \end{verbatim};
liefhebbers: gebruik package verbatim en het commando
\verbatiminput{eigen.file}
Er is een klein skelet voor de verslagen:
verslag.tex.
Zie ook
diverse opmerkingen.
De deadlines zijn strikt, overleg eventueel
met de docent(en).
Voor alle opdrachten geldt dat ze nog voorlopig zijn, aanvullingen
tijdens het semester zullen zeker voorkomen.
Eigen initiatief wordt —na overleg— op prijs gesteld.
De opgaven worden per stuk als volgt beoordeeld:
er wordt gekeken naar het verslag en het
programma (met name werking en leesbaarheid);
originaliteit beinvloedt de eind-afronding.
De cijfers zijn
hier
te vinden.
Het practicum bestaat zoals gezegd uit vier opgaven:
- Sudoku; deadline 27 februari 2006
De gebruiker kan een Sudoku-puzzel invoeren,
bijvoorbeeld vanuit een file, of vanaf het toetsenbord.
Het C++-programma probeert deze met eenvoudige regels
op te lossen. Houd het zo simpel mogelijk: niet-grafisch.
Een Sudoku (in eenvoudigste vorm) bestaat
uit een vierkant 9 bij 9 veld,
waarin in een aantal vakjes al een getal
uit 1,2,3,4,5,6,7,8,9 staat.
In alle overige vakjes moet uiteindelijk ook een getal
uit 1,2,3,4,5,6,7,8,9 komen,
zodanig dat iedere rij en iedere kolom alle
getallen 1,2,3,4,5,6,7,8,9 bevat (dat heet een
Latijns vierkant) en verder
moeten ook de 9 disjuncte 3 bij 3 vierkanten (linksboven,
middenboven, ..., rechtsonder) alle getallen
1,2,3,4,5,6,7,8,9 bevatten.
Er is
hier
en
elders
veel meer informatie over Sudoku's te vinden.
Bedenk zelf enkele eenvoudige regels die met
de instellingen van het programma aan of uit kunnen
worden gezet, bijvoorbeeld recursief (tot zekere diepte)
wat proberen.
Denk bij het verslag ook aan rapportage over experimenten;
op internet staan talloze puzzels in allerlei moeilijkheidsgraderingen.
Gebruik eventueel dit
skelet-programma.
- Robotica; deadline 20 maart 2006
Maak vier robots voor het programma
RoboCom,
zie verder Robot-opgave.
Tip: lees eerst deze
documentatie.
Inleveren: verslag op papier (met bots in de appendix) en email
met de bots.
- Neuraal netwerk; deadline 10 april 2006
Schrijf in C++ een neuraal netwerk, dat van een hit op
een webserver het (eerste gedeelte van het) ip-adres voorspelt.
Meer informatie hier.
-
Genetisch algoritme; deadline 8 mei 2006
Schrijf in C++ een Genetisch algoritme, dat een
graafkleuringsprobleem oplost.
Meer informatie hier.
Tijdens de colleges wordt het volgende behandeld.
Het programma is uiteraard voorlopig,
zelfs als het semester voorbij is — op deze webpagina is steeds
de meest actuele versie te vinden.
Voor sheets van voorgaande jaren raadplege men
de oude pagina's.
Tijdens de colleges vinden ook discussies plaats
over de genoemde hoofdstukken van Russell/Norvig.
De sheets zijn voornamelijk gebaseerd op die van deze beide heren,
en op sheets die vorige docenten fabriceerden.
En voor de liefhebbers:
alle 330 sheets (in PDF, 1.3 MB).
Er wordt op het
tentamen vanzelfsprekend nog wel eens iets gevraagd wat niet (letterlijk)
op de sheets staat ...
- maandag 6 februari 2006
Algemene introductie; het
practicum, met name de eerste opgave.
Hoofdstuk 1
(Introductie) in vogelvlucht, zie de sheets:
Algemene introductie
|
Introductie
Leuk leesvoer:
Jason Hutchens' "How to pass the Turing test by cheating"
- maandag 13 februari 2006
Hoofdstuk 2 (Intelligente agenten), zie de sheets:
Intelligente agenten
- maandag 20 februari 2006
Hoofdstuk 3 (Probleemoplossen en zoeken), zie de sheets:
Probleemoplossen en zoeken
- maandag 27 februari 2006
Robotica.
In 2005 deden we
Lego-robots,
zie de
handleiding
(288 kB, PDF; geschreven door Mark Overmars).
Dit jaar, 2006, doen we
RoboCom.
Lees ook Hoofdstuk 25 (Robotica) van Russell en Norvig.
Dit alles ten behoeve van de tweede
practicum-opgave.
Zie ook de sheets:
Robotica
Hoofdstuk 3, vervolg.
Leuk leesvoer:
Rodney Brooks' "Intelligence without representation"
- maandag 6 maart 2006
Hoofdstuk 3, vervolg.
Hoofdstuk 4 (Gericht zoeken), zie de sheets:
Gericht zoeken
- maandag 13 maart 2006
Hoofdstuk 4, vervolg.
Hoofdstuk 5 (Constraint Satisfaction Problemen),
zie de sheets:
CSP's
- maandag 20 maart 2006
Algemene informatie over de derde
practicum-opgave;
Perl.
Hoofdstuk 20.5 (Neurale netwerken; voorheen Hoofdstuk 19),
zie de sheets:
Neurale netwerken
- maandag 27 maart 2006
Hoofdstuk 6 (Spel(l)en), zie de sheets:
Spel(l)en
Leuk leesvoer:
H.J. van den Herik, J.W.H.M. Uiterwijk en J. van Rijswijck,
Games solved: Now and in the future,
Artificial Intelligence
134 (2002) 277-311
(ophalen vanaf PC binnen universiteit)
- maandag 3 april 2006
Hoofdstukken 7 (Logisch redenerende agenten),
8 (Eerste orde logica)
en 10.3, zie de sheets:
Logische agenten
- maandag 10 april 2006
Algemene informatie over de vierde
practicum-opgave.
Vervolg van vorige keer.
Hoofdstuk 4.3 (Genetische algoritmen),
zie de sheets:
Genetische algoritmen
- maandag 24 april 2006
Hoofdstuk 18 (Leren van/uit observaties),
met name ID3, en Hoofdstuk 19.1, kort;
Hoofdstuk 21.1,2,3 (Reinforcement leren, geillustreerd met 17.1,2; kort);
zie de sheets:
Leren
- maandag 1 mei 2006
Hoofdstuk 13 (Onzekerheid; kort) en
Hoofdstuk 14 (Bayesiaanse netwerken),
zie de sheets:
Bayesiaanse netwerken
- maandag 8 mei 2006
Van alles.
Oude tentamens, zie het
archief,
in het bijzonder opgaven
2, 7a/c, 11, 12 en 18 van
Compilatie 2001-2005 (in PDF, 12 pagina's);
enkele antwoorden (in PDF).
Genoemde hoofdstukken komen steeds uit het boek van Russell en Norvig,
tweede druk — met dank voor de sheets en de meeste plaatjes.
Vragen en/of opmerkingen kunnen worden gestuurd
naar: kosters@liacs.nl.
16 juni 2006 — http://www.liacs.nl/home/kosters/AI/jaar2006.html