Berekenbaarheid

Concepten in de informatica

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Wat is berekenbaarheid?

Berekenbaar probleem

  • Algoritme bestaat: Er is een duidelijke procedure.
  • Eindige tijd: Levert output in beperkte stappen.

Niet-berekenbaar probleem

  • Geen algoritme: Niet oplosbaar voor alle mogelijke input.
  • Oneindige berekening: Komt mogelijk nooit tot een conclusie.
1 Niet-berekenbare problemen kunnen berekenbaar worden zodra we een algoritme vinden en/of een bekend algoritme in eindige tijd laten stoppen.
Concepten in de informatica

Automaten

Definitie van automaten

  • Denkbeeldige machines
  • Helpen te begrijpen hoe rekenen/computatie werkt
  • Hebben toestanden
  • Hebben regels voor overgang tussen toestanden

Een afbeelding van een verkeerslicht als analogie voor automaten

Concepten in de informatica

Eindige automaat (FA)

Eindige automaat (FA)

  • Simpele machines
  • Vast aantal toestanden
  • Geen geheugen buiten de huidige toestand

Een afbeelding van een verkeerslicht en toestanden als analogie voor eindige automaten

Concepten in de informatica

Pushdown-automaat (PDA)

Pushdown-automaat (PDA)

  • Krachtiger
  • Heeft toestanden
  • Heeft stack-geheugen voor complexere beslissingen

Een afbeelding van een verkeerslicht en toestanden als analogie voor pushdown-automaten

Concepten in de informatica

Samenvatting

Eindige automaat (FA)

  • Handig voor simpele taken

Pushdown-automaat (PDA)

  • Krachtiger voor complexere problemen

Belang

  • Als een probleem door een automaat te modelleren is, dan KUNNEN we er een algoritme voor maken
Concepten in de informatica

Laten we oefenen!

Concepten in de informatica

Preparing Video For Download...