PhilKa: Die Seite wurde neu angelegt: „{{Infobox Fachgebiet | Name = Grundlagen der Theoretischen Informatik | Gebiet = Informatik | Teilgebiete = Automatentheorie, Formale Sprachen, Berechenbarkeitstheorie, Komplexitätstheorie, Logik | Zentrale Fragen = Was ist berechenbar? Wie effizient ist ein Problem lösbar? Wie lassen sich Sprachen, Automaten und Algorithmen formal beschreiben? }} '''Theoretische Informatik''' ist ein Teilgebiet der Informatik, das sich mit den mathematischen Grundlage…“

2026-04-30T10:05:55Z

Die Seite wurde neu angelegt: „{{Infobox Fachgebiet | Name = Grundlagen der Theoretischen Informatik | Gebiet = Informatik | Teilgebiete = Automatentheorie, Formale Sprachen, Berechenbarkeitstheorie, Komplexitätstheorie, Logik | Zentrale Fragen = Was ist berechenbar? Wie effizient ist ein Problem lösbar? Wie lassen sich Sprachen, Automaten und Algorithmen formal beschreiben? }} '''Theoretische Informatik''' ist ein Teilgebiet der Informatik, das sich mit den mathematischen Grundlage…“

Neue Seite

{{Infobox Fachgebiet
| Name = Grundlagen der Theoretischen Informatik
| Gebiet = Informatik
| Teilgebiete = Automatentheorie, Formale Sprachen, Berechenbarkeitstheorie, Komplexitätstheorie, Logik
| Zentrale Fragen = Was ist berechenbar? Wie effizient ist ein Problem lösbar? Wie lassen sich Sprachen, Automaten und Algorithmen formal beschreiben?
}}

