Algoritmer
Kurs
DIT093
Avancerad nivå
7,5 högskolepoäng (hp)
Om utbildningen
Kursen ger kunskaper om:
- Vad är en effektiv algoritm?
- Verktyg för analys av algoritmer. O-notation. Analysera loopar och rekursiva anrop. Lösa rekursionekvationer.
- Datastrukturer och algoritmer. Granskning av grundläggande datastrukturer.
- Kombinera datastrukturer. Merge-and-find.
- Grafalgoritmer.
- Giriga algoritmer.
- Divide-and-conquer.
- Dynamisk programmering.
- Backtracking och Implicita sökträd. Branch-and-bound.
- Kort introduktion till lokala sök-och approximationsalgoritmer.
- Grundläggande komplexitetsteori. Komplexitetsklasserna P, NP och NPC, reduktioner. Exempel på NP-fullständiga problem. Att hantera svåra problem.
- Kort introduktion till andra designtekniker: lokal sökning, approximationsalgoritmer, randomiserade algoritmer, förbehandling, nätverksflöde.
Behörigheter och urval
Behörighet
Förkunskapskravet är avklarade kurser om 120 hp i ämnet datavetenskap eller matematik, inklusive;
- 7,5 hp diskret matematik (DIT984 Diskret matematik för datavetare, ellerdelkursen Inledande algebra i MMG200 Matematik I eller mosvarande),
- ytterligare 10 hp matematik,
- 7,5 hp imperativ eller objektorienterad programmering (DIT013 Imperativprogrammering med grundläggande objektorientering, eller motsvarande),
- ytterligare 7,5 hp programmering,
- 7,5 hp datastrukturer (DIT962 Datastrukturer, DIT375 Python for Data Scientistseller motsvarande).
Följande kunskapsnivå i Engelska krävs; Engelska 6/Engelska B eller motsvarande frånett erkänt internationellt test, t.ex. TOELF, IELTS.
Urval
Högskolepoäng, max 285 hp.
