Algoritmiske metoder
2012-2013 - IMT2021 - 10sp

Anbefalt forkunnskap

IMT1082 - Objekt-orientert programmering
REA1101 - Matematikk for informatikkfag
eller
REA2091 Matematikk 2 for data

Forventet læringsutbytte

Kunnskaper:

Bli kjent med, kunne forklare, anvende og i noe grad kunne omskrive en del standard algoritmer for bl.a. sortering, søking og grafhåndtering.
Beskrive og forklare ulike datastrukturer (arrayer/tabeller, lenkede lister, køer, stakker, trær og grafer).
Analysere avanserte og kompliserte (ikke-trivielle) problemstillinger, og finne algoritmen for å løse disse.
Anvende rekursiv tankegang/metode ved problemløsning og programmering.
Bruke abstraksjon ved konstruksjon av programmer.

Ferdigheter:

Skrive pålitelige og effektive/raske dataprogrammer.
Skrive programkoden som løser avanserte og kompliserte problemstillinger.
Håndtere avanserte datastrukturer (med særlig vekt på trær og grafer).

Generell kompetanse:

Har evnen til å tenke over og løse avanserte og kompliserte problemer.
Finne/spore opp annen/nyere kunnskap (her: algoritmer), resultater og forskning innen fagfeltet.

Emnets temaer

Teknikker og algoritmer:

Objekt-orientering
Abstrakte datatyper
Rekursjon
Søking
Sortering
Hashing
Komprimering
Tilstandsmaskiner

Datastrukturer:

Tabeller/arrayer
Kø
Stakk
Pekere og dynamisk allokering
Lister
Trær
Grafer(connectivity, vekting, rettet)
Nettverksflyt

Effektivitet:

Kompleksitet og O-notasjon
Tids- og plassforbruk

Pedagogiske metoder

Forelesninger
Obligatoriske oppgaver
Oppgaveløsning
Veiledning

Vurderingsformer

Skriftlig eksamen, 5 timer

Karakterskala

Bokstavkarakterer, A (best) - F (ikke bestått)

Sensorordning

Vurderes av intern og ekstern sensor.

Utsatt eksamen (tidl. kontinuasjon)

Ingen kontinuasjon

Tillatte hjelpemidler (gjelder kun skriftlig eksamen)

Alle trykte og skrevne

Obligatoriske arbeidskrav

Øvingsoppgaver (hver 2.-4. uke, må være godkjent av fagassistent).

Læremidler

Sedgewick, Robert. (1992). Algorithms in C++. Boston, MA: Addison-Wesley.
Faglærer. Kompendium. Gjøvik: HiG.
Faglærer. Annet utdelt litteratur/artikler/notater. Gjøvik: HiG.

Supplerende opplysninger

Læreboka kan leies/lånes av høgskolen (mot et depositum). Opptrykk av utvalgte sider med kodesnutter vil bli å få kjøpt i bokhandelen.