Behörighetskrav

Introduktion till Informationsteknologi, Baskurs i matematik.

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