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

• Få føling med begrebet ressourceforbrug i forbindelse med computeres beregninger.
• Opleve behovet for metoder til at beskrive og analysere algoritmer.

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

• Modeller for beregninger og beregningsproblemer.
• Analyse af algoritmers ressourceforbrug.
• Beviser for algoritmers korrekthed.
• Beregningproblemers iboende sværhedsgrad.

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

• Algoritmer og datastrukturer 1
• Algoritmer og datastrukturer 2

• Advanced Algorithms - Data Structures
• Algorithms for Web Indexing and Searching
• Algorithms in Bioinformatics - Trees and Structures
• Algorithms in Bioinformatics - Sequences
• Complexity Theory
• Computational Geometry
• Dynamic Algorithms
• I/O Algorithms
• Kombinatorisk Søgning
• Lossless Data Compression
• Lossy Data Compression
• Optimering
• Randomized Algorithms
• Algorithmic Game Theory
• String Algorithms

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).