Theoretische Informatik - Definitionen
Definitionen der Theoretische Informatik
Definitionen der Theoretische Informatik
Definition 7.9 - Eingabelänge für Mengen
.
Definition 7.10 - Eingabelänge für Listen
.
Definition 7.12 - Eingabelänge für assoziative Listen
.
Definition 8.2 - DEA
.
Definition 8.5 - Erweiterte Überführungsfunktion DEA
.
Definition 8.7 - Von einem DEA akzeptierte Sprache
.
Definition 8.10 - \(DEA{\mathrm{_\Sigma}}\)
.
Definition 9.2 - NEA
.
Definition 9.4 Erweiterte Überführungsfunktion NEA
.
Definition 9.6 - Von einem NEA akzeptierte Sprache
.
Definition 9.9 - \(NEA \mathrm{_\Sigma}\)
.
Definition 10.2 - Syntax regulärer Ausdrücke
.
Definition 10.3 - Semantik regulärer Ausdrücke
.
Definition 10.6 - \(REG \mathrm{_\Sigma}\)
.
Definition 11.2 - Co-endliche Sprachen
.
Definition 14.1 - Polynomial- und Exponentialzeit
.
Definition 14.2 - Die Klassen P, FP und EXP
.
Definition 15.1 - Polynomialzeit-Many-one-Reduzierbarkeit
.
Definition 15.7 - NP-Vollständigkeit
.
Definition 14.9 - Die Klasse NP
.
Definition 3.1 - Alphabet
.
Definition 3.2 - Wort über Sigma, Länge
.
Definition 3.3 - Konkatenation von Wörtern
.
Definition 3.5 - Präfix, Suffix, Teilwort
.
Definition 3.7 - Sigma^k
.
Definition 3.10 - Formale Sprache über Sigma
.
Definition 3.12 - Entscheidungsproblem für L
.
Definition 3.13 - Mengenoperationen
.
Definition 3.15 - Konkatenation von Sprachen
.
Definition 3.17 - \({L^k}\)
.
Definition 3.19 - Spiegelung
.
Definition 5.1 - Algorithmus, WHILE-berechnb. Fkt.
.
Definition 5.4 - Turing-Vollständigkeit
.
Definition 5.6 - Mächtigskeitsrelation
.
Definition 5.7 - Endlische Mengen
.
Definition 5.8 - Abzählbare Mengen
.
Definition 5.16 - Charakteristische Funktion
.
Definition 5.17 - Entscheidbarkeit
.
Definition 6.1 - O-Notation
.
Definition 6.3 - \({\Omega}-Notation\)
.
-
- 1 / 43
-
Cartes-fiches
Definition 15.1 - Polynomialzeit-Many-one-Reduzierbarkeit
.
Definition 15.7 - NP-Vollständigkeit
.
Definition 14.9 - Die Klasse NP
.
