1954874
Description
Flashcards by Joscha Wülk, updated more than 1 year ago
|
Created by Joscha Wülk
almost 10 years ago
|
|
| Question | Answer |
| Definition Alphabet (D3.1) | Ein Alphabet Σ ist eine nichtleere, endliche Menge von Symbolen (=Buchstaben). |
| Wort ü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. |
| Konkatenation 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 |
| Prä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. |
| Σ^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 .... |
| Formale Sprache über Sigma (D3.10) | Sei Σ Alphabet. Eine formale Sprache über Σ(oder: Sprache über Σ) ist eine Teilmenge von Σ*. |
| Entscheidungsproblem 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. |
| Mengenoperationen ( 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} |
| Konkatenation 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 = {} |
| L^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 .... |
| Spiegelung (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 |
| Bindungsstärke | 1. Iteration ( * , +) 2. Konkatenation 3. Mengenoperation |
| Algorithmus ( 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} |
| Hauptsatz 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 .... |
| Turing-Vollständigkeit (5.4) | Ein Berechnungsmodell, mit dem alle Funktionen der Klasse WHILE berechnet werden können, heißt "Turing-vollständig" |
| Mächtigkeitsrelation ( D5.6 ) | Zwei Mengen M,N heißen gleichmächtig, i.S. M ≈ N, falls es eine Bijektion f: M-> N gibt. |
| Endliche Mengen ( D5.7 ) | Eine Menge M heißt endlich, falls ein m ∈ ℕ existiert, sodass M ≈ Nm. Andernfalls heißt M unendlich. |
| Abzä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. |
| Satz 5.10. | Für jedes Alphabet Sigma ist Σ* abzählbar unendlich. |
| Charakteristische 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. |
| Entscheidbarkeit (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. |
| Abschlusseigenschaften ( 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. |
| O-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) |
| Omega-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) |
| Schrittzahlfunktion ( 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. |
| Lä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. |
| Laufzeitfunktion (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 } |
| SORT (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 |
| Subword (7.2) | Eingabe: (w,v) ∈ Σ* x Σ*. Ausgabe: 1, falls x,y ∈ Σ* existieren, so dass w = xvy 0, sonst. |
| 7.3 SOS | Eingabe: (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. |
| MAXIMUM 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. |
| KNAPSACK ( 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) |
| Eingabelä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|. |
| Eingabelä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|. |
| Eingabelä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|. |
| DEA ( 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. |
| Erweiterte Ü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 Σ*. |
| Von 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 } |
| DEAΣ ( 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. |
| DEA-EMPTINESS ( P8.12) | Eingabe: DEA A Ausgabe: 1, falls L(A) = {} 0, sonst. |
| DEA-FINITENESS (P 8.14 ) | Eingabe: DEA A Ausgabe: 1, falls #L(A) endlich, und 0, sonst |
| Kardinalität | Anzahl Elemente einer Menge Bsp.: #{1,2,3} = 3 |
| NEA (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. |
| Erweiterte Ü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 ∈ Σ* |
| Von einem NEA akzeptierte Sprache(D9.6) | Sei A ein NEA. Die von A akzeptierte Sprache ist L(A) = { w ∈ Σ* | δ^(q0,w) ∩ F ≠ ∅} |
| NEAΣ (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. |
| Syntax 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 (α). |
| Semantik 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(α). |
| REGΣ (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. |
| Co-endliche Sprachen (D11.2) | Sei Σ ein Alphabet. Eine Sprache L ⊆ Σ* heisst co-endlich, falls Σ* \ L endlich ist. |
| Pumping 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. |
| Satz 11.8 | Die Sprache L=def {0^l 1^m 2^k | l,m,k ∈ ℕ und l > k} ist nicht regulär |
| Polynomial- 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))). |
| Die 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 } |
| Traveling 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? |
| Die 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) } |
| Satz 14.11 | P ⊆ NP ⊆ EXP |
| Polynomialzeit-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) |
| Lemma 15.4 | ≤pm ist reflexiv und transitiv (Quasiordnung) |
| Lemma 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. |
| NP-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 |
| Satz 15.8. | SOS,TSP, Knapsack, SAT sind NP-vollständig |
| Satisfiability (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. |
| Eigenschaften 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 |
Want to create your own Flashcards for free with GoConqr? Learn more.