Theoretische Informatik
Grundlagen
Grundlagen
-
- 1 / 31
-
Lernkarten
Assoziativgesetz?
Verknüpfungsgesetz, Klammergesetz
a * ( b * c ) = ( a * b ) * c
Kommutativgesetz?
Vertauschungsgesetz
x * y = y * x
Distributivgesetz?
Verteilungsgesetz
a * ( b + c ) = a * b + a * c
Surjektiv?
x -> y mit alle Bilder y haben ein Urbild in x
Injektiv?
x -> y mit alle Bilder y haben nur ein Urbild x
Bijektiv?
x -> y : f muss injektiv sein, f muss surjektiv sein, f^-1 muss surjektiv sein
Inverse?
wenn x -> y injektiv ist und wenn jedem Bild sein Urbild zugeordnet ist
Hamiltonscher Kreis?
Ein Hamiltonscher Kreis eines Graphen G ist ein geschlossener Weg (Kreis), der jeden Knoten von G genau einmal enthält.
Dreiecksungleichung?
bedeutet, dass
c({u, v}) ≤ c({u, w}) + c({w, v})
für alle Knoten u,v,w von G. Dies ist eine natürliche Eigenschaft, die besagt, dass die direkte Verbindung zwischen u und v nicht teurer sein darf als beliebige Umwege (Verbindungen über andere Knoten).
Knotenüberdeckung eines Graphen?
Eine Knotenüberdeckung eines Graphen G = (V, E) ist jede Knotenmenge U ⊆ V , so dass jede Kante aus E zu mindestens einem Knoten aus U inzident ist.
Eine Kante {u,v} ist inzident zu ihren Endpunkten u und v.
Disjunktion?
zum Beispiel x1 ∨ x3 ∨ x4 ∨ x7
Konjuktion?
z.B. x1 ∧ x2 ∧ x3
Kolmogorov-Komplexität?
Für jedes Wort x ∈ (Σbool)∗ ist die Kolmogorov-Komplexität K(x) des Wortes x das Minimum der binären Längen der Pascal-Programme, die x generieren.
Church’sche These?
Die Turingmaschinen sind die Formalisierung des Begriffes „Algorithmus“, d. h., die Klasse der rekursiven Sprachen (der entscheidbaren Entscheidungs- probleme) stimmt mit der Klasse der algorithmisch (automatisch) erkennbaren Sprachen überein.
Die Church’sche These ist das einzige informatikspezifische Axiom, auf welchem die Theoretische Informatik aufgebaut wird. Alle anderen benutzten Axiome sind die Axiome der Mathematik.
abzählbar?
Eine Menge A heißt abzählbar, falls A endlich ist oder |A| = |N|.
