Grundlagen der Theoretischen Informatik

Theoretische Informatik ist ein Teilgebiet der Informatik, das sich mit den mathematischen Grundlagen von Berechnung, Algorithmen, formalen Sprachen und Komplexität beschäftigt. Während die praktische Informatik häufig konkrete Systeme, Programme oder Anwendungen betrachtet, untersucht die theoretische Informatik abstrakte Modelle und allgemeine Gesetzmäßigkeiten. Sie beantwortet grundlegende Fragen wie: Was kann ein Computer prinzipiell berechnen? Welche Probleme sind algorithmisch lösbar? Welche Probleme sind zwar lösbar, aber nur mit sehr hohem Aufwand? Und wie kann man Programme, Sprachen und Berechnungen formal beschreiben?

Die theoretische Informatik bildet damit eine wichtige Grundlage für viele andere Bereiche der Informatik, etwa Compilerbau, Kryptographie, Datenbanken, Softwareverifikation, künstliche Intelligenz und Algorithmik.

Überblick

Die Grundlagen der theoretischen Informatik lassen sich grob in mehrere zentrale Themenbereiche einteilen:

• Formale Sprachen und Grammatiken
• Automatentheorie
• Berechenbarkeitstheorie
• Komplexitätstheorie
• Logik und formale Systeme
• Algorithmische Grundlagen

Diese Bereiche hängen eng miteinander zusammen. Formale Sprachen beschreiben beispielsweise Mengen von Wörtern nach festen Regeln. Automaten können solche Sprachen erkennen. Berechenbarkeitstheorie untersucht, welche Probleme überhaupt mit einem Algorithmus lösbar sind. Komplexitätstheorie betrachtet, wie viel Zeit oder Speicherplatz zur Lösung eines Problems benötigt wird.

Grundbegriffe

Alphabet

Ein Alphabet ist eine endliche, nichtleere Menge von Zeichen. In der theoretischen Informatik wird ein Alphabet häufig mit dem Symbol $\mathrm{\Sigma }$ bezeichnet.

Beispiele:

$\mathrm{\Sigma }=\{0,1\}$

Dies ist ein binäres Alphabet mit den Zeichen 0 und 1.

$\mathrm{\Sigma }=\{a,b,c\}$

Dies ist ein Alphabet mit drei Zeichen.

Wort

Ein Wort ist eine endliche Folge von Zeichen aus einem Alphabet.

Beispiele über dem Alphabet $\mathrm{\Sigma }=\{0,1\}$:

• $0$
• $101$
• $00110$

Das leere Wort wird meist mit $\epsilon$ bezeichnet. Es enthält kein Zeichen und hat die Länge 0.

Sprache

Eine formale Sprache ist eine Menge von Wörtern über einem Alphabet.

Formal gilt:

$L\subseteq {\mathrm{\Sigma }}^{*}$

Dabei bezeichnet ${\mathrm{\Sigma }}^{*}$ die Menge aller endlichen Wörter über dem Alphabet $\mathrm{\Sigma }$.

Beispiel:

$L=\{w\in \{0,1{\}}^{*}\mid w\text{ enthält eine gerade Anzahl von Einsen}\}$

Diese Sprache enthält alle binären Wörter, in denen die Anzahl der Einsen gerade ist.

Formale Sprachen

Formale Sprachen sind ein zentrales Konzept der theoretischen Informatik. Sie dienen dazu, syntaktische Strukturen exakt zu beschreiben. Ein wichtiges Anwendungsgebiet ist der Compilerbau, da Programmiersprachen durch formale Grammatiken beschrieben werden können.

Grammatiken

Eine Grammatik ist ein Regelsystem zur Erzeugung von Wörtern einer Sprache. Sie besteht typischerweise aus:

• einer Menge von Nichtterminalsymbolen,
• einer Menge von Terminalsymbolen,
• einem Startsymbol,
• einer Menge von Produktionsregeln.

Eine Grammatik wird häufig als Tupel dargestellt:

$G=(N,T,P,S)$

Dabei gilt:

Symbol	Bedeutung
$N$	Menge der Nichtterminalsymbole
$T$	Menge der Terminalsymbole
$P$	Menge der Produktionsregeln
$S$	Startsymbol

