Theoretische Informatik

Verknüpfungsgesetz, Klammergesetz

a * ( b * c ) = ( a * b ) * c

Vertauschungsgesetz

x * y = y * x

Verteilungsgesetz

a * ( b + c ) = a * b + a * c

x -> y mit alle Bilder y haben ein Urbild in x

x -> y mit alle Bilder y haben nur ein Urbild x

x -> y : f muss injektiv sein, f muss surjektiv sein, f^-1 muss surjektiv sein

wenn x -> y injektiv ist und wenn jedem Bild sein Urbild zugeordnet ist

Ein Hamiltonscher Kreis eines Graphen G ist ein geschlossener Weg (Kreis), der jeden Knoten von G genau einmal enthält.

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

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.

zum Beispiel x1 ∨ x3 ∨ x4 ∨ x7

z.B. x1 ∧ x2 ∧ x3

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.

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.

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

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

Folgen korrekter Folgerungen.

Beweise "A ⇒ C"! Wenn "A ⇒ B und B ⇒ C" dann "A ⇒ B ⇒ C" also "A ⇒ C"

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.

Lösungsmethode

Bezeichnet die Tätigkeit, in der wir Algorithmen in Programme umschreiben

Kardinalität von A. Die Anzahl der Elemente in A.

Eine Menge ist eine Sammlung von Objekten (Elementen), die paarweise unterschiedlich sind.

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.

Eine endliche nichtleere Menge Σ heißt Alphabet. Die Elemente eines Alphabets werden Buchstaben (Zeichen, Symbole) genannt.

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

Negation

Disjunktion