Studiegids

nl en

Fundamentele Informatica 3

Vak
2010-2011

Inhoud:

Context-vrije talen: grammatica’s en stapelautomaten, determinisme, parsing. De Turingmachine als algemeen model voor berekenbaarheid: herkennen, beslissen en rekenen met Turingmachines, niet-determinisme, universele Turingmachines, Church-Turing These. Recursief opsombare talen, de Chomsky hierarchie. Het stopprobleem, berekenbaarheid, (on)beslisbare problemen.

Methode

hoorcollege met werkgroep

Examinering

schriftelijk

Doel

Verwerven van inzicht in de mogelijkheden en beperkingen van computers (algoritmes). Kennismaken met fundamentele inzichten die ten grondslag liggen aan de informatica als wetenschappelijke discipline.

Voorkennis

Fundamentele Informatica 1 en 2

Literatuur

John C. Martin, Introduction to Languages and the Theory of Computation, 3rd edition, McGraw Hill, 2003

Website

Fundamentele Informatica 3

Materiaal

John C. Martin, Introduction to Languages and the Theory of Computation, 3rd edition, McGraw Hill, 2003