Beispiel einer Grammatik

Gegeben sei die Grammatik:

$G=(\{S\},\{a,b\},P,S)$

mit den Produktionsregeln:

S -> aSb
S -> ε

Diese Grammatik erzeugt die Sprache:

$L=\{a^n{b}^n\mid n\ge 0\}$

Die Sprache enthält also Wörter wie:

ε
ab
aabb
aaabbb
aaaabbbb

Chomsky-Hierarchie

Die Chomsky-Hierarchie ordnet formale Grammatiken und Sprachen nach ihrer Ausdrucksstärke. Sie ist eine der wichtigsten Klassifikationen in der theoretischen Informatik.

Typ	Bezeichnung	Erzeugte Sprachen	Erkennendes Maschinenmodell
Typ 0	Unbeschränkte Grammatiken	Rekursiv aufzählbare Sprachen	Turingmaschine
Typ 1	Kontext-sensitive Grammatiken	Kontext-sensitive Sprachen	Linear beschränkter Automat
Typ 2	Kontextfreie Grammatiken	Kontextfreie Sprachen	Kellerautomat
Typ 3	Reguläre Grammatiken	Reguläre Sprachen	Endlicher Automat

Die Hierarchie ist echt gestuft. Jede reguläre Sprache ist auch kontextfrei, jede kontextfreie Sprache ist auch kontextsensitiv, und jede kontextsensitive Sprache ist auch rekursiv aufzählbar. Umgekehrt gilt dies jedoch nicht immer.

Reguläre Sprachen

Reguläre Sprachen sind die einfachste Klasse formaler Sprachen innerhalb der Chomsky-Hierarchie. Sie können durch endliche Automaten, reguläre Ausdrücke oder reguläre Grammatiken beschrieben werden.

Beispiele regulärer Sprachen

Über dem Alphabet $\mathrm{\Sigma }=\{0,1\}$ sind folgende Sprachen regulär:

• Alle Wörter, die mit 0 beginnen.
• Alle Wörter, die eine gerade Anzahl von Einsen enthalten.
• Alle Wörter, die auf 101 enden.
• Alle Wörter mit höchstens drei Zeichen.

Reguläre Ausdrücke

Ein regulärer Ausdruck beschreibt eine reguläre Sprache. Wichtige Operatoren sind:

Operator	Bedeutung
$a$	Das Zeichen $a$
$r\mid s$	Alternative: $r$ oder $s$
$rs$	Konkatenation von $r$ und $s$
$r^{*}$	Beliebig viele Wiederholungen von $r$
$\epsilon$	Leeres Wort

Beispiel:

$(0\mid 1{)}^{*}101$

Dieser reguläre Ausdruck beschreibt alle binären Wörter, die auf 101 enden.

Automatentheorie

Die Automatentheorie untersucht abstrakte Maschinenmodelle. Diese Modelle dienen dazu, formale Sprachen zu erkennen oder Berechnungen zu beschreiben.

Wichtige Automatenmodelle sind:

• endliche Automaten,
• Kellerautomaten,
• linear beschränkte Automaten,
• Turingmaschinen.

Endliche Automaten

Ein endlicher Automat ist ein einfaches Berechnungsmodell mit endlich vielen Zuständen. Er liest ein Eingabewort Zeichen für Zeichen und wechselt abhängig vom aktuellen Zustand und Eingabezeichen in einen neuen Zustand.

Endliche Automaten erkennen genau die regulären Sprachen.

Deterministischer endlicher Automat

Ein deterministischer endlicher Automat, kurz DEA, wird formal beschrieben als:

$A=(Q,\mathrm{\Sigma },\delta ,q_0,F)$

Dabei gilt:

Symbol	Bedeutung
$Q$	Endliche Menge von Zuständen
$\mathrm{\Sigma }$	Eingabealphabet
$\delta$	Übergangsfunktion
$q_0$	Startzustand
$F$	Menge akzeptierender Endzustände

Die Übergangsfunktion hat die Form:

$\delta :Q\times \mathrm{\Sigma }\to Q$

Das bedeutet: Für jeden Zustand und jedes Eingabezeichen ist eindeutig festgelegt, in welchen Folgezustand der Automat wechselt.

