Theoretische Informatik (Vorlesung 3)

1.2 Zwei Beispiele

• Beispiel 1:
  • Graph g = (V,E)
  • Eine Teilmenge C ⊆ V heißt Clique, wenn je zwei Knoten aus C mit einer Kante verbunden sind.
  • Wenn alle mit allen verbunden sind, dann ist der Graph eine Clique
  • Wenn das Entscheidungsproblem nicht lösbar ist, dann ist das Optimierungsproblem auch nicht lösbar.
  • Das Entscheidungsproblem greift auf den Lösungsalgorithmus des Optimierungsproblems zurück.

Optimierungsproblem Clique

• Eingabe: Ein Graph G
• Ausgabe: Größte Clique in G

Entscheidungsproblem Clique

• Einbgabe: Ein Graph G, k ∈ ℕ (natürliche Zahlen)
• Ausgabe: Gibt es in G eine Clique der Größe k? → ja / nein
• Beispiel 2: 
  • Def. 1.3: Aussagenlogische Formeln
    • Seien x₁, …, x_n boolesche Variablen ( können nur die Werte falsch oder wahr annehmen)
    • Seien weiter ∧ (UND), ∨ (ODER), ¬ ( Negation) Operationen mit
    1. wahr ∧ wahr = wahr
    2. wahr ∧ falsch = falsch ∧ wahr = falsch ∧ falsch = falsch
    3. wahr ∨ wahr = wahr ∨ falsch = falsch ∨ wahr= wahr
    4.  falsch ∨ falsch = falsch
    5. wahr = ¬ falsch
    6. falsch = ¬ wahr
    • Die Variablen x₁ und ¬x₁ heißen auch Literale.
    • Ein Ausdruck (y₁ ∨ y₂ … ∨ y_n ) mit Literalen y₁, .., y_n heißt Klausel  und ein ein Ausdruck α = c₁ ∧ c₂ … ∧ _cm mit Klauseln c₁, …, c_n heißt Ausdruck in konjunktiver Normalform.
    • Beispiel 1:  
      • α =  (x₁ v x₂ v x₃ ) ∧ ( x₁ v ¬x₂ v ¬x₃ )
      • x₁, x₂, x₃ = Literal
    • Nur mit ∨ (ODER) Verknüpfung verbunden = Klausel
    • Eine Belegung der Variablen x₁, .., x_n ist eine Abbildung  μ{x₁, .. , x_n } → {wahr, falsch}
    • Eine Belegung μ erfüllt den Ausdruck α, wenn α den Wert wahr bekommt.
    • Bsp. (zu oben):
      • μ(x₁) = μ(x₂) = μ(x₃) = wahr 
        • (wahr ∨ wahr ∨ wahr) ∧ (wahr ∨ falsch ∨ falsch) = wahr
        • somit ist μ eine erfüllende Bedinung für α
      • μ(x₁) = μ(x₂) = μ(x₃) = falsch
        • (falsch ∨ falsch ∨ falsch)∧ (falsch ∨ wahr ∨ wahr) = falsch
        • somit ist μ keine erfüllende Bedingung für α
    • Beispiel 2:
      • α = ( x₁ ∨ x₂ ) ∧ ( x₁ ∨ ¬ x₂ ) ∧ (¬ x₁ ∨ x₂) ∧ (¬ x₁ v ¬ x₂)
      • hat keine erfüllende Bedingung

Optimierungsproblem Saturability ( Sat )

• Eingabe: Ein Ausdruck α in konjunktiver Normalform
• Ausgabe: Eine Belegung, die die meißten Klauseln erfüllt

Entscheidungsproblem Saturability ( Sat )

• Eingabe: Ein Ausdruck α in KNF
• Ausgabe: Gibt es eine erfüllende Belegung für α? → ja / nein

1.3 Optimierungs-, Entscheidungs- und Wortprobleme und formale Sprachen

