Vordiplomklausur ”Berechenbarkeit und Komplexität“, SS 2002

Prof. Hromkovič, Lehrstuhl I für Informatik, 01.08.2002

Aufgabe 1 (10 Punkte) Man gebe einen (deterministischen) endlichen Automaten an, der die folgende Sprache akzeptiert:

L = {w ∈ (Σ_{bool})^{∗} | w enthält mindestens zweimal das Teilwort 01 und |w|_{0} ist gerade}.

Man gebe die Klassen Kl[q] = {w ∈ (Σ_{bool})^{∗} | δ̂(q_{0}, w) = q} für jeden Zustand q des konstruierten Automaten an (dabei ist q_{0} der Anfangszustand des Automaten).

Aufgabe 2 (5 + 5 Punkte) Es sei L = {0^{n} 1 0^{2^{n}} | n ∈ ℕ}.

a) Man zeige mit dem Pumping-Lemma, daß L nicht regulär ist.

b) Man zeige mit der Kolmogorov-Komplexität, daß L nicht regulär ist.

Aufgabe 3 (10 Punkte) Hier ist genau einer der Aufgabenteile (3.A) und (3.B) zu bearbeiten. Werden beide Teile bearbeitet, wird nur (3.A) gewertet. (3.A) Man zeige L_{H} ⩽_{R} L_{H,λ}, das heißt, man zeige (ohne L_{H} ⩽_{EE} L_{H,λ} vorauszusetzen), daß

das Entscheidungsproblem L_{H} lösbar ist, wenn man einen Entscheidungsalgorithmus für L_{H,λ} = {Kod(M) | M ist Turingmaschine, die auf λ hält} hat.

(3.B) Es sei L_{rej} = {Kod(M)#w | M ist Turingmaschine, die auf w im Zustand q_{reject} hält}. Man zeige, daß L_{rej} nicht rekursiv ist. Dabei dürfen alle aus der Vorlesung bekannten Reduktionen benutzt werden.

Aufgabe 4 (10 Punkte) Hier ist genau einer der Aufgabenteile (4.A) und (4.B) zu bearbeiten. Werden beide Teile bearbeitet, wird nur (4.A) gewertet. (4.A) Man gebe einen 2-Approximationsalgorithmus für das Δ-TSP (Traveling-Salesman-

Problem mit Dreiecksungleichung) an und beweise die Approximationsgüte.

(4.B) Es sei

HITTING-SET = {((X, F), k) | X ist eine endliche Menge, F ⊆ P(X) und es gibt
ein C ⊆ X mit|C| ⩽ k, so daß C ∩ S ≠ ∅ für alle
S ∈ F gilt}.

Man beweise die NP-Vollständigkeit von HITTING-SET. Dabei dürfen alle aus der Vorlesung bekannten Reduktionen benutzt werden.

Hierbei handelt es sich nicht um die Originalklausur, sondern nur um ein Gedächtnisprotokoll. Zum Bestehen der Klausur brauchte man 20 Punkte.