studiehandbok@lith   Länk till universitetets hemsida
 

Tekniska högskolan vid Linköpings universitet

Sök

 Länk till universitetets hemsida
 
År : 2013
 
TDDD65 Introduction to the Theory of Computation, 4 p / 6 hp
/Introduction to the Theory of Computation/

För:   CS  

 

Prel. schemalagd tid: 48
Rek. självstudietid: 112

  Utbildningsområde: Teknik

Ämnesgrupp: Datateknik   Nivå (A-D):C

Huvudområde: Datateknik, Datavetenskap   Nivå (G1,G2,A): G2
  Mål:
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
 


Undervisningsspråk är Engelska .
Institution: IDA.
Studierektor: Tommy Färnqvist
Examinator: Gustav Nordh
Länk till kurshemsida på kursgivande institution
Ansvarig programnämnd: Data&Medie

Engelsk kursplan


Tekniska högskolan vid Linköpings universitet
Länk till sidans topp


Informationsansvarig: TFK , val@tfk.liu.se
Senast ändrad: 10/21/2013