2M150 Complexiteit (cursusjaar 2007/2008)
Deze cursus wordt niet meer gegeven.
Een videoregistratie
van de colleges is beschikbaar.
Op 11 november 2008 en 23 januari 2009 zijn de laatste tentamens.
Voor nadere vragen wende men zich tot de docent.
Nieuws
- 17 november 2008
Er is gelegenheid tot inzage in het tentamen van
11 november 2008
op donderdag 20 november 2008 van 13.00 tot 13.30 uur en
op woensdag 26 november 2008 van 10.00 tot 10.30 uur, HG 7.32.
- 14 november 2007
Er is gelegenheid tot inzage in het tentamen van 14 november 2007 op
29 november 2007 van 13.00 tot 13.30 uur en op 10 december 2007 van
11.00 tot 11.30 uur, HG 7.32.
- 1 november 2007
Het proeftentamen is geactualiseerd.
- 23 september 2007
Op maandag 8 oktober is er geen college.
- 24 augustus 2007
Het college begint op maandag 27 augustus 2007 en vindt plaats
in zaal AUD 16 gedurende de blokken A en B.
Verplichte literatuur
- D. Harel, Algorithmics: The Spirit of Computing, Addison
Wesley (2nd edition 1992, third edition 2004)
hoofdstukken 6 t/m 9, hoofdstuk 11
en enkele stukken uit hoofdstukken 4 en 5
- De reader Complexiteit 2M150 (uitgave 2005 of 2006) met daarin
-
blz. 248-271 uit
M. Sipser, Introduction to the Theory of Computation, PWS Publishing
Company 1997;
-
blz. 1-5 en 27-32 uit
V.V. Vazirani, Approximation Algorithms, Springer 2001;
-
blz. 511-524 uit
R. Johnsonbaugh and M. Schaefer,
Algorithms (international edition), Pearson Education 2004
-
blz. 531-552 uit
J. Kleinberg and E. Tardos,
Algorithm Design, Pearson Education 2005
- Daarnaast zijn op college ook een aantal passages behandeld uit
het boek van P. Linz, An introduction to Formal
Languages and Automata, D.C. Heatch and Company 1966, dat in het
eerste jaar gebruikt is.
Planning
| 27/8 |
Ch.9 Algorithmic universality and its robustness |
[sheets] |
| 3/9 |
Ch.6 The efficiency of algorithms |
[sheets] |
| 10/9 |
Ch.7 Inefficiency and intractability |
[sheets] |
| 17/9 |
Ch.8 Noncomputability and undecidability |
[sheets] |
| 24/9 |
Ch.9 Algoritmic universality and its robustness (cont.) |
[sheets] |
| 1/10 |
tussenweek |
|
| 8/10 |
geen college |
|
| 15/10 |
NP-completeness (Sipser p248-271) |
[sheets] |
| 22/10 |
NP-completeness (Sipser p248-271) |
[sheets] |
| 29/10 |
Approximation (Vazirani, Johnsonbauch & Schaefer) |
[sheets] |
| 5/11 |
Proeftentamen |
[hier] |
Opgaven
Nuttige opgaven in het boek van Harel (geselecteerde uitwerking vanaf
pagina 369, 2nd ed., resp., pagina 404, 3rd ed.):
6.2, 6.5, 6.13;
7.2, 7.12, 7.13;
8.5, 8.6, 8.15, 8.18;
9.7, 9.8, 9.11, 9.12.
Tentamen
Het schriftelijk tentamen is gepland op woensdagmorgen 14 november 2007.
De tweede gelegenheid wordt geboden op maandagmorgen 7 januari 2008.
De tentamenstof beslaat de stof die op college behandeld is plus de
verplichte literatuur m.u.v. het stuk uit de reader van Kleinberg and Tardos.
Er zijn oude tentamens en proeftentamens beschikbaar:
Docent
Dr. E.P. de Vink, HG 7.32, evink(at)win.tue.nl, 040-2473146