en_GB
Hold Ctrl-tasten nede. Trykk på + for å forstørre eller - for å forminske.

DAT200_1

Algoritmer og datastrukturer

Dette er studietilbudet for studieår 2019-2020. Endringer kan komme.


Emnet gir en grundig innføring i en del mye brukte datastrukturer og algoritmer.

Læringsutbytte

Etter å ha tatt dette emnet skal studenten:
Kunnskap
  • Vite hvordan grunnleggende algoritmer for sortering, søking, og veifinning i grafer virker
  • Vite hvordan grunnleggende datastrukturer for lister, stabler, køer, prioritetskøer, mengder, assosiative tabeller og grafer virker

Ferdigheter
  • Være i stand til å beregne effektiviteten til algoritmer
  • Være i stand til å forstå og lage effektive rekursive algoritmer
  • Være i stand til å implementere effektive algoritmer for sortering og søking

Generell kompetanse
  • Vite hvordan datastrukturer og algoritmer for lister, køer, stabler (stack), hauger (heap), binære tre, og grafer kan implementeres.
  • Kunne bruke standard algoritmer og datastrukturer til å lage effektive programmer

Innhold

Effektivitetsanalyse for algoritmer. Definisjon, bruk og implementeringer av abstrakte datatyper som: Stabler, køer, lister, assosiative tabeller (Python dictionary), trestrukturer, grafer, prioritetskøer, hauger. Hash-teknikker. Trestrukturer. Bruk og implementering av datastrukturer som kan representere grafer. Algoritmer for sortering og søking. Noen grunnleggende algoritmer for grafer, inkludert veifinning. Rekursjon som programmeringsteknikk.

Forkunnskapskrav

Ingen.

Anbefalte forkunnskaper

DAT100 Objektorientert programmering, DAT110 Grunnleggende programmering

Eksamen/vurdering

Vekting Varighet Karakter Hjelpemiddel
En skriftlig prøve1/14 timerA - FIngen hjelpemidler tillatt

Vilkår for å gå opp til eksamen/vurdering

Innleveringsoppgaver
Det er 9 øvinger i faget. For å få godkjent øvingsopplegget og dermed få lov til å ta eksamen i faget må minimum 7 av 9 øvinger være godkjente innen angitt frist.

Fagperson(er)

Emneansvarlig
Erlend Tøssebro
Instituttleder
Tom Ryen

Arbeidsformer

6 timer forelesning i uka. Alle studenter får tilbud om å delta på øvingstimer 4 timer i uken. På datalaben får en hjelp til å fullføre de obligatoriske oppgavene. Dessuten skal studentene presentere løsningene sine på laben.
Gjennomføring av obligatoriske øvinger skal gjøres til de tider og i de grupper som er oppsatt og publisert på Canvas. Fravær på grunn av sykdom eller av andre årsaker skal snarest mulig kommuniseres til laboratorie- eller fagansvarlig. Det kan ikke påregnes å få godkjent øvinger utenom oppsatt tid hvis dette ikke er kommunisert og ny avtale gjort.
Konsekvensen av at du ikke har fått godkjent øvingsoppgavene er at du ikke får gå opp til eksamen i faget.

Overlapping

Emne Reduksjon (SP)
Datastrukturer og algoritmer (TE0458_1) 6
Datastrukturer og algoritmer (TE0458_A) 6
Datastrukturer og algoritmer (BIE270_1) 10

Åpent for

Bachelornivå på Det teknisk-naturvitenskapelige fakultetet.

Masternivå på Det teknisk-naturvitenskapelige fakultetet

Emneevaluering

Skjer vanligvis gjennom skjema og/eller i samtaler etter til gjeldende retningslinjer.

Litteratur

Det finnes mange lærebøker i algoritmer av varierende kompleksitetsgrad og som bruker ulike programmeringsspråk for å presentere algoritmene. Dette faget vil ikke følge noen bestemt lærebok men vil ha et pensum, inkludert et kompendium. Pensumlister og kompendiet blir lagt ut på Canvas. Dette faget vil i år undervises med programmeringsspråket Python. En mulig lærebok som ligger på nett er:
Problem Solving with Algorithms and Data Structures using Python av Brad Miller and David Ranum, Luther College
Alternative lærebøker:
- Introduction to Algorithms, 3. utgave, av Cormen, Leiserson, Rivest, Stein, MIT press. Denne er grundig og brukes i masteremnet DAT600 Algoritmeteori samt i NTNU sin versjon av DAT200, men er svært teoretisk og matematisk. Denne har all kode i pseudokode heller enn i et programmeringsspråk.
- Python Algorithms: Mastering Basic Algorithms in the Python Language 2nd ed. Edition av Magnus Lie Hetland. Apress. Denne dekker et litt annet pensum enn DAT200 gjør.
Det finnes ingen Python-baserte lærebøker på Norsk, men det fins to Java-baserte:
- Algoritmer og datastrukturer med eksempler i C og Java av Helge Hafting og Mildrid Ljosland.Gyldendal akademisk forlag.
- Algoritmer og datastrukturer med Java 10, Nettbasert lærebok av Ulf Uttersrud
Et kompendium som legges ut på Canvas


Dette er studietilbudet for studieår 2019-2020. Endringer kan komme.

Sist oppdatert: 22.08.2019

Historikk