• „Warum interessieren wir uns für Formale sprachen?“
• Sei Σ ein endliches Alphabet z.B. Σ = { 0,1 } mit Σ* = { (W₁,…,W_n), n ∈ ℕ , W₁,…, W_n, ∈ Σbezeichnen wir die Menge aller Wörter über Σ.
• Für eine Sprache L ⊆  Σ* sei das Wortproblem L.
  • Eingabe: Ein Wort w ∈ Σ*
  • Ausgabe: Gilt w ∈ L?
• Aufgabe: Wie codiert man Eingaben zu einem Problem in einer für Computer verständlichen Sprache?
• Bsp.: Eingabe des Optimierungsprogrammes Clique sind Graphen G = (V,E)
  • V = {V₁,..,V_n}
  • E={E₁,..,E_n}
  • Dann kann der Graph durch folgende m x n – Matrix (Indizenz-Matrix) repräsentiert werden:

	v1	v2	v3	v4
e1	1	1	0	0
e2	1	0	1	0
e3	0	1	0	1
e4	0	1	1	0
e5	0	0	1	1

Bzw.:

• Dabei bedeutet:
  • x_ij = 1 : v_j ∈ e_i
  • x_ij = 0 : v_j ∉ e_i
  • Wenn eine Kante existiert, dann ist dies mit einer 1 gekennzeichnet.
  • Wenn keine Kante existiert, dann ist es mit einer 0 gekennzeichnet.

• Ziel:
  • Kodierung eines Graphen als Bitstring, d.h. als ein Wort über dem Alphabet Σ = {0,1}
  • Lösung = G → ( 1 … 1 0 1 … 1 0 x₁₁  x₁₂ .. x_mn)
  • n-mal die 1  = Anzahl der Knuten in G
  • Schließende 0
  • n-mal die 1 = Anzahl der Kanten in G
• Bsp.:
• Eingaben des Entscheidungsproblems Clique sind von der Form (G, K) → ( 1ⁿ 0 1^m 0 x₁₁ … x_mn  k₁ … k_t )
  • G = Graph
  • k = natürliche Zahl
  • Binärdarstellung von k
• Für das Entscheidungsproblem Clique zerfällt die Menge Σ* ( Menge aller Wörter ) in drei Teilmengen.
  • Teilmenge 1:
    • Wörter, die keine Eingaben des Entscheidungsproblems repräsentieren. ( 1 1 1 0 1 1 0 1 ) müssten mehr Zahlen sein
  • Teilmenge 2:
    • Wörter, die Eingaben repräsentieren, für die Frage mit nein beantwortet wird. ( „Eingabe G, k: hat keine Clique der Größe k“ )
  • Teilmenge 3:
    • Wörter, die Eingaben repräsentieren, für die die Frage mit ja beantwortet wird. ( „Eingabe G, k: hat eine Clique der Größe k“ )
    • Diese Dritte Teilmenge bildet eine Sprache L.
  • Das zugehörige Wortproblem L = Menge aller Wörter, die Ja-Eingaben repräsentieren …
    • Eingabe: Wort w ∈ Σ*
    • Frage: Gilt w ∈ L?
  • … heißt das zum Entscheidungsproblem Clique assoziierte Wortproblem.

2. Endliche Automaten und reguläre Sprachen

• 2.1 Endliche Automaten
  • Definition: ( Deterministischer endlicher Automat (DEA)) Ein DEA ist von der Form A = ( Q, Σ, q₀, δ, F ) mit
    • Q= Zustandsmenge / endliche Menge von Zuständen
    • Σ = endliches Alphabet
    • q₀ ∈ Q = Anfangszustand
    • δ: Q x Σ → Q ( Übergangsfunktion)
    • F ⊆ Q = Eine Menge von Endzuständen

Allgemeine Vorstellungvon der Arbeitsweise ist wie folgt:

• Am Anfang steht der Lesekopf auf dem ersten Feld des Bandes und das Programm befindet sich im Zustand q₀ ( Anfangszustand )
• Im nächsten Schritt passiert folgendes:
  1. Liest der Lesekopf den Buchstaben x ∈ Σ und befindet sich das Programm im Zustand q ∈ Q, dann bewegt sich des Lesekopf um eine Stelle nach Rechts und das Programm geht in den Zustand δ(q,x) über.