Videregående Algoritmik 2005-06
Litteratur og pensum

Litteratur

Pensum

Første kursusafsnit (14.11.05 - 01.12.05)

• 26.2: Detaljerne i korrekthedsbeviset for Edmonds-Karp kræves ikke.
• 26.4: Det er tilstrækkeligt at forstå figurerne 26.9 og 26.10 samt den ledsagende tekst.
• 29: Alternative beviser for bl.a. simplex algoritmens korrekthed, Lemma 29.8 og Theorem 29.10 findes i de ved forelæsningerne udleverede noter.

• JK notesæt 2: Kendskab til "Complementary Slackness Condition"
• JK notesæt 4: Af "Matrices, determinants, unimodularity" kræves kendskab til definitionen af "unimodularity" samt det deraf afledte "Corollary": "... where A is either
  1. the vertex-edge incidence matrix of a directed graph, or
  2. the vertex-edge incidence matrix of an undirected bi-partite graph ..."

Der har under kursusafsnittet været lejlighed til at stifte bekendtskab med flere tidligere eksamens- og projektopgaver.

Det kan forventes, at opgaven til skriftlig eksamen, 23. januar 2006, vil blive "et eller andet" i samme stil, og at alle hjælpemidler i form af bøger og noter men ikke lommeregner vil være tilladte. Med bogen ved hånden vil man således ikke blive krævet til regnskab med hensyn til eksempelvis lange korrrekthedsbeviser for diverse algoritmer.

Hvis et spørgsmål lyder: "gør dette eller hint" og der ikke stilles krav om en specifik fremgangsmåde, er man frit stillet i valg af denne. Bedes der explicit om brug af simplex algoritmen, er man ligeledes frit stillet i valg mellem slackformen eller tableauformatet.

Det vides ikke i skrivende stund, om det vil være tilladt at bruge blyant (og viskelæder) ved den skriftlige eksamen. Nævnes det ikke tidligere på kursets hjemmeside, vil det i hvert fald fremgå af opgavesættets forside.

Detaljeret (kursusafsnit 2)

• 31.1, 31.2,
• 31.3 (stop ved afsnittet "Subgroups" pp. 866)
• 31.4, 31.6, 31.7
• 31.8 (stop ved afsnittet "Error rate of the Miller-Rabin primality test" pp. 893)
• 34.1, 34.2, 34.3, 34.4, 34.5 (ej Lemma 34.6),
• 35.0, 35.1, 35.2, 35.5.

• Del 1 "branch-and-bound"

Kursorisk

• 31.5 "The Chinese Reminder theorem"
• 31.8 (fra og med "Error rate of the Miller-Rabin primality test")
• Bevis for Lemma 34.6

• Del 2 "generelle optimeringsheurstikker"