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.

Undervisningssemester

Vår

Eksamenssemester

Det er ordinær eksamen kvart semester

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

Krav til forkunnskapar

Ingen

Tilrådde forkunnskapar

Byggjer på INF234.

Fagleg overlapp

I235: 10 SP

Karakterskala

Ved sensur av emnet vert karakterskalaen A-F nytta.

Undervisningsstad

Bergen

Emneevaluering

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