Mathematik für INF 1 - Cheatsheet

Grundbegriffe der Mengenlehre: Menge, Element, Teilmenge

Definition:

Grundbegriffe der Mengenlehre: Menge, Element, Teilmenge

Details:

• Menge (\textbf{Set}): Jede Zusammenfassung von bestimmten wohlunterschiedenen Objekten, den Elementen der Menge.
• Element (\textbf{Element}): Ein Objekt einer Menge. Notation: \(a \in A\).
• Teilmenge (\textbf{Subset}): Menge A ist Teilmenge von Menge B, wenn jedes Element von A auch ein Element von B ist. Notation: \(A \subseteq B\).

Operationen mit Mengen: Vereinigung, Durchschnitt, Differenz

Definition:

Operationen mit Mengen umfassen die grundlegenden Operationen Vereinigung, Durchschnitt und Differenz. Diese sind Grundwerkzeuge der Mengenlehre, die in der Informatik zur Datenstrukturierung und -analyse verwendet werden.

Details:

• Vereinigung (\textbf{Union}): Die Vereinigung zweier Mengen A und B, geschrieben als \( A \cup B \), enthält alle Elemente, die in A oder B oder beiden enthalten sind.
• Durchschnitt (\textbf{Intersection}): Der Durchschnitt zweier Mengen A und B, geschrieben als \( A \cap B \), enthält nur die Elemente, die sowohl in A als auch in B liegen.
• Differenz (\textbf{Difference}): Die Differenz zweier Mengen A und B, geschrieben als \( A \setminus B \), enthält alle Elemente, die in A, aber nicht in B enthalten sind.

Aussagenlogik: Aussagen, logische Operatoren, Wahrheitstafeln

Definition:

Teilgebiet der Logik, das sich mit Aussagen und deren Verknüpfungen mittels logischer Operatoren beschäftigt.

Details:

• Aussagen: Sätze, die entweder wahr (W) oder falsch (F) sind.
• Logische Operatoren: Verknüpfungen wie UND (\textbf{\text {AND}}, \textbf{\text {∧}}), ODER (\textbf{\text {OR}}, \textbf{\text {∨}}), NICHT (\textbf{\text {NOT}}, \textbf{\text {¬}}), Implikation (\textbf{\text {→}}), Äquivalenz (\textbf{\text {↔}}).
• Wahrheitstafeln: Tabellen zur Darstellung aller möglichen Wahrheitswerte einer logischen Aussage oder einer Kombination von Aussagen. Beispiel für eine AND-Operation:
  • a = W, b = W ⇒ a ∧ b = W
  • a = W, b = F ⇒ a ∧ b = F
  • a = F, b = W ⇒ a ∧ b = F
  • a = F, b = F ⇒ a ∧ b = F

Prädikatenlogik: Quantoren, Prädikate, Formeln

Definition:

Verwendung von Prädikatenlogik zur formalen Darstellung und Analyse von Aussagen mit Variablen.

Details:

• Quantoren:
  • Allquantor \( \forall x : P(x) \)
  • Existenzquantor \( \exists x : P(x) \)
• Prädikate: Aussagenfunktionen, z.B. \( P(x) : x \text{ ist gerade}\)
• Formeln: Kombinationen von Prädikaten und Quantoren, z.B. \( \forall x ( x > 0 \implies P(x) ) \)

Graphenalgorithmen: Tiefensuche, Breitensuche

Definition:

Graphsuchalgorithmen zur Traversierung oder Suche in Graphen.

Details:

• Tiefensuche (Depth-First Search, DFS): Erkundet so tief wie möglich in ein Kind jedes Knotens bevor es zurückverfolgt.
• Verwendet einen Stack oder Rekursion.
• Komplexität: O(|V| + |E|).
• Praktisch für Pfadsuche und Zyklendetektion.
• Breitensuche (Breadth-First Search, BFS): Durchläuft alle Nachbarn eines Knotens, bevor weiter in die Tiefe gegangen wird.
• Verwendet eine Queue.
• Komplexität: O(|V| + |E|).
• Nützlich zur Ermittlung von kürzesten Pfaden in ungewichteten Graphen.

