Emner: INF235 Kompleksitetsteori - Høst 2014
Undervisningsspråk
Engelsk
Undervisningssemester
Vår
Undervisningsstad
Bergen
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
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.
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
Obligatorisk undervisningsaktivitet
Godkjente obligatoriske oppgåver.
Obligatoriske aktiviteter er gyldige i to semester, det semesteret aktiviteten godkjennes samt det påfølgjande 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 munnleg eksamen.
Ingen lovlege hjelpemiddel.
Karakterskala
Ved sensur av emnet vert karakterskalaen A-F nytta.
Fagleg overlapp
I235: 10 SP
Vurderingssemester
Det er ordinær eksamen kvart semester
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.