Endliche Automaten und Codierungstechniken
Diese Seite bietet einen umfassenden Überblick über verschiedene Konzepte der theoretischen Informatik, insbesondere im Bereich der endlichen Automaten und Codierungstechniken.
Endliche Automaten
Die Seite beginnt mit einer Erläuterung verschiedener Typen von endlichen Automaten:
- Deterministische Endliche Automaten (DEA): Diese Automaten haben für jede Eingabe genau einen eindeutigen Folgezustand.
Definition: Ein DEA ist ein endlicher Automat, bei dem jeder Zustand für jedes Eingabesymbol höchstens einen Folgezustand hat.
- Nicht-deterministische Endliche Automaten (NEA): Im Gegensatz zu DEAs können NEAs mehrere mögliche Übergänge für eine Eingabe haben.
Highlight: NEAs erlauben auch leere Übergänge, was ihre Flexibilität erhöht.
-
Mealy-Maschine: Ein endlicher Automat mit Ausgabe, bei dem die Ausgabe von den Übergängen abhängt.
-
Moore-Maschine: Ein endlicher Automat, bei dem die Ausgabe von den Zuständen abhängt.
Example: Bei einer Moore-Maschine könnte eine mögliche Ausgabe "abbaa" sein.
Binärbäume
Die Seite geht dann auf Binärbäume ein und erklärt verschiedene Traversierungsmethoden:
- Pre-Order-Verfahren
- In-Order-Verfahren
- Post-Order-Verfahren
Vocabulary: Traversierung bezeichnet das systematische Durchlaufen aller Knoten eines Baums.
Hamming-Distanz
Die Hamming-Distanz wird als wichtiges Konzept für die Fehlererkennung in der Datenübertragung vorgestellt.
Definition: Die Hamming-Distanz ist die Anzahl der Positionen, an denen sich zwei gleich lange Zeichenketten unterscheiden.
Huffman-Codierung
Die Huffman-Codierung wird als effiziente Methode zur Datenkompression erklärt.
Example: Für das Wort "KROKODIL" wird ein Beispiel für die Huffman-Codierung gegeben.
Verschlüsselungstechniken
Abschließend werden verschiedene Verschlüsselungstechniken vorgestellt:
-
Caesar-Verschlüsselung: Eine monoalphabetische Substitutionschiffre.
-
Vigenère-Verschlüsselung: Eine polyalphabetische Substitutionschiffre.
Highlight: Der Kasiski-Test wird als Methode zum Angriff auf die Vigenère-Verschlüsselung erwähnt.
Diese Zusammenfassung bietet einen detaillierten Überblick über wichtige Konzepte der theoretischen Informatik und Kryptographie, die für Studierende und Fachleute gleichermaßen relevant sind.