Behörighetskrav

Algebra och geometri. Programkonstruktion.

Syfte

Kursen skall ge grundläggande kunskaper om

teorin för beräkningar och formella språk samt

teorin för grupper och kroppar, samt ge en

introduktion till graf- och kodningsteori.

Innehåll

Kursen är uppdelad på två delkurser,

Automatateori och formella språk (Automata theory

and formal languages) och Algebraiska strukturer

(Algebraic structures).

Automatateori och formella språk, 3 poäng:

Automatateori: deterministiska och

icke-deterministiska ändliga automater, reguljära

språk, Kleenes sats, pushdownautomater,

sammanhangfria språk, pumpsatser. Chomskys

språkhierarki. Turingmaskiner: universalmaskinen

och stopproblemet. Orientering om

komplexitetsteori (kompexitetsklasserna P och NP).

Rekursiva funktioner. Rices sats och andra

oavgörbarhetsresultat. Church-Turings tes. Logik:

sats- och predikatlogik och deras semantiker.

Algebraiska strukturer, 4 poäng:

Relationer: partiella ordningar och ekvivalensrelationer. Talföljder. Ordo-notationen.

Heltalen (speciellt delbarhet och kongruensräkning), representation i olika baser,

Fermats lilla sats, Eulers φ-funktion.

Vektorrum, ekvationsystem och polynom över ändliga kroppar med tillämpningar på kodningsteori.

Kombinatorik: permutationer, kombinationer, Dirichlets lådprincip, grundläggande principer för enumeration, kombinatoriska identiteter,

rekursionsformler och analys av algoritmer.

Grafteori: Hamiltonska cykler, graffärgning, delgrafer, isomorfier, träd, flöden i nätverk, grafalgoritmer, matchningsproblem.

Undervisning

Föreläsningar, lektioner och laborationer.

Examination

Ett skriftligt och eventuellt ett muntligt prov

ges vid slutet av varje delkurs. Obligatoriska

uppgifter kan förekomma i samband med

undervisningen.