GoConqr has a new look! Let us know what you think.

Sign up free

Flashcards

THI Definitionen / Sätze / etc.pp

Joscha Wülk THI 0 German 5.0Average rating 5.0 out of 5 (1 rating) 64 cards

Cards in this deck (64)

  1. 1Definition Alphabet (D3.1)Ein Alphabet Σ ist eine nichtleere,
    endliche Menge von Symbolen (=Buchstaben).
  2. 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.
  3. 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
  4. 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. 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 ....
  6. 6Formale Sprache über Sigma (D3.10)Sei Σ Alphabet. Eine formale Sprache über Σ(oder: Sprache über Σ) ist eine Teilmenge von Σ*.
  7. 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.
  8. 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}
  9. 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 = {}
  10. 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 ....
  11. 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
  12. 12Bindungsstärke1. Iteration ( * , +)
    2. Konkatenation
    3. Mengenoperation
  13. 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}
  14. 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 ....
  15. 15Turing-Vollständigkeit (5.4)Ein Berechnungsmodell, mit dem alle Funktionen der Klasse WHILE berechnet werden können, heißt "Turing-vollständig"
  16. 16Mächtigkeitsrelation ( D5.6 )Zwei Mengen M,N heißen gleichmächtig, i.S. M ≈ N, falls es eine Bijektion f: M-> N gibt.
  17. 17Endliche Mengen ( D5.7 )Eine Menge M heißt endlich, falls ein m ∈ ℕ existiert, sodass M ≈ Nm. Andernfalls heißt M unendlich.
  18. 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.
  19. 19Satz 5.10.Für jedes Alphabet Sigma ist Σ* abzählbar unendlich.
  20. 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.
  21. 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.
  22. 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.
  23. 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)
  24. 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)
  25. 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.
  26. 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.
  27. 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 }
  28. 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
  29. 29Subword (7.2)Eingabe: (w,v) ∈ Σ* x Σ*.
    Ausgabe: 1, falls x,y ∈ Σ* existieren, so dass w = xvy
    0, sonst.
  30. 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.
  31. 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.
  32. 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)
  33. 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|.
  34. 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|.
  35. 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|.
  36. 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.
  37. 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 Σ*.
  38. 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 }
  39. 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.
  40. 40DEA-EMPTINESS ( P8.12)Eingabe: DEA A
    Ausgabe: 1, falls L(A) = {}
    0, sonst.
  41. 41DEA-FINITENESS (P 8.14 )Eingabe: DEA A
    Ausgabe: 1, falls #L(A) endlich, und
    0, sonst
  42. 42KardinalitätAnzahl Elemente einer Menge
    Bsp.: #{1,2,3} = 3
  43. 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.
  44. 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 ∈ Σ*
  45. 45Von einem NEA akzeptierte Sprache(D9.6)Sei A ein NEA. Die von A akzeptierte Sprache ist
    L(A) = { w ∈ Σ* | δ^(q0,w) ∩ F ≠ ∅}
  46. 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.
  47. 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 (α).
  48. 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(α).
  49. 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.
  50. 50Co-endliche Sprachen (D11.2)Sei Σ ein Alphabet. Eine Sprache L ⊆ Σ* heisst co-endlich, falls Σ* \ L endlich ist.
  51. 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.
  52. 52Satz 11.8Die Sprache L=def {0^l 1^m 2^k | l,m,k ∈ ℕ und l > k} ist nicht regulär
  53. 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))).
  54. 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 }
  55. 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?
  56. 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) }
  57. 57Satz 14.11P ⊆ NP ⊆ EXP
  58. 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)
  59. 59Lemma 15.4≤pm ist reflexiv und transitiv (Quasiordnung)
  60. 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.
  61. 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
  62. 62Satz 15.8.SOS,TSP, Knapsack, SAT sind NP-vollständig
  63. 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.
  64. 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

Information

Description
0 THI Flashcards on THI Definitionen / Sätze / etc.pp, created by Joscha Wülk on 03/02/2015.
Created by
Joscha Wülk
Views
129
Rating
Average rating 5.0 out of 5 (1 rating)

Feedback

What is it about?

What do you think of the new look?

How do you like it?