Einführung in die Theoretische Informatik - Cheatsheet.pdf

Syntax und Semantik der Aussagenlogik

Definition:

Syntax: Regeln für das Bilden gültiger Aussagen. Semantik: Bedeutung der Aussagen und deren Wahrheitswert.

Details:

• Syntax: Aussagenformen: Atomare Aussagen (z.B. p, q). Junktoren: ¬, ∧, ∨, →, ↔. Formelbildung: Rekursiv durch Anwendung von Junktoren.
• Semantik: Wahrheitswertzuweisung: Atomaussagen erhalten Wahrheitswerte, komplexe Aussagen durch Wahrheitstabellen oder Interpretationen.

Quantoren und Prädikate in der Prädikatenlogik

Definition:

Verwendung von Quantoren und Prädikaten zur Formalisierung und Analyse logischer Aussagen.

Details:

• Prädikat: Funktion mit einer Wahrheitswert-Zuordnung. Beispiel: \(P(x) = 'x > 0'\)
• Allquantor (\forall): Aussage gilt für alle Elemente des betrachteten Bereichs.
• Existenzquantor (\exists): Aussage gilt für mindestens ein Element des betrachteten Bereichs.
• Formalisierung: \(\forall x \in \mathbb{N}: P(x)\) bedeutet 'für alle natürlichen Zahlen x gilt P(x)'
• Formalisierung: \(\exists x \in \mathbb{N}: P(x)\) bedeutet 'es existiert eine natürliche Zahl x, für die P(x) gilt'

Deterministische und nichtdeterministische endliche Automaten (DFA/NFA)

Definition:

Deterministische endliche Automaten (DFA) und nichtdeterministische endliche Automaten (NFA) sind Modelle zur Erkennung regulärer Sprachen.

Details:

• DFA: Ein Zustand zu einem Zeitpunkt, deterministische Übergänge.
• NFA: Mehrere mögliche Zustände, nichtdeterministische Übergänge.
• Formal: Ein NFA wird definiert als ein 5-Tupel \( Q, \Sigma, \delta, q_0, F \) wobei \( Q \) Zustandsmenge, \( \Sigma \) Alphabet, \( \delta: Q \times \Sigma \rightarrow 2^Q \) Übergangsfunktion, \( q_0 \) Startzustand, \( F \subseteq Q \) Endzustände. Für DFA ist \( \delta: Q \times \Sigma \rightarrow Q \).
• DFA ist ein spezieller Fall des NFA.
• Jeder NFA kann in einen äquivalenten DFA umgewandelt werden (Powerset-Konstruktion).
• Akzeptanzbedingung: Ein Wort wird akzeptiert, wenn der Automat in einem akzeptierenden Endzustand endet.

Pumping-Lemma für reguläre Sprachen

Definition:

Pumping-Lemma hilft bei der Bestimmung, ob eine Sprache nicht regulär ist.

Details:

• Sei L eine reguläre Sprache. Es existiert eine Konstante n, sodass für jedes Wort w in L mit |w| ≥ n gilt: w kann in drei Teile x, y, z zerlegt werden, w = xyz, mit den Bedingungen:
  • |xy| ≤ n
  • |y| > 0
  • Für alle k ≥ 0 ist xy^kz in L
• Verwendung: Nachweis, dass eine Sprache nicht regulär ist, indem gezeigt wird, dass keine solche Zerlegung für einige Wörter existiert.

Turingmaschinen und Entscheidbarkeit

Definition:

Mathematisches Modell eines Computers. Untersucht die Berechenbarkeit und Entscheidungsprobleme.

Details:

• Turingmaschine (TM): Einfache Modell-Computer, bestehend aus unendlichem Band, Kopf, Zustandsmenge und Übergangsfunktion
• Berechenbarkeit: Ein Problem ist berechenbar, wenn eine TM existiert, die für jede Eingabe in endlicher Zeit hält
• Entscheidbarkeit: Ein Problem ist entscheidbar, wenn eine TM existiert, die für jede Eingabe ja oder nein in endlicher Zeit entscheidet
• Halteproblem: Nicht entscheidbares Problem, dass prüft, ob eine TM auf eine Eingabe hält
• Äquivalenzproblem von TM: Bestimmt, ob zwei TMs dasselbe berechnen, ebenfalls nicht entscheidbar
• Reduktion: Prozess zum Überführen eines Problems in ein anderes, um Entscheidbarkeit zu beurteilen

NP-Vollständigkeit und NP-Schwere

Definition:

NP-vollständig: Problem in NP, für das jedes Problem in NP in polynomieller Zeit darauf reduziert werden kann. NP-schwer: Problem mindestens so schwer wie NP-vollständige Probleme.

Details:

• Eine Sprache ist NP-vollständig (NP-complete), wenn sie in NP ist und jedes andere Problem in NP auf sie in polynomieller Zeit reduziert werden kann.
• Eine Sprache ist NP-schwer (NP-hard), wenn jedes Problem in NP auf sie in polynomieller Zeit reduziert werden kann, aber es muss selbst nicht in NP sein.
• Beispiel für ein NP-vollständiges Problem: SAT (Erfüllbarkeitsproblem).
• Beweis der NP-Vollständigkeit: Reduktion eines bekannten NP-vollständigen Problems auf das neue Problem.

Reduktion und Unentscheidbarkeitsbeweise

Definition:

Verfahren zum Nachweis der Unentscheidbarkeit durch Reduktion bekannter unentscheidbarer Probleme.

Details:

• Reduktion: Gegeben ein Problem A, wird gezeigt, dass es auf ein bekanntes unentscheidbares Problem B reduzierbar ist (A ≤ B).
• Zeiget Unentscheidbarkeit von A durch Existenz einer Turing-Maschine für B.
• Wichtige Methode: Diagonalisierungsargument.
• Beispiel: Halteproblem.

Hierarchiesätze und Orakelmaschinen

Definition:

Hierarchietheoreme trennen die Komplexitätsklassen voneinander. Orakelmaschinen sind erweiterte Turingmaschinen, die auf Anfragen spezielle Probleme sofort lösen können.

Details:

• Die Zeit- und Platz-Hierarchiesätze erweitern bekannte Klassen wie P und NP um mehr Rechenressourcen.
• Zeithierarchie: Wenn f(n) eine konstruierbare Funktion ist, dann gibt es Probleme, die in O(f(n)) Zeit gelöst werden, aber nicht in o(f(n)) Zeit.
• Platzhierarchie: Wenn f(n) platzkonstruierbar ist, gibt es Probleme, die in O(f(n)) Platz gelöst werden, aber nicht in o(f(n)) Platz.
• Orakelmaschinen: Turingmaschinen mit Zugang zu einem Orakel, das jede Ja/Nein-Frage zu einem spezifischen Problem sofort beantwortet.
• Nutzen Orakel, um komplexe Klassen wie P^NP oder NP^P zu definieren.
• Erlauben Analyse der relativen Komplexität von Problemen.