Behörighetskrav

60 hp varav 15 p matematik och 25 hp datavetenskap. Alternativ 45 hp in om Masterprogram i språkteknologi. Genomgången Programkonstruktion och datastrukturer varav 9 hp ska vara avklarade, alternativt genomgången Algoritmer och datastrukturer I. Engelska 6 (med en svensk kandidatexamen uppfylls kravet på engelska).

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 och flödesnätverk.
• definiera komplexitetsklasserna P och NP och diskutera den öppna frågan om P=NP.
• presentera och diskutera material relaterat till kursens innehåll muntligt och skriftligt med för utbildningsnivån lämplig färdighet.

Innehåll

Funktioners tillväxt, rekursiva algoritmers komplexitet. 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. Teori för svårlösta problem.

Undervisning

Föreläsningar, lektioner och övningar.

Examination

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

Om särskilda skäl finns får examinator göra undantag från det angivna examinationssättet och medge att en enskild student examineras på annat sätt. Särskilda skäl kan t.ex. vara besked om särskilt pedagogiskt stöd från universitetets samordnare för studenter med funktionsnedsättning.