1. Kontaktperson

Professor David Pisinger (kursusansvarlig), e-mail: pisinger@diku.dk, tlf.: 35 32 13 54

Andre Undervisere

Professor Jakob Krarup, e-mail: krarup@diku.dk, tlf.: 35 32 14 50
Lektor Pawel Winter, e-mail: pawel@diku.dk, tlf.: 35 32 14 27
Lektor Martin Zachariasen, e-mail: martinz@diku.dk, tlf.: 35 32 13 57

Instruktorer

Philip Bille, e-mail: beetle@diku.dk,
Jarl Friis, e-mail: jarl@diku.dk,
Jens Kristian Jensen, e-mail: doozer@diku.dk,
Henrik Chr. Grove, e-mail: grove@diku.dk,
Mads Jepsen, e-mail: mitzi@diku.dk,

2. Skemaoplysninger

Forelæsninger hver Onsdag kl. 13.15-15.00 i Aud. 2 på HCØ.
Øvelser starter i uge 6.

**Øvelseshold**
Hold	Ugedag	Tid	Lokale	Instruktor	Link
1	Mandag	9-11	N022	Jarl
2	Mandag	11-13 (tidspunkt flyttet)	N018	Philip	Link
3	Tirsdag	13-15	N030	(lukket)
4	Torsdag	13-15	N022	Henrik
5	Torsdag	13-15	N030	Jens	Link
6	Fredag	11-13	N004	Mads	Link

Instruktormøde: Mandag 13.15 - 14.00 i S225.

Kursusbeskrivelsen som vedligeholdes af Studienævnet og som ligger på www.sis.ku.dk er ikke up-to-date og indtil videre ikke gældende.

3. Undervisningsform
Undervisningen består af forelæsninger ved lærere og øvelsesregning ved instruktorer. Der er en ugentlig forelæsning á to timer. Øvelserne omfatter en ugentlig øvegang af to timers varighed.

4. Formål
Kursets formål er at bibringe de studerende et grundlag for analyse, design og implementering af algoritmer - et centralt område inden for datalogi.

5. Indhold
Algoritmik, grafalgoritmer, beregnelighed, kompleksitet og løsning af NP-fuldstændige problemer

Algoritmik [AL] ved Pawel Winter
Rapportopgave [RK1] ved Martin Zachariasen
Grafalgoritmer [GA] ved Jakob Krarup
Beregnelighed og uafgørlighed [BU] ved Jakob Krarup
Kompleksitet [KO] ved David Pisinger
Løsning af NP-fuldstændige problemer [NP] ved David Pisinger.

Generel introduktion til hele kursusdelen, fundamental kompleksitetsanalyse med brug af rekursionsligninger, eksempler på datastrukturer (Fibonacci hobe eller splay træer, samt randomiserede datastrukturer), samt avancerede typer af kompleksitetsanalyse som f.eks. amortisering. Paradigmer for algoritmekonstruktion (dynamisk programmering, grådige metoder, del-og-hersk, planfejning, søgning og markeringsbaserede metoder) illustreret via et ret bredt spektrum af emner: aritmetik, netværksoptimering og algoritmisk geometri.
Derefter kompleksitet (klasserne P, NP og NP-fuldstændighed), metoder til håndtering af NP-fuldstændige problemer (søgebaserede metoder til optimal løsning af NP-hårde problemer, approximationsalgoritmer og heuristikker), samt håndtering af specielle polynomielle tilfælde.
Kurset afsluttes med eksempler på uafgørlige problemer samt nogle vink med henblik på eksamensforberedelse.

6. Lærebøger

[CLRS01]	Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein: Introduction to Algorithms, Second Edition, MIT Press, Cambridge (2001).


[KB1]	Kursusbog bind 1: (Branch-and-Bound Algorithms & Generelle Optimeringsheuristikker). Benyttes først i april 2002, kan købes fra marts 2002.

7. Faglige forudsætninger
Kurset forudsætter Datalogi 0, Datalogi 1E, Datalogi 1F samt matematiske kundskaber svarende til kurset Diskret Matematik (årgang 98 eller tidligere) eller Matematik og Beregninger.

8. Formelle Krav

9. Eksamensform
Datalogi 2A eksamensform ser ud som følger:

Der stilles en karakterbedømt rapportopgave K1 i slutningen af efterårsemestret. Hovedvægten lægges på anvendelsen af datastrukturer og algoritmer gennemgået i løbet af efteråret. Rapporten vægtes 1/3.
Der stilles to skriftlige opgaver, O1,O2 i løbet af forårssemestret. Hvis en O-opgave ikke godkendes, kan besvarelsen omarbejdes og indleveres til ny bedømmelse, dog højst 1 gang for hver opgave.
Forud for den mundtlige eksamen (der vægtes 2/3) i maj/juni annonceres alle eksamensspørgsmål på kursets hjemmeside. Tilmelding til mundtlig eksamen forudsætter godkendelse af O-opgaver. En halv time før selve eksaminationen trækkes et af disse spørgsmål, og den halve time derefter er afsat til forberedelse i enerum. Der eksamineres hverken i K-opgaven eller i O-opgaverne eller de enkelte studerendes besvarelser af samme. For at bestå Datalogi 2A skal både karakteren for K-opgaven og for den mundlige eksamen være mindst 6.

10. Pensum skal opdateres
Cormen et al.: Kap. 1, 2, 3, 4.1-3, 7, 8, 9, 10, 13.1-3, 14?, 16.1-3, 17.1-3, 20, 21, 22, 23, 24, 25.1-3, 26.1-2, 27, 35, 36, 37.1-37.4.
Noter om kompleksitetsteori
Materiale om LEDA, ugesedler

11. Edb-system
Programmeringssprogene C, C++ og LEDA benyttes i de skriftlige opgaver.

12. Mundtlig eksamen
Mundtlig eksamen finder (iflg SIS) sted fra den 10. til den 14. juni 2002.