Besliskunde 3

Algemeen Evenals Besliskunde 2 is Besliskunde 3 een vervolg op het tweedejaarscolleges Besliskunde 1. Als voorkennis is alleen Besliskunde 1 vereist. Besliskunde 2 mag, maar hoeft dus niet gevolgd te zijn. Het vak Besliskunde 3 is zeer geschikt voor studenten die later als wiskundige in de praktijk werkzaam willen zijn. Een aantal mathematische beslissingsproblemen komt aan de orde, en wel de volgende onderwerpen:

Dynamische Programmering
Markov Beslissingstheorie
Markovprocessen
Wachttijdtheorie
Scheduling
Knapzakprobleem
Projectplanning
Semi-definiete Programmering

Besliskunde 3 kan voor 6 of 10 EC worden gedaan. Voor 10EC moeten meer huiswerkopgaven gemaakt worden.

Docenten en assistent

Floske Spieksma (spieksma@math.leidenuniv.nl)
Dirk Sierag (d.sierag@telfort.nl) assistent voor het huiswerk (en vragen).

Werkvorm
De colleges zijn in zaal 401 en op de volgende tijden:

maandag : 9.00-10.45 (vanaf 6 februari)
vrijdag 11.15-13.00 (vanaf 10 februari)

Literatuur
Het Dictaat Besliskunde 3 is als pdf file beschikbaar. Het is bij de secretaresse te verkrijgen voor 12,50 euro. Het bevat ook een aantal uitgewerkte vragen.

Tentamen
Het tentamen bestaat voor 50% uit wekelijks te maken opgaven en voor 50% uit een schriftelijk tentamen.
Het schriftelijk tentamen gaat voor een deel over een aantal stellingen en voor een deel over het toepassen van de behandelde stof (dit laatste als open boek tentamen).
Voor te laat ingeleverd huiswerk gaat er per week te laat ingeleverd een punt van het cijfer af, tenzij je geldige redenen hebt, wegens welke je niet aan de deadline hebt kunnen voldoen. Resultaten kun je hier vinden.
Het schriftelijk tentamen is op 11 juni, 14-17 uur..

Stellingen voor het tentamen
Worden nog bekend gemaakt.

Weekprogramma
Het weekprogramma (te behandelen stof en te maken opgaven) wordt in de loop van het college wekelijks bekend gemaakt. Hieronder staat een voorlopig programma.


Week	College	In te leveren opgaven (deadline)
Week 1: 06/02 en 10/02	Hoofdstuk 1 Hoofdstuk 2, paragrafen 2.1, 2.2 (deel)	HW 1: Opgaven 1.2, 1.4 en 2.1 Voor 10EC: 1.1 en 1.3 (extra) (24/02)
Week 2: 13/02 en 17/02	Hoofdstuk 2: paragrafen 2.2 (deel) en 2.3	HW 2: Opgaven 2.6, 2.7 en 2.9 Voor 10EC: 2.4 en 2.8 (extra) (02/03)
Week 3: 20/02 en 24/02	Hoofdstuk 2: paragrafen 2.3 (af) 2.4 en 2.5 (deel)	geen HW
Week 4: 27/02 en 02/03	Hoofdstuk 2: paragraaf 2.5 (deel)	HW 3: Extra opgaven 0.1, 0.2, 0.4 Voor 10 EC: 2.11 en 2.13 (extra) (16/03)
Week 5: 05/03 en 09/03	Hoofdstuk 2: paragraaf 2.5 (deel) Hoofdstuk 3: paragrafen 3.1, 3.2, 3.3 (deel)	HW 4: Opgaven 2.16, 3.2, 3.6 Voor 10 EC: 3.3, 3.5 (extra) (23/03)
Week 6: 12/03 en 16/03	Hoofdstuk 3: 3.3 (deel), 3.4, 3.5, 3.6.	HW 5: Opgaven 3.10, 3.13, 3.18 Voor 10 EC: 3.11, 3.17 (extra) (30/03)
Week 7: 19/03 (niet op 23/03!)	Hoofdstuk 4: paragrafen 4.1, 4.2, 4.3, 4.4	(05/04)
Week 8: 30/03	Hoofdstuk 4: paragraaf 4.4, 4.5	HW 6: Opgaven 4.2, 4.3, 4.4, 4.6 Voor 10 EC: 4.5, 4.7 (extra) (20/04)
Week 9: 02/04	Hoofdstuk 4: paragraaf 4.6 (deel)
Week 10: 13/04	Hoofdstuk 4: paragrafen 4.6 (deel), 4.7 (deel)	HW 7: Opgaven 4.10, 4.11 en 4.13 Voor 10EC: 4.8 en 4.12 (extra) (27/04)
Week 11: 16/04 en 20/04	Hoofdstuk 4: paragraaf 4.7 (deel) Hoofdstuk 5: paragrafen 5.1, 5.2.	HW 8: Opgaven 4.14, 4.15, en 5.2 Voor 10EC: 4.16 en 5.1 (11/05)
Week 12: 23/04 en 27/04	Hoofdstuk 5: paragrafen 5.3, 5.4.	HW 9: Opgaven 5.4, 5.6, 5.7 Voor 10 EC: 5.5, 5.8 (extra) (25/05)
Week 13: 07/05 en 11/05	Hoofdstuk 6: paragrafen 6.1, 6.3, 6.3 (deel), 6.5 (deel)	HW 10 Opgaven 6.2, 6.4, 6.5 Voor 10 EC: 6.1, 6.3 (extra) (02/06)
Week 14: 14/05		(7/6)
Week 15: 21/05 en 25/05		(05/06)
Tentamen

Extra Opgave VII
Beschouw een Geboorte-Sterfte proces. Interpreteer geboorts als klanten-aankomsten IN het systeem. laat zien dat de stationaire verdeling Pi waarin klanten bij binnenkomst het systeem zien, gegeven wordt door Pi_j=lambda_j P_j/\sum_k lambda_k P_k, waarbij (P_k)_k de stationaire verdeling van het systeem is. Hint: kijk naar de argumenten in het `bewijs' van PASTA. Het staat er al bijna.

Extra Opgave VIII
Drie steden A, B en C zijn verbonden door twee kabelgroepen. Groep 1 bestaat uit 3 kabels tussen A en B, groep 2 bestaat uit 2 kabels tussen B en C. Gesprekken tussen A en B, B en C, en A en C worden aangevraagd volgens onafhankelijke Poissonprocessen met parameters lambda_1=2, lambda_2=1, en lambda_3=3 resp. De gespreksduren zijn exponentieel verdeeld met parameters mu_1=1, mu_2=0,5 en mu_3=1 resp. Een gesprek tussen A en C houdt dus 1 kabel tussen A en B en 1 kabel tussen B en C bezet. We zijn geinteresseerd in de bezettingsgraden van de twee kabelgroepen.
a: Bepaal een geschikte toestandsbeschrijving. Wat is de verz. van mogelijke toestanden van het systeem? (Het zijn er 20 in totaal).
b: Laat zien dat het corresponderende Markov proces reversibel is.
c: Bereken de stationaire kans dat een aanvraag voor een gesprek tussen A en C verloren gaat.