| TDDC95 |
Introduction to the Theory of Computation, 2,5 p
/
4 hp
/Introduction to the Theory of Computation/ |
||
Prel. schemalagd
tid: |
|||
|
Utbildningsområde: Teknik Ämnesgrupp: Datavetenskap Nivå (A-D):C 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:
|
|||
| 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. |
|||
| 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. |
|||
| 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 UPG1 |
Skriftlig tentemen (U,3,4,5) Obligatoriska hemuppgifter (U,G) |
3 hp 1 hp |
|
Undervisningsspråk är Engelska .
Institution: IDA.
Studierektor: Patrick Lambrix
Examinator: Gustav Nordh
Länk till kurshemsida på kursgivande institution
Ansvarig programnämnd: Data&Medie
Engelsk kursplan
Kursen bedrivs på ett sådant sätt att både mäns och kvinnors erfarenhet och kunskaper synliggörs och utvecklas.
Planering och genomförande av kurs skall utgå från kursplanens formuleringar. Den kursvärdering som ingår i kursen skall därför genomföras med kursplanen som utgångspunkt.
Om inget annat anges ovan gäller betygsskala enligt avsnitt a8.5 i de gemensamma bestämmelserna.
Kursplanen gäller för 2011 enligt beslut av ansvarig programnämnd/fakultetstyrelse.
 |
||||||
| ||||||