Algoritmer och datastrukturer II

5 hp

Kursplan, Grundnivå, 1DL231

Det finns en senare version av kursplanen.
Kod
1DL231
Utbildningsnivå
Grundnivå
Huvudområde(n) med fördjupning
Datavetenskap G2F
Betygsskala
Med beröm godkänd, icke utan beröm godkänd, godkänd, underkänd
Fastställd av
Teknisk-naturvetenskapliga fakultetsnämnden, 8 mars 2012
Ansvarig institution
Institutionen för informationsteknologi

Behörighetskrav

60 hp varav minst 15 hp matematik och 30 hp datavetenskap inklusive Algoritmer och datastrukturer I.

Mål

Efter godkänd kurs ska studenten kunna

  • använda notationen för asymptotisk tillväxt av funktioner för att beskriva komplexitet hos algoritmer och beräkningsproblem.
  • härleda ekvationer för en algoritms komplexitet och lösa dessa.
  • använda vanliga algoritmiska tekniker som dynamisk programmering, "giriga" algoritmer, etc.
  • lösa enkla problem genom grafalgoritmer, strängmatchning, beräkningsgeometri och flödesnätverk.

Innehåll

Funktioners tillväxt, komplexitet av rekursiva algoritmer. Datastrukturer för disjunkta mängder. Dynamisk programmering, "giriga" algoritmer, grafalgoritmer, t.ex. kortaste vägen och minimalt uppspännande träd. Maximalt-flödesproblem i flödesnätverk. Algoritmer för strängmatchning, beräkningsgeometri, och datakomprimering.

Undervisning

Föreläsningar, lektioner och övningar.

Examination

Skriftligt prov (3 hp) samt inlämningsuppgifter (2 hp).

FÖLJ UPPSALA UNIVERSITET PÅ

facebook
instagram
twitter
youtube
linkedin