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
Ett krav är att ha en kandidatexamen om 180 hp inom datavetenskap (eller motsvarande), alternativt avklarade kurser om 120 hp i ämnena datavetenskap och matematik. Vidare gäller följande krav:
- 7,5 hp diskret matematik (DIT984 Diskret matematik för datavetare, eller delkursen Inledande algebra i MMG200 Matematik I, eller motsvarande),
- ytterligare 10 hp matematik,
- 15 hp programmering, och
- 7,5 hp datastrukturer (DIT962 Datastrukturer, DIT375 Python for Data Scientists, eller motsvarande).
Följande kunskapsnivå i Engelska krävs: Engelska 6/Engelska nivå 2 eller motsvarande från ett erkänt internationellt test, t.ex. TOEFL, IELTS.
Urval
Högskolepoäng, max 285 hp.
