Besliskunde 2 (najaar 2006)

Algemeen

Dit vak is een voortzetting van het tweedejaarscollege Besliskunde 1. Een aantal andere mathematische beslissingsproblemen komt aan de orde en voor enkele onderwerpen uit Besliskunde 1 worden aanvullende resultaten en methoden afgeleid. Het vak is zeer geschikt voor studenten die later als wiskundige in de praktijk werkzaam willen zijn. De volgende onderwerpen worden behandeld: 1. Enkele onderwerpen uit de grafentheorie (vlakke grafen; kleurproblemen). 2. Enkele onderwerpen uit de Lineaire optimalisatie (duale simplex methode; primale-duale simplex methode; inwendige punt methoden). 3. Geheeltallige lineaire programmering (branch-and-bound, sneden, Lagrange relaxatie, andere technieken, handelsreizigersprobleem 4. Niet-lineaire optimalisatie (onbeperkte en beperkte optimalisatie, inwendige-punt methoden). 5. Netwerkoptimalisatie (grafen en matrices, kortste paden, stromen in netwerken, koppelingen, netwerk simplex methode). 6. Markovbeslissingsketens. 7. Scheduling. 8. Speltheorie.

College

Het college is 4 uur per week, dinsdag 11.15 - 13.00 uur en donderdag 09.15 - 11.00 (beide in zaal 401).

Literatuur

Voor de vakken Besliskunde 1, 2 en 3 worden momenteel nieuwe dictaten vervaardigd met als titels Besliskunde A, B en C.
Het dictaat Besliskunde A wordt de eerste vier weken gebruikt en is in pdf format verkrijgbaar:  Dictaat Besliskunde A.  Het bevat de stof over de onderwerpen Complexiteitstheorie, Grafentheorie, Combinatoriek en Enumeratie, en Lineaire Optimalisatie. Tevens staan er 147 vragen met uitgewerkte oplossingen in en 149 opgaven zonder uitwerkingen. Voor het college Besliskunde 2 zijn de volgende pagina's nodig: 88 - 148; 265 - 276; 296 - 317; 350 - 352.
Het dictaat Besliskunde B wordt de volgende drie weken gebruikt en is ook in pdf format verkrijgbaar:  Dictaat Besliskunde B.  Het bevat de stof over de Geheeltallige Optimalisatie.
Voor de onderwerpen Niet-lineaire Optimalisatie en Netwerk Optimalisatie wordt het dictaat  Dictaat Besliskunde III  gebruikt.
Voor de onderwerpen Scheduling en Speltheorie gebruiken we de desbetreffende hoofdstukken uit het Dictaat Besliskunde 2 .

Tentamen

Het vak kan voor 6 en voor 10 ECTS worden gedaan. Voor 6 ECTS moet de stof tot en met het hoofdstuk Niet-lineaire Optimalisatie worden gedaan.
Het tentamen bestaat voor 50% uit wekelijks te maken van opgaven en voor 50% uit een schriftelijk tentamen.
Het schriftelijk tentamen gaat voor een deel over een beperkt aantal stellingen en voor een deel over het toepassen van de behandelde stof (dit laatste deel als open boek tentamen).
Het tentamen is op dinsdag 9 januari 10.00 - 13.00 uur.

Stellingen voor het tentamen

De volgende stellingen behoren tot de tentamenstof (alleen wat betreft de stof die is behandeld; dit lijsje wordt wekelijks bijgewerkt).
Dictaat A:
- Hoofdstuk 2: de Stellingen 2.49, 2.50, 2.73 en 2.74.
- Hoofdstuk 4: de Stellingen 4.29, 4.30 en de Lemma's 4.6 en 4.7.
Dictaat B:
- Hoofdstuk 5: de Stellingen 5.3, 5.5 en 5.12.
Dictaat III:
- Hoofdstuk 1: Stelling 1.9.
- Hoofdstuk 2: de Stellingen 2.10, 2.20, 2.21, 2.47 en 2.48.
Dictaat Besliskunde 2:
- Hoofdstuk 6: Lemma 6.2 en Stelling 6.8.
- Hoofdstuk 7: de Stellingen 7.1 en 7.6.
Deze stellingen staan in deze pdf file.

Weekprogramma

Hieronder staat het programma voor de eerste 12 weken. De stof die behandeld is en de in te leveren opgaven worden wekelijks 'opgefrist'. Op dit moment is dat t/m week 12 het geval.
Week College In te leveren opgaven (deadline)
Week 1: 05/09 en 07/09 Hoofdstuk 2: paragraaf 2.4 (behalve: de Stellingen 2.37, 2.38, 2.40, 2.41, 2.42, 2.43, 2.52, 2.53 en 2.54; de lemma's 2.8, 2.9, 2.10 en 2.11)
 Opgaven 2.37, 2.39 en 2.44  (21/09)
Week 2: 12/09 en 14/09 Hoofdstuk 2: Paragraaf 2.5 (behalve: de stellingen 2.61, 2.63, 2.64, 2.65, 2.66, 2.67, 2.68, 2.69, 2.70 en de lemma's 2.12 en 2.13; paragraaf 2.5.4 is ook niet behandeld)
 Opgaven 2.46, 2.48 en 2.49 (28/09)
Week 3: 19/09 en 21/09 Hoofdstuk 4: Paragraaf 4.7 Opgaven 4.24, 4.25 en 4.26 (05/10)
Week 4: 26/09 en 28/09 Hoofdstuk 4: Paragraaf 4.9.3
 Opgaven 4.34, 4.35 en 4.36 (12/10)
Week 5: 05/10 Hoofdstuk 5: Paragraaf 5.1 (deel)
 Opgaven 5.1, 5.2 en 5.6 (19/10)
Week 6: 10/10 en 12/10 Hoofdstuk 5: Paragrafen 5.1 (deel), 5.2 en 5.3
 Opgaven 5.7, 5.9 en 5.11 (31/10)
Week 7: 17/10 en 19/10 Hoofdstuk 5: Paragraaf 5.4
 Opgaven 5.12, 5.13 en 5.15 (09/11)
Week 8: 31/10 en 02/11 Hoofdstuk 1: Paragraaf 1.1 en 1.2 (deel)
 Opgaven 1.1, 1.5 en 1.7 (16/11)
Week 9: 07/11 en 09/11 Hoofdstuk 1: Paragraaf 1.3 (behalve de sectie 1.3.4) en paragraaf 1.4 (sectie 1.4.1)
 Opgaven 1.14, 1.18 en 1.23 (23/11)
Week 10: 14/11 en 16/11 Hoofdstuk 2: De paragrafen 2.1 (behalve de secties 2.1.5 en 2.1.6) en 2.2 (behalve sectie 2.2.6)
 Opgaven 2.1, 2.13 en 2.16 (30/11)
Week 11: 21/11 en 23/11 Hoofdstuk 2: De paragrafen 2.3.6 en 2.3.7 (alleen de toepassing van het scheduling probleem
 Opgaven 2.23, 2.39 en 2.40 (07/12)
Week 12: 28/11 en 30/11 Hoofdstuk 2: De paragrafen 2.4.1, 2.4.2, 2.4.3 en 2.4.4
 Opgaven 2.42, 2.43 en 2.44 (14/12)
Week 13: 05/12 en 07/12 Hoofdstuk 6 (Scheduling): De paragrafen 6.1, 6.2 (model A en B), 6.3
 Opgaven 6.1, 6.3 en 6.7 (21/12)
Week 14: 12/12 en 14/12 Hoofdstuk 7 (Speltheorie): De paragrafen 7.1, 7.2, 7.3 en 7.4
 Opgaven 7.1, 7.4 en 7.7 (21/12)