Modeller för beräkningsbarhet

Kursen ingår i utbildningsprogrammet Logik, masterprogram (H2LOG) och kan även ges som fristående kurs.

För tillträde till kursen krävs godkänt resultat om

• minst 60 hp sammanlagt inom ämnesområdena matematik, logik, datavetenskap eller formell lingvistik, eller
• minst 90 hp inom filosofi eller lingvistik, samt minst 30 hp sammanlagt inom ämnesområdena matematik, logik, datavetenskap eller formell lingvistik,

eller motsvarande kunskaper. Dessutom krävs språkkunskaper motsvarande Engelska 6.

En modell för beräkningsbarhet beskriver hur, och om, en funktion eller operation kan beräknas. Kursen behandlar flera sådana modeller samt hur dessa modeller är relaterade till varandra. Även centrala resultat och begrepp inom området diskuteras.
Kursens innehåll inkluderar:

• Ändliga automater
• Reguljära och kontextfria språk
• Turing-beräkningsbarhet och rekursiva funktioner
• Rekursionssatsen och relativ Turing-beräkningsbarhet
• Grundläggande resultat inom komplexitetsteori

Efter godkänd kurs ska studenten kunna:

Kunskap och förståelse

• redogöra för de olika modeller av beräkningsbarhet som behandlas i kursen, samt relatera dessa till varandra,
• förklara och tillämpa grundläggande resultat som relaterar automatateori till formella språk,
• redovisa förståelse för resursbegränsad beräkning,

Färdigheter och förmåga

• formulera och presentera bevis av de viktigaste resultaten i kursen, såväl som av lemman som används i bevisen,
• applicera kursens teoretiska resultat och metoder i självständig problemlösning,
• konstruera algoritmer och implementera dem i olika beräkningsmodeller,
• konstruera automater som känner igen ett givet språk och grammatiker som genererar det,
• analysera program och beräkningsproblem med avseende på deras komplexitet,

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

• kritiskt diskutera, analysera och utvärdera resultaten i kursen samt deras tillämpningar.

Undervisningen ges i form av föreläsningar och enskilt arbete eller arbete i grupp.

Undervisningsspråk: engelska

Kursen examineras individuellt i skriftlig form. Utöver avslutande skriftlig tentamen kan det också förekomma upp till fyra obligatoriska hemuppgifter under kursens gång.

Rättande lärare kan begära komplettering av examination.

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.

På kursen ges något av betygen Väl godkänd (VG), Godkänd (G) och Underkänd (U). Alla obligatoriska moment måste vara godkända för att erhålla betyget Godkänd. För betyget Väl godkänd krävs dessutom att den skriftliga tentamen bedöms med betyget Väl godkänd.

Studenter som deltar i eller har avslutat kursen ges möjlighet att anonymt framföra erfarenheter av och synpunkter på denna i en kursvärdering. En sammanställning av kursvärderingen och kursansvarig lärares reflektion tillgängliggörs för studenterna inom rimlig tid efter kursslut. Nästa gång kursen ges presenteras sammanställningen och eventuella genomförda åtgärder.

Kursen kräver tillgång till dator (eller motsvarande) med internetuppkoppling.
Kursen får ej ingå i examen tillsammans med kursen LOG260.