Datalogisk Institut
Københavns Universitet

Videregående Algoritmik, blok 2, 2006-07

[Meddelelser] [Opgaver] [Litteratur] [Pensum] [SIS]

Forudsætninger

Algoritmer og datastrukturer (AD)

Formål

Kurset tager udgangspunkt i lineær programmering (LP) hvor der gennemgås en række optimeringsmodeller med mange anvendelser samt dertil hørende algoritmer. Herpå præsenteres "maximum flow" problemet og LP-formuleringer nævnes. Vægten vil derefter blive lagt på formulering og løsning af svære problemer. Kurset er teoretisk orienteret, men vil også inddrage praktisk erfaring i form af en række projektopgaver. På kurset gennemgås en række vigtige algoritmiske problemer inden for kryptering, netværksoptimering og lineær programmering. Endvidere indføres teorien for NP-fuldstændighed samt algoritmiske principper for løsning af NP-hårde problemer (branch-and-bound, approksimationsalgoritmer og heuristikker).

Forelæsning og øvelser

Undervisere: David Pisinger (kursusansvarlig) (DP), Martin Paluszewski (MP), Martin Zachariasen (MZ), Pawel Winter (PW)

Instruktorer: Berit Løfstedt, Christian Wulff-Nielsen, Mikkel Engbo Jørgensen

Forelæsninger: Tirsdag 13-15 og fredag 10-12, Lille Auditorium, DIKU

Øvelser:
Hold 1 tirsdag 11:15-13:00 i N004, fredag 08:15-10:00 i N004 (Berit)
Hold 2 tirsdag 11:15-13:00 i N010, fredag 12:15-14:00 i N014 (Mikkel)
Hold 3 tirsdag 11:15-13:00 i N026, fredag 12:15-14:00 i N018 (Christian)
Første øvelsesgang er fredag d. 17. november, sidste øvelsesgang er tirsdag 16. januar.

Instruktormøde: Tirsdag 10.00-11.00.

Meddelelser

[27 mar] Eksamensspørgsmål til mundtlig re-eksamen 20. april 2007 findes her
[31 jan] Karaktliste findes her
[26 jan] Eksamen, den 26. januar 2007, Opgavesæt og vejledende løsninger findes her.
[16 jan] Gamle eksamensopgaver er blevet indscannet. Se her
[14 jan] Husk at der er øvelsesgang på tirsdag d.16, hvor et eksamenssæt vil blive gennemregnet.
[10 jan] Detaljeret pensumliste findes her
[8 jan] Køretider for P2 konkurrence her
[29 dec] Mindre præciseringer af P2 findes her.
[14 dec] De rettede opgaver fra P1 kan hentes på de respektive øvelseshold i morgen, fredag, til øvelserne.
[13 dec] Christians øvelseshold, hold 3, er flyttet fra tirsdag d. 2. januar til tirsdag d. 19. december. Tidspunktet er 11-13 i lokale N004. Det er ikke en spørgetime, men der kan stilles spørgsmål ang. P2.
[12 dec] P2 er stillet. Kan findes her.
[28 nov] Fredag d. 1. dec er der udelukkende spørgetime, samtlige øvelsesopgaver er flyttet til den følgende tirsdag. Se i øvrigt opgavelisten.
[24 nov] P1 er stillet. Kan findes her.
[22 nov] Øvelseshold 2 er om tirsdagen fremover flyttet fra lokale N014 til N010.
[19 nov] Øvelseshold 1 er tirsdag d. 21/11 flyttet til kl 15.15-17. Øvelserne kommer til at foregå i lokale N022.
[15 nov] Forelæsningen tirsdag 21/11 er flyttet til Aud 3, HCØ.
[6 nov] Kursusbogen "branch-and-bound" findes som pdf-fil under Litteratur
[5 nov] Forelæsninger holdes fredag 10-12 og ikke som tidligere annonceret 13-15. Samtidig flyttes øvelserne om fredagen.
[6 oct] Kursushjemmeside oprettet

Undervisningsplan

Foreløbig plan for kurset. Forbehold for ændringer.

