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.