Datalogisk Institut
Københavns Universitet

Videregående Algoritmik, blok 2, 2007-08

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

Meddelelser

[30 april] Karakterliste for re-eksamen april 2008 findes her.
[17 april] Re-eksamen og vejledende løsninger findes her og her.
[31 januar] Karakterer for eksamen findes her
[25 januar] Eksamen og vejledende løsninger findes her
[17 januar] Forslag til bachelorprojekter
[16 januar] De sidste P2-opgaver kan afhentes i informationen på DIKU
[15 januar] Pensum for kurset er det der er angivet i SIS (se link ovenfor). Brug plancherne fra forelæsningerne som læsevejledning.
[13 januar] Kim's implementering af P2-opgaven er tilgængelig her.
[11 januar] Kim er syg, så hans øvelseshold er aflyst - brug et af de andre hold.
[8 januar] Der holdes spørgetime tirsdag den 22. januar på øvelsesholdene. Send eventuelle spørgsmål pr. email i forvejen til instruktoren. Såfremt der ikke indkommer nogen spørgsmål af generel relevans senest søndag 20. januar vil spørgetimen blive aflyst.
[8 januar] Der holdes sædvanlige øvelser tirsdag 15. januar.
[8 januar] Tidligere eksamenssæt samt vejledende løsninger er tilføjet hjemmesiden.
[6 januar] Yderligere hints til opgave 9 er tilføjet listen over hints til P2.
[4 januar] Jeg har samlet nogle generelle spørgsmål i følgende hints til P2.
[21 december] I rammeprogrammet til P2 manglede instanserne geo10-geo40. De er nu lagt ind i filen.
[14 december] P1 opgaver, som ikke blev afhentet ved øvelserne, kan hentes i studieadministrationen.
[11 december] Der vil ikke være øvelser på hold 3, fredag den 4. januar - brug et af de andre hold
[10 december] Projektopgave P1 vil kunne afhentes ved øvelserne på fredag 14/12.
[10 december] Kim er blevet syg, så hans øvelseshold tirsdag 11/12 kl. 11-13 er aflyst - brug et af de andre hold
[9 december] P2 projektopgave, forside, rammeprogram (filer pakkes ud med kommandoen "tar -xf rammeprogram.tgz").
[3 december] P1 skal afleveres onsdag 5. december. På projektforsiden stod der fejlagtigt fredag 5. december. (ny version af forsiderne er lagt ud på nettet)
[27 november] Der afholdes en spørgerunde om P1 i starten af 2. forelæsningstime på fredag, den 30. november. Send eventuelle spørgsmål til Christian så han kan få en ide hvor de største problemer ligger. Hvis spørgsmål ikke har generel interesse, vil han svare direkte via e-mail.
[22 november] Forside til P1-opgaven: pdf-format og doc-format. Skal afleveres sammen med besvarelsen senest den 5. december 2007, kl. 12. P1-opgaveteksten vil blive lagt ud fredag, den 23. november 2007 efter forelæsningen (omkring kl. 12.15). Bemærk at der er ingen genaflevering.
[6 november] Øvelser afholdes 1/2 uge forskudt i forhold til forelæsninger, første gang fredag, den 16. november.

Relaterede kurser

VA kan med fordel følges sideløbende med introduktion til optimering i blok 2.

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), Pawel Winter (PW)

Instruktorer: Mads Sejersen, hold 2 (MS), Kim Vejlin, hold 1 (KV), Christian Wulff-Nielsen, hold 3 (CWN)

Forelæsninger og øvelser:
Skemagruppe B komplet oversigt
Forelæsning tirsdag 13-15, Lille Auditorium, DIKU
Forelæsning fredag 10-12, Store Auditorium, DIKU

Undervisningsplan

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

26.1-6,

Dato	Lærer	Indhold/Emne	Projektopgave	Litteratur	Plancher	Opgaver (foreløbige)
ti:13/11 fr:16/11	PW PW	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 23/11, ej obligatorisk) 29.3-2, -3, -4, -5, 29.3-6(læs afsnit 29.5 inden) 29.5-3, -4, -5
ti:20/11 fr:23/11	PW PW	Lineær programmering Maximum flow i netværk	P1 stilles, 23/11	Cormen 29.1-29.5 Cormen 26.1-26.2	ti:pdf fre:pdf	29.4-1, 29.4-5, 29-2, VA-P2 (hjemmeopgave, udleveres ved 3. forelæsning, afleveres den 30/11, ej obligatorisk). 26.1-1,26.1-2,26.1-4, 26.1-6, 26.1-9, 26.2-1, 26.2-2, 26.2-3
ti:27/11 fr:30/11	PW PW	Maximum flow i netværk		Cormen 26.2-26.4	ti:pdf fr:pdf	26-2.6, 26-2.7, 26.2-8, 26.3-2, 26-1. Håndkør push-relabel algoritmen på flownetværket i figur 26.6. 26.4-6, 26-4
ti:4/12 fr:7/12	DP DP	NP-fuldstændighed NP-fuldstændighed	P1 afleveres 5/12	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:11/12 fr:14/12	DP DP	NP-fuldstændighed Branch and bound	P2 stilles 11/12 (forside)	Cormen 34.1-34.5 Kursusbog, del 1	ti:pdf fr:pdf (maxcut)	Cormen 34-2, b&b opg. 1,2 projektopgave P2 b&b opg. 4,5,6,7,8 projektopgave P2(2006) 1,2,3,4
ti:18/12 fr:4/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 P2 (2006) 5,6,7,8. Eksamen januar 2005, 11,12,13,14,15,16,17,18,20.
ti:8/1 fr:11/1	DP DP	Talteoretiske algoritmer, RSA kryptosystemet Primtalstest (randomiserede algoritmer)	P2 afleveres 9/1	Cormen 31.1-31.8	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).

Eksamen

Eksamen: Skriftlig prøve den 25. januar 2008
Reeksamen: Skriftlig prøve den 17. april 2008.

Gamle eksamenopgaver og projektopgaver

Eksamen januar 2005 (sp. 11-20), (vejl løsn)
Eksamen januar 2005 (sp. 1-10), (vejl løsn)
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)
Projektopgave P2, 2006
Eksamen januar 2007, (vejl løsn)

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.