Nichtdeterministischer endlicher Automat

Ein nichtdeterministischer endlicher Automat, kurz NEA, darf für einen Zustand und ein Eingabezeichen mehrere mögliche Folgezustände besitzen. Außerdem können sogenannte $\epsilon$-Übergänge erlaubt sein, bei denen der Automat den Zustand wechseln kann, ohne ein Zeichen zu lesen.

Obwohl NEAs auf den ersten Blick mächtiger wirken, erkennen sie genau dieselbe Sprachklasse wie DEAs, nämlich die regulären Sprachen. Jeder NEA kann in einen äquivalenten DEA umgewandelt werden.

Kellerautomaten

Ein Kellerautomat ist ein Automat, der zusätzlich zu seinen Zuständen einen Speicher in Form eines Stapels besitzt. Dieser Stapel wird auch Keller genannt. Ein Kellerautomat kann Symbole auf den Stapel legen und wieder entfernen.

Kellerautomaten erkennen genau die kontextfreien Sprachen.

Ein typisches Beispiel für eine kontextfreie Sprache ist:

$L=\{a^n{b}^n\mid n\ge 0\}$

Diese Sprache ist nicht regulär, weil ein endlicher Automat sich nicht beliebig viele gelesene $a$-Zeichen merken kann. Ein Kellerautomat kann dagegen für jedes gelesene $a$ ein Symbol auf den Stapel legen und für jedes gelesene $b$ wieder ein Symbol entfernen.

Turingmaschinen

Die Turingmaschine ist eines der wichtigsten Modelle der theoretischen Informatik. Sie wurde von Alan Turing eingeführt und dient als mathematisches Modell für allgemeine Berechnung.

Eine Turingmaschine besitzt:

• eine endliche Zustandsmenge,
• ein Eingabeband,
• einen Schreib-/Lesekopf,
• eine Übergangsfunktion,
• Start-, Akzeptier- und Verwerfzustände.

Im Gegensatz zu einem endlichen Automaten kann eine Turingmaschine nicht nur lesen, sondern auch schreiben. Außerdem kann sich der Schreib-/Lesekopf nach links und rechts bewegen.

Bedeutung der Turingmaschine

Die Turingmaschine ist deshalb so wichtig, weil sie als formales Modell für das gilt, was algorithmisch berechenbar ist. Viele moderne Computer sind praktisch viel komplexer als Turingmaschinen, aber im theoretischen Sinn nicht mächtiger: Alles, was ein realer Computer berechnen kann, kann auch eine Turingmaschine berechnen.

Berechenbarkeitstheorie

Die Berechenbarkeitstheorie untersucht, welche Probleme durch Algorithmen lösbar sind. Dabei geht es nicht darum, ob ein Problem effizient lösbar ist, sondern ob überhaupt ein Algorithmus existiert, der für jede zulässige Eingabe eine korrekte Antwort liefert.

Entscheidungsprobleme

Ein Entscheidungsproblem ist ein Problem, dessen Antwort entweder „ja“ oder „nein“ lautet.

Beispiele:

• Ist eine gegebene Zahl eine Primzahl?
• Enthält ein Graph einen Kreis?
• Ist ein gegebenes Wort Element einer bestimmten Sprache?
• Hält ein bestimmtes Programm bei einer bestimmten Eingabe?

Viele Probleme der theoretischen Informatik werden als Entscheidungsprobleme formuliert, weil sie sich gut formal untersuchen lassen.

Entscheidbarkeit

Ein Problem heißt entscheidbar, wenn es eine Turingmaschine gibt, die für jede Eingabe nach endlich vielen Schritten anhält und die korrekte Antwort liefert.

Ein Problem heißt unentscheidbar, wenn kein solcher Algorithmus existiert.

Semi-Entscheidbarkeit

Ein Problem heißt semi-entscheidbar, wenn es eine Turingmaschine gibt, die bei Ja-Instanzen anhält und akzeptiert, bei Nein-Instanzen aber möglicherweise unendlich lange weiterläuft.

Das bedeutet: Positive Fälle können erkannt werden, negative Fälle aber nicht immer zuverlässig.

