Engelskt namn: Algorithmic Problem Solving
Denna kursplan gäller: 2012-01-02 till 2012-01-08 (nyare version av kursplanen finns)
Kursplan för kurser med start efter 2012-01-09
Kursplan för kurser med start innan 2012-01-08
Kurskod: 5DV130
Högskolepoäng: 7,5
Utbildningsnivå: Avancerad nivå
Betygsskala: TH teknisk betygsskala
Ansvarig institution: Institutionen för datavetenskap
Beslutad av: teknisk-naturvetenskapliga fakultetsnämnden, 2012-01-09
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.
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.
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).
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.
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.
Lämplig kurslitteratur bestäms utifrån de teman och frågeställningar som studenterna väljer att arbeta med. Några exempel på litteratur som kan bli relevant är: Suitable course litterature is decied from the themes and research question the individual student has chosen to work with. Some exampels of litterature that might be relevant are:
Sipser Michael
Introduction to the theory of computation
2. ed. : Boston, Mass. : Thomson Course Technology : 2006 : 437 s. :
ISBN: 0-619-21764-2 (int. ed.)
Obligatorisk
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
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. 3rd edition, MIT Press, 2009. ISBN-13: 978-0262533058
Lämplig kurslitteratur bestäms utifrån de teman och frågeställningar som studenterna väljer att arbeta med. Några exempel på litteratur som kan bli relevant är: Suitable course litterature is decied from the themes and research question the individual student has chosen to work with. Some exampels of litterature that might be relevant are:
Algorithms
Johnsonbaugh Richard, Schaefer Marcus
International ed. : Upper Saddle River, N.J. : Pearson Education : cop. 2004 : xiii, 752 s. :
ISBN: 0-02-360692-4
Obligatorisk
Se Umeå UB:s söktjänst
Sipser Michael
Introduction to the theory of computation
2. ed. : Boston, Mass. : Thomson Course Technology : 2006 : 437 s. :
ISBN: 0-619-21764-2 (int. ed.)
Obligatorisk
Se Umeå UB:s söktjänst
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. 3rd edition, MIT Press, 2009. ISBN-13: 978-0262533058
Lämplig kurslitteratur beror på vilken frågeställning som studenten valt att arbeta med och bestäms därför individuellt vid kursstart.
Inst för datavetenskap :
Läsanvisning: The suitable course literature is highly dependent on the research question chosen by the student. Therefore, the exact course literature is decided individually when the course begins.