Theoretische Informatik
Begriffe zur Vorlesung "Theoretische Informatik" an der ETHZ, HS18
Begriffe zur Vorlesung "Theoretische Informatik" an der ETHZ, HS18
-
- 1 / 35
-
Cartes-fiches
Alphabet
Endliche nichtleere Meenge E (Epsilon)
Buchstaben (Zeichen, Symoble)
Elemente eines Alphabets
Wort
Endliche, eventuell leere Folge von Buchstaben aus dem Alphabet
leeres Wort
λ, leere Buchstabenfolge (in jedem Alphabet enthalten)
Länge eines Wortes
|w|: Anzahl Buchstaben in w (|λ| = 0)
Σ*
Menge aller Wörter über Σ
Σ+
Σ* - {λ}
Konkatenation (von Wörtern)
Verkettung für ein Alphabet Σ ist eine Abbildung Kon: Σ*xΣ* -> Σ*
Umkehrung (Reversal) von a
a^R (alle Buchstaben in umgekehrter Reihenfolge)
Teilwort
v heisst ein Teilwort von w <=> w = xvy
Präfix
v heisst Präfix von w <=> w = vy
Suffix
v heisst ein Suffix von w <=> w = xy
echtes Teilwort
v (nicht λ) heisst echtes Teilwort von w <=> v != w und v Teilwort von w
|x|a
Anzahl der Vorkommen von a in x
Kardinalität
|A| (Anzahl Elemente in einer Menge)
Potenzmenge
P(A) = {S|S ist Teilmenge von A}
kanonische Ordnung
kurze Wörter zuerst, gleiche Wörter lexikographisch geordnet
Sprache
L, Teilmenge von Σ*
Komplement
LC = Σ* - L
Leere Sprache
L = {}
Konkatenation von Sprache
L1*L2 = {vw| v von L1 und w von L2}
Kleene'scher Stern von L
L*
Homomorphismus
Ein Homomorphismus von Σ1* nach Σ2* ist jede Funktion h: Σ1* -> Σ2* mit den Eigenschaften (i) h(λ) = λ (ii) h(uv) = h(u)+h(v)
Äquivalenz zweier Algorithmen
Zwei Algorithmen A und B sind äquivalent, wenn sie über dem gleichen Eingabealphabet arbeiten und A(x) = B(x)
rekursiv
Eine Sprache, wenn ein Algorithmus existiert, welcher die Sprache erkennt
Optimierungsproblem
Ein 6-Tupel U (Σ1, Σ0, L, M, cost, goal)
(i) Σ1: Eingabealphabet
(ii) Σ0: Ausgabealphabet
(iii) L: Sprache der zulässigen Eingaben
(iv) M: Menge der zulässigen Lösungen für x
(v) cost: Kostenfunktion
(vi) goal ist das Optimierungsziel (entweder min oder max)
optimale Lösung eines Optimierungsproblems
eine Lösung heisst optimal, wenn cost = goal
Knotenüberdeckung
Jede Knotenmenge U, so dass jede Kante aus E zu mindestens einem Knoten aus U inzident ist
Klausel
beliebige endliche Disjunktion von Literalen
Konjunktive Nornmalform (KNF)
Verundung von Veroderungen
Aufzählungsalgorithmus
Ein Algorithmus, der für jede Eingabe n die kanonisch n ersten Wörter ausgibt (Sprache L ist rekursiv <=> es existiert ein Aufzählungsalgorithmus für L
Kolmogorov-Komplexität
K(x): das Minimum der binären Längen der Pascal-Programme, die x generieren
K(n) der natürlichen Zahlen
K(n) = K(Bin(n))
Lemma 2.5
Es existiert für jede Zahl n ein nichtkomprimierbares Word der Länge n)
Primzahlsatz
lim(n->inf) Prim(n) / n/ln n = 1
