Algoritmer och datastrukturer I

5 hp

Kursplan, Grundnivå, 1DL210

Det finns en senare version av kursplanen.
Kod
1DL210
Utbildningsnivå
Grundnivå
Huvudområde(n) med fördjupning
Datavetenskap G1F, Teknik G1F
Betygsskala
Med beröm godkänd, icke utan beröm godkänd, godkänd, underkänd
Fastställd av
Teknisk-naturvetenskapliga fakultetsnämnden, 27 april 2010
Ansvarig institution
Institutionen för informationsteknologi

Behörighetskrav

10 hp programmering (Programkonstruktion, Programmeringsteknik II eller motsvarande) och 10 hp matematik, inklusive grundläggande algebra.

Mål

För godkänt betyg ska studenten kunna

  • analysera körtiden för en (enkel) algoritm/program i relation till indatats storlek, i bästa, sämsta, och genomsnittliga fall,
  • välja lämpliga algoritmer och datastrukturer för lagring av data, sökning och sortering, samt implementera dessa.
  • använda och implementera grundläggande grafalgoritmer.

Innehåll

Matematiska grunder: asymptotisk notation, summationer, rekursionsformler.

Datastrukturer: träd, prioritetsköer, "heaps".

Sökmetoder: binära sökträd, balanserade sökträd, hashtabeller.

Sorteringsmetoder.

Enkla grafalgoritmer: djup-först och bredd-först sökning.

Implementering av algoritmer och datastrukturer.

Undervisning

Föreläsningar, lektioner, laborationer och

obligatoriska inlämningsuppgifter.

Examination

Skriftligt prov (4 hp) samt inlämningsuppgifter (1 hp).

Övriga föreskrifter

Kursen kan inte räknas in i examen med Programkonstruktion II (1IT022) eller

Datastrukturer (1DL009, 1TD191, 1MB026).

FÖLJ UPPSALA UNIVERSITET PÅ

facebook
instagram
twitter
youtube
linkedin