Lernkarten

Karten 31 Karten
Lernende 3 Lernende
Sprache Deutsch
Stufe Universität
Erstellt / Aktualisiert 13.08.2020 / 22.01.2021
Lizenzierung Namensnennung - Nicht-kommerziell - Keine Bearbeitung (CC BY-NC-ND)     (n.a.)
Weblink
Einbinden
0 Exakte Antworten 31 Text Antworten 0 Multiple Choice Antworten
Fenster schliessen

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).

Fenster schliessen

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.

Fenster schliessen

Disjunktion?

zum Beispiel x1 x3 x4 x7

Fenster schliessen

Konjuktion?

z.B. x1 ∧ x2 ∧ x3

Fenster schliessen

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.

Fenster schliessen

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.

Fenster schliessen

abzählbar?

Eine Menge A heißt abzählbar, falls A endlich ist oder |A| = |N|.