Das Halteproblem

Das Halteproblem ist ein klassisches Beispiel für ein unentscheidbares Problem.

Es lautet:

Gegeben sei ein Programm $P$ und eine Eingabe $x$. Hält $P$ bei Eingabe $x$ nach endlich vielen Schritten an?

Alan Turing zeigte, dass es keinen allgemeinen Algorithmus geben kann, der dieses Problem für alle Programme und Eingaben korrekt entscheidet.

Bedeutung des Halteproblems

Das Halteproblem zeigt eine fundamentale Grenze der Informatik. Es beweist, dass es Probleme gibt, die grundsätzlich nicht algorithmisch lösbar sind, unabhängig davon, wie schnell oder leistungsfähig ein Computer ist.

Dies ist ein wichtiger Unterschied zur Komplexitätstheorie: Dort geht es um den Aufwand lösbarer Probleme. Beim Halteproblem geht es darum, dass überhaupt keine allgemeine algorithmische Lösung existiert.

Komplexitätstheorie

Die Komplexitätstheorie untersucht den Ressourcenverbrauch von Algorithmen. Besonders wichtig sind dabei:

• Zeitaufwand,
• Speicheraufwand,
• Eingabegröße.

Ein Problem kann also berechenbar sein, aber trotzdem praktisch kaum lösbar, wenn der Aufwand zu groß ist.

Zeitkomplexität

Die Zeitkomplexität beschreibt, wie viele Rechenschritte ein Algorithmus in Abhängigkeit von der Eingabegröße benötigt.

Beispiele:

Notation	Bedeutung	Einordnung
$O(1)$	Konstante Laufzeit	Sehr effizient
$O(\log n)$	Logarithmische Laufzeit	Sehr effizient
$O(n)$	Lineare Laufzeit	Effizient
$O(n\log n)$	Linear-logarithmische Laufzeit	Häufig bei effizienten Sortierverfahren
$O(n^2)$	Quadratische Laufzeit	Für große Eingaben oft problematisch
$O(2^n)$	Exponentielle Laufzeit	Meist praktisch schwer handhabbar

Speicherkomplexität

Die Speicherkomplexität beschreibt, wie viel Speicherplatz ein Algorithmus abhängig von der Eingabegröße benötigt.

Auch hier verwendet man häufig die O-Notation, zum Beispiel:

• $O(1)$ für konstanten Speicher,
• $O(n)$ für linearen Speicher,
• $O(n^2)$ für quadratischen Speicher.

O-Notation

Die O-Notation beschreibt das asymptotische Wachstum einer Funktion. Sie wird verwendet, um den Ressourcenverbrauch eines Algorithmus für große Eingaben abzuschätzen.

Wenn ein Algorithmus beispielsweise eine Laufzeit von

$O(n^2)$

hat, bedeutet das, dass seine Laufzeit höchstens proportional zu $n^2$ wächst, wenn die Eingabegröße $n$ groß wird.

Die O-Notation ignoriert konstante Faktoren und niedrigere Terme. Daher gilt beispielsweise:

$3n^2+5n+7\in O(n^2)$

In der Algorithmusanalyse interessiert man sich also vor allem für den dominierenden Term.

Komplexitätsklassen

Eine Komplexitätsklasse ist eine Menge von Problemen, die unter bestimmten Ressourcenbeschränkungen lösbar sind.

Wichtige Komplexitätsklassen sind:

• P
• NP
• NP-schwer
• NP-vollständig
• PSPACE
• EXPTIME

Die Klasse P

Die Klasse P enthält alle Entscheidungsprobleme, die von einer deterministischen Turingmaschine in polynomialer Zeit entschieden werden können.

Polynomial bedeutet, dass die Laufzeit durch ein Polynom beschränkt ist, zum Beispiel:

• $O(n)$
• $O(n^2)$
• $O(n^3)$

Probleme in P gelten im Allgemeinen als effizient lösbar.

Beispiele für Probleme in P:

• Sortieren einer Liste,
• Kürzeste Wege in Graphen mit nichtnegativen Kantengewichten,
• Testen, ob eine Zahl durch eine andere teilbar ist,
• Erreichbarkeit in bestimmten Graphmodellen.

