Ugeseddel nr. 1

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

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

Forelæsning onsdag 31. august kl. 14.15 - 15.00 i Aud. F

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

Slides til forelæsning: pdf | ps.

Open Learning Center torsdag 1. september kl 8.15/9:15-16:00 i Shannon-bygningen (Finlandsgade 24) 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 placeres filen i BSCW-systemet, i folderen for ens gruppe. 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.15-8.45: Udlevering af maskiner.

08.45-9.15: Registrering af private maskiner.

09:15-12.15: Øvelser 1-9

12.15-13.00: Frokostpause

13:00-16.00: Øvelser 10-17

Forelæsning fredag 2. september kl. 9.15-11.00 i Aud. F

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.

Torsdagens ø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 fra forelæsning: ps | pdf.

Relaterede kurser

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

• Algoritmer og datastrukturer 1
• Algoritmer og datastrukturer 2

• 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
• 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). Man kan læse mere om The Eternity Puzzle på dets website, og på en side om dem, der løste det.