Ugeseddel nr. 1

Ugens Emne: Algoritmer og kompleksitet
Ugens Forelæser: Gerth Stølting Brodal


Bemærk: Hvert gruppe skal tirsdag medbringe: en saks, to-tre ure med sekundvisere, skriveredskaber og lidt kladdepapir, evt. en lommeregner (gerne grafisk).

Forelæsning mandag 25. august kl. 10.15 - 11.00 i IT-huset Store Aud

Dagens forelæsning vil give en uformel introduktion til ugens emne. Vi vil også diskutere praktiske ting omkring tirsdagens øvelser, og lave lidt repetition af matematik relevant for disse.

Slides til forelæsning: intro-slides.pdf (511 KB).

Open Learning Center tirsdag 26. august kl 9:15-16:00 i Shannon-bygningen lokale 157, 159, 164

Målet for denne dag er via praktiske øvelser og opgaver at

Dagen består af en række mindre øvelser - nogle praktiske, nogle tænkeopgaver, og nogle regneopgaver. Alle øvelser afsluttes med at besvare et eller flere spørgsmål skriftligt. De fleste svar forventes at fylde een eller få linier.

Svarene gives i en simpel tekstfil (skabelon). Gem den på jeres laptop (brug "save as" fra Fil-menuen i browseren). Filen navngives som "u1grX.txt" hvor X er jeres gruppenummer. Skriv derefter svarene på de relevante steder ved at redigere i den, f.eks. Notepad under Windows, men ikke Word eller andre programmer med eget filformat. Ved dagens slutning uploades filen til kursus websiden. Gem jævnligt kopier af filen undervejs, så mister I ikke hele dagens arbejde ved en fejl.

Dagens program er som følger. Vi holder frokostpause 12.15-13.00. Grupperne sørger selv for passende pauser i øvrigt.

08.45-9.15 Udlevering af maskiner og registrering af private maskiner.

09:15-12.15: Øvelser 1-10.

12.15-13.00: Frokostpause

13:00-16.00: Øvelser 11-20.

Forelæsning onsdag 27. august kl. 14.15-16.00 i IT-huset Store Aud

Lidt mere formel gennemgang af ugens emne. Blandt andet snakker vi om

Tirsdagens øvelser vil undervejs blive diskuteret, og vil forhåbentligt virke som motivation for, og konkretisering af, de gennemgåede begreber. Mange yderligere eksempler på beregningsproblemer og algoritmer for disse vil blive diskuteret.

Målet for dagen er at give et indblik i dels de metoder og teknikker som anvendes inden for algoritmik og kompleksitetsteori, dels i hvor både anvendeligt og fundamentalt området er.

Slides til forelæsning: algoritmik-slides.pdf (680 KB).

Relaterede kurser

Adskillige kurser på datalogi ligger inden for ugens emne. Herunder de indledende kurser

samt en del videregående kurser

Yderligere materiale

Se lærebøger og materialer til ovenstående kurser. Følgende to bøger er ikke relaterede til kurser, men er meget inspirerende: Algorithmics: The Spirit of Computing, af David Harel, formidler de væsentlige pointer fra hele området algoritmer og kompleksitet uden at forudsætte matematisk baggrund hos læseren. Programming Pearls, af Jon Bentley, giver konkrete eksempler på samspillet mellem gode algoritmiske ideer og effektiv programmering (lidt erfaring i programmering forudsættes).