Videregående Algoritmik 2006-07
Litteratur og pensum

Litteratur

[CLRS]	Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, Second Edition, MIT Press, Cambridge (2001).
[KB1]	Kursusbog (del 1): Branch-and-bound http://www.diku.dk/undervisning/2006-2007/2006-2007_b2_va/branchbound.pdf
[KB2]	Kursusbog (del 2): Generelle Optimeringsheuristikker. http://www.diku.dk/undervisning/2006-2007/2006-2007_b2_va/Laursen.pdf

Pensum

[CLRS]

26, 26.1, 26.2, 26.3, 26.4 (stop ved afsnittet "Correctness of the push-relabel method" pp. 674).
29, 29.1, 29.2, 29.3, 29.4, 29.5.
31, 31.1, 31.2. 31.3 (stop ved afsnittet "Subgroups" pp. 866), 31.4, 31.5, 31.6, 31.7, 31.8.
34, 34.1, 34.2, 34.3, 34.4, 34.5 (ej Lemma 34.6).
35, 35.1, 35.2, 35.5.

[KB1]

"Branch-and-bound"

[KB2]

"Generelle Optimeringsheuristikker"

Af ovenstående pensum kan følgende læses kursorisk

Kursorisk betyder at man bør kende hovedresultaterne, men man vil ikke blive afkrævet detaljer i beviserne.

[CLRS]

Bevis for Lemma 26.8 og Theorem 26.9 (beviset for køretiden af Edmonds-Karps algoritme).
31.5 "The Chinese Reminder theorem"
31.8 (fra og med "Error rate of the Miller-Rabin primality test")
Bevis for Lemma 34.6

[KB2]

"Generelle Optimeringsheuristikker"

8. januar 2007