Einführung in die Theoretische Informatik - Cheatsheet.pdf

Zeit- und Platzkomplexität von Algorithmen

Definition:

Analyse des Ressourcenverbrauchs eines Algorithmus in Bezug auf Laufzeit (Zeitkomplexität) und Speicherverbrauch (Platzkomplexität). Sehr wichtig für Effizienz und Skalierbarkeit.

Details:

• Zeitkomplexität: Misst die Anzahl der elementaren Operationen als Funktion der Eingabegröße n.
• Platzkomplexität: Misst den Speicherbedarf als Funktion der Eingabegröße n.
• Asymptotische Notation: Beschreibt das Wachstumsverhalten (z.B. O(n), Ω(n), Θ(n)).
• Wichtige Klassen: P (polynomiell lösbar), NP (nichtdeterministisch polynomielle Zeit), NP-vollständig.
• Best-, Durchschnitts- und schlechtester Fall: Verschiedene Analyseansätze basierend auf den Eingaben.

Komplexitätsklassen (P, NP, NP-vollständig)

Definition:

Klassifikation von Problemen basierend auf ihrer Berechnungszeit und -schwierigkeit.

Details:

• P: Probleme, die in polynomieller Zeit von einem deterministischen Turing-Maschine (TM) gelöst werden können.
• NP: Probleme, deren Lösungen in polynomieller Zeit von einem nicht-deterministischen TM verifiziert werden können.
• NP-vollständig: Probleme in NP, die jedes andere Problem in NP durch polynomiellen Zeitaufwand reduzieren können.
• Wenn ein NP-vollständiges Problem in P liegt, gilt P = NP.

Deterministische vs. Nicht-deterministische Automaten und Algorithmen

Definition:

Definition und Erklärung der Unterschiede zwischen deterministischen und nicht-deterministischen Automaten und Algorithmen.

Details:

• Deterministische endliche Automaten (DEA): Zustandsübergänge sind eindeutig definiert; für jeden Zustand und jedes Eingabesymbol gibt es genau einen Folgezustand.
• Nicht-deterministische endliche Automaten (NEA): Zustandsübergänge können zu mehreren Zuständen führen; es kann mehrere mögliche Folgezustände für einen gegebenen Zustand und ein Eingabesymbol geben.
• Deterministische Algorithmen: Jede Schritt im Algorithmus ist eindeutig und führt zu einem bestimmten Folgeschritt.
• Nicht-deterministische Algorithmen: Enthalten Schritte, bei denen mehrere Pfade möglich sind; können durch „Raten“ Lösungen finden.
• Äquivalenz: Jeder NEA kann in einen äquivalenten DEA umgewandelt werden, obwohl die Anzahl der Zustände exponentiell wachsen kann.
• Komplexität: Deterministische Algorithmen sind oft einfacher zu analysieren und zu implementieren, nicht-deterministische Algorithmen können theoretisch effizienter sein.
• Beispiel für Übergangsfunktion DEA: \(\text{δ: Q × Σ → Q}\)
• Beispiel für Übergangsfunktion NEA: \(\text{δ: Q × Σ → 2^Q}\)
• P vs. NP: Diese Unterscheidung ist zentral für das Verständnis des Unterschieds in der Komplexitätstheorie.

Regular- und kontextfreie Sprachen

Definition:

Reguläre Sprachen: Erkennbar durch endliche Automaten (DFA/NFA). Kontextfreie Sprachen: Erkennbar durch Kellerautomaten und generierbar durch kontextfreie Grammatiken.

Details:

