Kompleksitetsteori

Undervisningsspråk

Engelsk

Krav til forkunnskapar

Ingen

Læringsutbyte

Ved fullført emne INF235 skal studenten:

• ha ei djupare forståing av kva ei algoritme er og kva for problem som teoretisk sett kan bli løyst vha. ei datamaskin.
• forstå samanhengen mellom formelle språk og Turing-maskinar.
• vite korleis ein klassifiserer problem i kompleksitetsklasser for tid og for minne.
• kunne avgjere kva for problem som praktisk lar seg løyse, eksakt eller tilnærma.

Kontaktinformasjon

Forelesar og Administrativ kontaktperson finn du på Mi side, kontakt ev studiekonsulenten på Insituttet.

Undervisningsmetodar

Undervisningsformen kan bli endret dersom det er få studenter som deltar.

Undervisningssemester

Vår

Eksamenssemester

Det er ordinær eksamen kvart semester

Undervisningsspråk

Engelsk

Krav til studierett

For oppstart på emnet er det krav om ein studierett knytt til Det matematisk-naturvitskaplege fakultet, samt at du oppfyller ev opptakskrav

Mål og innhald

Kompleksitet er eit mål for kor mykje ressursar (tid og plass) som krevst for å løyse eit problem algoritmisk. Kurset gir ein presis formell definisjon av algoritmeomgrepet (via Turingmaskiner). Hovudvekt blir lagt på sentrale kompleksitetsklassar, særleg NP-komplette problem, og algoritmer som gir tilnærma løysingar for NP-harde problem.

Læringsutbyte/resultat

Ved fullført emne INF235 skal studenten:

• ha ei djupare forståing av kva ei algoritme er og kva for problem som teoretisk sett kan bli løyst vha. ei datamaskin.
• forstå samanhengen mellom formelle språk og Turing-maskinar.
• vite korleis ein klassifiserer problem i kompleksitetsklasser for tid og for minne.
• kunne avgjere kva for problem som praktisk lar seg løyse, eksakt eller tilnærma.

Krav til forkunnskapar

Ingen

Tilrådde forkunnskapar

Byggjer på INF234.

Fagleg overlapp

I235: 10 SP

Obligatoriske arbeidskrav

Oppgåver.

Obligatoriske aktiviteter er gyldige i to semester, det semesteret aktiviteten godkjennes samt det påfølgende semesteret.

Vurderingsformer

3 timar skriftleg eksamen. Det er høve til å gi karakter på obligatoriske oppgåver som kan inngå i sluttkarakteren. Dersom det er færre enn 20 deltakarar kan det bli muntleg eksamen.

Ingen lovlege hjelpemiddel.

Karakterskala

Ved sensur av emnet vert karakterskalaen A-F nytta.

Undervisningssted

Bergen

Emneevaluering

Studentane skal evaluere undervisninga i tråd med UiB og instituttet sitt kvalitetssikringssystem.

Kontaktinformasjon

Forelesar og Administrativ kontaktperson finn du på Mi side, kontakt ev studiekonsulenten på Insituttet.