Die Klasse NP

Die Klasse NP enthält alle Entscheidungsprobleme, deren Ja-Lösungen in polynomialer Zeit überprüft werden können.

Wichtig ist: NP bedeutet nicht „nicht polynomial“. NP steht für nondeterministic polynomial time.

Ein Problem liegt in NP, wenn man eine vorgeschlagene Lösung effizient überprüfen kann.

Beispiel:

Beim Problem des Handlungsreisenden in Entscheidungsform fragt man:

Gibt es eine Rundreise mit Gesamtlänge höchstens $k$?

Wenn jemand eine konkrete Rundreise vorgibt, kann man in polynomialer Zeit prüfen, ob sie alle Städte genau einmal besucht und ob ihre Länge höchstens $k$ beträgt.

NP-schwere Probleme

Ein Problem heißt NP-schwer, wenn jedes Problem aus NP in polynomialer Zeit auf dieses Problem reduziert werden kann.

Anschaulich bedeutet das: Ein NP-schweres Problem ist mindestens so schwer wie alle Probleme aus NP.

Ein NP-schweres Problem muss selbst nicht zwingend in NP liegen. Es kann also auch ein Optimierungsproblem oder sogar ein unentscheidbares Problem sein.

NP-vollständige Probleme

Ein Problem heißt NP-vollständig, wenn zwei Bedingungen erfüllt sind:

1. Das Problem liegt in NP.
2. Das Problem ist NP-schwer.

NP-vollständige Probleme sind die schwierigsten Probleme innerhalb von NP. Wenn man für ein NP-vollständiges Problem einen polynomialen Algorithmus finden würde, dann könnte jedes Problem aus NP in polynomialer Zeit gelöst werden.

P-vs.-NP-Problem

Das P-vs.-NP-Problem ist eines der bekanntesten offenen Probleme der Informatik und Mathematik.

Es fragt:

Gilt $P=NP$ oder $P\ne NP$?

Anders formuliert:

Kann jedes Problem, dessen Lösung effizient überprüfbar ist, auch effizient gelöst werden?

Bis heute ist nicht bekannt, ob $P=NP$ oder $P\ne NP$ gilt. Die meisten Fachleute vermuten, dass $P\ne NP$ gilt.

Reduktionen

Eine Reduktion ist eine Methode, um ein Problem auf ein anderes Problem zurückzuführen.

Wenn ein Problem $A$ auf ein Problem $B$ reduziert werden kann, bedeutet das: Eine Lösung für $B$ kann verwendet werden, um auch $A$ zu lösen.

Formal schreibt man häufig:

$A{\le }_{p}B$

Das bedeutet: $A$ ist in polynomialer Zeit auf $B$ reduzierbar.

Reduktionen sind besonders wichtig, um NP-Schwere oder NP-Vollständigkeit zu zeigen.

Algorithmen

Ein Algorithmus ist eine eindeutige, endliche Handlungsvorschrift zur Lösung eines Problems.

Ein Algorithmus sollte folgende Eigenschaften besitzen:

Eigenschaft	Bedeutung
Eindeutigkeit	Jeder Schritt ist klar definiert
Endlichkeit	Die Beschreibung des Algorithmus ist endlich
Ausführbarkeit	Jeder Schritt kann tatsächlich ausgeführt werden
Terminierung	Der Algorithmus endet nach endlich vielen Schritten
Korrektheit	Der Algorithmus liefert das richtige Ergebnis

In der theoretischen Informatik werden Algorithmen nicht nur implementiert, sondern mathematisch analysiert.

Korrektheit von Algorithmen

Die Korrektheit eines Algorithmus bedeutet, dass er für jede zulässige Eingabe das richtige Ergebnis liefert.

Man unterscheidet:

• partielle Korrektheit,
• totale Korrektheit.

Partielle Korrektheit

Ein Algorithmus ist partiell korrekt, wenn gilt:

Falls der Algorithmus terminiert, liefert er ein korrektes Ergebnis.

Die partielle Korrektheit sagt also noch nichts darüber aus, ob der Algorithmus tatsächlich immer endet.

Totale Korrektheit

