Kursplan för Informationssystem B: Algoritmer och datastrukturer

Information Systems B: Algorithms and Data Structures

Kursplan

  • 7,5 högskolepoäng
  • Kurskod: 2IS012
  • Utbildningsnivå: Grundnivå
  • Huvudområde(n) och successiv fördjupning: Informationssystem G1F

    Förklaring av koder

    Koden visar kursens utbildningsnivå och fördjupning i förhållande till andra kurser inom huvudområdet och examensfordringarna för generella examina:

    Grundnivå

    • G1N: har endast gymnasiala förkunskapskrav
    • G1F: har mindre än 60 hp kurs/er på grundnivå som förkunskapskrav
    • G1E: innehåller särskilt utformat examensarbete för högskoleexamen
    • G2F: har minst 60 hp kurs/er på grundnivå som förkunskapskrav
    • G2E: har minst 60 hp kurs/er på grundnivå som förkunskapskrav, innehåller examensarbete för kandidatexamen
    • GXX: kursens fördjupning kan inte klassificeras

    Avancerad nivå

    • A1N: har endast kurs/er på grundnivå som förkunskapskrav
    • A1F: har kurs/er på avancerad nivå som förkunskapskrav
    • A1E: innehåller examensarbete för magisterexamen
    • A2E: innehåller examensarbete för masterexamen
    • AXX: kursens fördjupning kan inte klassificeras

  • Betygsskala: Underkänd (U), godkänd (G), väl godkänd (VG)
  • Inrättad: 2010-10-14
  • Inrättad av: Institutionsstyrelsen
  • Reviderad: 2019-01-24
  • Reviderad av: Institutionsstyrelsen
  • Gäller från: VT 2019
  • Behörighet: 15 hp informationssystem eller motsvarande
  • Ansvarig institution: Institutionen för informatik och media

Mål

Vad gäller kunskap och förståelse förväntas studenten efter genomgången kurs kunna:
- förklara kopplingen mellan val av datastrukturer och effektiv problemlösning,
- beskriva grundläggande datastrukturer och algoritmer,
- förklara kopplingen mellan datastrukturer, algebraiska datatyper och abstrakta datastrukturer,
- beskriva några av de olika teknikerna som används inom algoritmdesign och utveckling.

Vad det gäller färdigheter och förmåga förväntas studenten efter genomgången kurs kunna:
- skapa domänspecifika datastrukturer genom användning av algebraiska datatyper,
- dölja detaljer i datastrukturer bakom interfaces,
- använda grundläggande datastrukturer och kunna implementera standardalgoritmer som använder olika tekniker för algoritmkonstruktion såsom rekursiv nedstigning, divide & conquer eller beskärning,
- tillämpa eller anpassa en ny eller tidigare osedd algoritm för att lösa ett givet problem.

Vad det gäller värderingsförmåga och förhållningssätt förväntas studenten efter genomgången kurs kunna:
- jämföra och utvärdera algoritmer med avseende på korrekt funktion och effektivitet.

Innehåll

Kursens fokus ligger på algoritmisk problemlösning, dvs. hur generella lösningar till problem kan framgångsrikt tillämpas på exempelvis sök- och sorteringsrelaterade problem inom programmering. Kursen inleder genom att behandla datarepresentation i form av datastrukturer. Grundläggande begrepp såsom sammansatta datatyper (composite datatypes) som skapas genom att kombinera enklare datatyper, såsom heltal, bokstäver och strängar, samt grundläggande datastrukturer, såsom enkla listor och träd, introduceras och definieras. Vidare diskuteras felhantering med avsikt att nå robusthet. Efter detta behandlas olika grundläggande algoritmer för sökning och sortering inom dessa datastrukturer. Vidare behandlas grundläggande tekniker för algoritmkonstruktion, inklusive rekursiv nedstigning, divide and conquer, dynamisk programmering, "greedy" algoritmer, beskärning och min-max algoritmer. Slutligen introduceras metoder för att bedöma korrektheten, fullständigheten och komplexiteten hos olika algoritmer. Vid utgången av kursen har studenten fått en förståelse för hur datarepresentation och algoritmer används för att söka ut och sortera data och kan tillämpa detta i praktiken.

Undervisning

Föreläsningar, lektioner och laborationer

Examination

Kursen examineras genom inlämningsuppgifter och tentamen.

Om särskilda skäl finns får examinator göra undantag från det angivna examinationssättet och medge att en student examineras på annat sätt. Särskilda skäl kan t.ex. vara besked om särskilt pedagogiskt stöd från universitetets samordnare eller beslut om undantag som fattats av institutionens arbetsgrupp för studieärenden.

Litteratur

Litteraturlista

Gäller från: VT 2019

I bibliotekets söktjänst kan du se om en titel finns elektroniskt.

Kurslitteratur meddelas vid kursstart.