Engelskt namn: Efficient algorithms
Denna kursplan gäller: 2023-06-26 och tillsvidare
Kursplan för kurser med start efter 2023-06-26
Kursplan för kurser med start mellan 2022-06-27 och 2023-06-25
Kursplan för kurser med start mellan 2018-07-23 och 2022-06-26
Kurskod: 5DV182
Högskolepoäng: 7,5
Utbildningsnivå: Avancerad nivå
Huvudområden och successiv fördjupning:
Datavetenskap: Avancerad nivå, har endast kurs/er på grundnivå som förkunskapskrav
Betygsskala: TH teknisk betygsskala
Ansvarig institution: Institutionen för datavetenskap
Beslutad av: Teknisk-naturvetenskapliga fakultetsnämnden, 2017-08-04
Reviderad av: Teknisk-naturvetenskapliga fakultetsnämnden, 2023-03-07
Kursen behandlar tekniker för att konstruera effektiva algoritmer och typiska datastrukturer som används i dessa. Speciell hänsyn tas till att effektivitet inte bara beror på algoritmens inneboende asymptotiska beteende utan också på de specifika probleminstanser den appliceras på. Standardalgoritmer och -datastrukturer behöver därför ofta väljas ut och anpassas för att lösa problemet så effektivt som möjligt.
Modul 1, Algoritmiska tekniker och datastrukturer, 3 hp, behandlar effektiva algoritmiska tekniker (divide-and-conquer, greedy, dynamic programming) deras användningsområden och för- och nackdelar, illustrerar dessa med hjälp av centrala algoritmer, och diskuterar exempel på effektiva datatyper (t.ex. heaps, red-black trees, union-find) och deras implementation.
Modul 2, Problemlösning och algoritmanalys, 4,5 hp,
utgörs av att studenten både teoretiskt och empiriskt undersöker varianter av en känd algoritm med avseende på effektivitet och skriver en rapport om detta. Hela kedjan från initiala, vanligen otydligt specificerade frågeställningar till den färdiga algoritmiska lösningen och dess teoretisk och empirisk analys ingår. Modulen tränar studentens förmåga att gå från en otydlig formulerad problemspecifikation till en exakt formulering, ta fram en lämplig algoritmisk lösning, om möjligt förbättra den genom att anpassa den till problemets säregenheter, samt analysera och diskutera dess effektivitet.
Kunskap och förståelse
Efter avslutad kurs ska studenten kunna
Färdighet och förmåga
Efter avslutad kurs ska studenten kunna
Värderingsförmåga och förhållningssätt
Efter avslutad kurs ska studenten kunna
Minst 90 hp varav minst 60 hp datavetenskap eller minst 120 hp inom ett program. Minst 7,5 hp programmering; 7,5 hp datastrukturer och algoritmer; 7,5 hp diskret matematik; och 7,5 hp formella språk. Engelska för grundläggande behörighet för högskolestudier.
Undervisningen består av tre olika element: Lärarledda lektioner, handledningsmöten där problemställningar och av studenterna föreslagna lösningar eller identifierade problem diskuteras, samt feedback på rapportutkast som lämnas in vid i förväg definierade tillfällen. Utöver schemalagda aktiviteter krävs även individuellt arbete med materialet. Det är studentens ansvar att i tid sätta sig in i materialet och förbereda eventuella frågor för att kunna få lämplig feedback.
Modul 1 examineras genom ett muntligt prov. På modulen ges enbart betygen Underkänd (U) eller Godkänd (G).
Modul 2 examineras genom en skriftlig rapport. På modulen ges något av betygen Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5).
På kursen i sin helhet ges något av betygen Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). Betyget bestäms av betyget på Modul 2.
Anpassad examination
Examinator kan besluta om avsteg från kursplanens examinationsform. Individuell anpassning av examinationsformen ska övervägas utifrån studentens behov. Examinationsformen anpassas inom ramen för kursplanens förväntade studieresultat. Student som har behov av en anpassad examination ska senast 10 dagar innan examinationen begära anpassning hos Institutionen för datavetenskap. Examinator beslutar om anpassad examination som sedan meddelas studenten.
I en examen får denna kurs ej ingå, helt eller delvis, samtidigt med en annan kurs med likartat innehåll. Vid tveksamheter bör den studerande rådfråga studievägledare vid Institutionen för datavetenskap och/eller programansvarig för sitt program. Speciellt gäller att denna kurs inte kan, helt eller delvis, användas i en examen tillsammans med kursen 5DV170 Effektiva algoritmer.
Om kursplanen har upphört att gälla eller kursen slutat erbjudas garanteras en student som någon gång registrerats på kursen minst tre provtillfällen (inklusive ordinarie provtillfälle) enligt denna kursplan under en tid av maximalt två år från det att kursplanen upphört att gälla eller kursen slutat erbjudas.
Introduction to algorithms
Cormen Thomas H., Leiserson Charles E., Rivest Ronald L., Stein Clifford
Fourth edition : Cambridge, Mass. : MIT Press : [2022] : xx, 1291 pages :
ISBN: 9780262046305
Obligatorisk
Se Umeå UB:s söktjänst
Linz Peter
Introduction to formal languages and automata
Jones And Bartlett Publishers : 2016 : 450 sidor :
ISBN: 9781284077247
Se Umeå UB:s söktjänst
Cormen Thomas H.
Introduction to algorithms
3. ed. : Cambridge, Mass. : MIT Press : cop 2009 : xix, 1292 s. :
ISBN: 9780262033848 (inb.)
Obligatorisk
Se Umeå UB:s söktjänst
Linz Peter
Introduction to formal languages and automata
Jones And Bartlett Publishers : 2016 : 450 sidor :
ISBN: 9781284077247
Se Umeå UB:s söktjänst