Ein Algorithmus ist total korrekt, wenn er partiell korrekt ist und zusätzlich für jede zulässige Eingabe terminiert.

Totale Korrektheit umfasst also:

• Korrektheit des Ergebnisses,
• Terminierung.

Beweismethoden in der theoretischen Informatik

In der theoretischen Informatik spielen mathematische Beweise eine zentrale Rolle. Wichtige Beweismethoden sind:

• direkter Beweis,
• Beweis durch Widerspruch,
• vollständige Induktion,
• strukturelle Induktion,
• Reduktionsbeweis,
• Pumping-Lemma-Beweis.

Vollständige Induktion

Die vollständige Induktion ist eine Beweismethode für Aussagen über natürliche Zahlen.

Ein Induktionsbeweis besteht aus:

1. Induktionsanfang: Die Aussage wird für einen Startwert bewiesen, meist $n=0$ oder $n=1$.
2. Induktionsvoraussetzung: Man nimmt an, dass die Aussage für ein beliebiges $n$ gilt.
3. Induktionsschritt: Man zeigt, dass daraus die Aussage für $n+1$ folgt.

Induktion wird häufig verwendet, um Eigenschaften von Algorithmen, Rekursionen oder formalen Sprachen zu beweisen.

Pumping-Lemma

Das Pumping-Lemma ist ein wichtiges Werkzeug, um zu zeigen, dass eine Sprache nicht regulär ist.

Vereinfacht besagt es:

Wenn eine Sprache regulär ist, dann lassen sich hinreichend lange Wörter dieser Sprache in Teile zerlegen, sodass ein bestimmter Mittelteil beliebig oft wiederholt werden kann und das Wort trotzdem in der Sprache bleibt.

Das Pumping-Lemma wird meist indirekt verwendet:

1. Man nimmt an, eine Sprache sei regulär.
2. Dann müsste das Pumping-Lemma gelten.
3. Man zeigt, dass dies zu einem Widerspruch führt.
4. Also ist die Sprache nicht regulär.

Beispielidee

Die Sprache

$L=\{a^n{b}^n\mid n\ge 0\}$

ist nicht regulär.

Ein endlicher Automat kann nicht beliebig viele $a$-Zeichen zählen, um anschließend genau dieselbe Anzahl von $b$-Zeichen zu überprüfen.

Aussagenlogik

Die Aussagenlogik beschäftigt sich mit Aussagen, die entweder wahr oder falsch sind.

Beispiele für Aussagen:

• „Es regnet.“
• „5 ist eine Primzahl.“
• „Ein Automat akzeptiert das Wort.“

Wichtige logische Operatoren sind:

Symbol	Bedeutung	Beispiel
$\mathrm{\neg }$	Nicht	$\mathrm{\neg }A$
$\wedge$	Und	$A\wedge B$
$\vee$	Oder	$A\vee B$
$\to$	Implikation	$A\to B$
$\leftrightarrow$	Äquivalenz	$A\leftrightarrow B$

Aussagenlogik ist wichtig für Schaltalgebra, Verifikation, Datenbanken und formale Spezifikationen.

Prädikatenlogik

Die Prädikatenlogik erweitert die Aussagenlogik um Variablen, Prädikate und Quantoren.

Wichtige Quantoren sind:

Symbol	Bedeutung
$\mathrm{\forall }$	Für alle
$\mathrm{\exists }$	Es existiert

Beispiel:

$\mathrm{\forall }x\in \mathbb{\mathbb{N}}:x+0=x$

Diese Aussage bedeutet: Für alle natürlichen Zahlen $x$ gilt, dass $x+0=x$ ist.

Mengen, Relationen und Funktionen

Mathematische Grundbegriffe wie Mengen, Relationen und Funktionen sind für die theoretische Informatik unverzichtbar.

Mengen

Eine Menge ist eine Zusammenfassung von unterscheidbaren Objekten.

Beispiel:

$A=\{1,2,3,4\}$

Wichtige Mengenoperationen sind:

Operation	Bedeutung
$A\cup B$	Vereinigung
$A\cap B$	Schnittmenge
$A\setminus B$	Differenz
$A\subseteq B$	Teilmenge

Relationen

