Teoretisk datalogi

I kursen behandlas grunderna i automatateori, formella språk, beräkningsbarhets- och komplexitetsteori. Kursen är central för att förstå en dators möjligheter och begränsningar samt varför vissa problem är beräkningsmässigt omöjliga och andra svåra eller lätta.

Automatateori och formella språk:

• reguljära språk och uttryck samt ändliga automater
• kontextfria språk och grammatiker samt pushdown-automater
• pumpsatsen.

Beräkningsbarhetsteori:

• Turingmaskiner
• Church-Turing-hypotesen
• problems/språks avgörbarhet
• stopproblemet
• rekursionssatsen (koppling till datavirus).

Komplexitetsteori:

• komplexitetsklasser
• algoritmers tidskomplexitet
• kryptografi.

Fördjupningsnivå: G1F (har mindre än 60 hp kurs/er på grundnivå som förkunskapskrav)

Utbildningsnivå: Grundnivå

Behörighetskrav: Programmeringsteknik 7,5 hp. Diskret matematik 7,5 hp, alternativt Programutvecklingsmetodik 7,5 hp. Motsvarandebedömning kan göras.

Urval: 1) programförtur 2) akademiska poäng 3) övriga sökande

Kursen ingår i följande program

• Civilingenjör Datateknik (läses år 2)