Automaten

Womit beschäftigt sich die theoretische Informatik?
Sowohl für die Konstruktion von Algorithmen als auch für die Konstruktion von Computern spielen Methoden und Modelle aus der Mathematik eine wichtige Rolle. In der Mathematik werden aber überwiegend statische Strukturen betrachtet, in der Informatik dynamische (Prozesse).
Ein wichtiger Grundbegriff der Informatik ist der Begriff des Algorithmus. Die theoretische Informatik beschäftigt sich vor allem mit der Fundierung des Algorithmusbegriffs, untersucht die Leistungsfähigkeit von Algorithmen und erforscht die prinzipiellen Grenzen des Computers beim Lösen von Problemen.
Teilgebiete der theoretischen Informatik sind insbesondere:

• Theorie der formalen Sprachen,
• Automatentheorie,
• Algorithmentheorie,
• Berechenbarkeitstheorie,
• Komplexitätstheorie.

Theorie der formalen Sprachen
Damit Algorithmen durch Computer abgearbeitet werden können, müssen sie in einer Programmiersprache niedergeschrieben sein. Die Theorie der formalen Sprachen beschäftigt sich mit der Konstruktion von Programmiersprachen, allerdings ausschließlich mit deren Syntax. Die Bedeutung (die Semantik) spielt keine Rolle.
Unter Syntax versteht man die Lehre vom Satzbau. Sie umfasst sämtliche grammatikalischen Regeln, deren Anwendung zu korrekt gebauten Sätzen führt. Die Menge aller aus einer formalen Grammatik herleitbaren Sätze bildet die Menge der Sätze einer Sprache. Ein Satz kann also ein Teil eines Programms oder sogar ein vollständiges Programm sein.

Automatentheorie
In der Informatik bezeichnet man als Automaten die mathematischen Modelle von (technischen) Geräten, die Daten verarbeiten und auf Eingaben reagieren, wobei die Eingabegrößen nicht verändert werden dürfen. Die technische Realisierung solcher gedanklichen Modelle sind letztlich Computer.
Die Automatentheorie beschäftigt sich mit der Untersuchung der mathematischen Modelle von Computern. Automaten werden auch zur Beschreibung, Erkennung und Übersetzung von formalen Sprachen genutzt.

Algorithmentheorie
Ein Algorithmus ist eine eindeutig ausführbare Verarbeitungsvorschrift, die für eine Klasse von Problemen gilt, also für diese Klasse allgemeingültig ist, und nach endlich vielen Schritten zum Ziel führt. Dies ist eine sehr verschwommene Definition. Ein Algorithmus muss in der Notationsform „Programm“ so präzise formuliert sein, dass er von einem elektronisch arbeitenden Gerät (Computer) korrekt ausgeführt werden kann.
Algorithmen können durch Automaten (s. Automatentheorie), aber auch als berechenbare Funktionen (s. Berechenbarkeitstheorie) beschrieben werden.
Die Algorithmentheorie beschäftigt sich mit der mathematisch exakten Beschreibung, Untersuchung und Klassifizierung von Algorithmen.

Berechenbarkeitstheorie
Einen Algorithmus kann man auch als Abbildung betrachten, als eine Funktion, die Eingabedaten auf Ausgabedaten abbildet. Nicht jede mögliche Abbildung lässt sich durch einen Algorithmus beschreiben. Historisch gesehen hat man zunächst versucht, genau diejenigen Abbildungen zu definieren, die von Algorithmen beschrieben werden. Solche Abbildungen heißen berechenbare Funktionen.
Die Berechenbarkeitstheorie beschäftigt sich mit Algorithmen auf der Basis berechenbarer Funktionen.

Komplexitätstheorie
Die Komplexitätstheorie untersucht die Komplexität von Funktionen und Algorithmen, das heißt den notwendigen Rechenaufwand und Aufwand an Speicherplatz. Insbesondere werden auch Komplexitätsklassen (Aufwandsklassen) ausgegliedert und algorithmisch beschreibbare Probleme diesen Klassen zugeordnet.
Die Untersuchung erfolgt unabhängig von speziellen Computern. Man nutzt als formale Berechnungsmodelle gedankliche Automatenmodelle (s. Automatentheorie), insbesondere so genannte Turingmaschinen (mit mehreren Bändern) und Registermaschinen (oft als parallele Maschinen).