Programkonstruktion och datastrukturer
Kursplan, Grundnivå, 1DL201
- Kod
- 1DL201
- Utbildningsnivå
- Grundnivå
- Huvudområde(n) med fördjupning
- Datavetenskap G1F, Teknik G1F
- Betygsskala
- Underkänd (U), godkänd (3), icke utan beröm godkänd (4), med beröm godkänd (5)
- Fastställd av
- Teknisk-naturvetenskapliga fakultetsnämnden, 24 april 2013
- Ansvarig institution
- Institutionen för informationsteknologi
Behörighetskrav
Introduktion till Informationsteknologi, Baskurs i matematik.
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. 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: 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 ( 5+5 hp) samt muntlig och skriftlig redovisning av uppgifter ( 5+5 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).
Litteraturlista
- Litteraturlista giltig från och med höstterminen 2023
- Litteraturlista giltig från och med höstterminen 2022
- Litteraturlista giltig från och med höstterminen 2019
- Litteraturlista giltig från och med höstterminen 2017
- Litteraturlista giltig från och med vårterminen 2014
- Litteraturlista giltig från och med höstterminen 2013
- Litteraturlista giltig från och med höstterminen 2012
- Litteraturlista giltig från och med höstterminen 2010