Denna kurs handlar om att effektivt tillämpa algoritmisk problemlösning på verkliga problem. I sådana praktiska fall är problemet ofta informellt formulerat och de exakta behoven kan vara svåra att förutse. De problem som väljs för kursen är också sådana att en lösning typiskt består av mer än en standardiserad algoritm eller datastruktur. Praktiskt involverar detta att självständigt analysera ett givet informellt problem, formalisera det på en lämplig form (t.ex. i form av en graf), implementera en lösning, och designa lämpliga experiment för att undersöka om lösningen uppfyller de behov man förväntar sig. Detta görs genom föreläsningar om generella tekniker, ett stort antal mindre självständiga uppgifter, och några större uppgifter på vilka en djupare experimentell analys genomförs och dokumenteras. Implementationen revideras sedan utifrån resultaten av analysen.
Förväntade studieresultat
Kunskap och förståelse Efter avslutad kurs ska studenten kunna:
(FSR 1) Beskriva ett antal kategorier av algoritmer (exempelvis giriga algoritmer, söndra & härska-algoritmer, dynamisk programmering, sökmetoder med bakåtspårning, kombinatorisk sökning) samt förklara ett urval av specifika algoritmer ur vardera kategori.
Färdighet och förmåga Efter avslutad kurs ska studenten kunna:
(FSR 2) Konkretisera ett informellt formulerat problem på ett sätt som gör det möjligt att behandla problemet algoritmiskt.
(FSR 3) Planera en lämplig algoritmisk strategi för att lösa ett konkret problem.
(FSR 4) Designa, genomföra och dokumentera experiment som utvärderar en algoritmisk lösnings lämplighet i en informellt beskriven kontext.
(FSR 5) Implementera och testa en algoritmisk lösning för ett informellt formulerat problem, samt på ett systematiskt sätt uppdatera lösningen för förändrade behov.
Värderingsförmåga och förhållningssätt Efter avslutad kurs ska studenten kunna:
(FSR 6) Vetenskapligt resonera om och värdera mått på en algoritmisk lösnings beteenden, inklusive både experimentella resultat och de olika formerna av ordo-notation.
Behörighetskrav
Minst 7,5 hp grundläggande programmering; 15 hp datastrukturer och algoritmer med fördjupning (t.ex. DV1:Datavetenskapens byggstenar, 7,5 hp och DV2:Algoritmer och problemlösning, 7,5 hp); 7,5 hp diskret matematik.
Undervisningens upplägg
Undervisningen bedrivs i form av föreläsningar, obligatoriska övningsuppgifter, och diskussion av uppgifternas innehåll i grupp. Utöver schemalagda aktiviteter behövs omfattande individuellt arbete med materialet.
Examination
Examinationen sker dels genom en skriftlig salstentamen, dels genom ett antal skriftliga inlämningsuppgifter. På kursen ges något av betygen Väl Godkänd (VG), Godkänd (G) eller Underkänd (U). För att bli godkänd på hela kursen krävs att samtliga examinerande moment är godkända. Betyget utgör en sammanfattande bedömning av resultaten på de examinerande momenten.
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.
Övriga föreskrifter
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.
Litteratur
Giltig från:
2024 vecka 1
Skiena Steven S. The algorithm design manual Third edition : Cham : Springer : [2020] : 17, 793 sidor : ISBN: 9783030542580 Obligatorisk Se Umeå UB:s söktjänst