Eine Relation beschreibt eine Beziehung zwischen Elementen.

Beispiel:

$R=\{(1,2),(2,3),(3,4)\}$

Relationen sind wichtig für Graphen, Ordnungen, Äquivalenzklassen und Datenbanken.

Funktionen

Eine Funktion ordnet jedem Element einer Definitionsmenge genau ein Element einer Zielmenge zu.

Formal:

$f:A\to B$

Beispiel:

$f(x)=x^2$

Graphentheorie

Die Graphentheorie ist ein wichtiges Hilfsmittel der theoretischen Informatik. Ein Graph besteht aus Knoten und Kanten.

Formal wird ein Graph oft als

$G=(V,E)$

geschrieben.

Dabei ist:

Symbol	Bedeutung
$V$	Menge der Knoten
$E$	Menge der Kanten

Graphen werden verwendet, um Netzwerke, Abhängigkeiten, Zustandsräume, Verkehrsverbindungen oder Datenstrukturen zu modellieren.

Gerichtete und ungerichtete Graphen

Bei einem ungerichteten Graphen haben Kanten keine Richtung.

Bei einem gerichteten Graphen haben Kanten eine Richtung. Eine gerichtete Kante von $u$ nach $v$ wird als $(u,v)$ geschrieben.

Wichtige graphentheoretische Probleme

• Gibt es einen Weg zwischen zwei Knoten?
• Was ist der kürzeste Weg?
• Enthält der Graph einen Kreis?
• Gibt es eine topologische Sortierung?
• Gibt es eine Hamiltonsche Rundreise?
• Ist der Graph färbbar?

Einige dieser Probleme sind effizient lösbar, andere sind NP-vollständig.

Zusammenhang zwischen den Teilgebieten

Die verschiedenen Gebiete der theoretischen Informatik bauen stark aufeinander auf.

Teilgebiet	Zentrale Frage	Beispiel
Formale Sprachen	Wie beschreibt man Mengen von Wörtern?	Syntax einer Programmiersprache
Automatentheorie	Welche Maschinen erkennen welche Sprachen?	Endlicher Automat für ein Suchmuster
Berechenbarkeitstheorie	Was ist überhaupt algorithmisch lösbar?	Halteproblem
Komplexitätstheorie	Wie effizient ist ein Problem lösbar?	P, NP, NP-vollständig
Logik	Wie formalisiert man Aussagen und Beweise?	Programmverifikation
Graphentheorie	Wie modelliert man Beziehungen und Strukturen?	Netzwerke und Abhängigkeiten

Beispiel: Von Sprache zu Automat

Angenommen, es soll die Sprache aller binären Wörter erkannt werden, die auf $01$ enden.

Das Alphabet lautet:

$\mathrm{\Sigma }=\{0,1\}$

Die Sprache ist:

$L=\{w\in \{0,1{\}}^{*}\mid w\text{ endet auf }01\}$

Diese Sprache ist regulär. Sie kann beschrieben werden durch den regulären Ausdruck:

$(0\mid 1{)}^{*}01$

Ein endlicher Automat kann diese Sprache erkennen, indem er sich merkt, ob zuletzt eine 0 gelesen wurde und ob danach eine 1 folgt.

Beispiel: Von Problem zu Komplexitätsklasse

Betrachtet wird das Problem:

Gibt es in einem Graphen einen Weg von Knoten $s$ zu Knoten $t$?

Dieses Problem ist ein Entscheidungsproblem. Es kann mit einer Breitensuche oder Tiefensuche effizient gelöst werden. Die Laufzeit ist linear in der Anzahl der Knoten und Kanten.

Daher gehört das Problem zur Klasse P.

Ein anderes Problem lautet:

Gibt es in einem Graphen einen Kreis, der jeden Knoten genau einmal besucht?

Dies ist das Hamiltonkreisproblem. Es liegt in NP, weil eine vorgeschlagene Lösung effizient überprüft werden kann. Gleichzeitig ist es NP-vollständig, weil es zu den schwierigsten Problemen innerhalb von NP gehört.

Praktische Bedeutung

Obwohl theoretische Informatik abstrakt wirkt, hat sie viele praktische Anwendungen.

