Ubungen zur Vorlesung Berechenbarkeit und

Prof. Dr. Rolf Wanka
Bernd Bassimir, Moritz Mühlenthaler,
Alexander Raß, Sebastian Tschuppik
Erlangen, 22. Dezember 2015
Abgabe bis 11.1.16, 23:59 Uhr
Übungen zur Vorlesung
Berechenbarkeit und Formale Sprachen
WS 2015/2016
Blatt 10
Je mehr Plus-Zeichen +, desto wichtiger, je mehr Sterne ?, desto schwieriger.
AUFGABE 50:
[Präsenzaufgabe,++, ?] Sei G = (V, Σ, P, S) eine beliebige kontextfreie Grammatik. Eine Variable A ∈ V
∗
heißt nützlich, falls es ein Wort w ∈ Σ∗ gibt, so daß A → w. Anderenfalls wird A nutzlos genannt.
(a) Geben Sie einen Algorithmus an, der die nutzlosen Variablen von G berechnet, beweisen Sie seine
Korrektheit und bestimmen Sie seine Laufzeit in Abhängigkeit der Komponenten von G.
(b) Folgern Sie daraus, daß es zu gegebener kontextfreier Grammatik G entscheidbar ist, ob L(G) = 0/ ist
oder nicht.
AUFGABE 51 (6 Punkte):
[+ + +, ? ? ?] Geben Sie für die beiden folgenden Sprachen Grammatiken vom Typ Chomsky-3 an und
begründen Sie die Korrektheit.
(a) L1 = {w | w ∈ {0, 1}∗ , w enthält nicht die Teilfolge 011}
(b) L2 = {w | w ∈ {0, 1}∗ , w ist Binärdarstellung einer Zahl n ∈ IN mit n mod 5 = 3}
Hinweis: Ein möglicher Ansatz besteht darin, zweckmäßige endliche Automaten zu den Sprachen anzugeben
und diese in Grammatiken zu verwandeln.
AUFGABE 52 (4 Punkte):
[+ + +, ??] Sei L = {0` 1k | `, k ∈ IN, ` < k}. Ziel der Aufgabe ist es, zu zeigen, daß L nicht regulär ist.
Jemand behauptet, eine Grammatik G = (V, Σ, P, S) vom Typ Chomsky-3 gefunden zu haben mit L = L(G).
G soll n Variablen besitzen, also n = |V |.
Geben Sie in Abhängigkeit von n ein Wort z ∈ L an mit folgender Eigenschaft:
Aus einer Herleitung von z durch G (also S → · · · → z) können Sie Wörter ẑ konstruieren mit der Eigenschaft:
• ẑ besitzt eine Herleitung durch G;
• ẑ 6∈ L
Zeigen Sie formal, daß z die genannte Eigenschaft besitzt.
AUFGABE 53 (4 Punkte):
[+ + + + +, ??] (Alte Klausuraufgabe)
(a) Aus der Vorlesung kennen Sie das NP-vollständige Knotenüberdeckungsproblem (engl.: Vertex Cover)
VC := {hG, ki | k ∈ IN, G = (V, E) ist ein ungerichteter Graph, für den es eine Knotenmenge U, U ⊆ V ,
gibt mit |U| = k, so daß für jede Kante {u, v} ∈ E gilt: u ∈ U oder v ∈ U}.
bin(a) bezeichne die Binärdarstellung der natürlichen Zahl a. Sei
n
S UMME = bin(a1 )# · · · #bin(an ) | n ≥ 2, a1 = ∑ ai .
i=2
Zeigen Sie: S UMME ≤p VC
Hinweis: Vergessen Sie nicht, die Laufzeit der Berechnung der Reduktionsfunktion zu begründen.
(b) Angenommen, P = NP. Zeigen Sie, daß S UMME dann NP-vollständig ist, indem Sie zeigen: VC ≤p
S UMME
Begründen Sie insbesondere durch Hinweis auf die Definition des Begriffs NP-Vollständigkeit, warum
S UMME damit NP-vollständig ist (was gilt dann für alle NP-vollständigen Probleme wie (nur als
Beispiel) SAT?).
Es kommen noch zwei Seiten mit zwei bonuspunktereichen Zusatzaufgaben und einer kurzen Biographie
David Hilberts.
AUFGABE 54 (4 Bonus- Punkte):
[++, ??] Sei
L = {w | w ∈ {a, b}∗ , #a (w) = #b (w)} .
Geben Sie eine kontextfreie Grammatik G an, die L erzeugt. Beweisen Sie die Korrektheit Ihrer Grammatik.
(#a (w) gibt die Anzahl an, wie oft das Zeichen a in w vorkommt)
Hinweis: Die Lösungsidee besteht darin, eine rekursive Beziehung der Wörter in L zu finden. Ist z. B. w ∈ L
von der Form aw0 b, dann ist auch w0 ∈ L. Dieser Beziehung würde die Produktion S → aSb entsprechen.
Schwieriger ist der Fall für Wörter wie aababbbbaa ∈ L. Zählen Sie positionsweise von links nach rechts
den Überschuß“ an as (der auch negativ sein kann ,). Was muß passieren?
”
Vergessen Sie nicht, daß das leere Wort ε auch in L ist.
AUFGABE 55 (8 Bonus- Punkte):
[+ + +, ? ? ?] Abgabe bis 19.1.16
In dem in Aufgabe 36 auf Blatt 6 erwähnten Aufsatz schreibt Martin Grötschel über das NP-schwere TSP:
Exakte und approximative Lösungsverfahren werden an Beispielen skizziert, und es wird angedeutet, dass man, obwohl TSPs zu den theoretisch schweren Problemen zählen, in der Praxis
TSPs von atemberaubender Größe optimal lösen kann.
Ziel dieser Aufgabe ist es, ein ziemlich kleines Problem kennenzulernen, das sich gegen Holzhammeransätze
hartnäckig zu wehren versteht, die sog. 17 × 17 Challenge.
Das Grid Coloring Problem GCP kann sehr einfach beschrieben werden: The n × n grid is 4-colorable if
”
there is a way to 4-color the vertices of the n × n grid so that there is no rectangle with all four corners the
same color.“ Wir schreiben dann: GCP := {n | das n × n-Gitter ist 4-färbbar}.
Z. B. ist 7 ∈ GCP, da das 7 × 7-Gitter 4-färbbar ist, wie die folgende Abbildung links zeigt:
1324234
1323443
2214343
2123424
3423334
2434433
4341344
Eines der Rechtecke ist markiert, es geht bei diesem Problem nur um die Farben in den vier Ecken der
Rechtecke. Es müssen mindestens zwei verschiedene Farben sein. Eine mögliche Kodierung dieser Färbung
sehen Sie rechts.
Einfach mit Computer-Power zu zeigen ist, daß {2, . . . , 16} ⊆ GCP, und daß 19 6∈ GCP und damit n 6∈ GCP
für alle n ≥ 19 kann man durch Nachdenken beweisen. Die Fälle n=17 und n=18 waren lange unbekannt.
Erst seit Februar 2012 weiß man, daß 18 ∈ GCP (und damit auch 17 ∈ GCP) (veröffentlicht in: B. Steinbach, C. Posthoff. Extremely Complex 4-Colored Rectangle-Free Grids Solution of Open Multiple-Valued
Problems. doi:10.1109/ISMVL.2012.12). Nachdenken und die computergestützte Suche nach Symmetrien
führte erst zum Erfolg.
GCP ist also eine endliche Menge.
(a) Modellieren Sie die Aufgabe, eine 4-Färbung für das n × n-Gitter zu berechnen, durch eine KNF Φn ,
so daß gilt:
n ∈ GCP ⇐⇒ Φn ∈ SAT
Aus einer erfüllenden Belegung soll also eine Färbung abgeleitet werden können und umgekehrt. Mit
anderen Worten: Zeigen Sie GCP ≤p SAT.
Wieviele Variablen benötigen Sie? Geben Sie size(Φn ) an.
(b) Implementieren Sie ein Programm, das für n = 8, n = 10 und n = 16 Färbungen berechnet. Und wie
ist es mit 17 und 18 ?
Auf der Webseite der Vorlesung finden Sie die Datei GCP.txt, in die sie Ihre mutmaßlichen Lösungen eingeben können. Schicken Sie die Dateien (Lösung und Programm) per Email an Alexander Raß
([email protected]) mit dem Betreff: GridColoring (kein Blank)
Bearbeiten Sie ein NP-vollständiges Problem und tun Sie was Gutes:,
https://edom.mi.uni-erlangen.de/weihnachten-2015/
Das BFS-Team wünscht Ihnen ein frohes Weihnachtsfest, einen guten Rutsch
und ein erfolgreiches Jahr 2016!
DAVID H ILBERT wurde vor fast genau 154 Jahren, am 23. Januar 1862, in
Königsberg geboren. Er gilt als einer der bedeutensten Mathematiker der neueren Zeit. Sein legendärer Vortrag auf dem internationalen Mathematikerkongress in Paris im Jahre 1900 hat die Forschung der Mathematik und später
der Theoretischen Informatik nachhaltig beeinflußt. Der Gödelsche Unvollständigkeitssatz (1931) und der für uns so wichtige Aufsatz von Alan Turing
(1936) sind ohne Hilberts Arbeiten nicht vorstellbar. Das 10. Hilbertsche Problem, eine heute typische Fragestellung der Theoretischen Informatik (“Gibt
es ein Verfahren, das für eine beliebige diophantische Gleichung entscheidet,
ob sie lösbar ist?”, vgl. Aufgabe 37(b) auf Blatt 7), wurde 1970 durch eine Reduktion des Halteproblems mit N EIN beantwortet. Wie ein roter Faden zieht
sich durch seine Arbeiten die Frage nach Axiomen für bestimmte Gebiete und
nach Regeln, wie man aus den Axiomen Folgerungen ableiten kann.
Im Jahr 1885 promovierte er in Königsberg, und 1886, im Alter von 24 Jahren (Foto), habilitierte er
sich. F ELIX K LEIN, unter anderem 1872 – 1875 Professor für Mathematik an der Uni Erlangen und heute
der Namensgeber für das neue Mathematik/Informatik-Gebäude, holte Hilbert 1895 nach Göttingen, damals
eines der bedeutendsten Zentren der Mathematik und Physik weltweit. Hilbert und Klein waren es dann
auch, die E MMY N OETHER aus Erlangen nach Göttingen brachten und eine berühmte Auseinandersetzung
(das gab’s damals wie heute) zwischen der Uni Göttingen und dem zuständigen preußischen Ministerium
anführten, als es um die Habilitierung Emmy Noethers ging. Natürlich setzte sich das Ministerium (damals
wie heute) mit dem Verbot durch.
Hilbert hat zwischen 1898 und 1934 insgesamt 69 Doktoranden hervorgebracht.
(siehe http://genealogy.math.ndsu.nodak.edu/id.php?id=7298&fChrono=1)
Unter ihnen ist W ILHELM ACKERMANN, der die Berechenbarkeitstheorie untersuchte, und nach dem die
berühmte Ackermann-Funktion, die man beweisbar nicht mit (klassischen) for-Schleifen berechnen kann,
benannt ist.
In bewußter Analogie zu den 23 Problemen aus Hilberts Vortrag (und den zugehörigen Ergänzungen)
im Jahr 1900 hat das Clay Mathematics Institute (CMI) im Jahr 2000 eine Liste von sieben Problemen, die
sog. Millennium-Probleme, zusammengestellt und für jede Lösung eine Million US-Dollar ausgelobt. Das
P-NP-Problem ist dabei das Problem mit der Nummer 4.
Den unwiederbringlichen Verlust kreativer Köpfe der Universität Göttingen, darunter auch einige seiner
eigenen Doktoranden, in der Zeit nach 1933 hat Hilbert mehrfach öffentlich bedauert. Er starb am 14. Februar
1943, im Alter von 81 Jahren, an den Folgen eines Sturzes bei einem Spaziergang.

Download Report