Kursplan för Programkonstruktion och datastrukturer

Program Design and Data Structures

Kursplan

  • 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-08-30
  • Reviderad av: Teknisk-naturvetenskapliga fakultetsnämnden
  • Gäller från: vecka 30, 2019
  • 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.

Om särskilda skäl finns får examinator göra undantag från det angivna examinationssättet och medge att en enskild 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 för studenter med funktionsnedsättning.

Ö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

Litteraturlista

Gäller från: vecka 30, 2019

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

Rekommenderad litteratur

Referenslitteratur