KURSPLAN
Algoritmer, 7,5 högskolepoäng
Algorithms, 7.5 credits
Kursplan för studenter vår 2025
| Kurskod: | TAIK12 |
| Fastställd av: | VD 2021-03-01 |
| Gäller fr.o.m.: | 2022-01-01 |
| Version: | 1 |
| Utbildningsnivå: | Grundnivå |
| Utbildningsområde: | Tekniska området |
| Ämnesgrupp: | DT1 |
| Fördjupning: | G1F |
| Huvudområde: | Datavetenskap |
Lärandemål
Efter genomgången kurs skall studenten
Kunskap och förståelse
- visa förståelse för innebörden och konsekvenserna av komplexitetsklasser
- visa kunskap om generiska strategier för algoritmdesign
- visa kunskap om etablerade algoritmer för att hantera diskreta matematiska strukturer och numeriska problem
- visa förståelse för konsekvenser av val av representation
- visa kunskap om generiska strategier för algoritmdesign
- visa kunskap om etablerade algoritmer för att hantera diskreta matematiska strukturer och numeriska problem
- visa förståelse för konsekvenser av val av representation
Färdighet och förmåga
- visa förmåga att utföra komplexitetsanalys av iterativa och rekursiva algoritmer
- visa förmåga att tillämpa generiska strategier för algoritmdesign
- visa färdighet i att utifrån en generell algoritmbeskrivning implementera en algoritm i ett programspråk
- visa förmåga att självständigt implementera och anpassa etablerade algoritmer.
- visa förmåga att tillämpa generiska strategier för algoritmdesign
- visa färdighet i att utifrån en generell algoritmbeskrivning implementera en algoritm i ett programspråk
- visa förmåga att självständigt implementera och anpassa etablerade algoritmer.
Värderingsförmåga och förhållningssätt
- visa insikt om samband mellan datarepresentation och algoritmers komplexitet.
Innehåll
Kursen behandlar design och analys av algoritmer, med fokus på komplexitetsanalys och generiska strategier för algoritmdesign. Särskilt tonvikt läggs på detaljerad genomgång av ett antal etablerade och viktiga algoritmer.
Kursen innehåller följande moment:
- Komplexitetsteori: komplexitetsanalys, rekurrensrelationer, komplexitetsklasser P/NP, lower bounds.
- Algoritmtyper: brute force, divide-and-conquer och varianter härav, problemtransformering, time/space tradeoffs, dynamisk programmering, giriga algoritmer, iterative improvement, backtracking, branch-and-bound, approximativa algoritmer.
- Algoritmer för tillämpningar inom: sökning, sortering, kombinatorik, strängmatchning, numeriska problem, optimering, grafer, träd.
Kursen innehåller följande moment:
- Komplexitetsteori: komplexitetsanalys, rekurrensrelationer, komplexitetsklasser P/NP, lower bounds.
- Algoritmtyper: brute force, divide-and-conquer och varianter härav, problemtransformering, time/space tradeoffs, dynamisk programmering, giriga algoritmer, iterative improvement, backtracking, branch-and-bound, approximativa algoritmer.
- Algoritmer för tillämpningar inom: sökning, sortering, kombinatorik, strängmatchning, numeriska problem, optimering, grafer, träd.
Undervisningsformer
Föreläsningar, övningar, handledning av laboration och inlämningsuppgifter.
Undervisningen bedrivs normalt på svenska men undervisning på engelska kan förekomma.
Förkunskapskrav
Grundläggande behörighet samt genomgången kurs i Datastrukturer 7,5 hp (eller motsvarande kunskaper).
Examination och betyg
Kursen bedöms med betygen 5, 4, 3 eller Underkänd.
Poängregistrering av examinationen för kursen sker enligt följande system:
| Examinationsmoment | Omfattning | Betyg |
|---|---|---|
| Tentamen1 | 5 hp | 5/4/3/U |
| Laboration | 1 hp | U/G |
| Inlämningsuppgift | 1,5 hp | U/G |
Kurslitteratur
Kurslitteraturen fastställs 8 veckor innan kursstart.
Titel: Introduction to the Design and Analysis of Algorithms. International Edition, 3. uppl.
Författare: Anany Levitin
Förlag: Pearson Education, 2012
ISBN-13: 9780273764113
Titel: Introduction to the Design and Analysis of Algorithms. International Edition, 3. uppl.
Författare: Anany Levitin
Förlag: Pearson Education, 2012
ISBN-13: 9780273764113