| Kursusnavn (dansk): | Effektive Algoritmer og Programmering |
| Kursusnavn (engelsk): | Efficient Algorithms and Programming |
| Semester: | Forår 2002 |
| Udbydes under: | cand.it., internet- og softwareteknologi (int) |
| Omfang i ECTS: | 7,50 |
| Kursussprog: | Dansk |
| Kursushjemmeside: | https://learnit.itu.dk |
| Min. antal deltagere: | 15 |
| Forventet antal deltagere: | 19 |
| Maks. antal deltagere: | 500 |
| Formelle forudsætninger: | Den studerende skal før kurset:
- Kunne designe, programmere og teste mindre programmer (500 linier)
- beherske asymptotisk notation (O-notation) og dennes anvendelse ved analyse af basale algoritmers køretid.
- have kendskab til sortering, hobe, prioritetskøer, hashing, dynamisk programmering, træer.
Disse forudsætninger kan for eksempel opnås
ved at have fulgt kurset "Introduktion til Algoritmer og Datastrukturer" (IADS) eller tilsvarende. |
| Læringsmål: | At sætte deltagerne i stand til at
- forstå udvalgte algoritmers opbygning og deres effektivitet,
- implementere algoritmerne som effektive programmer,
- teste korrektheden af programmer,
- teste effektiviteten af programmer, bl.a. at en implementation af en algoritme rent faktisk lever op til den teoretiske køretid for algoritmen
- anvende og tilpasse algoritmer til løsning af konkrete problemer.
Desuden bliver den studerende bekendt med og kan identificere en række hyppigt forekommende svære problemer (såkaldte NP-komplette problemer) som kun har delvist effektive løsninger. |
| Fagligt indhold: | Kurset har to hoveddele, som tidsmæssigt gennemføres parallelt:
- En teoretisk del hvor algoritmer og deres analyse gennemgås ved forlæsninger og øvelser.
- En praktisk del hvor algoritmerne implementeres i et konkret (valgfrit) programmeringssprog.
Følgende emner dækkes:
- dybde-først og bredde-først søgning i grafer
- korteste vej-algoritmer
- letteste udspændende træer
- hashing og dynamisk programmering
- binære beslutningsdiagrammer (BDDer)
- NP-fuldstændighed
I den praktiske del af kurset læggers der stor vægt på hvorledes algoritmer implementeres som effektive programmer. Vi vil derfor også komme ind på en række programmerings-tekniske emner, så som programmering-triks, teknikker til kvalitetssikring af software, kode-stil, debugging, og teknikker til forbedring af performance. Disse praktiske aspekter bliver øvet ved at den studerende implementerer en række algoritmer som afleveres og rettes. Der er ialt 10 obligatoriske opgaver hvoraf de fleste er programmeringsopgaver.
Der er mere specifik information på kursets hjemmesider. |
| Læringsaktiviteter: | Ugentlige forelæsninger og øvelser samt obligatoriske opgaver. |
| Eksamensform og -beskrivelse: | X. experimental examination form (7-scale; external exam), 13-skala, Intern censur 4 timers skriftlig eksamen. Ekstern censor. Alle skriftlige hjælpemidler er tilladt. Det er en forudsætning for at blive indstillet til eksamen, at de obligatoriske opgaver er afleveret og godkendt
|
| Litteratur udover forskningsartikler: | Kurset er baseret på Cormen, Leiserson, Rivest, "Introduction to Algorithms", MIT Press,
og udleverede noter. |
| | |
Kursusoversigt