Berechenbarkeit

Konzepte der Informatik

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Was ist Berechenbarkeit?

Berechenbares Problem

Algorithmus vorhanden: Es gibt ein klares Verfahren.
Endliche Zeit: Liefert Ergebnis in begrenzten Schritten.

Nicht-berechenbares Problem

Kein Algorithmus: Nicht für alle Eingaben lösbar.
Unendliche Berechnung: Erreicht ggf. nie ein Ergebnis.

¹ Nicht-berechenbare Probleme können berechenbar werden, wenn wir einen Algorithmus finden und/oder einen bekannten Algorithmus in endlicher Zeit beenden lassen.

Automaten

Definition von Automaten

Gedachte Maschinen
Helfen zu verstehen, wie Berechnung funktioniert
Haben Zustände
Haben Übergangsregeln zwischen Zuständen

Ein Bild einer Ampel als Analogie für Automaten

Endliche Automaten (FA)

Endliche Automaten (FA)

Einfache „Maschinen“
Feste Anzahl an Zuständen
Kein Speicher über den aktuellen Zustand hinaus

Ein Bild einer Ampel und Zustände als Analogie für Endliche Automaten

Kellerautomaten (PDA)

Kellerautomaten (PDA)

Mächtiger
Hat Zustände
Stapelspeicher für komplexere Entscheidungen

Ein Bild einer Ampel und Zustände als Analogie für Kellerautomaten

Zusammenfassung

Endliche Automaten (FA)

Nützlich für einfache Aufgaben

Kellerautomaten (PDA)

Mächtiger für komplexere Probleme

Wichtigkeit

Wenn sich ein Problem per Automat modellieren lässt, KÖNNEN wir einen Algorithmus dafür umsetzen

Lass uns üben!

Konzepte der Informatik