Datastrukturer och algoritmer, 6 hp

Data Structures and Algorithms, 6 credits

TDDC91

Huvudområde

Informationsteknologi

Utbildningsnivå

Grundnivå

Kurstyp

Programkurs

Examinator

Erik Nilsson

Studierektor eller motsvarande

Ola Leifler

Undervisningstid

Preliminär schemalagd tid: 52 h
Rekommenderad självstudietid: 108 h
VOF = Valbar / Obligatorisk / Frivillig
Kursen ges för Termin Period Block Språk Ort VOF
6CITE Civilingenjör i informationsteknologi 3 (HT 2018) 1 3 Svenska Linköping O

Huvudområde

Informationsteknologi

Utbildningsnivå

Grundnivå

Fördjupningsnivå

G1X

Kursen ges för

  • Civilingenjör i informationsteknologi

Särskild information

Kursen går sista gången 2018 och ersätts därefter av TDDE22.

Förkunskapskrav

OBS! Tillträdeskrav för icke programstudenter omfattar vanligen också tillträdeskrav för programmet och ev. tröskelkrav för progression inom programmet, eller motsvarande.

Rekommenderade förkunskaper

Diskret matematik. Analys i en variabel. Grundläggande programmering och programspråket Java.

Lärandemål

Kursens syfte är att ge studenten verktyg att självständigt kunna konstruera datorprogram som effektivt utnyttjar tid och minne.
Efter genomgången kurs skall den studerande:

  • ha god förmåga att analysera tids- och rumskomplexitet hos iterativa och enkla rekursiva algoritmer.
  • kunna redogöra för och använda de vanligaste abstrakta datatyperna och sorteringsalgoritmerna.
  • kunna implementera de vanligaste abstrakta datatyperna med olika datastrukturer och algoritmer.
  • kunna beskriva etablerade metoder för design (och analys) av algoritmer i allmänhet.

Kursinnehåll

  • Grundläggande begrepp
  • Matematiska grunder för algoritmanalys
  • Grundläggande abstrakta datatyper och datastrukturer såsom listor, stackar, köer, sökträd, hashtabeller och grafer.
  • Resursanalys av algoritmer
  • Sortering och urval
  • Paradigmer för design av algoritmer

Undervisnings- och arbetsformer

Föreläsningarna används till genomgång av teori. Lektionerna används till övningar. Laborationerna är huvudsakligen datorbaserade men innehåller även vissa "skrivbordsmoment".

Examination

UPG2Datorbaserade inlämningsuppgifter1 hpU, G
LAB1Laborationskurs2 hpU, G
UPG1Frivillig uppgift0 hpU, G
DAT1Datortentamen2 hpU, 3, 4, 5
BAS1Basgruppsarbete1 hpU, G
UPG1 består av en samling frivilliga progammeringsuppgifter som, om de löses, ger bonuspoäng till kursomgångens första tentamenstillfälle.

Betygsskala

Fyrgradig skala, LiU, U, 3, 4, 5

Kurslitteratur

 

 

Övrig information

Konstruktion och analys av algoritmer. Komplexitetsteori.
 

Om undervisningsspråk

Undervisningsspråk visas på respektive kurstillfälle på fliken "Översikt".

  • Observera att även om undervisningsspråk är svenska kan delar av kursen ges på engelska.
  • Om undervisningsspråk är Svenska/Engelska kan kursen i sin helhet ges på engelska vid behov.
  • Om undervisningsspråk är Engelska ges kursen i sin helhet på engelska. 

Övrigt

Kursen bedrivs på ett sådant sätt att både mäns och kvinnors erfarenhet och kunskaper synliggörs och utvecklas.

Planering och genomförande av kurs skall utgå från kursplanens formuleringar. Den kursvärdering som ingår i kursen skall därför genomföras med kursplanen som utgångspunkt. 

Institution

Institutionen för datavetenskap

Studierektor eller motsvarande

Ola Leifler

Examinator

Erik Nilsson

Kurshemsida och andra länkar

http://www.ida.liu.se/~TDDC91/

Undervisningstid