Bereich	Bedeutung der theoretischen Informatik
Compilerbau	Formale Grammatiken beschreiben die Syntax von Programmiersprachen
Datenbanken	Relationen, Logik und Anfrageauswertung beruhen auf formalen Grundlagen
Kryptographie	Sicherheit hängt oft von komplexitätstheoretisch schwierigen Problemen ab
Softwareverifikation	Logik wird genutzt, um Programme formal zu prüfen
Netzwerke	Graphen modellieren Verbindungen und Routing
Künstliche Intelligenz	Suchprobleme und Optimierungsprobleme werden formal analysiert
Algorithmik	Laufzeiten und Korrektheit werden mathematisch untersucht

Typische Klausurfragen

Typische Aufgaben in der theoretischen Informatik sind:

• Geben Sie eine formale Grammatik für eine Sprache an.
• Konstruieren Sie einen endlichen Automaten für eine gegebene Sprache.
• Wandeln Sie einen NEA in einen DEA um.
• Zeigen Sie mit dem Pumping-Lemma, dass eine Sprache nicht regulär ist.
• Bestimmen Sie, ob eine Sprache regulär, kontextfrei oder entscheidbar ist.
• Analysieren Sie die Laufzeit eines Algorithmus.
• Ordnen Sie ein Problem einer Komplexitätsklasse zu.
• Zeigen Sie, dass ein Problem NP-schwer oder NP-vollständig ist.
• Beweisen Sie die Korrektheit eines Algorithmus.
• Entscheiden Sie, ob eine logische Formel erfüllbar ist.

Wichtige Begriffe

Begriff	Kurzdefinition
Alphabet	Endliche Menge von Zeichen
Wort	Endliche Folge von Zeichen
Sprache	Menge von Wörtern
Grammatik	Regelsystem zur Erzeugung einer Sprache
Automat	Abstraktes Berechnungsmodell
Reguläre Sprache	Sprache, die durch endliche Automaten erkannt wird
Kontextfreie Sprache	Sprache, die durch Kellerautomaten erkannt wird
Turingmaschine	Allgemeines mathematisches Modell der Berechnung
Entscheidbares Problem	Problem, für das ein Algorithmus immer anhält und korrekt entscheidet
Unentscheidbares Problem	Problem, für das kein allgemeiner Entscheidungsalgorithmus existiert
Komplexitätsklasse	Menge von Problemen mit ähnlichem Ressourcenbedarf
P	Klasse effizient entscheidbarer Probleme
NP	Klasse effizient überprüfbarer Entscheidungsprobleme
NP-schwer	Mindestens so schwer wie alle Probleme aus NP
NP-vollständig	Problem ist sowohl in NP als auch NP-schwer

Zusammenfassung

Die theoretische Informatik untersucht die formalen Grundlagen von Berechnung und Information. Sie beschäftigt sich mit Sprachen, Automaten, Algorithmen, Berechenbarkeit, Komplexität und Logik. Ihre zentrale Bedeutung liegt darin, die Möglichkeiten und Grenzen algorithmischer Verfahren zu verstehen.

Formale Sprachen und Automaten helfen dabei, syntaktische Strukturen und einfache Berechnungsmodelle zu beschreiben. Die Berechenbarkeitstheorie zeigt, welche Probleme grundsätzlich algorithmisch lösbar sind. Die Komplexitätstheorie untersucht, welche lösbaren Probleme effizient lösbar sind und welche vermutlich einen hohen Rechenaufwand benötigen. Logik, Mengenlehre und Graphentheorie liefern die mathematischen Werkzeuge, um diese Fragen präzise zu formulieren und zu beweisen.

Damit ist die theoretische Informatik nicht nur ein abstraktes Grundlagenfach, sondern eine zentrale Basis für viele praktische Bereiche der Informatik.

Siehe auch

• Automatentheorie
• Formale Sprachen
• Reguläre Sprachen
• Kontextfreie Sprachen
• Turingmaschine
• Berechenbarkeit
• Halteproblem
• Komplexitätstheorie
• P
• NP
• NP-schwer
• NP-vollständig
• P versus NP
• Graphentheorie
• Aussagenlogik
• Prädikatenlogik