Videregåande algoritmeteknikkar

Masteremne

Emnebeskrivelse

Mål og innhald

Emnet gjev ein introduksjon til avanserte metodar for å designe og handsamast med algoritmar for vanskelege berekningsproblem. Anvendingsområder er mellom anna grafar, nettverk, sett og geometriske objekt.

Emnet dekkjer ulike paradigme for å handsamast med vanskelege berekningsproblem, nemlig approksimasjonsalgoritmar, parameteriserte algoritmar, eksponensiell-tid algoritmar, samt polynomisk-tid algoritmar for avgrensa inndataklasser. Emnet dekkjer óg bruk av tilfeldigheit i algoritmar.

Læringsutbyte

Studenten skal ved avslutta emne ha oppnådd følgjande læringsutbyte definert i kunnskapar, ferdigheiter og generell kompetanse:

 

Kunnskapar
Studenten kjenner til:

  • Dei sentrale definisjonane innanfor ulike paradigme for å handsamast med NP-vanskelege problem, som FPT-algoritmar, kjernar, approksimasjonsalgoritmar og polynomisk-tid algoritmar for avgrensa inndataklassar.
  • Dei grunnleggjande teknikkane for å lage algoritmar innanfor kvart paradigme
  • Inndataklassar som tre, kordale grafar og grafar med bunden tre-bredde, samt strukturelle karakteristikkar av slike klassar.
  • Definisjonen av randomiserte algoritmar.

  

Ferdigheiter
Studenten kan:

  • analysere algoritmar innanfor rammene til dei ulike paradigma for å handsamast med NP-vanskelege problem.
  • Designe nye algoritmar for konkrete berekningsproblem innanfor kvar av dei ulike paradigma
  • Bruke dei strukturelle karakteristikkar av dei ulike inndataklassane til å gje meir effektive algoritmar for inndata frå disse klassene.
  • Designe randomiserte algoritmar og analysere forventningsverdien til algoritmen si køyretid, forventningsverdien til kvaliteten på løysinga som algoritmen produserar, samt berekne sannsyna for at køyretida til algoritmen eller kvaliteten til den produserte løysinga er over/under ei oppgjeve grense.

 

Generell kompetanse

  • Studenten kan analysere og utvikle algoritmar for NP-vanskelege berekningsproblem.

Studiepoeng, omfang

10

Studienivå (studiesyklus)

Master

Undervisningssemester

Haust
Krav til forkunnskapar
Ingen
Tilrådde forkunnskapar
Studiepoengsreduksjon
I238: 10 ECTS
Krav til studierett
For oppstart på emnet er det krav om ein studierett knytt til Det matematisk-naturvitskaplege fakultet www.uib.no/matnat/52646/opptak-ved-mn-fakultetet
Arbeids- og undervisningsformer
Det er 4 timar med ordinær undervisning kvar veke. Ved høve er det og 2 timar med gruppeundervisning kvar veke.
Obligatorisk undervisningsaktivitet
Ingen
Vurderingsformer

Munnleg eksamen.

Opp til 30% av karakteren blir satt på grunnlag av aktivitet i løpet av semesteret, som innleveringsoppgåver og midtsemestereksamen i førelesingstimane. Informasjon om aktivitet som teller på karakteren og vekting av desse vil bli gjeve i byrjinga av semesteret.

Karakterskala
Ved sensur av emnet vert karakterskalaen A-F nytta.
Vurderingssemester

Det er ordinær eksamen kvart semester.

Aktiviteter som teller på karakteren er gyldige i to semester; i undervisningssemesteret, samt det påfølgjande semesteret.

Litteraturliste
Litteraturlista vil vere klar innan 01.06. for haustsemesteret og 01.12. for vårsemesteret.
Emneevaluering
 Studentane skal evaluere undervisninga i tråd med UiB og instituttet sitt kvalitetssikringssystem.
Hjelpemiddel til eksamen
Ingen
Programansvarleg
Programstyret har ansvar for fagleg innhald og oppbygging av studiet og for kvaliteten på studieprogrammet og alle emna der.
Emneansvarleg
Emneansvarleg og administrativ kontaktperson finn du på Mitt UiB, kontakt eventuelt studierettleiar
Administrativt ansvarleg
Det matematisk-naturvitenskapelige fakultet v/ Institutt for informatikk har det administrative ansvaret for emnet og studieprogrammet.