Dato	Lærer	Indhold/Emne	Projektopgave	Litteratur	Plancher	Opgaver (foreløbige)
ti:14/11 fr:17/11	PW PW	Lineær programmering Lineær programmering		Cormen 29.1-29.5	ti:pdf fr:pdf	29.1-2, -3, -4, -5, -6, -7, -8, -9. BBB (hjemmeopgave, udleveres ved 1. forelæsning, afleveres den 24/11, ej obligatorisk) 29.3-2, -3, -4, -5, -6. 29.5-3, -4, -5
ti:21/11 fr:24/11	PW MZ	Lineær programmering Aud 3, HCØ Maximum flow i netværk	P1 stilles, 24/11	Cormen 29.1-29.5 Cormen 26.1-26.2 (s. 643-660)	ti:pdf fre:pdf	29.4-1, 29.4-5, 29-2, VA-P2 (hjemmeopgave, udleveres ved 3. forelæsning, afleveres den 1/12, ej obligatorisk). 26.1-4, 26.1-9, 26.2-1, 26.2-2.
ti:28/11 fr:1/12	MP --	Maximum flow i netværk ingen forelæsning		Cormen 26.2-26.4 (s. 660-674)	pdf	Spørgetime. 26.2-8, 26.3-2. Håndkør push-relabel algoritmen på flownetværket i figur 26.6. Eksamensopgave, 19. januar 2005, opg 1-10.
ti:5/12 fr:8/12	DP DP	NP-fuldstændighed NP-fuldstændighed	P1 afleveres 5/12 kl 10.30	Cormen 34.1-34.5	ti:pdf fr:pdf	34.1-1, 34.1-4, 34.1-6, 34.2-1, 34.2-4, 34.2-6, 34.2-8, 34-3 a)+b)+c), 34.1-2 34.5-2, 34.3-3, 34.4-5, 34.4-6, 34.4-7, 34.5-1, 34.5-5, 34.5-6, 34-3 d)+e)+f)
ti:12/12 fr:15/12	DP DP	NP-fuldstændighed Branch and bound	P2 stilles 12/12	Cormen 34.1-34.5 Kursusbog, del 1	ti:pdf fr:pdf	Cormen 34-2, b&b opg. 1,2 projektopgave P2 b&b opg. 4,5,6,7,8 Projektopgave 3(2004) 1,4,5,6.
ti:2/1 fr:5/1	DP DP	Approximations algoritmer, Heuristikker		Cormen 35.1-35.5 Kursusbog, del 2	ti:pdf fr:pdf	35.1-1, 35.1-2, 35.1-4, 35.1-5, 35-1 Projektopgave 3(2004) 7. Eksamen januar 2005, 11,12,13,14,15,16,17,18,20.
ti:9/1 fr:12/1	DP DP	Talteoretiske algoritmer, RSA kryptosystemet Primtalstest (randomiserede algoritmer)	P2 afleveres 9/1	Cormen 31.1-31.7	ti:pdf fr:pdf	31.2-2, 31.2-3, 31.2-4, 31.2-6, 31.2-8, 31.3-1, 31.3-4. 31.4-1, 31.4-2, 31.6-3, 31.7-1, 31.7-2. Eksamen januar 2005, 19. Eksamen januar 2006, 11-20. (kræver at man har kigget på P2 fra 2005-06).

Projektopgaver

P1
Forside til P1
P2

Eksamen

Eksamen: 26. januar 2007
Reeksamen: 20. april 2007

Gamle eksamenopgaver og projektopgaver

Projektopgave 3, 2004
Projektopgave 4, 2004
Eksamen januar 2005 (sp. 11-20), (vejl løsn)
Eksamen januar 2005 (sp. 1-10)
Reeksamen april 2005 (sp. 11-20), (vejl løsn)
Projektopgave P2, 2005
Eksamen januar 2006 (sp. 11-20), (vejl løsn)
Eksamen januar 2006 (sp. 1-10)

Litteratur

[CLRS]	Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, Second Edition, MIT Press, Cambridge (2001).
[KB1]	Kursusbog: Branch-and-bound og Generelle optimeringsheuristikker.

Elektronisk materiale

Ordbog over alle begreber fra lærebogen.
Liste over rettelser til lærebogen.
Kompendium over NP-hårde problemer.
Diskussion af kvantecomputeren og NP-fuldstændighed findes i Wikipedia og yderligere her.

Bedømmelse

Undervejs i kurset stilles to godkendelsesopgaver, som skal besvares i grupper på 2-3 personer (grupper med 1 person kræver accept fra instruktoren). For at blive godkendt skal opgaverne afspejle at der er gjort et reelt forsøg på at besvare hele sættet.

Godkendelse af begge opgavebesvarelser er en forudsætning for tilmelding til skriftlig eksamen. Genaflevering af ikke-godkendte besvarelser kan grundet den stramme tidsplan ikke finde sted.

Kurset afsluttes med en fire timers skriftlig eksamen, hvor lærebøger og egne noter må medtages. Omkring 2/3 af opgaverne vil tage udgangspunkt i de to godkendelsesopgaver, og kan besvares med multiple-choice valg. Omkring 1/3 af opgaverne er tekstspørgsmål som går fagligt dybt i stoffet.