Hauptseite: Unterschied zwischen den Versionen
Css (Diskussion | Beiträge) (→Kapitel 4: Logik) |
Css (Diskussion | Beiträge) (→Kapitel 2: Berechenbarkeitstheorie) |
||
| (6 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 14: | Zeile 14: | ||
=== Kapitel 1: Automaten === | === Kapitel 1: Automaten === | ||
* [[Deterministische Endliche Automaten]] | * [[Deterministische Endliche Automaten]] | ||
| − | |||
* [[Nichtdeterministische Endliche Automaten]] | * [[Nichtdeterministische Endliche Automaten]] | ||
| − | |||
* [[Reguläre Ausdrücke]] | * [[Reguläre Ausdrücke]] | ||
* [[Pumping Lemma]] | * [[Pumping Lemma]] | ||
* [[Kellerautomaten]] | * [[Kellerautomaten]] | ||
| − | |||
=== Kapitel 2: Berechenbarkeitstheorie === | === Kapitel 2: Berechenbarkeitstheorie === | ||
* [[Deterministische Turingmaschinen]] | * [[Deterministische Turingmaschinen]] | ||
| − | |||
* [[Registermaschinen]] | * [[Registermaschinen]] | ||
* [[Die Universelle Registermaschine]] | * [[Die Universelle Registermaschine]] | ||
| Zeile 33: | Zeile 29: | ||
=== Kapitel 3: Komplexitätstheorie === | === Kapitel 3: Komplexitätstheorie === | ||
| + | * [[Nichtdeterministische Turingmaschinen]] | ||
* [[Zeit- und Platzklassen]] | * [[Zeit- und Platzklassen]] | ||
| − | * [[ | + | * [[L]] |
| + | * [[NL]] | ||
| + | * [[P]] | ||
| + | * [[NP]] | ||
| + | * [[LINSPACE]] | ||
| + | * [[PSPACE]] | ||
=== Kapitel 4: Logik === | === Kapitel 4: Logik === | ||
Aktuelle Version vom 29. August 2018, 17:19 Uhr
MediaWiki wurde installiert.
$\sum\limits_{i=1}^\infty i=-\frac{1}{12}$
Hilfe zur Benutzung und Konfiguration der Wiki-Software findest du im Benutzerhandbuch.
Inhaltsverzeichnis
Index
Kapitel 0: Einführung
Kapitel 1: Automaten
- Deterministische Endliche Automaten
- Nichtdeterministische Endliche Automaten
- Reguläre Ausdrücke
- Pumping Lemma
- Kellerautomaten
Kapitel 2: Berechenbarkeitstheorie
- Deterministische Turingmaschinen
- Registermaschinen
- Die Universelle Registermaschine
- Das Halteproblem
- Entscheidbarkeit
- Orakel
Kapitel 3: Komplexitätstheorie
Kapitel 4: Logik
- Logische Theorien
- Klassische Modelle
- Logische Komplexität
- Der Satz von Fagin
- Der Kalkül des natürlichen Schließens
- Der Vollständigkeitssatz (evtl.)
- Der Unvollständigkeitssatz (evtl.)
- Intuitionistische Logik und Kripkemodelle (evtl.)
