Behörighetskrav

Krav på grundläggande kurs i programmering om minst 7.5 hp.

Fördjupningsnivå i förhållande till examensfordringarna

Kursen ingår i huvudområdet datavetenskap på nivå 1-30 hp och kan ingå i examensfordringarna för kandidatexamen i datavetenskap.

Innehåll

Kursen innefattar följande:

• algoritmanalys och algoritmkonstruktion: rimlighetsbedömningar, giriga algoritmer, söndra-och-härska-algoritmer, amorterad analys, heuristiska metoder
• algoritmer: sorteringsalgoritmer, amorterad analys och elementär beräkningsgeometri
• grundläggande och avancerade datastrukturer såsom binära sökträd, hashtabeller, prioritetsköer och grafer
• datastrukturer och algoritmer med särskild relevans för spelprogrammering, såsom BSP (binary space partitioning) och quad-träd

Lärandemål

**Kunskap och förståelse
**Efter avslutad kurs ska studenten kunna:

• visa en grund för algoritmiskt tankesätt och förståelse för att använda informell och formell logik vid utformandet av algoritmer
• redogöra för grundläggande begrepp relaterade till datastrukturer och algoritmer
• redogöra för abstrakta datatyper såsom stack, lista, kö, träd, mängd och graf
• redogöra för grundläggande algoritmer och dess komplexitet samt egenskaper
• visa förståelse för grundläggande geometriska problemställningar och algoritmer för lösandet av sådana problemställningar

**Färdighet och förmåga
**Efter avslutad kurs ska studenten kunna:

• implementera grundläggande datastrukturer för att hantera stora mängder data
• implementera tillämpade datastrukturer för att hantera data och informationsmängder för hantering i spelprogramvara
• implementera algoritmer för effektiv manipulation av tillämpade datastrukturer för spelprogramvara
• välja lämpliga kontrollstrukturer, objektsamlingar och klasser vid konstruktion av mindre spelprogramvara
• analysera enklare algoritmer praktiskt och teoretiskt med avseende på tidskomplexitet
• använda sig av grundläggande problemlösningsstrategier på problem

Arbetsformer

I kursen ges undervisning genom föreläsningar, laborationer, seminarier och handledning.

Bedömningsformer

Krav för godkänd:

Godkänd skriftlig tentamen (4,5 hp, UV) och godkända inlämningsuppgifter (3 hp, UG).

Krav för väl godkänd:

Väl godkänd skriftlig tentamen och godkända inlämningsuppgifter.

Kurslitteratur

• Sedgewick, Robert & Wayne, Kevin Daniel (2011). Algorithms. 4. ed. Upper Saddle River, NJ: Addison-Wesley.

Referenslitteratur:

• Cormen, Thomas H. (2009). Introduction to algorithms. 3. ed. Cambridge, Mass.: MIT Press.
• Sánchez-Crespo Dalmau, Daniel (2003). Core techniques and algorithms in game programming. Indianapolis, Ind.: New Riders.

Kursvärdering

Högskolan ger studenter som deltar i eller har avslutat en kurs en möjlighet att framföra sina erfarenheter av och synpunkter på kursen genom en kursvärdering som anordnas av högskolan. Högskolan sammanställer kursvärderingarna samt informerar om resultaten och eventuella beslut om åtgärder som föranleds av kursvärderingarna. Resultaten ska hållas tillgängliga för studenterna. (HF 1:14).

Övergångsbestämmelser

Om en kurs upphört att ges eller genomgått större förändringar ska studenterna, under ett år efter det att förändringen skett, erbjudas två tillfällen för omprov baserade på den kursplan som gällde vid registreringen.

Övrigt

Om en student har beslut om riktat pedagogiskt stöd, har examinator rätt att ge ett anpassat prov eller låta studenten genomföra prov på ett alternativt sätt.