Forelæsninger ved 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).
| Mandag | intro-slides.pdf |
| Tirsdag |
opgaver.html uge1gruppeX.txt (skabelon til afleveringer) |
| Onsdag | algoritmik-slides.pdf
dm_i_programmering_2010.pdf |
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.
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.15 | Udlevering af maskiner og registrering af nye brugere. |
| 9:15-12.15 | Øvelser 1-10 (sortering) |
| 12.15-13.00 | Frokostpause |
| 13:00-15:45 | Øvelser 11-19 |
| 15:45-16:00 | Upload af besvarelserne til øvelserne og udfyldning af kursusevaluering for uge 1. |
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.
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.
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.