Sök i programutbudet

Använd sökfunktionen för att leta efter kurser och program i Chalmers utbildningsutbud. Den programplan och utbildningsplan som avser dina studier är i allmänhet från det läsår du började dina studier.

​​​​​​​​​​​​​

Kursplan för

Läsår
TDA183 - Beräkningsmodeller
 
Kursplanen fastställd 2015-02-12 av programansvarig (eller motsvarande)
Ägare: MPALG
7,5 Poäng
Betygskala: TH - Fem, Fyra, Tre, Underkänt
Utbildningsnivå: Avancerad nivå
Huvudområde: Datateknik, Informationsteknik
Institution: 37 - DATA- OCH INFORMATIONSTEKNIK


Undervisningsspråk: Engelska
Sökbar för utbytesstudenter
Blockschema: A

Modul   Poängfördelning   Tentamensdatum
Lp1 Lp2 Lp3 Lp4 Sommarkurs Ej Lp
0108 Tentamen 7,5 hp Betygskala: TH   7,5 hp   13 Jan 2016 fm M,  07 Apr 2016 em M

I program

MPALG DATAVETENSKAP - ALGORITMER, PROGRAMSPRÅK OCH LOGIK, MASTERPROGRAM, Årskurs 1 (obligatoriskt valbar)
MPALG DATAVETENSKAP - ALGORITMER, PROGRAMSPRÅK OCH LOGIK, MASTERPROGRAM, Årskurs 2 (valbar)
MPCSN DATORER, NÄTVERK OCH SYSTEM, MASTERPROGRAM, Årskurs 1 (valbar)
MPCSN DATORER, NÄTVERK OCH SYSTEM, MASTERPROGRAM, Årskurs 2 (valbar)
TKITE INFORMATIONSTEKNIK, CIVILINGENJÖR, Årskurs 3 (valbar)

Examinator:

Professor  Bengt Nordström


Ersätter

TDA181   Beräkningsmodeller TDA182   Models of computation


  Gå till kurshemsida

Behörighet:


För kurser på avancerad nivå gäller samma grundläggande och särskilda behörighetskrav som till det kursägande programmet. (När kursen är på avancerad nivå men ägs av ett grundnivåprogram gäller dock tillträdeskrav för avancerad nivå.)
Undantag från tillträdeskraven: Sökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.

Kursspecifika förkunskaper

Grundläggande kunskap i logik och funktionell programmering. Denna kunskap kan erhållas genom Chalmerskurserna DAT060 Logic in computer science och TSA452 Functional programming eller på annat sätt.

Syfte

Kursen syftar att ge studenterna en god grund inom olika beräkningsmodeller. Ett huvudproblem som studeras är skillnaden mellan liknande begrepp (t.ex. mängd/typ, funktion/program) inom datavetesnkap och matematik. För att se ämnenas gemensamma grund är det viktigt att förstå dessa grundläggande begrepp. Studenterna kommer att förstå både program och programmeringsspråk som matematiska objekt och kunna studera dessa med matematiska metoder.

Lärandemål (efter fullgjord kurs ska studenten kunna)

  • Förstå skillnaden mellan ett program och en funktion
  • förstå abstrakt och konkret syntax
  • förklara Churchs tes
  • förklara primitiv rekursion
  • förstå när en mängd är enumerabel
  • ge exempel på problem som inte är beräkningsbara
  • representera induktivt definierade mängder i olika beräkningsmodeller
  • presentera olika beräkningsmodeller
  • ge exempel på hur man representerar program i de olika modellerna

Innehåll

I denna kurs studeras begreppen program, programspråk och beräkning från ett mer allmännt och matematiskt perspektiv än i de inledande programmeringskurserna. Speciellt studeras olika beräkningsmodeller. Dessa kan ses som förenklade programmeringsspråk som innehåller en kärna med all beräkningskraft. Exempel på sådana är lambdakalkylen, som är grunden till funktionella språk och Turing-maskiner som är en förenklad (teoretisk) dator som definierades på 1930-talet av matematikern Alan Turing. Vi kommer att diskutera begränsningar som finns i alla programmeringsspråk - t.ex. Turings resultat att det inte finns någon beräkningmässig lösning till stopp-problemet. Kursen innehåller också en introduktion till hur man definierar syntax och semantik för programmeringsspråk på ett precist sätt. Mer konkret så innehåller kursen följande delämnen:
Grundläggande matematiska begrepp: mängder, induktion, relationer, funktioner, uppräkneliga mängder
Beräkningsmodeller: lambda-kalkyl, primitivt rekursiva funktioner, allmänt rekursiva funktioner, turing-maskiner, andra modeller (t.ex. X, PCF, P)
Beräkningsbarhet: Finns det problem som ingen dator kan lösa?

Organisation

Föreläsningar, övningar

Litteratur

Kursens hemsida, föreläsningsanteckningar

Examination

hemuppgifter, veckovisa övningar, skriftlig examen


Sidansvarig Publicerad: on 24 jan 2018.