Theoretische Informatik
Grundlagen
Grundlagen
Fichier Détails
| Cartes-fiches | 31 |
|---|---|
| Langue | Deutsch |
| Catégorie | Informatique |
| Niveau | Université |
| Crée / Actualisé | 13.08.2020 / 22.01.2021 |
| Lien de web |
https://card2brain.ch/box/20200813_sieben_wunder_der_informatik
|
| Intégrer |
<iframe src="https://card2brain.ch/box/20200813_sieben_wunder_der_informatik/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Definieren?
bedeutet, so genau zu beschreiben, dass jede und jeder, der noch nie einen ... gesehen hat, anhand dieser Beschreibung für jeden Gegenstand eindeutig entscheiden kann, ob es ein ... ist oder nicht. In der Definition dürfen nur Wörter (Begriffe) verwendet werden, deren Bedeutung schon vorher festgelegt wurde.
Axiome?
sind Grundbausteine der Wissenschaft. Es sind Tatsachen oder Begriffsspezifikationen, von deren Wahrhaftigkeit und Korrektheit wir fest überzeugt sind, obwohl es keine Möglichkeit gibt, ihre Korrektheit zu beweisen.
A ⇒ B
A impliziert B
Wenn A wahr ist (wenn A gilt), dann ist auch B wahr (dann gilt B). In anderen Worten, die Unwahrheit kann nicht die Folgerung aus einer Wahrheit sein.
Direkte Beweise?
Folgen korrekter Folgerungen.
Beweise "A ⇒ C"! Wenn "A ⇒ B und B ⇒ C" dann "A ⇒ B ⇒ C" also "A ⇒ C"
Was ist eine Methode?
Eine Methode zur Lösung einer Aufgabe ist eine Beschreibung einer Vorgehensweise, die zur Lösung der Aufgabe führt. Die Beschreibung besteht aus einer Folge von Instruktionen, die für jeden (auch einen Nichtmathematiker) durchführbar sind.
Algorithmus?
Lösungsmethode
Programmieren?
Bezeichnet die Tätigkeit, in der wir Algorithmen in Programme umschreiben
Mächtigkeit einer Menge |A|?
Kardinalität von A. Die Anzahl der Elemente in A.
Menge A?
Eine Menge ist eine Sammlung von Objekten (Elementen), die paarweise unterschiedlich sind.
unendlich?
Eine Menge A ist genau dann unendlich, wenn eine echte Teilmenge B von A existiert, so dass |A| = |B| (Kardinalität, Mächtigkeit ist gleich)
Ein Objekt ist unendlich, wenn es einen echten Teil des Objektes gibt, der genau so groß wie das ganze Objekt ist.
Alphabet?
Eine endliche nichtleere Menge Σ heißt Alphabet. Die Elemente eines Alphabets werden Buchstaben (Zeichen, Symbole) genannt.
Was ist Informatik?
„Informatik ist die Wissenschaft von der algorithmischen Darstellung, Erkennung, Verarbeitung, Speicherung und Übertragung von Information.“
Σ∗ ?
ist die Menge aller Wörter über Σ, Σ+= Σ∗ − {λ}.
Das leere Wort λ ist die leere Buchstabenfolge. (Manchmal benutzt man ε statt λ.)
Boole’schen Operationen ¬
Negation
Boole’schen Operationen ∨
Disjunktion
Boole’schen Operationen ∧
Konjunktion
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|.
