Dina studier

Kursplan för Beräkningsmodeller

Kursplanen innehåller ändringar
Se ändringar

Kursplan fastställd 2018-02-13 av programansvarig (eller motsvarande).

Kursöversikt

  • Engelskt namnModels of computation
  • KurskodTDA184
  • Omfattning7,5 Högskolepoäng
  • ÄgareMPALG
  • UtbildningsnivåAvancerad nivå
  • HuvudområdeDatateknik, Informationsteknik
  • InstitutionDATA- OCH INFORMATIONSTEKNIK
  • BetygsskalaTH - Fem, Fyra, Tre, Underkänd

Kurstillfälle 1

  • Undervisningsspråk Engelska
  • Anmälningskod 02115
  • Blockschema
  • Sökbar för utbytesstudenterJa

Poängfördelning

0116 Tentamen 4,5 hp
Betygsskala: TH		4,5 hp
  • 16 Jan 2019 fm M
  • 25 Apr 2019 em J
0216 Inlämningsuppgift 3 hp
Betygsskala: UG		3 hp

    I program

    Examinator

    Ersätter

    • TDA181 Beräkningsmodeller
    • TDA182 Models of computation
    • TDA183 Beräkningsmodeller

    Behörighet

    Information saknas

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

    Anges på kurshemsidan.

    Examination inklusive obligatoriska moment

    Kursen examineras genom en individuell skriftlig salstentamen samt individuella inlämningsuppgifter.

    Kursplanen innehåller ändringar

    • Ändring gjord på tentamen:
      • 2018-11-12: Plats Plats ändrat från Johanneberg till M av TENTAMENSADM
        [2019-01-16 F, 0116]