Beräkningsbarhet

Kursen kan ingå i följande program:

1. Computer Science, masterprogram (N2COS)
2. Datavetenskap, kandidatprogram (N1COS)

Kursen ges även som fristående kurs vid Göteborgs Universitet.

För tillträde till kursen krävs att studenten har minst 120 hp i datavetenskap eller motsvarande.

Specifikt krävs följande kurser, eller motsvarande:

• 7,5 hp i diskret matematik (t.ex. DIT980 Diskret matematik för datavetare)
• 7,5 hp i funktionell programmering (t.ex. DIT143 Funktionell programmering eller DIT440 Introduktion till funktionell programmering)

Följande kunskapsnivå i Engelska krävs: Engelska 6/Engelska nivå 2 eller motsvarande från ett erkänt internationellt test, t.ex. TOEFL, IELTS.

Kursen handlar om beräkningar: hur de kan modelleras, och vad som kan beräknas. 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.

Efter godkänd kurs ska studenten kunna:

Kunskap och förståelse

• definiera begreppet beräkningsbar funktion,
• förklara Church-Turings hypotes,
• förklara sambandet mellan induktivt definierade mängder, primitiv rekursion, och bevismetoden strukturell induktion,

Färdigheter och förmåga

• 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,

Värderingsförmåga och förhållningssätt

• analysera program hörandes till några beräkningsmodeller, och
• manipulera och analysera beräkningsmodeller.

Föreläsningar och övningar.

Undervisningsspråk: engelska

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

Om en student som har underkänts två gånger på samma examinerande moment önskar byta examinator inför nästa examinationstillfälle ska en sådan begäran bifallas om det inte finns särskilda skäl däremot (6 kap. 22 § HF).

Om en student har fått besked om pedagogiskt stöd från Göteborgs universitet med rekommendation om anpassad examination och/eller anpassad examinationsform kan examinator, i det fall det är förenligt med kursens lärandemål och förutsatt att inte orimliga resurser krävs, besluta att bevilja studenten anpassad examination och/eller anpassad examinationsform.

Om en kurs har avvecklats eller genomgått en större förändring ska studenten erbjudas minst två examinationstillfällen, utöver ordinarie examinationstillfälle. Dessa tillfällen fördelas under en tid av minst ett år, dock som längst två år efter det att kursen avvecklats/förändrats. Vad gäller praktik och verksamhetsförlagd utbildning (VFU) gäller motsvarande, men med begränsning till endast ett ytterligare examinationstillfälle.

Om en student har fått besked om att denne uppfyller kraven för att vara student vid Riksidrottsuniversitetet (RIU-student) har examinator rätt att besluta om anpassning vid examination, om detta görs i enlighet med Lokala regler gällande RIU-studenter vid Göteborgs universitet

Delkurser

1. Skriftlig salstentamen, 4,5 hp
   Betygsskala: Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3) och Underkänd (U)
2. Inlämningsuppgifter, 3 hp
   Betygsskala: Godkänd (G) och Underkänd (U)

På kursen ges något av betygen Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3) och Underkänd (U).

För att få något av betygen 5, 4 eller 3 krävs dels att man får betyget G på delkursen inlämningsuppgifter, och dels att man får godkänt resultat (5, 4 eller 3) på delkursen skriftlig salstentamen. I så fall är betyget på hela kursen betyget på delkursen skriftlig salstentamen. I annat fall är betyget på hela kursen U (underkänt).

Kursen utvärderas genom möten, både under och efter kursen, mellan lärare och studentrepresentanter. Ett anonymt skriftligt frågeformulär skickas även ut till studenterna efter kursens slut. Resultaten av utvärderingarna används för att förbättra kursinnehållet och som indikation till vilka delar som skulle kunna läggas till, tas bort, förbättras eller ändras.

Kursen är samläst med Chalmers.

Kursen ersätter kursen DIT312, 7,5 hp. Den här kursen kan inte ingå i en examen som innehåller DIT312. Den kan inte heller ingå i en examen som bygger på en annan examen där DIT312 ingår.