Begrip van berekenbaarheidstheorie en complexiteitstheorie.
|
|
Deel I: Formele talen: eindige automaten, reguliere talen en grammatica's.
Deel II: Berekenbaarheidstheorie: Turing machines, berekenbare functies, Church-Turing these, Universele Turing machine, niet-determinisme versus determinisme, onbeslisbaarheid, Halting probleem, beslisbare en onbeslisbare talen.
Deel III: Complexiteitstheorie: complexiteitsklassen, P, PSPACE, NP, EXP, satisfiability probleem, graafproblemen, reduceerbaarheid, volledigheid.
|
|