Diskrete Strukturen - Cheatsheet.pdf

Teilweise und totale Ordnungen

Definition:

Teilweise und totale Ordnungen beschreiben Beziehungen zwischen Elementen einer Menge, wobei teilweise Ordnungen nicht notwendigerweise jedes Paar von Elementen vergleichen können, während totale Ordnungen dies tun.

Details:

• Teilordnung: Eine Relation \( \leq \) auf einer Menge \( M \) ist eine Teilordnung, wenn sie reflexiv, antisymmetrisch und transitiv ist.
• Totale Ordnung: Eine Relation \( \leq \) auf einer Menge \( M \) ist eine totale Ordnung, wenn sie eine Teilordnung ist und zusätzlich für alle \( a, b \in M \) gilt: \( a \leq b \) oder \( b \leq a \).
• Beispiel: \( (\mathbb{N}, \leq) \) ist eine totale Ordnung.

Tiefensuche und Breitensuche in Graphen

Definition:

Tiefensuche (DFS) und Breitensuche (BFS) in Graphen sind grundlegende Algorithmen zur Durchsuchung oder Traversierung von Knotenstrukturen.

Details:

• DFS: Stößt in die Tiefe des Graphen vor, bevor es zu einem Nachbarknoten zurückkehrt.
• BFS: Erkunden auf jeder Ebene die benachbarten Knoten, bevor es auf die nächste Ebene voranschreitet.
• DFS: Einsatz eines Stacks (LIFO) oder rekursive Implementierung.
• BFS: Einsatz einer Queue (FIFO).
• DFS: Laufzeitkomplexität \(O(V + E)\), wobei \(V\) die Anzahl der Knoten und \(E\) die Anzahl der Kanten ist.
• BFS: Laufzeitkomplexität ebenfalls \(O(V + E)\).
• DFS kann zur Erkennung von Zyklen und zur Topologischen Sortierung genutzt werden.
• BFS kann zur Bestimmung der kürzesten Pfade in ungewichteten Graphen genutzt werden.
• DFS: Vorteilhaft bei tiefen, wenig verzweigten Graphen.
• BFS: Vorteilhaft bei breiten, stark verzweigten Graphen.

Beweismethoden: Direkter Beweis, Widerspruchsbeweis und Induktionsbeweis

Definition:

Beweismethoden in der Vorlesung Diskrete Strukturen: direkter Beweis, Widerspruchsbeweis, Induktionsbeweis.

Details:

• Direkter Beweis: Zeigt, dass die Aussage \textit{A} wahr ist, indem man sie logisch aus bekannten Axiomen, Definitionen und Theoremen ableitet.
• Widerspruchsbeweis: Zeigt die Wahrheit einer Aussage, indem man annimmt, dass die Aussage falsch ist und zum Widerspruch gelangt. Also beweist man \textit{A} durch Annahme von \textit{¬A} und Ableitung eines Widerspruchs.
• Induktionsbeweis: Nutzt das Prinzip der mathematischen Induktion, bestehend aus dem Basisfall (Beweis der Aussage für den kleinsten möglichen Wert) und dem Induktionsschritt (Annahme, dass die Aussage für einen Wert \textit{k} gilt und Beweis, dass sie auch für \textit{k + 1} gilt).

Kartesisches Produkt und Potenzmenge

Definition:

Kartesisches Produkt und Potenzmenge sind fundamentale Konzepte in der Mengenlehre.

Details:

• Kartesisches Produkt: Für Mengen A und B ist das Kartesische Produkt definiert als: \[ A \times B = \{ (a, b) | a \in A, b \in B \} \]
• Potenzmenge: Die Potenzmenge einer Menge A ist die Menge aller Teilmengen von A: \[ \mathcal{P}(A) = \{ B | B \subseteq A \} \]

Hamiltonkreise und Eulerkreise

Definition:

Hamiltonkreise und Eulerkreise sind spezielle Arten von Kreisen in Graphen.

Details:

• Hamiltonkreis: Ein Kreis, der jeden Knoten genau einmal besucht.
• Ein Graph besitzt einen Hamiltonkreis, wenn eine Permutation seiner Knoten eine zyklische Sequenz ergibt.
• Eulerkreis: Ein Kreis, der jede Kante genau einmal besucht.
• Ein zusammenhängender Graph besitzt einen Eulerkreis, wenn jeder Knoten geraden Grad hat.
• Hamiltonkreis: Entscheidungsproblem NP-vollständig.
• Eulerkreis: Existenzproblem in linearer Zeit lösbar (Hierholzer Algorithmus).

Konjunktive und disjunktive Normalform

Definition:

Normale Formen von booleschen Ausdrücken, um sie zu standardisieren.

Details:

• Konjunktive Normalform (KNF/CNF): AND von ORs
• Disjunktive Normalform (DNF): OR von ANDs
• Beispiel KNF: \((A \lor B) \land (C \lor D)\)
• Beispiel DNF: \((A \land B) \lor (C \land D)\)
• Jeder boolesche Ausdruck kann in KNF und DNF umgewandelt werden

Inklusions-Exklusions-Prinzip

Definition:

Das Inklusions-Exklusions-Prinzip wird verwendet, um die Vereinigungsmenge mehrerer Mengen zu bestimmen und dabei Überschneidungen zwischen den Mengen zu berücksichtigen.

Details:

• Formel für zwei Mengen: \( |A \cup B| = |A| + |B| - |A \cap B| \)
• Allgemein für n Mengen: \[ |A_1 \cup A_2 \cup ... \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - ... + (-1)^{n+1} |A_1 \cap A_2 \cap ... \cap A_n| \]
• Nützlich zur Berechnung der Kardinalität von Mengen und zur Bestimmung der Wahrscheinlichkeit von Ereignissen.

Reguläre Ausdrücke und deren Einsatz in der Informatik

Definition:

Reguläre Ausdrücke (regex): Muster zur Beschreibung von Zeichenketten; verwendet zur Textsuche und -manipulation.

Details:

• Syntax: Kombination aus Zeichen (a-z), Metazeichen (.*, [ ]), und Operatoren (|, *, +).
• Beispiele:
  • Eine Ziffer: \d
  • Ein Wort: \w+
  • Email-Validierung: [\w.-]+@[\w.-]+\t\.[a-z]{2,}
• Anwendungen in Informatik: Textverarbeitung, Validierung, Syntax-Highlighting, Parser.
• Komplexität: Durch Backtracking kann Performance variieren.
• Verwendung in Programmiersprachen: Python (re-Modul), JavaScript (RegExp-Objekt), etc.