Bachelorproject in de Besliskunde (voorjaar 2008)
Algemeen
Het is mogelijk om in het voorjaar 2008 een bachelorproject in de
mathematische besliskunde te doen. Het aantal studiepunten hiervoor
bedraagt 18 ECTS. Het is aan te raden dit te combineren met een of meer
vakken in de besliskunde, bijvoorbeeld Besliskunde
3. Voor het bachelorproject neemt men deel aan
het Bachelorseminarium
Analyse, Stochastiek en Besliskunde, dat in de periode 22 januari -
eind
mei/begin juni wordt
gehouden (op de dinsdagen 22 en 29 januari van 11.15-13.00 en
van 13.45-15.30 uur en vanaf 6 februari op woensdagmiddag 13.45 uur).
Iedere
student geeft hierin tweemaal een voordracht en aan het einde van het
semester dient de
scriptie te worden ingeleverd. Daarnaast doet men een project waarover
de scriptie wordt geschreven.
Projecten
Voor het kiezen van een project binnen de mathematische besliskunde
zijn
er de volgende projecten (eventueel zijn andere projecten in overleg
ook mogelijk):
1. Complexiteit van
Markovbeslissingsketens
Bij Markovbeslissingsketens hebben we te maken met een aantal Markov
ketens, waaruit de beste (volgens een bepaald criterium) moet worden
gekozen. Er zijn verschillende manieren om Markov beslissingsketens te
klassificeren. Er kan onderscheid worden gemaakt tussen communicerende
en niet-communicerende
Markov beslissingsketens. Een tweede klassificatie betreft de
ergodische structuur. We maken onderscheid tussen irreducibele,
unichain en multichain
Markov beslissingsketens.
Bij dit project gaat
het om deze klassificaties op een efficiente manier (in de zin van de
complexiteitstheorie) te bepalen of om te bewijzen dat er geen
efficiente manier bestaat. Met name wordt gekeken naar
een recent artikelen uit 2007 en naar een open probleem voor
deterministische ketens.
Voor een verdere beschrijving zie deze
file.
2. Hoe te serveren bij
tennis?
We beschouwen een simpel model, waarin beide spelers kunnen kiezen uit
twee typen services: type 1 (harde service) en type 2 (langzame
service). De harde service gaat vaker mis, maar is moeilijk
te retourneren als deze in is; de langzame service is betrouwbaarder,
maar makkelijke te retourneren.
We nemen aan dat we over de volgende gegevens beschikken: de kansen dat
een harde resp. langzame service goed is (in is),
en de kansen dat je het punt wint als je harde
resp. langzame service goed is.
De vraagstelling luidt: gegeven de score in de game en of je een eerste
of een tweede service moet slaan, wat is de beste strategie om de game
te winnen?
Dit probleem kan worden geanalyseerd met behulp van een
Markovbeslissingsketen.
Voor een verdere beschrijving zie deze
file.
3. Algoritmen voor
multichain Markov
beslissingsketens
Bij Markovbeslissingsketens hebben we te maken met een aantal
Markovketens, waaruit de beste (volgens een bepaald criterium) moet
worden
gekozen. Als er een ketens is met meerdere recurrente klassen,
dan spreken we van een multichain Markovbeslissingsketen. Voor
dergelijke ketens bestond tot voor kort geen waarde-iteratie
methode om de gemiddelde opbrengst te optimaliseren. In 2007 hebben de
Japanners Iki, Horiguchi en Kurano een waarde-iteratie methode
voorgesteld voor multichain Markovbeslissingsketens.
In dit project wordt hun artikel (en enkele andere artikelen waarop dit
gebaseerd is) bestudeerd en wordt een implementatie van deze
methode gemaakt.
Voor een verdere beschrijving zie deze
file.