Hoppa till huvudinnehållet

ID1021 Algoritmer och datastrukturer 7,5 hp

En grundläggande kurs i datalogi som ger behörighet till flera fortsättningskurser inom datalogi. Kursen tar upp både teori om algoritmer och datastrukturer och praktisk programkonstruktion.

Välj termin och kursomgång

Välj termin och kursomgång för att se aktuell information och mer om kursen, såsom kursplan, studieperiod och anmälningsinformation.

Kursval

Gäller för kursomgång

HT 2024 Start 2024-08-26 programstuderande

Anmälningskod

50284

Rubriker med innehåll från kursplan ID1021 (HT 2022–) är markerade med en asterisk ( )

Innehåll och lärandemål

Kursinnehåll

Grundläggande algoritmanalys:

  • Enklare analys avseende algoritmers resursbehov i form av tid och minne.

Grundläggande algoritmer:

  • enkla numeriska algoritmer
  • sekventiella och binära sökalgoritmer
  • djupet först- och bredden först-sökning
  • sorteringsalgoritmer: urvalssortering, insättningssortering, Quicksort, heapsort, mergesort.

Grundläggande datastrukturer:

  • linjära listor, stackar, köer, hashtabeller, binära träd, heapar, binära sökträd och problemträd.

Programkonstruktion:

  • design och implementering av program som använder grundläggande algoritmer och datastrukturer för att lösa datalogiska problem.

Lärandemål

Efter godkänd kurs ska studenterna kunna

  • beskriva ett antal vanliga algoritmer för sökning och sortering och deras egenskaper
  • jämföra algoritmer med avseende på tids- och minnesåtgång
  • implementera datastrukturer som linjära listor, stackar, köer, hashtabeller, binära träd och sökträd
  • identifiera problem där datastrukturerna ovan är användbara och konstruera enkla algoritmer med dessa
  • skriva program som använder algoritmer och datastrukturer med hjälp av goda programmeringsprinciper som t.ex. systematiska tester och abstraktion
  • modellera problem som sökproblem och implementera algoritmer för breddenförstsökning, djupetförstsökning eller bästaförstsökning

i syfte att

  • kunna konstruera program som löser problem genom att använda vanligt förekommande algoritmer och datastrukturer
  • ha tillräckliga förkunskaper för att kunna läsa fortsättningskurser i datalogi.

Kurslitteratur och förberedelser

Särskild behörighet

Kunskaper och färdigheter i programmering, 7,5 hp, motsvarande slutförd kurs ID1018.

Rekommenderade förkunskaper

Kursupplägget är baserat på att deltagarna har programmeringsvana och utan hjälp kan editera, kompilera och köra enklare program även i språk de kanske inte använder normalt eller har använt förut.

Utrustning

Ingen information tillagd

Kurslitteratur

Kursmaterial kommer finnas tillgängligt för nedladdning.

Examination och slutförande

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

Betygsskala

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

Examination

  • INL1 - Inlämningsuppgifter, 7,5 hp, betygsskala: A, B, C, D, E, FX, F

Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

Möjlighet till komplettering

Ingen information tillagd

Möjlighet till plussning

Ingen information tillagd

Examinator

Etiskt förhållningssätt

  • Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
  • Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
  • Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.

Ytterligare information

Kursrum i Canvas

Registrerade studenter hittar information för genomförande av kursen i kursrummet i Canvas. En länk till kursrummet finns under fliken Studier i Personliga menyn vid kursstart.

Ges av

Huvudområde

Teknik

Utbildningsnivå

Grundnivå

Påbyggnad

Ingen information tillagd

Övergångsbestämmelser

Studenter som påbörjat kursen med den tidigare examinationen ARBA och TENA kan fullfölja denna och skriva en tentamen och göra de inlämningar som saknas, dessa skall slutföras senast HT23.

Övrig information

I denna kurs tillämpas EECS hederskodex, se:

http://www.kth.se/eecs/utbildning/hederskodex.