Kursplan fastställd 2019-02-07 av programansvarig (eller motsvarande).
Kursöversikt
- Engelskt namnData structures and algorithms
- KurskodDAT038
- Omfattning7,5 Högskolepoäng
- ÄgareTKDAT
- UtbildningsnivåGrundnivå
- HuvudområdeDatateknik, Informationsteknik
- InstitutionDATA- OCH INFORMATIONSTEKNIK
- BetygsskalaTH - Fem, Fyra, Tre, Underkänd
Kurstillfälle 1
- Undervisningsspråk Engelska
- Anmälningskod 49135
- Max antal deltagare165
- Sökbar för utbytesstudenterNej
Poängfördelning
Modul | LP1 | LP2 | LP3 | LP4 | Sommar | Ej LP | Tentamensdatum |
---|---|---|---|---|---|---|---|
0119 Laboration 3 hp Betygsskala: UG | 3 hp | ||||||
0219 Tentamen 4,5 hp Betygsskala: TH | 4,5 hp |
|
I program
- TKDAT - DATATEKNIK, CIVILINGENJÖR, Årskurs 2 (obligatorisk)
- TKTEM - TEKNISK MATEMATIK, CIVILINGENJÖR, Årskurs 3 (obligatorisk)
Examinator
- Peter Ljunglöf
- Universitetslektor, Computing Science, Data- och informationsteknik
Ersätter
- DAT035 Datastrukturer
- DAT036 Datastrukturer
- DAT037 Datastrukturer
Behörighet
För kurser på grundnivå inom Chalmers utbildningsprogram gäller samma behörighetskrav som till de(t) program där kursen ingår i programplanen.Kursspecifika förkunskaper
Programmering i ett objektorienterat programmeringsspråk, inklusive rekursiva funktioner och metoder. Grundläggande matematiska begrepp, såsom mängder, funktioner, relationer, grafer, logaritmer och induktionsbevis.
Syfte
Datastrukturer och algoritmer utgör fundamentala byggstenar i nästan alla programvaror. Kunskap om dataabstraktion, datastrukturer och algoritmer är nödvändig vid konstruktion, användning och underhåll av förändringsbara, återanvändbara och effektiva programkomponenter.
Kursen ger kunskaper och färdigheter i konstruktion och användning av algoritmer och datastrukturer, samt en introduktion till algoritmanalys och dataabstraktion.
Lärandemål (efter fullgjord kurs ska studenten kunna)
Kunskap och förståelse
- redogöra för några grundläggande abstrakta datatyper och datastrukturer, bland annat listor, köer, hashtabeller, träd och grafer
- redogöra för några av de algoritmer som används för att effektivt hantera dessa datastrukturer, och förklara varför de är korrekta
Färdigheter och förmåga
- tillämpa grundläggande abstrakta datatyper och datastrukturer, samt algoritmer relaterade till dessa
- implementera och använda abstrakta datatyper som gränssnitt och datastrukturer som klasser, i ett objektorienterat programmeringsspråk
- använda ett standardbibliotek för datastrukturer och algoritmer
Värderingsförmåga och förhållningssätt
- analysera effektivitet hos vissa algoritmer, till exempel söknings- och sorteringsalgoritmer
- göra välgrundade val mellan olika datastrukturer och algoritmer för olika tillämpningar
Innehåll
- abstrakta datatyper
- asymptotisk effektivitet och enkel komplexitetsanalys av imperativ kod
- vanliga datastrukturer såsom fält, listor, träd och hashtabeller
- hur dessa kan användas för att implementera abstrakta datatyper såsom stackar, köer, prioritetsköer, avbildningar, mängder och grafer
- standardalgoritmer för dessa datastrukturer, inklusive deras resurskrav
- söknings- och sorteringsalgoritmer
- standardbibliotek för datastrukturer och algoritmer
- vanliga algoritmdesigntekniker, såsom brute force, divide and conquer ("dela upp och erövra"), och randomisering
Organisation
Undervisningen består av föreläsningar, övningar och laborationer med handledning.
Litteratur
Se kursens hemsida.
Examination inklusive obligatoriska moment
Kursen examineras genom en individuell skriftlig salstentamen (4,5 hp) samt laborationer (3,0 hp). Laborationerna genomförs normalt i par.
Kursplanen innehåller ändringar
- Ändring gjord på tentamen:
- 2020-03-31: Tentamensdatum Tentamensdatum ändrat från 2020-04-06 Eftermiddag till 2020-04-30 Förmiddag av Beslut Grulg
[2020-04-06 4,5 hp, 0219] - 2020-01-13: Plats Plats ändrat från Johanneberg till SB Multisal av grunnet
[2020-01-14 4,5 hp, 0219]
- 2020-03-31: Tentamensdatum Tentamensdatum ändrat från 2020-04-06 Eftermiddag till 2020-04-30 Förmiddag av Beslut Grulg
- Ändring gjord på kurstillfälle:
- 2019-05-03: Max antal deltagare Max antal deltagare 165 tillagt av UOL
[Kurstillfälle 1]
- 2019-05-03: Max antal deltagare Max antal deltagare 165 tillagt av UOL