THI Definitionen / Sätze / etc.pp

Joscha Wülk
Flashcards by Joscha Wülk, updated more than 1 year ago
Joscha Wülk
Created by Joscha Wülk about 6 years ago
102
1

Description

0 THI Flashcards on THI Definitionen / Sätze / etc.pp, created by Joscha Wülk on 02/03/2015.

Resource summary

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
Show full summary Hide full summary

Similar

SMART School Year Goals
Alice ExamTime
Statistics Equations & Graphs
Andrea Leyden
Edexcel Additional Science Biology Topic 1
hchen8nrd
Crime and Punishment Flashcards - Edexcel GCSE Religious Studies Unit 8
nicolalennon12
Biology -B2
Sian Griffiths
GCSE AQA Physics 1 Energy & Efficiency
Lilac Potato
Repaso prueba Revalida Enfermeria 2016 Parte:2
Rodrigo Lopez
1PR101 2.test - Část 7.
Nikola Truong
Mapas mentales con ExamTime
Nazareth Olivo
3.1 Keywords - Marketing
EMI D
Maths Revision 1- end of year test
Monica Harris