Zoekalgoritmen

Vakcode:

INFOZA

Studiepunten:

7.5 ECTS (=5.25 oude studiepunten)

Periode:

periode 4 (week 17 t/m 27, dwz 19-4-2004 t/m 2-7-2004; herkansing week 35)

Deelnemers:

tot nu toe 99 inschrijvingen

Rooster:

Dit is een oud rooster!

vorm	groep	tijd	week	zaal	docent
college		di 11-13	17-20,22-24,26	KRUYT-W105	Peter Bosman Marinus Veldhorst
		di 11-13	25	AARD-klein
		vr 09-11	17,19,20,22-26	AARD-groot
werkcollege	groep 1	ma 11-13	18-20,22,24-26	BBL-505
	groep 1	wo 15-17	17,18,20,22-26	BBL-505
	groep 2	ma 13-15	18-20,22,24-26	BBL-505
	groep 2	do 11-13	17-20,22-26	BBL-505
	groep 3	di 09-11	17-20,22-26	BBL-416
	groep 3	do 09-11	17-20,22-26	BBL-416

Inhoud:

In deze cursus worden de volgende hoofdonderwerpen behandeld: representatie van een probleem als zoekprobleem, verschillende klassen zoekalgoritmen, specifieke algoritmen voor elke klasse.

Een specifieke indeling van onderwerpen is als volgt:

Representeren van een probleem als zoekprobleem en de relatie met het kortste pad in een netwerk;
Algoritmen voor ongeïnformeerd zoeken: breadth-first search, depth-first search en varianten;
Heuristisch zoeken: best-first search, heuristische depth-first search, A, A^*, ontwerpen van heuristieken;
Zoekalgoritmen met beperkt geheugen: hill-climbing, tabu search;
Branch-and-bound, minimax, alpha-beta algoritme;
Constraint satisfaction;
Stochastische zoekalgoritmen en zoekalgoritmen voor continue ruimtes: locaal (gradiënt-gebaseerd) zoeken, random restart, simulated annealing, evolutionaire algoritmen.

Literatuur:

Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach (Second Edition). Prentice Hall, 2003. ISBN: 0-13-080302-2 (US ISBN: 0-13-790395-2).

Werkvorm:

Het vak bestaat uit 16 à 18 hoor- en werkcolleges, waarbij alle bijeenkomsten 2 uur duren. Verder is er een practicum bij dit vak.

Toetsvorm:

Toetsing vindt plaats door middel van twee schriftelijke toetsen en een aantal practicumopgaven. De uiteindelijke weging wordt nog bepaald.

Inspanningsverplichting voor aanvullende toets:

Om aan de aanvullende toets te mogen meedoen is ontbreken van ten hoogte 1 toetsactiviteit toegestaan.

Beschrijving:

Het oplossen van problemen laat zich in het algemeen beschrijven als het zoeken in een toestandsruimte, of zoekruimte. Voor het zoeken naar een (optimale) oplossing in een toestandsruimte moeten soms alle toestanden onderzocht worden. Meestal kan het aantal te onderzoeken toestanden echter sterk gereduceerd worden door gebruik te maken van kennis van het onderhavige probleem. De wijze van representatie van toestanden en oplossingen speelt hierbij een belangrijke rol. Voor het doorzoeken van een toestandsruimte zijn verscheidene algoritmen ontwikkeld, variërend van systematische tot niet-systematische, waaronder stochastische, zoekalgoritmen. In dit vak worden verschillende soorten zoekalgoritmen behandeld en, waar mogelijk, geïllustreerd met toepassingen.

wijzigen?