| TDDD65 |
Introduction to the Theory of Computation, 6 hp
/Introduction to the Theory of Computation/
För:
CS
|
| |
Prel. schemalagd
tid: 54
Rek. självstudietid: 106
|
| |
Utbildningsområde: Teknik
Huvudområde: Datateknik, Datavetenskap Nivå (G1,G2,A): G2
|
| |
Mål:
IUAE-matris
Kursen skall ge en introduktion till formella språk, automatateori, beräkningsbarhet och komplexitetsteori. Efter att ha fullgjort kursen skall studenten kunna:
- Hantera reguljära och kontextfria språk; konstruera, förstå och tillämpa deras formella definitioner.
- Modellera enkla situationer med automater och grammatiker
- Tillämpa metoder av oavgörbarhetsanalys
- Analysera komplexitet av algoritmer och klassificera algoritmiska problem.
samt känna till
- grundläggande regler och bestämmelser för studier på högre nivå och hur den akademiska hederskodexen ska tillämpas i de egna studierna,
- kraven på rapporter och examination i den egna utbildningen.
|
| |
Förkunskaper: (gäller studerande antagna till program som kursen ges inom, se 'För:' ovan)
Grudläggande matematik, grundkurs i datastrukturer och algoritmer
OBS! Tillträdeskrav för icke programstudenter omfattar vanligen också tillträdeskrav för programmet och ev. tröskelkrav för progression inom programmet, eller motsvarande.
|
| |
Påbyggnadskurser
Kompilatorkonstruktion
|
| |
Organisation:
Föreläsningarna tar upp teoretiska avsnitt och på lektionerna övas dessa med problem.
Kursen pågår hela höstterminen.
|
| |
Kursinnehåll:
- �"ndliga automater och reguljära uttryck.
- Kontextfria grammatiker och pushdown-automater.
- Turingmaskiner och Church-Turing thesis.
- Ordonotationen, komplexitetsanalys av algoritmer.
- Tidskomplexitetsklasser P och NP.
- NP-fullständiga problem.
- Orientering om rumskomplexitet.
Kursen innehåller också universitets regler, etiska regler, akademiskt skrivande och rapporter samt hur man förbereder sig inför examination.
|
| |
Kurslitteratur:
Kursbok: Michael Sipser, Introduction to the Theory of Computation (2nd edition), Thomson 2006
Additional reading: Thomas A. Sudkamp, Languages and Machines (3d edition), Pearson Education 2006
|
| |
Examination: |
TEN1
UPG2
UPG3
|
Skriftlig tentemen (U,3,4,5)
Uppgifter - akademiska studier (U,G)
Uppgifter - computation (U,G)
|
3 hp
2 hp
1 hp
|
| |
|
|