Fichas
THI Definitionen / Sätze / etc.pp
Fichas del conjunto (64)
- 1Definition Alphabet (D3.1)Ein Alphabet Σ ist eine nichtleere,
endliche Menge von Symbolen (=Buchstaben). - 2Wort über Sigma, Länge (D3.2)Sei Σ ein Alphabet. Ein Wort über Σ ist eine endliche Folge von Symbolen aus Σ, also w= a0,a1... am-1 mit m >= 0 und ai ∈ Σ.
Die Länge eines Wortes ist die Anzahl der Positionen. Falls w = a0 a1 ... am-1 mit m>= 0, dann ist |w| = m.
Leeres Wort hat Länge 0 und wird mit ε bezeichnet. - 3Konkatenation von Wörtern (D3.3.)Seien w= a0...am-1 und v=b0 ... bk-1 mit m,k >= 0 zwei Wörter über Alphabet Σ.
Die Konkatenation von w und v ist das Wort wv = a0... am-1 b0... bk-1.
w ε = ε w = w
w^n = n-fache Konkatenation mit sich selbst.
Im Fall n=0 gilt w^0 = epsilon - 4Präfix, Suffix, Teilwort ( D3.5 )w ist Wort über Alphabet Σ. Das Wort y ist Teilwort von w, falls Wörter x, z existieren, sodass w = xyz.
Gilt zusätzlich, dass x = ε, dann heißt y Präfix von w. Falls z = ε, dann heißt y Suffix von w. - 5Σ^k ( D3.7 )Sei Σ ein Alphabet und k>= 0. Dann ist Σ^k = def { w | w Wort über Σ mit |w| = k}
die Menge aller Wörter der Länge k über Σ und
Σ* =def Σ^0 ∪ Σ^1 .... - 6Formale Sprache über Sigma (D3.10)Sei Σ Alphabet. Eine formale Sprache über Σ(oder: Sprache über Σ) ist eine Teilmenge von Σ*.
- 7Entscheidungsproblem für L (D3.12)Sei L eine fest vorgegebene Sprache über Σ. Das Entscheidungsproblem für L ist folgende Aufgabe:
Eingabe: w ∈ Σ*
Ausgabe: 1, falls w ∈ L
0, falls w ∉ L. - 8Mengenoperationen ( D3.13 )Seien L und L' Sprachen über dem gleichen Alphabet Σ. Dann ist
L ∪L' =def { w ∈ Σ* | w E L oder w E L'}
L ∩ L' =def { w ∈ Σ* | w E L und w E L'}
L(quer) =def { w ∈ Σ* | w ∉ L} - 9Konkatenation von Sprachen ( D3.15 )Seien L1, L2 Sprachen über einem Alphabet Σ. Dann ist
L1 * L2 =def {wv ∈ Σ* | w ∈ L1 und v ∈ L2}
die Konkatenation von L1 mit L2
L* {} = {} * L = {} - 10L^k ( D3.17 )Sei L ⊆ Σ*. Dann ist
L^0 =def { ε }
L^k+1=def L^k * L für k>=0.
und
L*=def L^0 ∪ L^1 ∪ L^2 .... - 11Spiegelung (D3.19)Sei w=a0a1... am-1 ∈ Σ* und L ⊆ Σ*. Dann ist
w^R =def am-1 am-2 ... a0
die Spiegelung von w
und
L^R =def {w^R | w ∈ L}
die Spiegelung von L - 12Bindungsstärke1. Iteration ( * , +)
2. Konkatenation
3. Mengenoperation - 13Algorithmus ( D5.1 )Sei m >=0
1. Ein Algorithmus ist ein WHILE-Programm.
2. Eine Funktion φ : ℤ^m -> ℤ heißt WHILE-berechenbar, wenn es ein WHILE-Programm gibt, das φ berechnet.
3. WHILE=def {φ: ℤ^m -> ℤ |φ WHILE-berechenbar} - 14Hauptsatz der Algorihmentheorie ( S5.2 )Für eine Funktion phi: ℤ^m -> ℤ sind die folgenden Aussagen äquivalent:
(1) φ ist WHILE-berechenbar.
(2) φ ist von einer Turingmaschine berechenbar
(3) φ ist von einer Registermaschine berechenbar
(4) φ ist mit einem Quantencomputer berechenbar .... - 15Turing-Vollständigkeit (5.4)Ein Berechnungsmodell, mit dem alle Funktionen der Klasse WHILE berechnet werden können, heißt "Turing-vollständig"
- 16Mächtigkeitsrelation ( D5.6 )Zwei Mengen M,N heißen gleichmächtig, i.S. M ≈ N, falls es eine Bijektion f: M-> N gibt.
- 17Endliche Mengen ( D5.7 )Eine Menge M heißt endlich, falls ein m ∈ ℕ existiert, sodass M ≈ Nm. Andernfalls heißt M unendlich.
- 18Abzählbare Mengen ( D5.8 )Eine Menge M heißt abzählbar unendlich, falls M ≈ IN. Eine Menge heißt abzählbar, falls sie endlich oder abzählbar unendlich ist. Andernfalls heißt die Menge überabzählbar.
- 19Satz 5.10.Für jedes Alphabet Sigma ist Σ* abzählbar unendlich.
- 20Charakteristische Funktion ( D5.16 )Sei A ⊆ G . Die Funktion cA : G-> {0,1} mit
cA(x) =def { 1 falls x ∈ A
{ 0 falls x ∉ A
für alle x ∈ G heißt charakteristische Funktion von A. - 21Entscheidbarkeit (D5.17)Eine Menge A ⊆ G heißt genau dann entscheidbar, wenn ihre charakteristische Funktion cA berechenbar ist.
Mit REC bezeichnen wir die Klasse aller entscheidbaren Mengen. - 22Abschlusseigenschaften ( S5.19 )1. Jede endliche Menge ist entscheidbar (einschl. {} )
2. Das Komplement einer entscheidbaren Menge ist entscheidbar.
3. Vereinigung und Durchschnitt entscheidbarer Mengen sind entscheidbar. - 23O-Notation ( D6.1)Seien f,g zwei totale Funktionen von ℕ nach ℕ. Dann heißt g asymptotisch obere Schranke von f, falls Konstanten c > 0 und n0
∈ ℕ existieren, sodass für alle n>= n0 gilt
f(n) <= c*g(n) - 24Omega-Notation ( D6.3)f,g Funktionen von ℕ nach ℕ.
g ist asymptotisch untere Schranke von f, falls Konstanten c > 0 und n0 ∈ ℕ, so dass für alle n >= n0 gilt,
f(n) >= c* g(n).
Mit Ω(g) bezeichnet man die Menge aller Funktionen mit asymptotisch unterer Schranke g. Wir schreiben f E Θ(g), falls f E O(g) und f E Ω(g) - 25Schrittzahlfunktion ( 6.9 )Sei M ein WHILE-Programm, das eine totale Funktion f : ℤ^m -> ℤ berechnet (und damit immer anhält). Die Schrittzahlfunktion von M bei Eingabe x1, ... xm ∈ ℤ ist
STEPm : ℤ^m -> ℕ
mit STEPm (x1, .... , xm) =def Rechenschritte von M bei Eingabe ( x1, ... , xm) bis zum Stopp. - 26Länge, Eingabelänge (D6.11)Für alle x ∈ ℤ ist |x| =def |bin(abs(x))| die Länge von x.
Für Eingaben x = (x1,x2 ... xm ) ∈ ℤ^m ist
|x| =def |x1| + |x2| + |xm|
Die Eingabelänge wird einheitlich mit n bezeichnet. - 27Laufzeitfunktion (D6.14)Sei M ein WHILE-Programm, das eine totale Funktion f: ℤ^m -> ℤ berechnet. Die Laufzeitfunktion von M ist
TIMEm : ℕ -> ℕ
mit
TIMEm(n) =def max{STEPm (x) | |x| = n } - 28SORT (Problem 7.1)Eingabe: a0, .... am-1) mit m ∈ ℕ und ai ∈ ℤ.
Ausgabe: Eine Permutation (b0, .... , bm-1 ) von ( a0, ... , am-1 ) mit bi <= bi+1 für alle 0 <= i <= m-2 - 29Subword (7.2)Eingabe: (w,v) ∈ Σ* x Σ*.
Ausgabe: 1, falls x,y ∈ Σ* existieren, so dass w = xvy
0, sonst. - 307.3 SOSEingabe: (a0, .... , am-1) , k mit m, ai , k ∈ ℕ.
Frage: Gibt es I ⊆ { 0, ...., m-1} mit Σi∈I ai = k?
==Kombination der Elemente, sodass die Summe = k ist. - 31MAXIMUM KNAPSACK (P7.5)EIngabe: m Gegenstände mit Größen s0,... ∈ ℕ
und Werten v0, .... ∈ ℕ, sowie eine Maximalgröße S ∈ ℕ.
Lösung: Eine Auswahl I ⊆ { 0, .... , m-1} der Gegenstände, sodass Summe(i ∈ I si <= S).
Maß: Σ i ∈ I v i. - 32KNAPSACK ( P 7.7)Eingabe: m Gegenstände, mit Größen s ∈ ℕund v ∈ ℕ, und Maximalgröße S und k ∈ ℕ.
Frage: Existiert I ⊆ { 0, ... , m-1} mit Σ(i ∈ I si ≤ S) und Σ(i ∈ I vi ≥ k) - 33Eingabelänge für Mengen ( D7.9 )Für eine endliche Menge A = {e0, e1, ... , em-1} ist die Länge von A definiert als |A| =def Σ(i=0, m-1) |ei|.
- 34Eingabelänge für Listen (D7.10)Für eine Liste l= [b0,b1, ... , bm-1] ist die Länge von l definiert als |l| =def Σ(i=0, m-1) |bi|.
- 35Eingabelänge für assoziative Listen ( D7.12)Sei d = {k0: v0 , k1:v1 , .... km-1: vm-1} eine assoziative Liste. Die Länge von d ist definiert als |d| =def Σ(i=0, m-1) |ki| + |vi|.
- 36DEA ( D8.2)Ein DEA A ist ein 5 Tupel
A = (Q, Σ, δ, q0, F)
wobei gilt:
Q ist eine endliche Menge von Zuständen.
Σ ist ein Alphabet.
δ ist die Überführungsfunktion von A. Sie bildet ab von Q x Σ nach Q und ist eine totale Abbildung.
q0 ist eine Element aus Q, der Startzustand.
F ist eine Teilmenge von Q, die Menge der akzeptierenden Zustände. - 37Erweiterte Überführungsfunktion DEA (D8.5)Die erweiterte Überführungsfunktion δ^ (Delta Dach) eines DEA A = (Q, Σ, δ, q0, F) ist eine Abbildung
δ^: Q x Σ* -> Q
mit
(IA) δ^(q, ε) =def q für alle q E Q, und
(IS) δ^(q, wa) =def δ(δ^(q,w),a) für alle q E Q, a E Σ und w E Σ*. - 38Von einem DEA akzeptierte Sprache ( D8.7)Sei A= ( Q, Σ , δ, q0, F) ein DEA. Die von A akzeptierte Sprache ist
L(A) = { w E Σ* | δ^ (q0, w) E F } - 39DEAΣ ( D8.10)Sei Σ ein Alphabet. Eine Sprache L ⊆ Σ* ist in der Klasse DEAΣ genau dann, wenn ein DEA A mit Eingabealphabet Σ existiert, so dass L(A) = L.
- 40DEA-EMPTINESS ( P8.12)Eingabe: DEA A
Ausgabe: 1, falls L(A) = {}
0, sonst. - 41DEA-FINITENESS (P 8.14 )Eingabe: DEA A
Ausgabe: 1, falls #L(A) endlich, und
0, sonst - 42KardinalitätAnzahl Elemente einer Menge
Bsp.: #{1,2,3} = 3 - 43NEA (D9.2)Ein nichtdeterministischer endlicher Automat (NEA) A ist ein 5-Tupel
A= ( Q, Σ, δ, q0, F)
wobei gilt:
Q: endliche Menge von Zuständen
Σ: Alphabet
δ: Q x Σ -> P(Q) ist die totale Überführungsfunktion. Sie bildet ab in die Potenzmenge von Q.
q0: Startzustand
F ist eine Teilmenge von Q, die Menge der akzeptierenden Zustände. - 44Erweiterte Überführungsfunktion NEA (D9.4)Die erweiterte Überführungsfunktion δ^ eines NEA ist eine Abbildung:
δ^ : Q x Σ* -> P(Q)
mit
(IA) δ^(q, ε ) =def {q} für alle q ∈ Q und
(IS) δ^(q, wa ) =def ∪p∈δ^(q, w ) δ(p,a) für alle q ∈ Q, a ∈ Σ und w ∈ Σ* - 45Von einem NEA akzeptierte Sprache(D9.6)Sei A ein NEA. Die von A akzeptierte Sprache ist
L(A) = { w ∈ Σ* | δ^(q0,w) ∩ F ≠ ∅} - 46NEAΣ (D9.9)Sei Σ ein Alphabet. Eine Sprache L ⊆ Σ* ist in der Klasse NEAΣ genau dann, wenn ein NEA A mit Eingabealphabet Σ existiert, so dass L(A) = L.
- 47Syntax regulärer Ausdrücke (D10.2)Ein regulärer Ausdruck über Σ ist eine Zeichenfolge über dem Alphabet Σ ∪ { +, .(Konkatenation) , * , ( , ) , ε, ∅}, die wie folgt gebildet werden kann:
(IA) Für alle a ∈ Σ sind a, sowie ε und ∅ reguläre Ausdrücke.
(IS) Sind α und β reguläre Ausdrücke, dann auch α + β, αβ, α* und (α). - 48Semantik Regulärer Ausdrücke (D10.3)Sei γ ein regulärer Ausdruck über Σ. Dann bezeichnet L(γ) ⊆ Σ* die von γ beschriebene Sprache.
(IA)Falls γ = a für a ∈ Σ, dann ist L(γ) =def {a}
Falls γ = ε, dann ist L(γ) =def {ε}
Falls γ = ∅, dann ist L(γ) =def ∅
(IS)
Falls γ = α + β, dann ist L(γ) =def L(α)
∪ L(β).
Falls γ = αβ, dann L(γ) =def L(α)
* L(β).
Falls γ = α*, dann ist L(γ) =def L(α)*.
Falls γ = (a), dann ist L(γ) =def L(α). - 49REGΣ (D10.6)Sei Σ ein Alphabet. Eine Sprache L ⊆ Σ* ist in der Klasse RegΣ genau dann, wenn ein regulärer Ausdruck α über Σ existiert, sodass L(α) = L.
- 50Co-endliche Sprachen (D11.2)Sei Σ ein Alphabet. Eine Sprache L ⊆ Σ* heisst co-endlich, falls Σ* \ L endlich ist.
- 51Pumping Lemma für reg. Sprachen (Lemma 11.6)Sei L eine reguläre Sprache. Dann existiert eine Konstante n ∈ ℕ+ ( die von L abhängt), sodass für jedes Wort w ∈ L mit |w| ≥ n gilt:
Es gibt Teilwort x, y, z mit w = xyz, sodass
(1) y ≠ ε,
(2) |xy| ≤ n und
(3) für alle i ≥ 0 ist xy^i z ∈ L. - 52Satz 11.8Die Sprache L=def {0^l 1^m 2^k | l,m,k ∈ ℕ und l > k} ist nicht regulär
- 53Polynomial- und Exponentialzeit (D14.1)Ein Algorithmus M berechnet eine Funktion
->in Polynomialzeit, falls ein Polynom p existiert, sodass TIMEm(n) ∈ O(p(n)),
->in Exponentialzeit, falls ein Polynom p existiert, so dass TIMEm(n) ∈ O(2^(p(n))). - 54Die Klassen P, FP und EXP (D 14.2)Nicht Teil der Definition: "G ist irgendeine der Grundmengen Σ, oder ℤ^m oder ℕ^m für ein m ≥ 0"
P=def { A ⊆ G | es existiert ein Algorithmus M, der A in Polynomialzeit entscheidet}
FP=def { f: G^m -> G | es existiert ein Algorithmus M, der f in Polynomialzeit berechnet}
EXP=def { A ⊆ G | es existiert ein Algorithmus M, der A in Exponentialzeit entscheidet } - 55Traveling Salesman - TSP (P14.8)Eingabe: Eine vollständige m x m - Distanzmatrix D(i,j) ∈ ℕ für m Orte und k ∈ ℕ.
Frage: Gibt es eine Rundreise durch alle Orte mit Distanz ≤ k? - 56Die Klasse NP(D14.9)NP=def { A ⊆ G |es existieren ein Polynom p und ein Polzeit-Entscheidungsalgorithmus V mit
x ∈ A <-> ∃y ( |y| ≤ p(|x|) ∧ V(x,y) =1) } - 57Satz 14.11P ⊆ NP ⊆ EXP
- 58Polynomialzeit-Many-one-Reduzierbarkeit (D15.1)Eine Menge A ist auf B Polynomialzeit-Many-one-reduzierbar, i.S. A ≤pm B, falls eine Funktion f ∈ FP existiert, sodass für alle x gilt:
x ∈ A ⇔ f(x) ∈ B.
Falls A A ≤pm B und B ≤pm A schreiben wir A ≡pm B (Polynomialzeit-Many-one-Äquivalenz) - 59Lemma 15.4≤pm ist reflexiv und transitiv (Quasiordnung)
- 60Lemma 15.5.1. Ist A ≤pm B und B ∈ P, dann ist auch A ∈ P.
2. Ist A ≤pm B und B ∈ NP, dann ist auch A ∈ NP. - 61NP-Vollständigkeit (D15.7)Eine Menge B heißt NP-vollständig genau dann, wenn
1. B ∈ NP und
2. für alle A ∈ NP gilt A ≤pm B - 62Satz 15.8.SOS,TSP, Knapsack, SAT sind NP-vollständig
- 63Satisfiability (SAT) (P15.9)Eingabe: Eine aussagenlog. Formel F(x0, ... , xm-1) mit Booleschen Var. V= {x0, ... , xm-1}.
Ausgabe: 1, falls für F eine erfüllende Wahrheitswerte-Belegung f: V -> {0,1} existiert,
0, sonst. - 64Eigenschaften NP-vollst. Probleme (Satz 15.10)1. Ist B NP-vollständig, B ≤pm A und A ∈ NP, dann ist A ebenfalls NP-vollständig.
2. Für je zwei NP-vollständige Mengen A und B gilt A ≡pm B.
3. Für jede NP-vollständige Menge A gilt
A ∈ P ⇔ P = NP
Información
- Descripción
- 0 THI Fichas sobre THI Definitionen / Sätze / etc.pp, creado por Joscha Wülk el 03/02/2015.
- Creado por
- Joscha Wülk
- Visitas
- 129
- Valoración