Hjem
Utdanning
Masteremne

Videregåande algoritmeteknikkar

  • Studiepoeng10
  • UndervisingssemesterHaust
  • EmnekodeINF334
  • Talet på semester1
  • SpråkEngelsk. Emnet kan undervisast på norsk dersom berre norskspråklege studentar meldar seg til emnet.
  • Ressursar

Studiepoeng, omfang

10

Studienivå (studiesyklus)

Master

Fulltid/deltid

Fulltid

Undervisningssemester

Haust

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.

Krav til forkunnskapar

Ingen

Tilrådde forkunnskapar

INF234

Studiepoengsreduksjon

I238: 10 ECTS

Krav til studierett

For oppstart på emnet er det krav om ein studierett knytt til Det matematisk-naturvitskaplege fakultet https://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.

Hjelpemiddel til eksamen

Ingen

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.

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.

Kontakt

Kontaktinformasjon

Studierettleiar kan kontaktast her:

studierettleiar

Tlf 55 58 42 00

Eksamensinformasjon