'''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 <math>\Sigma</math> bezeichnet.

Beispiele:

<math>\Sigma = \{0,1\}</math>

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

<math>\Sigma = \{a,b,c\}</math>

Dies ist ein Alphabet mit drei Zeichen.

=== Wort ===

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

Beispiele über dem Alphabet <math>\Sigma = \{0,1\}</math>:

* <math>0</math>
* <math>101</math>
* <math>00110</math>

Das leere Wort wird meist mit <math>\varepsilon</math> 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:

<math>L \subseteq \Sigma^*</math>

Dabei bezeichnet <math>\Sigma^*</math> die Menge aller endlichen Wörter über dem Alphabet <math>\Sigma</math>.

Beispiel:

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

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:

<math>G = (N, T, P, S)</math>

Dabei gilt:

{| class="wikitable"
! Symbol
! Bedeutung
|-
| <math>N</math>
| Menge der Nichtterminalsymbole
|-
| <math>T</math>
| Menge der Terminalsymbole
|-
| <math>P</math>
| Menge der Produktionsregeln
|-
| <math>S</math>
| Startsymbol
|}

=== Beispiel einer Grammatik ===

Gegeben sei die Grammatik:

<math>G = (\{S\}, \{a,b\}, P, S)</math>

mit den Produktionsregeln:

<pre>
S -> aSb
S -> ε
</pre>

Diese Grammatik erzeugt die Sprache:

<math>L = \{a^n b^n \mid n \geq 0\}</math>

Die Sprache enthält also Wörter wie:

<pre>
ε
ab
aabb
aaabbb
aaaabbbb
</pre>

== Chomsky-Hierarchie ==

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

{| class="wikitable"
! 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 <math>\Sigma = \{0,1\}</math> 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:

{| class="wikitable"
! Operator
! Bedeutung
|-
| <math>a</math>
| Das Zeichen <math>a</math>
|-
| <math>r \mid s</math>
| Alternative: <math>r</math> oder <math>s</math>
|-
| <math>rs</math>
| Konkatenation von <math>r</math> und <math>s</math>
|-
| <math>r^*</math>
| Beliebig viele Wiederholungen von <math>r</math>
|-
| <math>\varepsilon</math>
| Leeres Wort
|}

Beispiel:

<math>(0 \mid 1)^*101</math>

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:

<math>A = (Q, \Sigma, \delta, q_0, F)</math>

Dabei gilt:

{| class="wikitable"
! Symbol
! Bedeutung
|-
| <math>Q</math>
| Endliche Menge von Zuständen
|-
| <math>\Sigma</math>
| Eingabealphabet
|-
| <math>\delta</math>
| Übergangsfunktion
|-
| <math>q_0</math>
| Startzustand
|-
| <math>F</math>
| Menge akzeptierender Endzustände
|}

Die Übergangsfunktion hat die Form:

<math>\delta : Q \times \Sigma \rightarrow Q</math>

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 <math>\varepsilon</math>-Ü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:

<math>L = \{a^n b^n \mid n \geq 0\}</math>

Diese Sprache ist nicht regulär, weil ein endlicher Automat sich nicht beliebig viele gelesene <math>a</math>-Zeichen merken kann. Ein Kellerautomat kann dagegen für jedes gelesene <math>a</math> ein Symbol auf den Stapel legen und für jedes gelesene <math>b</math> 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 <math>P</math> und eine Eingabe <math>x</math>. Hält <math>P</math> bei Eingabe <math>x</math> 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:

{| class="wikitable"
! Notation
! Bedeutung
! Einordnung
|-
| <math>O(1)</math>
| Konstante Laufzeit
| Sehr effizient
|-
| <math>O(\log n)</math>
| Logarithmische Laufzeit
| Sehr effizient
|-
| <math>O(n)</math>
| Lineare Laufzeit
| Effizient
|-
| <math>O(n \log n)</math>
| Linear-logarithmische Laufzeit
| Häufig bei effizienten Sortierverfahren
|-
| <math>O(n^2)</math>
| Quadratische Laufzeit
| Für große Eingaben oft problematisch
|-
| <math>O(2^n)</math>
| 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:

* <math>O(1)</math> für konstanten Speicher,
* <math>O(n)</math> für linearen Speicher,
* <math>O(n^2)</math> 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

<math>O(n^2)</math>

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

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

<math>3n^2 + 5n + 7 \in O(n^2)</math>

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:

* <math>O(n)</math>
* <math>O(n^2)</math>
* <math>O(n^3)</math>

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 <math>k</math>?

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 <math>k</math> 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:

# Das Problem liegt in NP.
# 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 <math>P = NP</math> oder <math>P \neq NP</math>?

Anders formuliert:

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

Bis heute ist nicht bekannt, ob <math>P = NP</math> oder <math>P \neq NP</math> gilt. Die meisten Fachleute vermuten, dass <math>P \neq NP</math> gilt.

== Reduktionen ==

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

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

Formal schreibt man häufig:

<math>A \leq_p B</math>

Das bedeutet: <math>A</math> ist in polynomialer Zeit auf <math>B</math> 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:

{| class="wikitable"
! 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:

# '''Induktionsanfang''': Die Aussage wird für einen Startwert bewiesen, meist <math>n = 0</math> oder <math>n = 1</math>.
# '''Induktionsvoraussetzung''': Man nimmt an, dass die Aussage für ein beliebiges <math>n</math> gilt.
# '''Induktionsschritt''': Man zeigt, dass daraus die Aussage für <math>n+1</math> 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:

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

=== Beispielidee ===

Die Sprache

<math>L = \{a^n b^n \mid n \geq 0\}</math>

ist nicht regulär.

Ein endlicher Automat kann nicht beliebig viele <math>a</math>-Zeichen zählen, um anschließend genau dieselbe Anzahl von <math>b</math>-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:

{| class="wikitable"
! Symbol
! Bedeutung
! Beispiel
|-
| <math>\neg</math>
| Nicht
| <math>\neg A</math>
|-
| <math>\land</math>
| Und
| <math>A \land B</math>
|-
| <math>\lor</math>
| Oder
| <math>A \lor B</math>
|-
| <math>\rightarrow</math>
| Implikation
| <math>A \rightarrow B</math>
|-
| <math>\leftrightarrow</math>
| Äquivalenz
| <math>A \leftrightarrow B</math>
|}

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:

{| class="wikitable"
! Symbol
! Bedeutung
|-
| <math>\forall</math>
| Für alle
|-
| <math>\exists</math>
| Es existiert
|}

Beispiel:

<math>\forall x \in \mathbb{N}: x + 0 = x</math>

Diese Aussage bedeutet: Für alle natürlichen Zahlen <math>x</math> gilt, dass <math>x + 0 = x</math> 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:

<math>A = \{1,2,3,4\}</math>

Wichtige Mengenoperationen sind:

{| class="wikitable"
! Operation
! Bedeutung
|-
| <math>A \cup B</math>
| Vereinigung
|-
| <math>A \cap B</math>
| Schnittmenge
|-
| <math>A \setminus B</math>
| Differenz
|-
| <math>A \subseteq B</math>
| Teilmenge
|}

=== Relationen ===

Eine '''Relation''' beschreibt eine Beziehung zwischen Elementen.

Beispiel:

<math>R = \{(1,2), (2,3), (3,4)\}</math>

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:

<math>f : A \rightarrow B</math>

Beispiel:

<math>f(x) = x^2</math>

== Graphentheorie ==

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

Formal wird ein Graph oft als

<math>G = (V,E)</math>

geschrieben.

Dabei ist:

{| class="wikitable"
! Symbol
! Bedeutung
|-
| <math>V</math>
| Menge der Knoten
|-
| <math>E</math>
| 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 <math>u</math> nach <math>v</math> wird als <math>(u,v)</math> 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.

{| class="wikitable"
! 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 <math>01</math> enden.

Das Alphabet lautet:

<math>\Sigma = \{0,1\}</math>

Die Sprache ist:

<math>L = \{w \in \{0,1\}^* \mid w \text{ endet auf } 01\}</math>

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

<math>(0 \mid 1)^*01</math>

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 <math>s</math> zu Knoten <math>t</math>?

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.

{| class="wikitable"
! 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 ==

{| class="wikitable"
! 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]]

== Kategorien ==

[[Kategorie:Theoretische Informatik]]
[[Kategorie:Informatik]]
[[Kategorie:Formale Sprachen]]
[[Kategorie:Automatentheorie]]
[[Kategorie:Komplexitätstheorie]]
[[Kategorie:Berechenbarkeit]]

Grundlagen der Theoretischen Informatik - Versionsgeschichte