NITH 2012 - 2013 / Emner / Programmeringsemner (PG,IPG) / PG4200 Algoritmer og datastrukturer  

PG4200 Algoritmer og datastrukturer

Emnenivå
Bachelor

Emnekode
PG4200

Emnenavn
Algoritmer og datastrukturer

Studiepoeng
7,50

Emneansvarlig
Lars Sydnes

Tilsynssensor
Magnus Lie Hetland, NTNU

Godkjenningsdato
28.11.2012

Hensikt
Emnet skal gi innsikt i algoritmer og datastrukturer som er sentrale i arbeidet med implementasjon og design av effektive datasystemer.

Forutsetninger
PG1100 og PG2100 eller tilsvarende grunnleggende programmeringskunnskap.

Læringsutbytte

Kunnskapsmål

Studentene skal kjenne til

  • egenskapene til en rekke ulike datastrukturer som lister, køer, stakker, trær og grafer,
  • egenskapene til ulike implementasjoner av disse datastrukturene,
  • egenskapene til grunnleggende algoritmer,
  • sentrale algoritmer for søk og sortering,
  • rekursive algoritmer
  • grunnleggende begreper innen teorien for beregningskompleksitet,
  • kjente problemer med/uten kjente effektive løsninger.

Ferdighetsmål

Studenten skal beherske

  • å bruke eksisternde bilblioteker for algoritmer og datastrukturer,
  • å implementere kjente algoritmer og datastrukturer,
  • utvilking av skreddersydde algoritmer og datastrukturer,
  • enkel generisk programmering i java med bruk av maler (templates),
  • vurdering av tids- og ressursbruk for ulike algoritmer.

Generelle kompetansemål

Studenten skal

  • kunne bruke eksisterende bibliotek og egenutviklede algoritmer og datastrukturer til å løse praktiske problemer,
  • se hvilke problemer som krever egenutviklede løsninger, og hvilke problemer som kan løses med velkjente metoder og eksisterende bibliotek,
  • kunne identifisere kritiske elementer i dataprogrammer, og beherske ulike verktøy for å forbedre ytelse og struktur.
Gjennomføring
Forelesninger (ca. 50%) og øvinger (ca. 50%)

Anbefalt tidsbruk

Aktivitet

Tidsbruk

Deltakelse i undervisning

 24

Selvstudium

128

Forberedelse til presentasjon/diskusjon i klassen

 

Øving

 24

Vurdering

 24

Anbefalt tidsbruk totalt

200

Verktøy

Java Development Kit 1.6 (eller nyere versjoner)

Karakterskala
Letter grades A-E for passed and F for failure

Vitnemålstekst
Emnet skal gi innsikt i algoritmer og datastrukturer som er sentrale i arbeidet med implementasjon og design av effektive datasystemer.

Vurderingstype
Mappevurdering

Vurdering

Mappevurdering med skriftlig eksamen:

  • To eller flere obligatoriske innleveringer
  • Skriftlig eksamen ved semesterets slutt



Litteraturliste:
Tittel Forfatter Forlag Utgitt år ISBN Utgave Kommentar Type Litteratur
Java Software Structures: Designing and Using Data Structures  John Lewis, Joseph Chase  Addison-Wesley  2010  978-0-13-607858-6  3.    Bok  Pensum 

Vurdering / Assessment

Vekting (%):
100

Vurderingstype:
Mappevurdering m/skriftlig prøve (se emnesiden) / Portfolio w/written test

Hjelpemiddel:
Ingen / None

Varighet:
3 timer

Semester:
Vår / Spring