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,
NL, satisfiability probleem, graafproblemen, traveling salesman probleem,
reduceerbaarheid, volledigheid, approximaties en cryptografie.
|
|