Preliminär schemalagd tid: 52 h
Rekommenderad självstudietid: 108 h
Kod Benämning Omfattning Betygsskala
UPG2 Datorbaserade inlämningsuppgifter 1 hp U, G
LAB1 Laborationskurs 2 hp U, G
UPG1 Frivillig uppgift 0 hp U, G
DAT1 Datortentamen 2 hp U, 3, 4, 5
BAS1 Basgruppsarbete 1 hp U, G
UPG1 består av en samling frivilliga progammeringsuppgifter som, om de löses, ger bonuspoäng till kursomgångens första tentamenstillfälle.
Det finns ingen kurslitteratur tillgänglig på studieinfo för den här kursen.
I = Introducera, U = Undervisa, A = Använda
I U A Moduler Kommentar
1. ÄMNESKUNSKAPER
1.1 Kunskaper i grundläggande (motsvarande G1X) matematiska och naturvetenskapliga ämnen
X
X
U: Analysera tids- och rumskomplexitet hos iterativa och enkla rekursiva algoritmer (TEN1) A: Diskret matematik, analys i en variabel
1.2 Kunskaper i grundläggande (motsvarande G1X) teknikvetenskapliga ämnen
X
X
X
LAB1
I: Etablerade metoder för design och analys av algoritmer i allmänhet U: Abstrakta datatyper och deras implementation med olika datastrukturer och algoritmer (TEN1, LAB1) U: Sorteringsalgoritmer (TEN1, LAB1) U: Etablerade metoder för design och analys av algoritmer i allmänhet (TEN1) A: Grundläggande programmering och programspråket Java (LAB1)
1.3 Fördjupade kunskaper (motsvarande G2X), metoder och verktyg inom något/några teknik- och naturvetenskapliga ämnen

                            
1.4 Väsentligt fördjupade kunskaper (motsvarande A1X), metoder och verktyg inom något/några teknik- och naturvetenskapliga ämnen

                            
1.5 Insikt i aktuellt forsknings- och utvecklingsarbete

                            
2. INDIVIDUELLA OCH YRKESMÄSSIGA FÄRDIGHETER OCH FÖRHÅLLNINGSSÄTT
2.1 Analytiskt tänkande och problemlösning
X
X
BAS1
LAB1
U: Abstrakta datatyper och deras implementation med olika datastrukturer och algoritmer (TEN1, LAB1) A: Problemlösning i basgrupp (BAS1)
2.2 Experimenterande och undersökande arbetssätt samt kunskapsbildning
X
LAB1
A: Grundläggande programmering (LAB1)
2.3 Systemtänkande

                            
2.4 Förhållningssätt, tänkande och lärande
X
X
BAS1
LAB1
U: Datorövningar (LAB1) A: Självstyrt lärande i basgrupp, utvärdering av arbete i basgrupp (BAS1)
2.5 Etik, likabehandling och ansvarstagande

                            
3. FÖRMÅGA ATT ARBETA I GRUPP OCH ATT KOMMUNICERA
3.1 Arbete i grupp
X
X
BAS1
LAB1
A: Datorövningar görs i par (LAB1), basgruppsarbete (BAS1)
3.2 Kommunikation

                            
3.3 Kommunikation på främmande språk
X
kurslitteratur på engelska
4. PLANERING, UTVECKLING, REALISERING OCH DRIFT AV TEKNISKA PRODUKTER OCH SYSTEM MED HÄNSYN TILL AFFÄRSMÄSSIGA OCH SAMHÄLLELIGA BEHOV OCH KRAV
4.1 Samhälleliga villkor, inklusive ekonomiskt, socialt och ekologiskt hållbar utveckling

                            
4.2 Företags- och affärsmässiga villkor

                            
4.3 Att identifiera behov samt strukturera och planera utveckling av produkter och system

                            
4.4 Att konstruera produkter och system

                            
4.5 Att realisera produkter och system

                            
4.6 Att ta i drift och använda produkter och system

                            
5. PLANERING, GENOMFÖRANDE OCH PRESENTATION AV FORSKNINGS- ELLER UTVECKLINGSPROJEKT MED HÄNSYN TILL VETENSKAPLIGA OCH SAMHÄLLELIGA BEHOV OCH KRAV
5.1 Samhälleliga villkor, inklusive ekonomiskt, socialt och ekologiskt hållbar utveckling för kunskapsutveckling

                            
5.2 Ekonomiska villkor för kunskapsutveckling

                            
5.3 Att identifiera behov samt strukturera och planera forsknings- eller utvecklingsprojekt

                            
5.4 Att genomföra forsknings- eller utvecklingsprojekt

                            
5.5 Att redovisa och utvärdera forsknings- eller utvecklingsprojekt

                            

Denna flik innehåller det material som är publikt i Lisam. Den information som publiceras här är inte juridiskt bindande, sådant material hittar du under övriga flikar på denna sida.

Det finns inga filer att visa.