Diskrete Mathematik - Cheatsheet.pdf

Grundlagen von Graphen: Knoten, Kanten, Pfade und Zyklen

Definition:

Definitionen von Knoten, Kanten, Pfade und Zyklen in Graphen; verwendet in der diskreten Mathematik zur Darstellung und Analyse vernetzter Strukturen.

Details:

• Knoten (V): Grundelement eines Graphen; Repräsentiert Objekte oder Zustände.
• Kanten (E): Verbindung zwischen zwei Knoten; Repräsentiert Beziehungen oder Übergänge.
• Pfad: Folge von Knoten, bei der jede angrenzende Paarung durch Kanten verbunden ist; bezeichnet auch als Weg.
• Zyklus: Pfad, der zum Startknoten zurückkehrt ohne Knoten zu wiederholen (außer dem Startknoten).
• Notation: Ein Graph wird durch \( G = (V, E) \) dargestellt, wobei \( V \) die Menge der Knoten und \( E \) die Menge der Kanten ist.
• Adjazenzmatrix: \( A = (a_{ij}) \) , wobei \( a_{ij} = 1 \) , wenn Kante zwischen Knoten \( v_i \) und \( v_j \) existiert, sonst\( = 0 \).

Graphenalgorithmen: Tiefensuche (DFS) und Breitensuche (BFS)

Definition:

Tiefensuche (DFS) und Breitensuche (BFS) sind grundlegende Graphsuchalgorithmen, die zur Erkundung und Traversierung von Graphen verwendet werden.

Details:

• Tiefensuche (DFS):
• Traversiert Graph durch vollständige Erschöpfung eines Pfads, bevor ein neuer Pfad begonnen wird.
• Verwendet Stack (LIFO-Prinzip).
• Rekursive Implementierung möglich.
• Breitensuche (BFS):
• Traversiert Graph schichtweise.
• Verwendet Queue (FIFO-Prinzip).
• Erster gefundener Pfad in ungewichteten Graphen ist der kürzeste.
• Komplexität:
• Beide haben Zeitkomplexität von \(\text{O}(V + E)\), wobei \(\text{V}\) die Anzahl der Knoten und \(\text{E}\) die Anzahl der Kanten ist.
• Speicherkomplexität bei DFS kann bis zu \(\text{O}(V)\) betragen, wobei \(\text{V}\) die maximale Rekursionstiefe ist.
• Speicherkomplexität bei BFS \(\text{O}(V)\), erforderlich, um den gesamten Frontlevel der Suche zu speichern.

Inklusions-Exklusions-Prinzip in der Kombinatorik

Definition:

Methode zur Berechnung der Anzahl Elemente in der Vereinigung mehrerer Mengen unter Berücksichtigung von Überlappungen.

Details:

• Formel für zwei Mengen A und B: \( |A \cup B| = |A| + |B| - |A \cap B| \)
• Formel für drei Mengen A, B und C: \( |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \)
• Allgemeine Formel für n Mengen:\[ |A_1 \cup A_2 \cup ... \cup A_n| = \sum_{i=1}^n |A_i| - \sum_{1 \le i < j \le n} |A_i \cap A_j| + \sum_{1 \le i < j < k \le n} |A_i \cap A_j \cap A_k| - ... + (-1)^{n+1} |A_1 \cap A_2 \cap ... \cap A_n| \]

Beweistechniken: Indirekter Beweis, Widerspruchsbeweis und Induktionsbeweis

Definition:

Beweistechniken in der Diskreten Mathematik: Indirekter Beweis, Widerspruchsbeweis und Induktionsbeweis

Details:

• Indirekter Beweis: Zeige, dass die Negation der Aussage zu einem Widerspruch führt.
• Widerspruchsbeweis: Gehe von der Richtigkeit der zu widerlegenden Aussage aus und zeige, dass dies zu einem Widerspruch führt.
• Induktionsbeweis: Nutze die mathematische Induktion, um die Gültigkeit einer Aussage für alle natürlichen Zahlen zu beweisen.
• Induktionsbasis: Zeige, dass die Aussage für den Startwert (meistens 0 oder 1) gilt.
• Induktionsschritt: Zeige, dass aus der Gültigkeit der Aussage für einen beliebigen Schritt die Gültigkeit für den nächsten Schritt folgt.
• Formeln:Induktionsbasis: \(P(0)\) oder \(P(1)\)Induktionsannahme: \(P(k)\) giltInduktionsschritt: \(P(k) \Rightarrow P(k+1)\)

Primzahlen und ihre Eigenschaften: Primzahltests

Definition:

Primzahlen sind Zahlen größer als 1, die nur durch 1 und sich selbst teilbar sind.

Details:

• Ein Primzahltest überprüft, ob eine Zahl prim ist.
• Kleine Teilerregel: Eine Zahl ist nicht prim, wenn sie einen Teiler kleiner gleich ihrem Quadratwurzel hat.
• Miller-Rabin-Test: Probabilistischer Test für große Zahlen.
• Fermat-Test: Basierend auf Fermat's kleinem Satz.
• AKS-Algorithmus: Deterministischer, polynomialzeitiger Test.
• Wenn ein Test keine Teiler findet, ist die Zahl wahrscheinlich prim.

Grundbegriffe der Algorithmenanalyse: Laufzeitanalyse und Big-O-Notation

Definition:

Bestimmt die Effizienz eines Algorithmus hinsichtlich der benötigten Zeit in Abhängigkeit von der Eingabegröße. Big-O-Notation beschreibt das asymptotische Verhalten der Laufzeit.

Details:

• Big-O-Notation: \(\text{O}(f(n))\)
• Beschreibt das Wachstumsverhalten einer Funktion im schlimmsten Fall
• Typische Komplexitätsklassen: \(\text{O}(1)\), \(\text{O}(\text{log } n)\), \(\text{O}(n)\), \(\text{O}(n \log n)\), \(\text{O}(n^2)\), \(\text{O}(2^n)\), \(\text{O}(n!)\)
• wichtige Begriffe: obere Schranke (worst-case), durchschnittliche Laufzeit (average-case), untere Schranke (best-case)
• Vergleich von Algorithmen basierend auf deren Komplexitätsklassen

Kongruenzen und modulares Rechnen

Definition:

Werkzeuge zur Lösung und Vereinfachung von Problemen, wo Zahlen nach einem bestimmten Modul betrachtet werden.

Details:

• Kongruenz: \(a \equiv b \pmod{m}\) bedeutet, dass \(a - b\) durch \(m\) teilbar ist.
• Eigenschaften: Reflexivität, Symmetrie, Transitivität.
• Arithmetik: Addition, Subtraktion, Multiplikation (jeweils modulo m).
• Modulo-Operator: \(a \% m\) gibt den Rest, wenn \(a\) durch \(m\) geteilt wird.
• Exponentiation: \(a^b \mod m\) effizient mit Modularexponentiation berechnen.

Algorithmendesign-Paradigmen: Greedy-Methoden, Divide and Conquer und dynamische Programmierung

Definition:

Algorithmenansätze zur Lösung komplexer Probleme.

Details:

• Greedy-Methoden: Wähle Schrittweise die beste Option, basierend auf einer lokalen Heuristik.
• Divide and Conquer: Zerteile das Problem in kleinere, einfachere Teilprobleme, löse diese rekursiv und kombiniere die Lösungen.
• Dynamische Programmierung: Zerlege Problem in überlappende Teilprobleme, speichere bereits berechnete Teillösungen zur Vermeidung doppelter Berechnungen.