Kursplan för Programkonstruktion och datastrukturer

Program Design and Data Structures

Det finns en senare version av kursplanen.

  • 20 högskolepoäng
  • Kurskod: 1DL201
  • Utbildningsnivå: Grundnivå
  • Huvudområde(n) och successiv fördjupning: Datavetenskap G1F, Teknik 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 (3), icke utan beröm godkänd (4), med beröm godkänd (5)
  • Inrättad: 2010-03-18
  • Inrättad av: Teknisk-naturvetenskapliga fakultetsnämnden
  • Reviderad: 2018-04-19
  • Reviderad av: Teknisk-naturvetenskapliga fakultetsnämnden
  • Gäller från: vecka 27, 2018
  • Behörighet: Introduktion till Informationsteknologi, Baskurs i matematik.
  • Ansvarig institution: Institutionen för informationsteknologi

Mål

Efter godkänd kurs ska studenten kunna

  • analysera enklare problem, designa lösningar med hjälp av algoritmer och programmering samt förklara dessa lösningar;
  • beskriva algoritmbegreppet och konstruera algoritmer med sekvensering, alternativ och upprepning (iteration/rekursion);
  • redogöra för grundläggande syntax och semantik för ett funktionellt programspråk
  • koda och dokumentera program för enklare problem;
  • förklara, använda och göra ändringar i kod som konstruerats av andra.
  • beskriva -- oberoende av programkoden -- den uppgift ett program skall lösa och de förutsättningar som krävs för att det skall kunna arbeta
  • motivera att körningen av ett program (en algoritm) med upprepning faktiskt avslutas;
  • välja lämpliga algoritmer och datastrukturer för lagring av data, sökning och sortering, samt implementera dessa.
  • använda och implementera grundläggande grafalgoritmer.
  • analysera körtiden för enklare algoritmer/program i relation till indatats storlek, i bästa, sämsta och genomsnittliga fall;
  • utvärdera algoritmer med avseende på komplexitet, välja lämplig algoritm bland olika alternativ;
  • genomföra kodgranskning samt systematiskt söka efter, tolka och förklara fel i enklare program;
  • förklara grundläggande programspråksbegrepp som uttryck, värde, typ, funktion, bindning, rekursion, pekare, sidoeffekt, variabel, tilldelning m.fl.
  • presentera och diskutera kursens innehåll muntligt och skriftligt med för utbildningsnivån lämplig färdighet.

Innehåll

Introduktion till programmering: syftet med programmering, programmeringsprocessens faser, programmering satt i sitt sammanhang genom exempel på tillämpningar, kort historik över programmering, datorsystemet ur programmerarens synvinkel, programmeringsmiljöer.
Algoritmer: vad en algoritm är, programmet som realisering av en algoritm, skillnaden i preciseringsgrad mellan datorprogram och vardagslivets algoritmer.
Algoritmer för sökning (binära sökträd, balanserade sökträd, hashtabeller) och sortering (insättningssortering, merge sort, quick sort, heap sort). Enkla grafalgoritmer (djup-först och bredd-först sökning, topologisk sortering, komponenter).
Matematiska grunder för algoritmanalys: asymptotisk notation, summationer, rekursionsformler.
Designmetoder: dela och härska.
Datastrukturer: enkla datatyper, poster, fält, listor, träd, stackar, köer, prioritetsköer, "heaps".
Dataabstraktion.
Grundläggande funktionell programmering: funktionsanrop, värden och typer, funktionsabstraktion, definitionsabstraktion.
Grundläggande programstrukturer: sekvensering, alternativ, upprepning.
Sidoeffekter: tilldelning, grundläggande in/utmatning.
Grundläggande programmeringsteknik: systematisk arbetsgång för kravspecifikation, problemanalys, programdesign, kodning, kodgranskning, testning, felsökning samt dokumentation.

Undervisning

Föreläsningar, lektioner, laborationer och inlämningsuppgifter.

Examination

Kursen examineras med skriftliga tentamina samt muntlig och skriftlig redovisning av uppgifter/projekt: 10 hp teori och 10 hp praktik.

Övriga föreskrifter

Kursen kan inte räknas in i examen med kursen Programkonstruktion (1IT020, 1DL200), Programkonstruktion I (1IT021), Programkonstruktion II (1IT022), Programmeringsmetodik DV1 (2AD524), Algoritmer och datastrukturer I (1DL210) eller Datastrukturer MN1 (1DL009, 1TD191, 1MB026).

Litteratur

Uppgift om kurslitteratur saknas. Ta kontakt med ansvarig institution för mer information.