Kursplan för Programkonstruktion och datastrukturer

Program Design and Data Structures

Det finns en senare version av kursplanen.

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: 2012-04-25
  • Reviderad av: Teknisk-naturvetenskapliga fakultetsnämnden
  • Gäller från: vecka 27, 2012
  • Behörighet: Introduktion till Informationsteknologi, Baskurs i matematik.
  • Ansvarig institution: Institutionen för informationsteknologi

Mål

För godkänt betyg ska studenten kunna

  • analysera enklare problem och designa lösningar med hjälp av algoritmer och programmering;
  • 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, t.ex. Standard ML;
  • koda och dokumentera program för enklare problem;
  • utforma specifikationer för önskat beteende hos ett program med hjälp av för- och eftervillkor;
  • motivera att körningen av ett program (en algoritm) med upprepning faktiskt avslutas;
  • välja och konstruera lämpliga datastrukturer för en algoritm;
  • 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, testning och felsökning av enklare program;
  • använda 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. Enkla grafalgoritmer.
  • Matematiska grunder för algoritmanalys: asymptotisk notation, summationer, rekursionsformler.
  • Datastrukturer: enkla datatyper, poster, fält, listor, träd, stackar, köer, träd, prioritetsköer, "heaps".
  • Dataabstraktion.
  • Grundläggande funktionell programmering i Standard ML eller annat funktionellt språk: 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 skriftlig tentamen (10 hp) samt muntligt och/eller skriftlig redovisning av uppgifter (10 hp).

Ö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 27, 2012

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

Referenslitteratur

M.R. Hansen and H. Rischel: Introduction to Programming using SML. Addison-Wesley, 1999. J.D. Ullman: Elements of ML Programming. Prentice-Hall, 1998. B.W. Kernighan and R. Pike: The Practice of Programming. Addison-Wesley, 1999. T.H. Cormen, C.E. Leiserson, R.L. Rivest, and Clifford Stein: Introduction to Algorithms, third edition, MIT Press, 2009. A. Levitin: Introduction to the Design & Analysis of Algorithms, second edition. Addison-Wesley, 2007. C. Okasaki: Purely Functional Data Structures. Cambridge University Press, 1998.