Uge 1 - Algoritmer og Kompleksitet

Forelæsninger ved Gerth Stølting Brodal.

Materiale

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

Mandag intro-slides.pdf
Tirsdag opgaver.html
uge1gruppeX.txt (skabelon til afleveringer)
Onsdag algoritmik-slides.pdf
dm_i_programmering_2010.pdf

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

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

Open Learning Center tirsdag 24. august kl 9:15-16:00 i Shannon-bygningen

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 én eller få linier.

Svarene gives i en simpel tekstfil. Gem den på jeres laptop (brug "save as" fra Fil-menuen i browseren). Filen navngives som "uge1gruppeX.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.

8.45-9.15Udlevering af maskiner og registrering af nye brugere.
9:15-12.15Øvelser 1-10 (sortering)
12.15-13.00Frokostpause
13:00-15:45Øvelser 11-19
15:45-16:00Upload af besvarelserne til øvelserne og udfyldning af kursusevaluering for uge 1.

Forelæsning onsdag 25. august kl. 14.15-16.00 i Aud F, Ny Munkegade

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.

Relaterede kurser

Adskillige kurser på datalogi udbydes inden for området algoritmik og kompleksitet. Herunder de indledende kurser

samt en del videregående kurser (nogle udbydes regelmæssigt hvert år, andre med mindre regelmæssighed)

Der findes mange internationale konkurrencer hvor studerende konkurrerer om hvem der hurtigst muligt kan lave et program der løser et algoritmisk problem. Studerende ved Datalogisk Institut ved Aarhus Universitet har deltaget i disse konkurrencer med flotte resultater igennem de seneste år. Information om disse konkurrencer kan fåes på Mark Greve's hjemmeside om programmerings konkurrencer.

Yderligere materiale

Følgende to bøger er ikke lærebøger på kurser, men er meget inspirerende læsning: 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). Yderligere er der mange reference til lærebøger og materialer på hjemmesiderne til ovenstående kurser.