|
Erstellt von Joscha Wülk
vor mehr als 9 Jahre
|
|
Definition Alphabet (D3.1)
Wort über Sigma, Länge (D3.2)
Konkatenation von Wörtern (D3.3.)
Präfix, Suffix, Teilwort ( D3.5 )
Σ^k ( D3.7 )
Formale Sprache über Sigma (D3.10)
Entscheidungsproblem für L (D3.12)
Mengenoperationen ( D3.13 )
Konkatenation von Sprachen ( D3.15 )
L^k ( D3.17 )
Spiegelung (D3.19)
Bindungsstärke
Algorithmus ( D5.1 )
Hauptsatz der Algorihmentheorie ( S5.2 )
Turing-Vollständigkeit (5.4)
Mächtigkeitsrelation ( D5.6 )
Endliche Mengen ( D5.7 )
Abzählbare Mengen ( D5.8 )
Satz 5.10.
Charakteristische Funktion ( D5.16 )
Entscheidbarkeit (D5.17)
Abschlusseigenschaften ( S5.19 )
O-Notation ( D6.1)
Omega-Notation ( D6.3)
Schrittzahlfunktion ( 6.9 )
Länge, Eingabelänge (D6.11)
Laufzeitfunktion (D6.14)
SORT (Problem 7.1)
Subword (7.2)
7.3 SOS
MAXIMUM KNAPSACK (P7.5)
KNAPSACK ( P 7.7)
Eingabelänge für Mengen ( D7.9 )
Eingabelänge für Listen (D7.10)
Eingabelänge für assoziative Listen ( D7.12)
DEA ( D8.2)
Erweiterte Überführungsfunktion DEA (D8.5)
Von einem DEA akzeptierte Sprache ( D8.7)
DEAΣ ( D8.10)
DEA-EMPTINESS ( P8.12)
DEA-FINITENESS (P 8.14 )
Kardinalität
NEA (D9.2)
Erweiterte Überführungsfunktion NEA (D9.4)
Von einem NEA akzeptierte Sprache(D9.6)
NEAΣ (D9.9)
Syntax regulärer Ausdrücke (D10.2)
Semantik Regulärer Ausdrücke (D10.3)
REGΣ (D10.6)
Co-endliche Sprachen (D11.2)
Pumping Lemma für reg. Sprachen (Lemma 11.6)
Satz 11.8
Polynomial- und Exponentialzeit (D14.1)
Die Klassen P, FP und EXP (D 14.2)
Traveling Salesman - TSP (P14.8)
Die Klasse NP(D14.9)
Satz 14.11
Polynomialzeit-Many-one-Reduzierbarkeit (D15.1)
Lemma 15.4
Lemma 15.5.
NP-Vollständigkeit (D15.7)
Satz 15.8.
Satisfiability (SAT) (P15.9)
Eigenschaften NP-vollst. Probleme (Satz 15.10)