THI Definitionen / Sätze / etc.pp

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)