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.

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.

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.

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.

Studierettleiar kan kontaktast her:

mailto:studieveileder@ii.uib.nostudierettleiar

Tlf 55 58 42 00