Lineare Gleichungssysteme und deren Lösung

Definition:

Gleichungen mit mehreren Unbekannten in Form von Matrizen lösen, Lösungen können eindeutig, unendlich oder nicht vorhanden sein.

Details:

• Allgemeine Form: \[ A \mathbf{x} = \mathbf{b} \] mit Matrix \( A \) und Vektoren \( \mathbf{x} \), \( \mathbf{b} \).
• Gauss-Algorithmus zur Lösung von \( A \mathbf{x} = \mathbf{b} \).
• Gauss-Jordan-Algorithmus zur Berechnung der Inversen von \( A \).
• Lösungsarten: eindeutig, unendlich viele Lösungen (Rang-Defizit), keine Lösung (inkonsistent).
• Homogen: \[ A \mathbf{x} = \mathbf{0} \] , trivial if \( \mathbf{x} = \mathbf{0} \); Nicht-trivial if \( \text{Rang}(A) < \text{Anzahl der Unbekannten} \) .

Kombinatorik: Zählprinzipien, Permutationen, Kombinationen

Definition:

Zählprinzipien: Grundlegende Methoden zur Bestimmung der Anzahl von Elementen in Mengen. Permutationen: Anordnungen von Elementen in einer bestimmten Reihenfolge. Kombinationen: Auswahl von Elementen ohne Berücksichtigung der Reihenfolge.

Details:

• Produktregel: Wenn ein Ereignis auf k Arten und ein anderes auf m Arten auftreten kann, dann gibt es insgesamt k \times m Kombinationen.
• Summenregel: Wenn ein Ereignis auf k Arten oder ein anderes auf m Arten auftreten kann, dann gibt es insgesamt k + m Kombinationen.
• Permutationen ohne Wiederholung: Anzahl der Anordnungen n verschiedener Elemente: n! (Fakultät).
• Permutationen mit Wiederholung: Anordnungen bei k1, k2, ..., kr Wiederholungen: \( \frac{n!}{k_1! k_2! \dots k_r!} \).
• Kombinationen ohne Wiederholung: Auswahl von k Elementen aus n: \( \binom{n}{k} = \frac{n!}{k!(n-k)!} \).
• Kombinationen mit Wiederholung: Auswahl von k Elementen aus n mit Wiederholung: \( \binom{n+k-1}{k} \).

Endliche Automaten und formale Sprachen

Definition:

Endliche Automaten sind Modelle für Berechnungen mit endlichem Speicher, formale Sprachen sind Mengen von Zeichenketten, die durch Grammatiken oder Automaten definiert werden.

Details:

• Ein endlicher Automat besteht aus Zuständen, einem Eingabealphabet, einer Übergangsfunktion, einem Startzustand und einer Menge von Endzuständen.
• Deterministischer endlicher Automat (DEA): \( A = (Q, \Sigma, \delta, q_0, F) \) wobei \( Q \) Zustandsmenge, \( \Sigma \) Eingabealphabet, \( \delta: Q \times \Sigma \rightarrow Q \) Übergangsfunktion, \( q_0 \) Startzustand, \( F \subseteq Q \) Endzustände.
• Nichtdeterministischer endlicher Automat (NEA): \( A = (Q, \Sigma, \delta, q_0, F) \) wobei \( \delta: Q \times \Sigma \rightarrow \mathcal{P}(Q) \)
• Äquivalenz von DEA und NEA: Jeder NEA kann in einen äquivalenten DEA umgewandelt werden.
• Minimierung endlicher Automaten: Verfahren zur Reduktion der Zustandsanzahl eines DEA.
• Formale Sprache: Menge von Zeichenketten (Wörtern), die durch Automaten oder Grammatiken generiert werden.
• Reguläre Sprachen: Können durch endliche Automaten erkannt oder durch reguläre Ausdrücke beschrieben werden.