Hoppa till huvudinnehåll
Länkstig

Algoritmer

Kurs
DIT093
Avancerad nivå
7,5 högskolepoäng (hp)
Studietakt
50%
Undervisningstid
Dag
Studieort
Göteborg
Undervisningsform
Campus
Undervisningsspråk
Engelska
Start/slut
-
Ansökan öppen
-
Anmälningskod
GU-18680
Ansökan stängd. Sen anmälan öppnar 16 juli 2021.

Om utbildningen

Följande ämnen behandlas under kursens gång:

- 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

Förkunskapskrav

Förkunskapskravet är avklarade kurser om 120 hp i ämnet datavetenskap eller matematik, inklusive; 7,5 hp diskret matematik (DIT980 Diskret matematik för datavetare, eller delkursen Inledande algebra i MMG200 Matematik I eller mosvarande), ytterligare 15 hp matematik, 7,5 hp imperativ eller objektorienterad programmering (DIT012 Imperativ programmering med grundläggande objektorientering, eller motsvarande), ytterligare 7,5 hp programmering, 7,5 hp datastrukturer (DIT960 Datastrukturer, eller motsvarande). Följande kunskapsnivå i Engelska krävs; Engelska 6/Engelska B eller motsvarande från ett erkänt internationellt test, t.ex. TOELF, IELTS. 

Urval

Högskolepoäng, max 225 hp

För antagning till sommaren 2021 och framåt gäller följande urval: högskolepoäng, max 165 hp.