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