Emnet gjennomgår avanserte metodar for utvikling og analyse av diskrete algoritmer. Desse vil dekkja fleire typar problem: over grafar med bestemt struktur (grafalgoritmer), over geometriske objekt (geometriske algoritmer), der avgjersler må takast før heile input er gitt (online-algoritmer), og der input-objektet endrar seg over tid (dynamiske algoritmer). Kurset vil gje grunnlag for forsøk på handtering av NP-harde problem gjennom approksimasjonsalgoritmer, randomiserte algoritmer, eller eit studium av problemet sin fixed- parameter kompleksitet.
Læringsutbyte
Ved fullført emne INF334 skal studenten kunne:
beherske avanserte metodar innanfor algoritmeutvikling og algoritmeanalyse.
ta i bruk disse metodane til å kunne utvikle praktiske algoritmar for store eller vanskelege problem.
anvende ulike metodar som er utvikla for handtering av problem som ikkje lar seg løyse effektivt innan den klassiske P vs. NP dikotomi.
Krav til forkunnskapar
Ingen
Tilrådde forkunnskapar
Byggjer på INF235
Krav til studierett
For oppstart på emnet er det krav om ein studierett knytt til eit masterprogram/Ph.d-utdanninga ved Det matematisk-naturvitskaplege fakultet, samt at du oppfyller ev opptakskrav
Vurderingsformer
3 timar skriftleg eksamen. 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
I238: 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å instituttet.