Kursplan för Programkonstruktion och datastrukturer

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.

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).