Matematisk-datalogiska linjens datalogiinriktning årskurs 3, 25 poäng
(NA8650)

(Study Programme in Mathematics­Computer Science,
Computer Science Branch, third year, 25 credits)


Förkunskapskrav

För tillträde till kursen krävs godkänt resultat på moment motsvarande minst 60 poäng på matematisk-datalogiska linjens två första år.

Mål

Kursen syftar till att
  • ge fördjupade kunskaper om programmering,
  • ge insikt om datorns interna uppbyggnad,
  • ge färdigheter i att klassificera problem efter deras beräkningskomplexitet,
  • ge förtrogenhet med grafisk databehandling,
  • ge en grundlig förståelse för uppbyggnad och hantering av databassystem.
    
    

    Innehåll

  • Datorsystemstrukturer, 6 poäng
    Moderna datorsystems interna uppbyggnad och struktur med exempel från mikro-, mini- och stordator. Operativsystemet Unix och programspråket C.

  • Databasteknik, 4 poäng
    Modellering och informationsstrukturering enligt ²Entity-Relation-ship²-modellen. Normalisering. Relationsalgebra, tupelkalkyl, domänkalkyl. Frågespråk, särskilt SQL. Lagrings- och åtkomstmetoder.

  • Komplexitet, 4 poäng
    Exempel på beräkningsproblem och tekniker för att konstruera effektiva algoritmer. Komplexitetsklasserna P och NP. NP-fullständighet och oavgörbarhet.

  • Interaktion med grafiska gränssnitt, 4 poäng
    Grafisk databehandling: Tillämpningar, utrustning, programvara, standarder. Grundläggande algoritmer för 2D-, 3D-, raster- och vektorgrafik. Människa-datorinteraktion, främst användarcentrerad gränssnittsutveckling inklusive dialogutformning, bruksmodeller, programvaruverktyg för konstruktion av interaktiva system.

  • Projektarbete, 4 poäng
    Dokumentationskunskap. I större grupp utveckla interaktiv tillämpning för och på grafisk arbetsstation.

  • Programdeklarationer och deklarativ programmering, 3 poäng
    Typer: syntax och semantik, variabler, typsystem, sidoeffekter. Variabler: uppdatering och livstid, statisk och dynamisk bindning, omgivningar. Abstraktion: data- och programabstraktion, abstrakta datatyper, matematisk specifikation av abstrakta datatyper, parametrar, parameteröverföring, inkapsling. Typsystem: monomorfism, polymorfism, statisk och dynamisk typning. Programmeriparadigm, speciellt deklarativ programmering. Något om restriktionsteknik.
    
    

    Litteratur

    Elmasri, R & Navathe, S B:
    Fundamentals of Database Systems (Redwood City, Cal: Benjamin/Cummings Publ Comp, 1994).
    Foley, J, van Dam, A, Feiner, S, Hughes, J & Phillips, R:
    Introduction to Computer Graphics (Reading, Mass: Addison-Wesley, 1994).
    Kernighan, B W & Ritchie, D M:
    The C Programming Language (Englewood Cliffs, N J: Prentice Hall, 1988, 2:a uppl., pb).
    Manber, U:
    Introduction to Algorithms ­ A Creative Approach (Reading, Mass: Addison-Wesley, 1989).
    [Myers, C, Clack, C & Poon, E:
    Programming with Standard ML (Englewood Cliffs, N J: Prentice Hall, 1993).]
    Preece, J:
    A Guide to Usability, Human Factors in Computing (Reading, Mass: Addison-Wesley, 1993, pb).
    Tanenbaum, A S:
    Structured Computer Organisation (Englewood Cliffs, N J: Prentice Hall, 1990, 3:e uppl., pb).
    Watt, D A:
    Programming Language Concepts and Paradigms (Englewood Cliffs, N J: Prentice Hall, 1990, pb).
    
    

    Kursledare läsåret 96/97

    Delen Datorsystemstrukturer:
    Jonas Mölsä, tel. 790 66 46, datorpost jbm@nada.kth.se

    Delen Databasteknik:
    Kjell Lindqvist, tel. 790 62 76, datorpost kjellq@nada.kth.se

    Delen Komplexitet:
    Mikael Goldmann, tel. 790 68 13, datorpost migo@nada.kth.se

    Delarna Interaktion med grafiska gränssnitt och Projektarbete:
    Serafim Dahl , tel. 790 62 76, datorpost serafim@nada.kth.se

    Delen Programdeklarationer och deklarativ programmering:
    Karl Meinke , tel. 790 63 40, datorpost karlm@nada.kth.se

    
    

    Kursinformation (om sådan finns tillgänglig)

    Datorsystemstrukturer
    Databasteknik
    Komplexitet
    Interaktion med grafiska gränssnitt
    Projektarbete
    Programdeklarationer och deklarativ programmering

    
    
    ^ Upp till kursplaner; innehållsförteckning.


    Senast ändrad 96-12-17 <svl-su@nada.kth.se>