5DV037 · Umeå universitet
Datavetenskapens grunder
Ny kurs
Inga tentor än
Ladda upp dina tidigare tentor och få hjälp med att strukturera ditt studiematerial
Få dina tentauppgifter kategoriseradeBli guidad genom ditt studiematerialFå hjälp direkt med teori och tipsHåll koll på dina framsteg
HP
7.5
Språk
Svenska
Institution
Institutionen för datavetenskap
Lärandemål
Kunskap och förståelse Efter avslutad kurs ska studenten kunna:
- (FSR 1) förstå hur reguljära språk och kontextfria språk kan representeras, hur olika representationer förhåller sig till varandra, och hur de kan transformeras
- (FSR 2) förstå Turingmaskinen som en modell för beräkning och dess relation till Church-Turing-tesen samt begreppen avgörbarhet, igenkännbarhet, och beräkningsbarhet
- (FSR 3) förstå definitionerna av tidskomplexitet och i synnerhet komplexitetsklasserna P och NP
- (FSR 4) redogöra för några aktuella forskningsfrågor inom formella språk och beräkningsteori
- Färdighet och förmåga Efter avslutad kurs ska studenten kunna:
- (FSR 5) konstruera Turingmaskiner för givna beräkningsproblem och analysera deras tidskomplexitet
- (FSR 6) bevisa egenskaper relaterade till reguljära språk och kontextfria språk, till exempel bevis för stängningsegenskaper och motbevis för språktillhörighet
- (FSR 7) använda reduktioner för att demonstrera förhållanden mellan beräkningsproblem, till exempel NP-svårighet
- (FSR 8) skriftligt diskutera en teoretisk fördjupning av någon del av innehållet
Kursinnehåll
Kursen ger en introduktion till formella språk och beräkningsteori.
Förutsättningar
- För behörighet krävs följande kurser (eller motsvarande):
- Introduktion till diskret matematik, 7,5 hp
- Datastrukturer och algoritmer, 7,5 hp
Litteratur
Saknas
Liknande kurser vid andra universitet
Gör som 15 000+ studenter och ta kontroll över ditt tentaplugg.
Kom igång gratis