Department of Information and Computing Sciences

Departement Informatica Onderwijs
Bachelor Informatica Informatiekunde Kunstmatige intelligentie Master Computing Science Game&Media Technology Artifical Intelligence Human Computer Interaction Business Informatics

Onderwijs Informatica en Informatiekunde

Vak-informatie Informatica en Informatiekunde

Zoekalgoritmen

Te lang geleden voor docent- en roosterinformatie
Inhoud:

Veel praktijkproblemen, zoals het maken van roosters, het configureren van computernetwerken en het plannen van routes, worden gekenmerkt door een grote ruimte van potentiële oplossingen. Het oplossen van een dergelijk probleem komt dan neer op het zoeken naar een daadwerkelijke oplossing in deze ruimte. Als de ruimte heel groot is, zou het systematisch doorzoeken veel te veel tijd kosten. In de cursus Zoekalgoritmen zullen we aandacht besteden aan het ontwerpen van slimme algoritmen waarmee een grote ruimte van potentiële oplossingen efficiënt doorzocht kan worden.

De volgende onderwerpen zullen onder andere in de cursus aan bod komen:

  • het representeren van een praktijkprobleem als zoekprobleem;
  • algoritmen voor ongeïnformeerd zoeken: breadth-first search, depth-first search, backtracking;
  • heuristisch zoeken: best-first search, heuristische depth-first search, A, A*;
  • zoeken met kosten: cost-based search, heuristische cost-based search;
  • zoeken met beperkt geheugen: hill-climbing, tabu search, simulated annealing;
  • zoeken met een tegenstander: minimax, alfa-beta pruning;
  • constraint satisfaction: chronologische backtracking, forward checking, backjumping.

Literatuur:Voor de cursus wordt gebruikt gemaakt van de volgende literatuurbronnen:
  • kopieën van de tijdens de colleges getoonde transparanten;
  • S. Russell and P. Norvig (2003). Artificial Intelligence: A Modern Approach (Second Edition), Prentice Hall. ISBN: 0-13-080302-2 (US ISBN: 0-13-790395-2).

Werkvorm:De cursus omvat hoorcolleges, werkcolleges/vragenuren en een practicum. Tweemaal per week wordt een hoorcollege verzorgd en eenmaal per week wordt een bijbehorend werkcollege/vragenuur aangeboden; bij het practicum worden enkele (verplichte) contactmomenten georganiseerd.

Toetsvorm:De toetsing van het vak vindt plaats door middel van een tussentijdse toets over de eerste helft van de behandelde stof en een eindtoets die in principe over de gehele stof gaat; daarnaast wordt het practicum getoetst door middel van programmatuur, een scriptie en een mondelinge voordracht.

Inspanningsverplichting voor aanvullende toets:De minimale inspanningsverplichting bestaat uit deelname aan de eindtoets en een voltooid practicum (inleveren van programmatuur en een paper, en het houden van een voordracht). Men komt in aanmerking voor deelname aan aanvullende toetsing als het eindcijfer van het vak op basis van de toetsen en het practicum minstens 4.0 is. Voor verdere details wordt verwezen naar de vakpagina van Zoekalgoritmen.
wijzigen?