Algoritmisk problemlösning, 7,5 hp

Innehåll

Kursen behandlar problemlösning med algoritmiska metoder. Den belyser hela arbetsprocessen, som består i

- formaliseringen av ett konkret beräkningsproblem utifrån en given frågeställning,
- strukturerad analys av problemet,
- val av lösningsmetod baserat på en verktygslåda av algoritmiska tekniker och avancerade datastrukturer,
- implementation av lösningen i ett lämpligt programspråk, och
- utvärdering av resultatet.

Typiska algoritmiska metoder som kan tas upp under kursen är dynamisk programmering, giriga algoritmer, linjärprogrammering, parallellisering, randomisering och approximation. Typiska datastrukturer som behandlas är fibonacci-heapar, B-träd, binära beslutsdiagram och hash-tabeller.

Förväntade studieresultat

Efter avslutad kurs ska studenten kunna

- ta fram en lämplig formalisering av ett informellt beskrivet beräkningsproblem;
- redogöra för viktiga algoritmiska metoder och avancerade datastrukturer samt analysera dem med avseende på tids- och platskomplexitet;
- systematiskt analysera ett formellt definierat beräkningsproblem och utifrån analysens resultat välja lämpliga algoritmiska tekniker och datastrukturer för att lösa det;
- muntligt och skriftligt kunna presentera ett problem och dess formalisering samt lösning.

Behörighetskrav

Univ: För tillträde till kursen krävs 60 hp inom huvudområdet datavetenskap eller matematik eller minst 2 års avklarade studier i båda fallen inkluderande kurserna Datastrukturer och algoritmer (5DV108, 5DV127 eller 5DV128) och Datavetenskapens grunder (5DV037) eller motsvarande kunskaper. Engelska A och svenska för grundläggande behörighet för högskolestudier (om kursen ges på svenska).

Undervisningens upplägg

Undervisningstillfällen anordnas kontinuerligt under kursen med minst 15 tillfällen/termin (normalt en gång i veckan). I normalfallet ges kursen som en flexkurs under hela läsåret. Tanken är att studenten om den så önskar ska ha möjlighet att avsluta den inom en termin.).

Undervisningen sker genom
- föreläsningar om algoritmiska tekniker och avancerade datastrukturer samt deras analys med avseende på tids- och platskomplexitet;
- seminarier, där kursdeltagarna diskuterar problem, möjliga formaliseringar och lösningar;
- studentpresentationer där resultat av studenters individuella arbete i samband med något problem redovisas.

Ett undervisningstillfälle kan innehålla flera av de ovan nämnda momenten.

Eftersom kursen är avsedd att stärka intresset för ämnesområdet och uppmuntra till fortsatt lärande tas stor hänsyn till deltagarnas egen nyfikenhet och upptäckarglädje i valet av seminarieämnen. Studenterna skall också visa sin individuella förmåga genom att på egen hand lösa beräkningsproblem och implementera sina lösningar.

Examination

För att bli godkänd på kursen skall studenten aktivt ha deltagit i minst 12 undervisningstillfällen (FSR 1-2). Vidare ska studenten ha genomfört minst två muntliga presentationer (FSR 2,4) vid två av de givna examinationstillfällena (se nedan). I samband med minst en av dessa presentationer ska en skriftlig rapport lämnas in (FSR 3,4).

Under året schemaläggs ett antal examinationstilfällen (minst sex). Studenten väljer själv när denne vill göra sin examination och ansvarar själv för att se till att denne deltar i examinationens alla delar minst en gång under kurstiden (normalt ett läsår). Om studenten vid kursens slut fortfarande inte har fått godkänt på kursen ges betyget U.

På kursen ges betyget Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). Betyget utgör en sammanfattande bedömning av resultatet vid examinationens olika delar och sätts först när alla obligatoriska moment är godkända. Den som godkänts i ett prov får ej undergå förnyat prov för högre betyg.

För studerande som inte godkänns vid ordinarie provtillfälle anordnas ytterligare provtillfälle. Hur detta provtillfälle utformas avgörs av kursansvarig i samråd med berörda studenter.

En student som utan godkänt resultat har genomgått två prov för en kurs eller en del av en kurs, har rätt att få en annan examinator utsedd, om inte särskilda skäl talar emot det (6 kap. 22 §, HF). Begäran om ny examinator ställs till prefekten vid Institutionen för datavetenskap.

TILLGODORÄKNANDE

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.

Tillgodoräknande av studier prövas individuellt (se universitetets regelsamling och tillgodoräknandeordning). Ansökan om tillgodoräknande görs på speciell blankett och ställs till den Teknisk-naturvetenskapliga fakultetsnämnden, Umeå universitet.