| TDDA89 |
Formella språk och automatateori, 3,5 p
/
5 hp
/Formal Languages and Automata Theory/ |
|||
Prel. schemalagd
tid: 50 |
||||
|
Utbildningsområde: Teknik Ämnesgrupp: Datalogi, Datateknik Nivå (A-D):B Huvudområde: Datateknik, Datavetenskap Nivå (G1,G2,A): G2 |
||||
| Datavetenskap Datavetenskap, datalogi. |
||||
|
Mål:
Kursen skall ge en introduktion till formella språk och automatateori. Automater och formella språk uppträder (eventuellt i olika förklädnader) i nästan varje gren av datalogin. Efter att ha fullgjort kursen skall studenten kunna:
|
||||
| Förkunskaper: (gäller studerande antagna till program som kursen ges inom, se 'För:' ovan) Grundläggande matematik, t.ex. en kurs i diskret matematik (TATA17). 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 TDDB44 Kompilatorkonstruktion, TDDB41 Komplexitetsteori, TDDB40 Omskrivningssystem, TDDA43 Programmeringsteori, TDDB08 Logik fördjupningskurs |
||||
| 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. Deterministiska kontextfria sprÃ¥k, LR parsning, Chomskys sprÃ¥khierarki. Orientering om Turingmaskiner och oavgörbarhetsproblem. |
||||
Kurslitteratur:
|
||||
| Examination: | ||||
| TEN1 UPG1 |
En skriftlig tentamen (U,3,4,5) Inlämningsuppgifter (U,G) |
3,5 p 0 p |
/ / |
5 hp 0 hp |
Undervisningsspråk är Engelska.
Institution: IDA.
Studierektor: sas-sr@ida.liu.se
Examinator: Ulf Nilsson
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 2008 enligt beslut av ansvarig programnämnd/fakultetstyrelse.
 |
||||||
| ||||||