TW2020 Optimalisering/Besliskunde 1 Technische Wiskunde (TUD

TW2020 Optimalisering/Besliskunde 1
Technische Wiskunde (TUD), Wiskunde (Leiden)
Versie 02/12/2014
Docenten:
Prof.dr.ir. K.I. (Karen) Aardal, [email protected], (hoorcollege H1-H6, H8)
TUD: kamer HB 04.160, UL (woensdag): kamer 215
http://ta.twi.tudelft.nl/wst/users/aardal/
Drs. P.L. (Pieter) van den Berg, [email protected], TUD: kamer HB 04.130,
UL (woensdag): kamer 215 (hoorcollege H7, H9-H13, werkcollege TUD)
Herman Blok, [email protected], kamer 217, (werkcollege UL)
Literatuur: Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial Optimization:
Algorithms and Complexity. Dover Publications, Inc., Mineola, NY, 1998.
Paperback.
Extra materiaal (E) (Beschikbaar via Webpagina K. Aardal).
Rooster (voorlopig):
Nr.
Datum
Hoofdstukken
Onderwerp
H1.
W1.
03/09
05/09
1, App A2
Introductie.
Opgaven: 1.1a, 1.5 (alleen N2 (t)), 1.6, 1.7, 1.11, (1.15)
H2.
10/09
2.1 – 2.3
W2.
12/09
2, E
LP in standaard vorm, basisoplossing, polyeder,
polytoop, relatie hoekpunt van polyeder en bfs.
Geometrie van LP, opgaven: 2.1, 2.3, extra opgave.
H3.
W3.
17/09
19/09
2.4 – 2.6, 2.8
2.5, 2.7
E
Simplexalgoritme.
Simplex: tableauvorm, cycling
Opgaven: extra opgaven.
H4.
W4.
24/09
26/09
3.1
3, E
Dualiteit.
Opgaven: 3.11, extra opgaven.
H5.
08/10
3.2 – 3.6
W5.
10/10
3, E
Farkas’ Lemma, Complementary slackness (toepassing;
kortste paden), duale simplex.
Opgaven: 3.6∗ , 3.21, extra opgaven.
H6.
W6.
15/10
17/10
6. – 6.3
6.3, 6.4, E
Max flow, min cut.
Ford-Fulkerson en Dijkstra, opgaven: extra opgaven
H7.
W7.
22/10
24/10
8.1 – 8.5
8.6
Analyse van algoritmen.
Simplex is niet polynomiaal. Opgaven: 8.3, 8.6a, 8.7
H8.
W8.
29/10
31/10
12.1, 12.3, 12.4
12.2
12, E
Opspannende bomen.
En O(|E| · log |V |) greedy algoritme voor MST
12.1, extra opgaven.
H9.
W9.
12/11
14/11
13.1-2
13, E
Geheeltallige optimalisering, totale unimodulariteit.
Opgaven: 13.1, 13.9, extra opgaven.
H10. 19/11
W10. 21/11
18.1, 14.1
E
Branch-and-bound(B&B), cutting planes.
Duale simplex. Opgaven: Extra opgaven.
H11.
15.1-15.6
26/11
W11. 28/11
E
Complexiteit (niet bewijs van ”Cook’s theorem”, niet bewijs
van Theorem 15.1). Van 15.6 alleen pp 358–363.
Voorbeelden van reducties.
H12. 03/12
W12. 05/12
17.1 - 17.2
17.2, 17.4
Benaderingsalgoritmen.
Worst-case voorbeeld TSP, Stelling 17.10.
H13. 10/12
W13. 12/12
Repetitie, vervolg.
Repetitie en vragen. Feedback op huiswerk.
Inleverdata huiswerk:
1. di 23/09
2. di 21/10
3. di 18/11
4. vr 12/12
2

Download Report