Algoritmer, datastrukturer och komplexitet
Algorithms, Data Structures and Complexity

EDAF05, 5.0 högskolepoäng, G2 (Grundnivå, fördjupad)

Gäller för: 2024/25
Fakultet: Lunds tekniska högskola
Beslutad av: Programledning C/D
Beslutsdatum: 2024-04-16
Ikraftträdande: 2024-05-08

Allmänna uppgifter

Huvudområde: Teknik Fördjupning: Grundnivå, kurs/er som inte kan klassificeras
Obligatorisk för: D2, Pi3
Valfri för: C4-pvt, E4, F4, F4-pv, I4, L4-gi
Undervisningsspråk: Kursen ges på svenska

Syfte

Algoritmer och datastrukturer spelar en fundamental roll inom datavetenskap. Datastrukturer används för att modellera verkligheten och valet av representation påverkar algoritmers effektivitet. Ett syfte med kursen är att ge kunskap om ett antal avancerade datastrukturer för några av de abstrakta modeller som ingått i tidigare kurser samt om datastrukturer för ytterligare modeller såsom grafer. Ett annat syfte är att ge utökade kunskaper om algoritmer, framför allt grafalgoritmer. Vidare skall kursen ge goda kunskaper i hur man analyserar en algoritm med avseende på effektivitet.

Mål

Kunskap och förståelse
För godkänd kurs skall studenten

• kunna beskriva datastrukturer för grafer och deras tillämpningar
• kunna redogöra för olika problemlösningsstrategier såsom t ex söndra-och-härska och giriga algoritmer
• behärska ett antal tekniker för beräkning av algoritmers tidskomplexitet (effektivitet)
• vara orienterad om begreppen undre gränser, komplexitetsklasser och oavgörbara problem

Färdighet och förmåga
För godkänd kurs skall studenten

• utifrån problembeskrivningar kunna identifiera algoritmer och datastrukturer som är lämpliga att använda i en lösning
• kunna implementera de datastrukturer som ingår i kursen i ett objektorienterat språk
• kunna tillämpa problemlösningsstrategier på nya problem
• kunna tillämpa tekniker för beräkning av algoritmers tidskomplexitet och kunna använda sig av notationer för asymptotisk tillväxt av funktioner för att beskriva algoritmers komplexitet

Värderingsförmåga och förhållningssätt
För godkänd kurs skall studenten

• ha utvecklat ett kritiskt förhållningssätt till hur val av lösningsmetod och representation påverkar programs användbarhet och effektivitet
• inse att det finns problem för vilka alla kända algoritmer är orealistiskt tidskrävande

Kursinnehåll

Grafer och grafalgoritmer. Datastrukturer för representation av grafer. Strategier för problemlösning såsom söndra-och-härska, giriga algoritmer och brute force. Tekniker för att analysera algoritmers tidskomplexitet. Orientering om komplexitetsklasserna P och NP. Orientering om beräkningsbarhet och Church-Turings tes.

Kursens examination

Betygsskala: TH - (U, 3, 4, 5) - (Underkänd, Tre, Fyra, Fem)
Prestationsbedömning: För godkänt betyg krävs godkända obligatoriska moment och godkänd muntlig tentamen. Slutbetyg i kursen grundar sig på resultatet av den muntliga tentamen.

Om så krävs för att en student med varaktig funktionsnedsättning ska ges ett likvärdigt examinationsalternativ jämfört med en student utan funktionsnedsättning, så kan examinator efter samråd med universitetets avdelning för pedagogiskt stöd fatta beslut om alternativ examinationsform för berörd student.

Moduler
Kod: 0122. Benämning: Tentamen.
Antal högskolepoäng: 3.0. Betygsskala: TH - (U, 3, 4, 5). Prestationsbedömning: Godkänd tentamen Modulen omfattar: Muntlig tentamen
Kod: 0222. Benämning: Obligatoriska moment.
Antal högskolepoäng: 2.0. Betygsskala: UG - (U, G). Prestationsbedömning: Godkända obligatoriska moment Modulen omfattar: Laborationer och inlämningsuppgift.

Antagningsuppgifter

Förkunskapskrav:

• Godkänd på de obligatoriska momenten eller tentamen i EDAA01.
• EDA011 Programmeringsteknik eller EDA016 Programmeringsteknik eller EDA017 Programmeringsteknik eller EDA501 Programmering eller EDAA01 Programmeringsteknik - fördjupningskurs eller EDAA20 Programmering och databaser eller EDAA45 Programmering, grundkurs eller EDAA50 Programmeringsteknik eller EDAA55 Programmeringsteknik eller EDAA65 Programmering

Kurslitteratur

• Jonas Skeppstedt: Algorithms: a concise introduction. Amazon, 2020, ISBN: 9781723831362.

Kontaktinfo

Examinator: Jonas Skeppstedt, jonas.skeppstedt@cs.lth.se
Hemsida: https://cs.lth.se/edaf05