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ökningsperiod
-
Anmälningskod
GU-28652
Ansökan stängd

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.