Gedächtnisprotokoll

Vordiplomklausur Berechenbarkeit und Komplexität bei Prof. Hromkovič im Wintersemester 02/03

Aufgabe 1 (10 Punkte)

a) Konstruieren sie einen deterministischen endlichen Automaten, der L = {x01100y | x, y ∈ {0, 1}^{∗}} erkennt.

b) Geben sie Kl[q] an.

c) Beweisen sie, daß der EA mindestens 6 Zustände haben muß.

Aufgabe 2 (10 Punkte)

Bearbeiten Sie nur genau eine der Teilaufgaben A oder B. Werden beide Teilaufgaben bearbeitet, wird nur Teilaufgabe A gewertet.

A) Zeigen sie: (L_{diag})^{∁} ≤_{R} L_{U} B) Zeigen sie: L(M) = {Kod(M)|M hält immer } ist nicht rekursiv. Sie dürfen dazu alle aus der Vorlesung bekannten Reduktionen benutzen.

Aufgabe 3 (10 Punkte)

Zeigen Sie, daß für jede platzkonstruierbare Funktion Funktion s(n) gilt, daß

NT IME(s(n)) ⊆ SP ACE(s(n))

indem Sie eine geeignete deterministische Simulation eine NTM beschreiben.

Aufgabe 4 (10 Punkte)

Bearbeiten Sie nur genau eine der Teilaufgaben A oder B. Werden beide Teilaufgaben bearbeitet, wird nur Teilaufgabe A gewertet.

A) Zeigen Sie, daß unter der Voraussetzung P ≠ NP für kein d > 1 einen polynomiellen d-Approximationsalgorithmus für das TSP gibt. B) 3−COV ER = {((X, F) , k) | X ist eine endliche Menge und F ⊆ P(X), so daß jedes Element aus X in ≤ 3 Menge aus F vorkommt, und es existiert Teilmenge C ⊆ F mit X = ⋃_{S⊆C} S und |C| ≤ k.

Zeige: 3−COV ER ist NP-schwer. Sie dürfen alle aus der Vorlesung bekannten Reduktionen nutzen.

Erstellt am 12. Mai 2003 von Florian Schmidt (Florian.Schmidt@rwth-aachen.de). Eine neue Version gibt’s, wenn Fehler in dieser sind (und mich jemand darauf hinweist).