Mål og innhald
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 avgjerdsler 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.
Mål og innhald
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/resultat
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.
Undervisningssemester
Haust
Eksamenssemester
Det er ordinær eksamen kvart semester
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
Krav til forkunnskapar
Ingen
Tilrådde forkunnskapar
Byggjer på INF235
Fagleg overlapp
I238: 10 SP
Vurderingsformer
3 timar skriftleg eksamen. Dersom det er færre enn 20 deltakarar kan det bli muntleg eksamen.
Ingen lovlege hjelpemiddel.
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.
Emneevaluering
Studentane skal evaluere undervisninga i tråd med UiB og instituttet sitt kvalitetssikringssystem.
