Innledning

Emnet skal gi innsikt i algoritmer og datastrukturer som er sentrale i arbeidet med implementasjon og design av effektive datasystemer. Det legges vekt på asymptotisk analyse av worst-case ressursrbruk, samt sentrale algoritmer og datastrukturer knyttet til søk og sortering. Emnet tar også for seg enkelte graf-algoritmer, optimalisering-algoritmer og komprimering-algoritmer.

Læringsutbytte

Kunnskap

Studenten...

  • kjenner til sentrale abstrakte datatyper som lister, stakker, køer, mengder (sets,collections), symboltabeller (maps), trær og grafer
  • kjenner til egenskapene til sentrale datastrukturer som tabeller (arrays), lenkede lister, heaps, binære trær, søketrær, balanserte søketrær, hashtabeller og grafer implementert ved naboskapslister og -matriser.
  • kjenner til Java Generics og Streams
  • kjenner til sentrale søkealgoritmer som lineært søk, binært søk, søk i binære søketrær, søk i hashtabeller
  • kjenner til sentrale sorteringsalgoritmer som Bubble sort, Quicksort og Merge sort
  • kjenner til metoder for traversering av grafer, samt Depth-First og Breadth-First algoritmer
  • kjenner til oppbygning, virkemåte og bruk av rekursive funskjoner, inkludert rekursiv traversering av trær og grafer, rekursiv søk og sortering, backtracking
  • kjenner til problemstillinger knyttet til måling av kjøretid for dataprogrammer.
  • kjenner til P, NP og NP-complete problemer
  • kjenner til optimalisering-algoritmer, samt Hill-Climbing og Genetic-Algorithms
  • kjenner til komprimering-algoritmer

Ferdigheter

Studenten...

  • kan bruke kunnskapene nevnt i avsnittet over (kunnskapsmål) til å bruke eksisterende biblioteker for algoritmer og datastukturer på en fornuftig måte
  • kan implementerer kjente datastrukturer som tabell-lister, lenkede lister, binære søketrær, heaps, hash-tabeller og grafer
  • kan implementere kjente algoritmer som Bubble sort, Quicksort og Merge Sort.
  • kan bedømme worst-case ressursbruk for konkrete dataprogrammer ved hjelp av O-notasjon og tilde-notasjon
  • behersker grunnleggende generisk programmering, samt bruken av grensesnitt (interface) og implementasjoner av grensesnitt, for effektiv bruk av algoritmer i kode.
  • kan sammenligne empiriske målinger av ressursbruk med teoretiske estimater, med tanke på å vurdere om estimatene er korrekte, å identifisere interessante avvik samt å anslå størrelsen på ukjente faktorer i estimatene

Generell kompetanse

Studenten...

  • behersker klassisk asymptotisk analyse av dataprogrammer med O- og tilde-notasjon.
  • kan bruke eksisterende bibliotek og egenutviklede algoritmer og datastrukturer på en klok måte
  • behersker terminologi som gjør det mulig å diskutere ressursbruk i dataprogrammer på en tilstrekkelig presis måte
  • besitter kunnskap om algoritmer og datastrukturer som kommer til nytte i videre informatikkstudier og arbeidslivet

Emnet inngår i

Bachelor i informasjonsteknologi - Programmering 

Bachelor i informasjonsteknologi - Spillprogrammering

Bachelor i informasjonsteknologi - Intelligente systemer

Valgemne for Bachelor i informasjonsteknologi - Frontend- og mobilutvikling

Læringsaktiviteter

Undervisningen foregår som fellesforelesninger og egenarbeid under veiledning av foreleser og studentveileder.

Anbefalt tidsbruk

Deltakelse i undervisning og veiledning - 48 timer

Selvstudium - 128 timer

Gjennomføring av og forberedelse til eksamen - 24 timer

Anbefalt tidsbruk totalt - 200 timer

Arbeidsverktøy

Tilgang til pc og Java Development Kit.

Eksamen

Eksamensdel: Skriftlig individuell eksamen 

Varighet: Tre timer 

Gradering: Nasjonal karakterskala A - F (F er ikke bestått) 

Vekting: 100 % av hel vurdering 

Hjelpemidler: Ingen hjelpemidler er tillatt