• Reguläre Sprachen: Beschreibbar durch reguläre Ausdrücke.
• Reguläre Sprachen: Abgeschlossen unter Vereinigung, Konkatenation, Kleene-Stern, Durchschnitt und Komplement.
• Kontextfreie Sprachen: Beschreibbar durch kontextfreie Grammatiken (Grammatiken der Typ 2).
• Kontextfreie Sprachen: Abgeschlossen unter Vereinigung, Konkatenation und Kleene-Stern, aber nicht unter Durchschnitt und Komplement.
• Pumping-Lemma für reguläre und kontextfreie Sprachen: Zum Nachweis, dass eine Sprache nicht in der jeweiligen Klasse liegt.
• Entscheidbarkeitsprobleme: Leerheit, Endlichkeit und Mitgliedschaft für reguläre Sprachen entscheidbar; Leerheit und Mitgliedschaft für kontextfreie Sprachen entscheidbar, aber Endlichkeit und Äquivalenz nicht immer.
• Bsp. reguläre Sprache: \(a^*b^*\); Bsp. kontextfreie Sprache: \(a^n b^n\), \(n \geq 0\).

Entwurf und Analyse von Algorithmen (Greedy, Dynamische Programmierung, Divide-and-Conquer)

Definition:

Entwurf und Analyse von Algorithmen beschäftigen sich mit der Entwicklung effizienter Lösungswege für Probleme unter Berücksichtigung von Zeit- und Platzkomplexität.

Details:

• Greedy-Algorithmus: Wähle stets die beste lokale Option in der Hoffnung, damit zur global besten Lösung zu gelangen.
• Dynamische Programmierung: Zerlege das Problem in überlappende Teilprobleme, deren Lösungen zwischengespeichert werden, um Redundanzen zu vermeiden.
• Divide-and-Conquer: Teile das Problem rekursiv in kleinere Teilprobleme, löse diese und kombiniere die Teillösungen zur Gesamtlösung.
• Greedy: meist einfach zu implementieren, aber nicht immer optimallösungsgarantie.
• Dynamische Programmierung: oft effizient bei optimalen Lösungen für komplexe Probleme, benötigt meist mehr Speicher.
• Divide-and-Conquer: Nutzt Rekursion, oft effizient und einfach zu verständliche Strukturierung, aber kann hohen Overhead durch Rekursion verursachen.

Chomsky-Hierarchie

Definition:

Chomsky-Hierarchie kategorisiert formale Grammatiken nach ihrer Ausdrucksstärke.

Details:

• Typ-0 (rekursiv aufzählbar): Keine Einschränkungen.
• Typ-1 (kontextsensitiv): Produktionsregeln der Form \(\alpha A \beta \rightarrow \alpha \gamma \beta\) (\(\gamma\) ist nicht leer, \(A\) ist eine Nichtterminal).
• Typ-2 (kontextfrei): Produktionsregeln der Form \(A \rightarrow \gamma \) (\(A\) ist eine Nichtterminal, \(\gamma\) ist eine Zeichenkette von Terminalen und Nichtterminalen).
• Typ-3 (regulär): Produktionsregeln der Form \(A \rightarrow aB \) oder \(A \rightarrow a\) (\(A, B\) sind Nichtterminal, \(a\) ist ein Terminal).

Model-Checking

Definition:

Model-Checking ist ein automatisiertes Verfahren zur Überprüfung, ob ein Modell eines Systems einer formalen Spezifikation entspricht.

Details:

• Systemmodell: meistens als endlicher Zustandsautomat oder Kripke-Struktur dargestellt.
• Spezifikation: üblicherweise in temporaler Logik (z.B. LTL, CTL) formuliert.
• Algorithmus: überprüft alle möglichen Zustände und Übergänge des Modells.
• Ergebnis: liefert entweder ein Zertifikat der Korrektheit oder ein Gegenbeispiel.
• Werkzeuge: bekannte Tools sind SPIN, SMV, und UPPAAL.

Turingmaschinen und ihre Bedeutung

Definition:

Turingmaschine: Abstraktes Berechnungsmodell, das zur Definition der Berechenbarkeit dient.

Details:

• Besteht aus Band, Lese/Schreibkopf, Zustandsregister
• Akzeptanzproblem: Entscheidet, ob eine TM eine Eingabe akzeptiert
• Church-Turing-These: Jede berechenbare Funktion kann von einer Turingmaschine berechnet werden
• Halteproblem: Nicht entscheidbar
• Deterministische und nicht-deterministische Turingmaschinen