Datalogisk Institut
Københavns Universitet

Videregående Algoritmik, blok 2, 2005

[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: Jakob Krarup (JK), David Pisinger (DP)

Instruktorer: Søren Mark Elverskov, Jesper Stemann Andersen

Forelæsninger: Mandag 13-15 og torsdag 10-12, Auditorium 4, HCØ

Øvelser:
Hold 1 mandag 15:00-17:00 i A101, torsdag 12:00-14:00 i A106 (Søren)
Hold 2 mandag 15:00-17:00 i N034, torsdag 12:00-14:00 i A110 (Jesper)
Hold 4 mandag 11:00-13:00 i N014, torsdag 08:00-10:00 i N014 (Søren)
I forhold til oplysningerne i SIS oprettes hold 3 og 5 ikke.

Første øvelsesgang er torsdag d. 17. november.

Meddelelser

[7 feb] Information om reeksamen findes her (incl. eksamensspørgsmål)
[30 jan] Karakterliste er ophængt overfor DIKU's studieadministration.
[23 jan] Eksamen 2006 pdf, vejledende svar pdf (sidste 10 spørgsmål).
Eksamen 2006 første 10 spørgsmål: vejl løsning findes i dueslaget.
[22 jan] Der er flere studerende som efterlyser deres projektopgaver. Jeg har i bunkerne i studieadministrationen fundet følgende rapporter (fødselsdato i parantes): VA-P2 hold 1 (300679,170183,260576) godkendt
VA-P2 hold 2 (260479,090684) ikke godkendt
VA-P2 hold 3 (310383,040683) godkendt
VA-P2 hold 6 (220383,150282,140280)godkendt
VA-P2 hold 21 (011074,141176) godkendt
VA-P2 hold 23 (140880,180880,100180) godkendt
VA-P2 hold 24 (241080,200381,290684) godkendt
VA-P2 hold 25 (220981,240381,260674) godkendt
VA-P2 hold 29 (110484,310880,090883) godkendt
VA-P2 hold 31 (040777) godkendt
VA-P2 hold 36 (251178,191277) godkendt
VA-P2 hold 37 (100183,121280) godkendt
VA-P2 hold 38 (100183,121280) godkendt
VA-P2 hold 39 (101280,030780) godkendt
Rapporterne kan afhentes i studieadministrationen. Jeg vil ikke udelukke at der findes yderligere rapporter som er lagt i en forkert bunke. - David
[17 jan] Projektopgave P2 kan afhentes i studieadministrationen. Alle "problemetiske" projektopgaver har fået besked pr email, så hvis ikke du har modtaget nogen besked kan du gå ud fra at opgaven er godkendt.
[12 jan] Projektopgave P2 forventes rettet tirsdag 17/1. Ved samme lejlighed vil en skematisk løsning til projektopgaven blive lagt ud på hjemmesiden. her
[12 jan] Vejledende løsninger til gamle eksamener er lagt ud på siden.
[9 jan] Løsning til "Written exam, 23 January 2006" (Q1-Q10) vil kunne hentes i kursets dueslag (samme sted som de hidtil uddelte noter) umiddelbart efter eksaminens afslutning.
[19 dec] Projektopgave P2 er blevet præciseret mht. due dates. En opdateret version er lagt på nettet (se link nedenfor).
[19 dec] Første øvelsesgang i 2006 for hold 2, mandag d. 2. jan., flyttes til fredag d. 6. jan. kl. 13-15 i N014. Opgaver til om mandagen gennemgås om torsdagen, opgaver til om torsdagen gennemgås om fredagen.
[6 dec] Projektopgave P2 er tilgængelig her. Forbehold for mindre rettelser. Forside til P2 findes her.
[3 dec] Forsøget med at flytte øvelseshold 2's tidspunkt om torsdagen til om fredagen var ikke videre succesfuldt, så forsøget er hermed afsluttet.
[25 nov] Øvelseshold nr. 2 flyttes forsøgsvist i uge 48 fra torsdag kl. 12-14 til fredag kl. 13-15 i N030.
[24 nov] Der er en fejl i projektopgave VA-P1! I næstsidste linie på side 1 skal der stå "... by a set {C_1, C_2, C_3} of constraints...". Som følge heraf gives løsningen på opgave Q1 i LaTeX-format:
$\{C_1, C_2, C_3\}=\{3x_1+x_2 \leq 24, x_2 \leq 6, -2x_1+3x_2 \leq 12\}$
[24 nov] Øvelserne i uge 48 vil bestå af en times gennemgang af opgaver, samt en times spørgetime/regneøvelsestime.
[17 nov] Øvelseshold 2 er forholdsvis tyndt befolket - de studerende er derfor velkomne til at fordele sig mere ligeligt. Det overvejes at flytte hold 2's torsdagstimer til om fredagen (samme tid) hvis det er muligt. Hvis man er interesseret i at følge hold 2 - om torsdagen eller om fredagen - bedes man sende en kort e-mail til Jesper med angivelse af et muligt tidsinterval.
Opgaver til en given uge, fastlægges og publiceres her på siden om torsdagen, ugen før.
[11 nov] Opgaverne BBB Q1-Q12 til første øvelsesgang (torsdag d. 17.) henviser til opgaver som udleveres ved første forelæsning.

Undervisningsplan

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

Dato	Lærer	Indhold/Emne	Projektopgave	Litteratur	Plancher	Opgaver
ma:14/11 to:17/11	JK	Lineær programmering		Cormen 29.1-29.5	Udleveres ved forelæsningen	29.1-2, -4, -5, -6 og -7. BBB Q1-Q12.
ma:21/11 to:24/11	JK	Lineær programmering	P1 stilles, forside (pdf) 24/11	Cormen 29.1-29.5	Udleveres ved forelæsningen	29.1-8 og -9. 29.3-3, -4, -5 og -6. PB Q1-Q10. VA-P2(2004) S1-S3. 29.4-1 og -5. 29-2. PB Q11-Q15. VA-P2(2004) S4-S9.
ma:28/11 to:1/12	JK	Maximum flow i netværk		Cormen 26.1-26.4	Udleveres ved forelæsningen	VA-P2(2004) (resten: S6-S9). PB: Q16-Q20. VA-P1(2004).
ma:5/12 to:8/12	DP	NP-fuldstændighed	P1 afleveres 8/12	Cormen 34.1-34.5	ma:pdf to:pdf	Eksamensopgave, 19. januar 2005. 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
ma:12/12 to:15/12	DP	NP-fuldstændighed Branch and bound	P2 stilles 12/12	Cormen 34.1-34.5 Kursusbog, del 1	ma:pdf to:pdf	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) Cormen 34-2, b&b opg. 1,2 projektopgave P2
ma:2/1 to:5/1	DP	Approximations algoritmer, Heuristikker		Cormen 35.1-35.5 Kursusbog, del 2	ma:pdf to:pdf	b&b opg. 4,5,6,7,8 Projektopgave 3(2004) 1,4,5,6. 35.1-1, 35.1-2, 35.1-4, 35.1-5, 35-1 Projektopgave 3(2004) 7.
ma:9/1 to:12/1	DP	Talteoretiske algoritmer, RSA kryptosystemet Primtalstest (randomiserede algoritmer)	P2 afleveres 9/1	Cormen 31.1-31.7	ma:pdf to:pdf	Eksamen januar 2005, 11,12,13,14,15,16,17,18,20. 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

Eksamen: 23. januar 2006
Reeksamen: 10. april 2006

Gamle eksamenopgaver og projektopgaver

Projektopgave 3, 2004
Projektopgave 4, 2004
Eksamen januar 2005, (vejl)
Reeksamen april 2005, (vejl)

Litteratur

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

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.

Oversigt over ændringer på websiden

Dato	Beskrivelse
6/12/2005	Pensum for første kursusafsnit publiceret.
3/12/2005	Forsøg med øvelseshold 2's tidspunkt om torsdagen afsluttet.
2/12/2005	Opgaver til uge 49 fastlagt.
28/11/2005	Forside til VA-P1 gjort tilgængelig.
25/11/2005	Lokale for hold 2's øvelsesgang i uge 48.
24/11/2005	Meddelelser, hold 2's øvelsestidspunkt, opgaver til uge 48 og 49.
17/11/2005	Opgaver til uge 47 publiceret. Har skjult opgaver stammende fra sidste år for de følgende uger. Flyttet afsnit om elektronisk materiale.
11/11/2005	Rettelser, specielt mht. første øvelsesgang.