ID1020 Algoritmer och datastrukturer 7,5 hp

Algorithms and Data Structures

  • Utbildningsnivå

    Grundnivå
  • Huvudområde

    Teknik
  • Betygsskala

    A, B, C, D, E, FX, F

Kurstillfällen/kursomgångar

HT19 för programstuderande

HT19 TCOMK för programstuderande

HT18 för programstuderande

HT18 för programstuderande

Lärandemål

Målet med kursen är att ge en gedigen kunskap om hur man designar och analyserar de viktigaste klasserna av algoritmer. Kursen avser att ge studenterna färdigheter som ger dem möjlighet att självständigt konstruera datorprogram som använder tid och minne på ett effektivt sätt. Studenterna skall lära sig identifiera problem som är orealistiskt resurskrävande att lösa eller som rent av är omöjliga att lösa med vanliga beräkningsmodeller. Vid slutet av kursen skall studenterna kunna utveckla egna lösningsalgoritmer till problem och kunna jämföra olika lösningar och hur väl de fungerar.

Efter att framgångsrikt ha avslutat kursen skall studenterna kunna:

  1. utveckla och implementera algoritmer och datastrukturer och analysera dem med avseende på korrekthet.
  2. definiera termerna P, NP, NP-fullständighet och beräkningsbarhet.
  3. analysera hur effektiva algoritmer och datastrukturer är utgående från olika mått på effektivitet som t.ex. tidskomplexitet och minneskomplexitet.
  4. skriva program som implementerar större enheter som använder algoritmer och datastrukturer med hjälp goda programmeringsprinciper som t.ex. specificerandet av API:er och användandet av tester som utnyttjar algoritmer eller datastrukturer.
  5. lösa problem genom användandet av datastrukturer som linjära listor, stackar, köer, hashtabeller, binära träd, heapar, turneringsträd, binära sökträd och grafer och skriva program för lösningarna.
  6. lösa problem genom att använda algoritmdesignmetoder som t.ex. giriga algoritmer, dekomposition, dynamisk programmering backtracking och branch and bound och  skriva program för lösningarna.
  7. givet ett specifikt problem antingen designa en lämplig datastruktur eller skapa en algoritm  som löser problemet eller identifiera problemet som ett som inte går att lösa effektivt.

Kursens huvudsakliga innehåll

Grundläggande analys

  • Asymptotisk analys av komplexitetsgränser i värsta fall och i medeltal.
  • Att identifiera skillnader mellan uppträdanden i bästa fall, värsta fall och i medeltal.
  • Ordo-, omega- och teta-notation.
  • De vanligaste komplexitetsklasserna.
  • Empirisk uppskattning av komplexitet.
  • Tids- och minneskomplexitet.
  • Användandet av rekursionssamband för att analysera algoritmer.

Strategier för algoritmer och dataabstraktion

  • Brute-force algoritmer.
  • Giriga algoritmer.
  • Dekompositionsalgoritmer.
  • Backtracking.
  • Branch-and-bound.
  • Heuristik.

Grundläggande algoritmer

  • Enkla numeriska algoritmer.
  • Sekventiella och binära sökalgoritmer.
  • Kvadratiska sorteringsalgoritmer (urval, insättning).
  • Sortering i O(N log N) (Quicksort, heapsort, mergesort).
  • Hashtabeller inkluderande sådan som undviker kollisioner.
  • Binära sökträd.
  • Representationer av graf (grannlistor, grannmatriser).
  • Djupet först- och bredden först-sökning.
  • Kortaste väg-algoritmer (Dijkstras och  Floyds algoritmer).
  • Transitiv tillslutning(Floyds algoritm).
  • Minimala spännande träd (Prims och Kruskals algoritmer).
  • Topologisk sortering.

Grundläggande beräkningsbarhet

  • Ändliga tillstånds-maskiner.
  • Kontextfria grammatiker.
  • Lösbara och olösbara problem.
  • Beräkningsbara och icke beräkningsbara funktioner.
  • Halting-problemet.
  • Konsekvenser av oavgörbarhet.

P versus NP.

  • Definition av klasserna P och NP.
  • NP-fullständighet (Cooks sats).
  • De vanligaste NP-fullständiga problemen.
  • Reduktionstekniker.

Behörighet

En grundläggande programmeringskurs som t.ex. ID1018 : Programmering I

Rekommenderade förkunskaper

En grundläggande programmeringskurs som t.ex. ID1018 : Programmering I

Litteratur

 Algorithms, 4th Edition, 2011. Robert Sedgewick and Kevin Wayne. Addison-Wesley. ISBN-10: 032157351X.

Examination

  • ARBA - Kursarbete, 4,5, betygsskala: P, F
  • TENA - Skriftlig tentamen, 3,0, betygsskala: A, B, C, D, E, FX, F

Lärandemålen som definierats ovan examineras både genom kontinuerlig examination och genom en skriftlig tenta. Allt arbete av studenterna är individuellt. Det förekommer inga grupprojekt. 

Ges av

EECS/Datavetenskap

Kontaktperson

Robert Rönngren

Examinator

Robert Rönngren <rron@kth.se>

Övrig information

Kursen ges första gången läsåret 14/15 och ersätter då ID1005 på samtliga program.

Versionsinformation

Kursplan gäller från och med VT2019.
Examinationsinformation gäller från och med VT2019.