Kursplan fastställd 2021-02-26 av programansvarig (eller motsvarande).
Kursöversikt
- Engelskt namnComputability
- KurskodDAT415
- Omfattning7,5 Högskolepoäng
- ÄgareMPALG
- UtbildningsnivåAvancerad nivå
- HuvudområdeDatateknik, Informationsteknik
- InstitutionDATA- OCH INFORMATIONSTEKNIK
- BetygsskalaTH - Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3), Underkänd
Kurstillfälle 1
- Undervisningsspråk Engelska
- Anmälningskod 02123
- Blockschema
- Sökbar för utbytesstudenterJa
Poängfördelning
Modul | LP1 | LP2 | LP3 | LP4 | Sommar | Ej LP | Tentamensdatum |
|---|---|---|---|---|---|---|---|
| 0119 Tentamen 4,5 hp Betygsskala: TH | 4,5 hp |
| |||||
| 0219 Inlämningsuppgift 3 hp Betygsskala: UG | 3 hp |
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)
Examinator
Nils Anders Danielsson- Docent, Computing Science, Data- och informationsteknik
Behörighet
Grundläggande behörighet för avancerad nivåSökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.
Särskild behörighet
Engelska 6Sökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.
Kursspecifika förkunskaper
7,5 hp diskret matematik (till exempel TMV200 eller TMV210).7,5 hp funktionell programmering (till exempel TDA452 eller TDA555).
Syfte
Kursen handlar om beräkningar: hur de kan modelleras, och vad som kan beräknas.Lärandemål (efter fullgjord kurs ska studenten kunna)
Efter godkänd kurs ska studenten kunna
- definiera begreppet beräkningsbar funktion,
- förklara Church-Turings hypotes,
- förklara sambandet mellan induktivt definierade mängder, primitiv rekursion, och bevismetoden strukturell induktion,
- bevisa att mängder är uppräkneliga eller ouppräkneliga, till exempel genom att använda diagonalisering,
- koda induktivt definierade mängder på ett sådant sätt att element i dessa mängder kan användas som indata eller utdata för program i en eller flera beräkningsmodeller,
- implementera program, i synnerhet interpretatorer, korrekt i en eller flera beräkningsmodeller,
- bevisa att funktioner är eller inte är beräkningsbara i några beräkningsmodeller,
- analysera program hörandes till några beräkningsmodeller, och
- manipulera och analysera beräkningsmodeller.
Innehåll
För att undvika onödiga komplikationer väljer man ofta att studera beräkningar via förenklade, men kraftfulla, modeller. De här modellerna kan till exempel vara enkla programmeringsspråk (som λ-kalkyl), eller idealiserade datorer (som Turingmaskiner). Kursen behandlar flera sådana modeller, både "imperativa" och "funktionella".
En eller flera modeller kommer att användas för att utforska gränserna för vad som kan beräknas: problem som inte kan lösas (inom en viss modells ramar), och program som kan köra godtyckliga program (modellerade på ett visst sätt).
Kursen innehåller också en diskussion av Church-Turings hypotes, en förmodan om att en funktion är beräkningsbar på ett visst intuitivt sätt endast om den kan definieras i en av flera beräkningsmodeller.
Organisation
Föreläsningar och övningar.
Litteratur
Kurslitteratur kommer att publiceras senast 8 veckor innan kursstart.
Examination inklusive obligatoriska moment
Kursen examineras genom en individuell skriftlig salstentamen samt individuella inlämningsuppgifter.
Kursens examinator får examinera enstaka studenter på annat sätt än vad som anges ovan om särskilda skäl föreligger, till exempel om en student har ett beslut från Chalmers om pedagogiskt stöd på grund av funktionsnedsättning.