Skript zur Vorlesung Diskrete Modellierung · 2020. 9. 22. · Um die richtigen Geisterfallen auszulegen, müssen die Geisterjäger wissen, welche Arten von Geistern dort spuken

1 BeispielklausurenDie Modulabschlussprüfung Diskrete Modellierung findet in Form einer 120 minütigen Klausurstatt. Die Erstklausur findet am 25.02.2016 um 9:00 s.t. und die Zweitklausur am 07.04.2016ebenfalls um 9:00 s.t. statt. Der Ort ist jeweils H V oder H VI im Jügelhaus.

Details zum Ablauf der Klausur:• Grundsätzlich gelten die in der Ordnung Ihres Studiengangs festgelegten Regelungen. Dieses

hier sind nur ergänzende Hinweise.

• Vor Beginn der Klausur wird die Zuweisung in die Hörsäle mitgeteilt.

• Legen Sie ihre „Goethe-Card“ deutlich sichtbar auf ihren Platz, damit wir ihre Identitätüberprüfen können.

• Außer einem dokumentenechten Schreibstift sind keine weiteren Hilfsmittel zugelassen. DasMitbringen nicht zugelassener Hilfsmittel stellt eine Täuschung dar und führt zwangsläufigzum Nichtbestehen der Klausur. (Schalten Sie insbesondere Handys und Smartwatches vorBeginn der Klausur aus.)

• Schreibpapier wird von uns bereitgestellt. Gegebenenfalls können auch die beigefügtenZusatzblätter benutzt. Weitere Blätter sind auf Nachfrage erhältlich.

• Begründungen sind nur dann notwendig, wenn die Aufgabenformulierung dies verlangt.

• Jedes(!) Blatt der abgegebenen Lösung muss mit Namen, Vornamen und Matrikelnummergekennzeichnet sein.

• Werden zu einer Aufgabe zwei oder mehr Lösungen angegeben, so gilt die Aufgabe als nichtgelöst. Entscheiden Sie sich also immer für eine Lösung.

Checkliste - zur Klausur müssen Sie mitbringen:• einen dokumentenechten Schreibstift

• Ihre Goethe-Card

Durch die in den Übungen gesammelten Punkte kann ein Bonus für die Klausur erworbenwerden. Zur Benotung wird die Summe aus dem Klausurergebnis und der Bonuspunkte verwendet.Die Klausur ist bestanden, wenn mit dem Bonus mindestens 50% der in der Klausur erzielbarenPunkte erreicht werden.Nachfolgend finden Sie die Aufgaben der Klausuren aus den Wintersemestern 2014/15 und

2011/12 sowie den Sommersemestern 2011 und 2015.

1

Aufgaben der Klausur SoSe 2015

Name, Vorname: Matrikelnummer:

Aufgabe 1:(a) [8 Pkte]Das alte Philosophicum auf dem Campus Bockenheim steht schon so lange leer, dass dort

inzwischen Geister spuken. Da das Gebäude umgebaut werden soll, werden die BockenheimerGeisterjäger beauftragt. Um die richtigen Geisterfallen auszulegen, müssen die Geisterjägerwissen, welche Arten von Geistern dort spuken. Dabei kommen drei Sorten von Geistern inFrage: Poltergeister, Zeitgeister und Himbeergeister.Bei ihren Vorbereitungen machen die Geisterjäger folgende Beobachtungen über das Philo-sophicum:Beobachtung 1: Dort spuken Poltergeister oder Zeitgeister.Beobachtung 2: Falls dort Zeitgeister spuken, dann spuken dort keine Himbeergeister und

keine Poltergeister.Beobachtung 3: Wenn dort Himbeergeister spuken, dann spuken dort auch Zeitgeister.Formalisieren Sie die drei Aussagen durch je eine aussagenlogische Formel, indem Sie dieatomaren Aussagen H (Himbeergeister spuken), P (Poltergeister spuken) und Z (Zeitgeisterspuken) benutzen.

ϕBeobachtung 1 :=

ϕBeobachtung 2 :=

ϕBeobachtung 3 :=

Nehmen Sie an, dass alle drei Beobachtungen zutreffen. Ist es möglich, dass im PhilosophicumHimbeergeister spuken? Beweisen Sie Ihre Antwort.

Sie können die folgende Vorlage für Ihre Wahrheitstafel verwenden:H P Z ϕBeobachtung 1 ϕBeobachtung 2 ϕBeobachtung 3

0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1

– Seite 3 von 20 –

(b) [6 Pkte]Geben Sie zu jeder der folgenden aussagenlogischen Formeln an, ob sie erfüllbar und/oderallgemeingültig ist. Kreuzen Sie alle richtigen Antworten an.Wenn Sie „erfüllbar“ ankreuzen, dann müssen Sie eine Belegung angeben, die die Formelerfüllt. Falls Sie „allgemeingültig“ ankreuzen, müssen Sie Ihre Antwort beweisen und an-sonsten eine Belegung angeben, die die Formel nicht erfüllt.

• ϕ =((X1 → (X1 → X2))↔ X1

)

erfüllbar: ja nein (0.5 Pkte)

allgemeingültig: ja nein (0.5 Pkte)

(1 Pkt)Falls ϕ erfüllbar ist, geben Sie hier eine zu ϕ passende Belegung an, die ϕ erfüllt:

(1 Pkt)Falls ϕ allgemeingültig ist, beweisen Sie Ihre Antwort; andernfalls geben Sie eine zu ϕpassende Belegung an, die ϕ nicht erfüllt:

• ψ =((X1 → (X1 → X2))↔ (X1 → X2)

)

erfüllbar: ja nein (0.5 Pkte)

allgemeingültig: ja nein (0.5 Pkte)

(1 Pkt)Falls ψ erfüllbar ist, geben Sie hier eine zu ψ passende Belegung an, die ψ erfüllt:

(1 Pkt)Falls ψ allgemeingültig ist, beweisen Sie Ihre Antwort; andernfalls geben Sie eine zu ψpassende Belegung an, die ψ nicht erfüllt:



(c) [10 Pkte](i) (6 Pkte)Seien ϕ, ψ und χ beliebige aussagenlogische Formeln. Gelten die folgenden semantischen

Äquivalenzen (≡)?Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz erhalten Sie zweiPunkte, für jedes falsche Kreuz werden zwei Punkte abgezogen; wird keine Optionangekreuzt, erhalten Sie keinen Punkt. Ihre Gesamtpunktzahl für diese Teilaufgabe istaber mindestens 0.

¬(ϕ ∨ (¬ψ ∧ ¬χ)) ≡ (¬ϕ ∧ (ψ ∨ χ)) wahr falsch

((ϕ ∧ ψ)→ ϕ) ≡ (ϕ ∨ ¬ϕ) wahr falsch

(ϕ→ ψ) ≡ (¬ψ → ¬ϕ) wahr falsch

(ii) (4 Pkte)Geben Sie eine zur Formel

ϕ :=((X1 ↔ (X2 ↔ X3)

)∧X1

)

äquivalente Formel ϕ′ in disjunktiver Normalform an. Geben Sie auch Ihren Lösungs-weg an.(Ihr Lösungsweg ist nur dann relevant, wenn Ihre Formel ϕ′ falsch ist; Sie können dann Teil-punkte erhalten. Für die richtige Formel erhalten Sie stets die volle Punktzahl.)


Aufgabe 2:

(a) [4 Pkte]Sei G = (V,E) der ungerichtete Graph mit Knotenmenge V = {1, 2, 3, 4, 5, 6} und Kanten-menge E =

{{1, 2}, {1, 4}, {2, 6}, {3, 4}, {3, 6}, {4, 5}, {5, 6}}.

(i) (1 Pkt)Geben Sie die graphische Darstellung von G an.

Graphische Darstellung:

2

1 6

5

43

(ii) (1 Pkt)Geben Sie alle Nachbarn von Knoten 4 an.

(iii) (1 Pkt)Geben Sie einen einfachen Kreis der Länge 5 in G an.

(iv) (1 Pkt)Ist G bipartit? Begründen Sie Ihre Antwort!



(b) [8 Pkte]Betrachten Sie die folgenden Graphen G1, G2 und G3:

a b

cd

e

f

g

h

G1

a b c d

e f g h

G2

0

1

2

34

5 6

78

9

G3

(i) (1 Pkt)Geben Sie einen Hamiltonweg in G1 an:

(ii) (4 Pkte)Welche der folgenden Aussagen sind wahr, welche falsch?

Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz bekommen Sie einenPunkt, für jedes falsche Kreuz wird ein Punkt abgezogen; wird keine Optionangekreuzt, erhalten Sie keinen Punkt. Ihre Gesamtpunktzahl ist aber mindestens 0.

• G1 ist stark zusammenhängend. wahr falsch

• G2 ist azyklisch. wahr falsch

• G1 und G2 sind isomorph. wahr falsch

• Alle Knoten in G3 haben denselben Grad. wahr falsch

(iii) (1 Pkt)Geben Sie ein größtmögliches Matching für G3 an:

(iv) (2 Pkte)Ist die folgende Aussage wahr oder falsch? Begründen Sie Ihre Antwort.

Jeder stark zusammenhängende gerichtete Graph besitzt einen Hamiltonweg.

wahr falsch

Begründung:


(c) [10 Pkte]Alice, Bob, Charlie und Eve haben sich sieben Filme auf DVD gekauft: Carnage, The Nego-tiator, Django Unchained, Contact, Sydney, Gangs of New York und Titanic.Als sie die DVDs in die Hand nehmen, fällt ihnen jedoch auf, dass folgende Schauspieler inmehreren der Filme mitspielen:• Samuel L. Jackson spielt in Django Unchained, in The Negotiator und in Sydney mit.• Leonardo DiCaprio spielt in Gangs of New York, in Django Unchained sowie in Ti-

tanic mit.• John C. Reilly spielt in Carnage mit, außerdem in Sydney und in Gangs of New York.• Jodie Foster spielt in Carnage und in Contact mit.• Christoph Waltz spielt in Django Unchained und in Carnage mit.• Kate Winslett spielt sowohl in Carnage als auch in Titanic mit.• David Morse spielt in den beiden Filmen Contact und The Negotiator mit.

(i) (2 Pkte)Stellen Sie den Konfliktgraphen auf. Ein Konflikt zwischen zwei Filmen besteht genaudann, wenn einer der oben genannten Schauspieler in beiden Filmen mitspielt.(Beispielsweise besteht ein Konflikt zwischen Django Unchained und Sydney, da in beidenFilmen Samuel L. Jackson mitspielt.)

Django Carnage

Titanic

Gangs of NY

Sydney

Negotiator Contact

(ii) (2 Pkte)Da Alice und Bob nicht mehrmals am Tag denselben Schauspieler sehen wollen, verteilen siedie Filme auf mehrere Tage. Dabei dürfen am selben Tag nicht zwei Filme geschaut werden,in denen derselbe Schauspieler mitspielt.Aufgrund ihres vollen Terminplans stehen den beiden nur 4 Tage zum Filmschauen zur Verfü-gung.

Formulieren Sie Alice’ und Bobs Vorhaben als graphentheoretische Fragestellung.



(iii) (2 Pkte)Können Alice und Bob ihr Vorhaben in die Tat umsetzen? Beweisen Sie, dass Ihre Antwortkorrekt ist.

(iv) (4 Pkte)Charlie und Eve haben einen anderen Plan: Sie wollen alle Filme hintereinander an einemeinzigen Tag schauen. Dabei dürfen aber nicht zwei Filme direkt aufeinander folgen, in denenderselbe Schauspieler mitspielt. (Beispielsweise kann Django Unchained direkt vor oder nachContact geschaut werden, nicht aber direkt vor oder nach Sydney.)Außerdem wollen sie unbedingt mit dem Film Titanic beginnen.

Können Charlie und Eve ihren Plan umsetzen? Beweisen Sie, dass Ihre Antwort korrekt ist.

Django

Carnage

Titanic

Gangs of NY

Sydney

Negotiator

Contact

(Sie können den hier abgebildeten Graphen für Ihre Lösung verwenden.)


Aufgabe 3:[8 Pkte]Betrachten Sie den folgenden Webgraphen G und den Dämpfungsfaktor d = 1

2 :

1

2

3

(i) (4 Pkte)Geben Sie die Matrix Pd(G) an.

Pd(G) :=

(ii) (1 Pkt)Vervollständigen Sie die folgende Definition:

Eine Verteilung π ist genau dann eine stationäre Verteilung für die Markov-Kette(G,Pd(G)), wenn

(iii) (3 Pkte)Bestimmen Sie den Page-Rank Vektor PR = (PR1,PR2,PR3), also die stationäre Verteilungder Markov-Kette (G,Pd(G)).

PR1 =

PR2 =

PR3 =



Aufgabe 4:(a) [9 Pkte]

(i) Sei Σ := {a, b}. Die Sprache L ⊆ Σ∗ sei wie folgt definiert:L := {w ∈ Σ∗ : der erste und der letzte Buchstabe von w sind unterschiedlich}

Geben Sie einen regulären Ausdruck R an, so dass L(R) = L. (3 Pkte)

(ii) (4 Pkte)Sei A der folgende nichtdeterministische Automat über dem Alphabet Σ := {a, b}:

q0 q1 q2

q3 q4

a

b

b

a

a, b

a, b

Welche der folgenden Worte liegen in der von A akzeptierten Sprache L(A), welchenicht? Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz erhalten Sieeinen Punkt, für jedes falsche Kreuz wird ein Punkt abgezogen; wird keine Optionangekreuzt, erhalten Sie keinen Punkt. Ihre Gesamtpunktzahl ist aber mindestens 0.

Wort . . . liegt in L(A)?

aaab ja nein

baq4 ja nein

bbbb ja nein

abaa ja nein

(iii) (2 Pkte)Geben Sie eine (mathematische oder umgangssprachliche) Beschreibung der SpracheL(A) des obigen NFAs an, zum Beispiel in Form eines regulären Ausdrucks.


(b) [6 Pkte]Sei A der folgende nichtdeterministische Automat über dem Alphabet Σ := {a, b, c}:

1 2 3c

a, bb

a, c

b

Wandeln Sie den NFA A mit Hilfe der Potenzmengenkonstruktion in einen vollständigenDFA A′ um. Berücksichtigen Sie nur solche Zustände von A′, die vom Startzustand von A′aus erreicht werden können, und geben Sie die graphische Darstellung von A′ an.



(c) [7 Pkte]Geben Sie für jede der folgenden beiden Sprachen an, ob sie regulär ist. Kreuzen Sie allerichtigen Antworten an. Für jedes korrekte Kreuz erhalten Sie einen Punkt, für jedes falscheKreuz wird ein Punkt abgezogen; wird keine Option angekreuzt, erhalten Sie keinenPunkt. Ihre Gesamtpunktzahl ist aber mindestens 0.Beweisen Sie, dass Ihre jeweilige Antwort korrekt ist.

L1 := {anbm : n,m ∈ N}

regulär: ja nein

Beweis:

L2 := {wbw : w ∈ {a, b}∗}

regulär: ja nein

Beweis:


(d) [8 Pkte](i) Der folgende deterministische Automat A1 über dem Alphabet Σ={a, b, c} sei gegeben:

q4 q3

q1 q2

ab, c

a

b

c

a

b c

a

b

c

(3 Pkte)Geben Sie für die Zustandspaare {q1, q2}, {q2, q3}, {q3, q4} jeweils einen Zeugen für ihreNicht-Äquivalenz bezüglich der Verschmelzungsrelation an.

Erinnerung: Ein Zeuge für die Nicht-Äquivalenz eines Zustandspaares {qi, qj} ist einWort z ∈ Σ∗, sodass δ(qi, z) ∈ F und δ(qj , z) 6∈ F (oder umgekehrt: δ(qi, z) 6∈ F undδ(qj , z) ∈ F ) gilt.

Zeuge für q1 6≡A1 q2:



(ii) (5 Pkte)Der folgende deterministische Automat A2 über dem Alphabet Σ = {d, e} sei gegeben:

12

3 4 5

e

d

e

d

e

d

e d

e

d

Minimieren Sie A2, d.h. finden Sie einen vollständigen DFA A′2 mit L(A′2) = L(A2) undminimaler Zustandszahl. Sie müssen keine Zwischenschritte angeben. Geben Sie A′2 ingraphischer Darstellung an.

Minimaler DFA A′2:

Weiterer Platz zur Lösung dieser Aufgabe befindet sich auf der nächsten Seite.



Minimaler DFA A′2 (Fortsetzung):


Aufgabe 5:

(a) [6 Pkte]Die kontextfreie Grammatik G=(Σ, V, S, P ) sei definiert durch V :={S,A,B}, die acht Ter-minale

Σ :={

_ , nix , fleiss , kommt , ohne , von , preis , kein}

und

P := { S → ohne_A | von_B,A→ fleiss_A_preis | kein,B → nix_B_nix | kommt }.

(i) (4 Pkte)Welche der folgenden Worte liegen in der von G erzeugten Sprache L(G), welche nicht?Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz erhalten Sie einenPunkt, für jedes falsche Kreuz wird ein Punkt abgezogen; wird keine Optionangekreuzt, erhalten Sie keinen Punkt. Ihre Gesamtpunktzahl ist aber mindestens 0.

Wort . . . liegt in L(G)?

von_nix_kein_preis ja nein

von_nix_kommt_nix ja nein

ohne_fleiss_kein_preis_preis ja nein

von_nix_nix_kommt_nix_nix ja nein

(ii) (2 Pkte)Geben Sie einen Ableitungsbaum für das Wortohne_fleiss_fleiss_kein_preis_preis ∈ L(G) an.



(b) [4 Pkte]Die Sprache L über dem Alphabet Σ = { ( , ) , [ , ] } von runden und eckigen Klammernsei wie folgt rekursiv definiert:Basisregel: (B) Es gilt () ∈ L und [ ] ∈ L.Rekursive Regeln: (R1) Ist w ∈ L, so sind auch (w) ∈ L und [w] ∈ L.

(R2) Sind u, v ∈ L, so ist auch uv ∈ L.Beispielsweise ist [(()[ ])] ∈ L ein Wort dieser Sprache.Geben Sie eine kontextfreie Grammatik G an, so dass L(G) = L.

G = (Σ, V, S, P )

V =

P =


(c) [6 Pkte]Die Funktion f : N→ N sei für alle n ∈ N wie folgt definiert:

f(n) :={

0 falls n = 0,f(n− 1) + 2n falls n ≥ 1.

Zeigen Sie durch vollständige Induktion, dass f(n) = n2 + n für alle n ∈ N gilt.





Aufgaben der Klausur WS 14/15


Aufgabe 1: (24 Punkte)

(a) (8 Pkte)Mary Modder besucht die Zauberschule Modwarts. Im Unterrichtsfach Zaubertränke muss sieeinen Konzentrationstrank zubereiten. Dazu muss sie entscheiden, welche der drei möglichenZutaten Fliegenpilze, Krötenaugen und Spinnenbeine sie verwendet (oder nicht verwendet).Laut Rezeptbuch muss sie die drei folgenden Anweisungen beachten:Anweisung 1: Mindestens eine der drei Zutaten Fliegenpilze, Krötenaugen und Spinnen-

beine muss verwendet werden.Anweisung 2: Wenn Fliegenpilze verwendet werden, darf keine der anderen beiden Zutaten

verwendet werden.Anweisung 3: Werden keine Fliegenpilze und keine Spinnenbeine verwendet, so dürfen auch

keine Krötenaugen verwendet werden.Formalisieren Sie die drei Aussagen durch je eine aussagenlogische Formel, indem Sie dieatomaren Aussagen F (Fliegenpilze werden verwendet), K (Krötenaugen werden verwendet)und S (Spinnenbeine werden verwendet) benutzen.

ϕAnweisung 1 :=

ϕAnweisung 2 :=

ϕAnweisung 3 :=

Nach etwas Überlegen hat Mary den Verdacht, dass diese Anweisungen kein eindeutigesRezept ergeben. Gibt es mehr als eine Möglichkeit, unter den drei Zutaten eine Auswahl zutreffen, so dass alle drei Anweisungen erfüllt sind? Beweisen Sie Ihre Antwort.

Sie können die folgende Vorlage für Ihre Wahrheitstafel verwenden:F S K ϕAnweisung 1 ϕAnweisung 2 ϕAnweisung 3

0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1


(b) (6 Pkte)Geben Sie zu jeder der folgenden aussagenlogischen Formeln an, ob sie erfüllbar und/oderallgemeingültig ist. Kreuzen Sie alle richtigen Antworten an.Wenn Sie „erfüllbar“ ankreuzen, dann müssen Sie eine Belegung angeben, die die Formelerfüllt. Falls Sie „allgemeingültig“ ankreuzen, müssen Sie Ihre Antwort beweisen und an-sonsten eine Belegung angeben, die die Formel nicht erfüllt.

• ϕ =((¬X1 ∨X2)↔ (X1 → X2)

)

erfüllbar: ja nein

allgemeingültig: ja nein

Falls ϕ erfüllbar ist, geben Sie hier eine zu ϕ passende Belegung an, die ϕ erfüllt:

Falls ϕ allgemeingültig ist, beweisen Sie Ihre Antwort; andernfalls geben Sie eine zu ϕpassende Belegung an, die ϕ nicht erfüllt:

• ψ =((X1 ∨ (X1 ∧X2))↔ X1

)

erfüllbar: ja nein

allgemeingültig: ja nein

Falls ψ erfüllbar ist, geben Sie hier eine zu ψ passende Belegung an, die ψ erfüllt:

Falls ψ allgemeingültig ist, beweisen Sie Ihre Antwort; andernfalls geben Sie eine zu ψpassende Belegung an, die ψ nicht erfüllt:



(c) (6 Pkte)Seien ϕ, ψ und χ beliebige aussagenlogische Formeln. Gelten folgende (semantische) Äquiva-lenzen (≡)?Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz erhalten Sie zwei Punkte,für jedes falsche Kreuz werden zwei Punkte abgezogen; wird keine Option angekreuzt,erhalten Sie keinen Punkt. Ihre Gesamtpunktzahl für diese Aufgabe ist aber mindestens 0.

(ϕ→ ψ) ≡ (¬ψ → ¬ϕ) wahr falsch

((ϕ ∧ ψ)→ χ) ≡ (¬χ→ (¬ϕ ∨ ¬ψ)) wahr falsch

(ϕ→ ψ) ≡ (ϕ ∧ ¬ψ) wahr falsch

(d) (4 Pkte)Geben Sie eine zur Formel

ϕ :=(X3 ∧

((¬X1 ∨X2) ∧ (X1 ∨ ¬X2)

))

äquivalente Formel in disjunktiver Normalform an. Geben Sie auch Ihren Lösungsweg an.(Ihr Lösungsweg ist nur dann relevant, wenn Ihre Formel falsch ist; Sie können dann Teilpunkteerhalten. Für die richtige Formel erhalten Sie stets die volle Punktzahl.)



(a) Sei G = (V,E) der gerichtete Graph mit Knotenmenge V = {a, b, c, d, e} und KantenmengeE =

{(a, a), (a, b), (b, b), (b, c), (b, e), (c, d), (d, e), (e, b)

}.

(i) (1 Pkt)Geben Sie die graphische Darstellung von G an.

Graphische Darstellung:

a

b c

de

(ii) (1 Pkt)Geben Sie Ein-GradG(b) an.

(iii) (1 Pkt)Geben Sie einen Kreis der Länge 4 in G an.

(iv) (2 Pkte)Ist G stark zusammenhängend? Begründen Sie Ihre Antwort.



(b) Betrachten Sie die folgenden ungerichteten Graphen G1, G2 und G3:

a

b c

de

f g

h

G1

a

b

c d

e

fg

h

G2

0

1

2

345 6

78

9

G3

(i) (1 Pkt)Geben Sie ein größtmögliches Matching in G1 an:

(ii) (4 Pkte)Welche der folgenden Aussagen sind wahr, welche falsch?Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz bekommen Sie einenPunkt, für jedes falsche Kreuz wird ein Punkt abgezogen; wird keine Optionangekreuzt, erhalten Sie keinen Punkt. Ihre Gesamtpunktzahl ist aber mindestens 0.

• G1 ist bipartit. wahr falsch

• G1 ist ein Teilgraph von G2. wahr falsch

• Die chromatische Zahl χ(G2) von G2 ist 3. wahr falsch

• G2 und G3 sind isomorph. wahr falsch

(iii) (2 Pkte)Geben Sie eine konfliktfreie Knotenfärbung f : V3 → {1, 2, 3} für die Knotenmenge V3von G3 an. Tragen Sie dazu in jeden Knoten v den Wert f(v) ein.

G3 :

(iv) (2 Pkte)Ist die folgende Aussage wahr oder falsch? Begründen Sie Ihre Antwort.

Für alle n ∈ N>2 besitzt der vollständige ungerichtete Graph Kn mit Knotenmenge{1, 2, . . . , n} einen Hamiltonkreis.

wahr falsch

Begründung:


(c) Der DisMod-Supermarkt hat sein Warenangebot auf zehn Abteilungen verteilt (davon dienteine als Eingangsbereich). Der unten stehende Gebäudeplan zeigt deren Anordnung:

Eingang

Obst

Wein

Bier

Gemüse

Putzmittel

Milch

Fleisch

Chips

Käse

Dabei sind zwei angrenzende Abteilungen genau dann direkt mit einem Durchgang verbun-den, wenn auf dem Plan eine Tür eingezeichnet ist. (Beispielsweise sind die Abteilungen fürFleisch und Käse direkt verbunden, nicht aber die Abteilungen für Gemüse und Chips.)

(i) (1 Pkt)Modellieren Sie den Raumplan des Supermarktes als ungerichteten Graphen. Dabeisollen die Knoten die Abteilungen repräsentieren und genau dann durch eine Kanteverbunden sein, wenn es einen Durchgang zwischen ihnen gibt.

Eingang

Obst

Wein

Bier

Gemüse

Putzmittel

Milch

Fleisch

Chips

Käse



(ii) (1 Pkt)Für seinen Großeinkauf muss Klaus Uhr alle zehn Abteilungen aufsuchen.Dies möchte er so effizient wie möglich machen: Er plant seinen Einkauf so, dass er –beginnend im Eingangsbereich – alle Abteilungen genau einmal betritt und am Endewieder im Eingangsbereich ankommt.

Formulieren Sie Klaus’ Plan als graphentheoretische Fragestellung.

(iii) (2 Pkte)Geben Sie eine Lösung für Klaus’ Einkaufsproblem an.Sie können die Abteilungen durch ihre jeweiligen Anfangsbuchstaben abkürzen. (z.B.E für Eingang, O für Obst, etc.)

(iv) (4 Pkte)Auch Leo plant einen Einkauf und möchte nach demselben Verfahren wie Klaus vor-gehen. Allerdings benötigt Leo keinerlei Putzutensilien und möchte deshalb die Putz-mittel-Abteilung komplett auslassen.

Kann Leo den Einkauf wie gewünscht durchführen? Beweisen Sie, dass Ihre Antwortkorrekt ist.



(a) (4 Pkte)Betrachten Sie den folgenden Webgraphen

G :

1

2

3

Geben Sie die Übergangsmatrix Pd(G) für den Dämpfungsfaktor d = 1 an. (Der Zufalls-Surferdarf somit nur die Kanten des Webgraphen benutzen.)

Pd(G) :=

(b) (4 Pkte)Diesmal kennen wir weder Webgraphen noch Dämpfungsfaktor, aber wir kennen die Über-gangsmatrix P mit

P :=

12

13

16

16

12

13

13

16

12

Gegeben sei die Anfangsverteilung X(0) :=(

12 ,

12 , 0). Der Zufalls-Surfer befindet sich anfangs

also mit Wahrscheinlichkeit 12 im Knoten 1 und mit Wahrscheinlichkeit 1

2 im Knoten 2.Bestimmen Sie die Verteilung X(1) = (π1, π2, π3), die die Wahrscheinlichkeit πj angibt, mitder sich der Zufalls-Surfer nach einem Schritt im Knoten j befindet.

π1 =

π2 =

π3 =




(a) (3 Pkte)Sei Σ := {a, b}. Die Sprache L ⊆ Σ∗ sei wie folgt definiert:

L := {w ∈ Σ∗ : w beginnt mit ab oder enthält bb als Teilwort}Geben Sie einen regulären Ausdruck R an, so dass L(R) = L.

(b) Sei A der folgende nichtdeterministische Automat über dem Alphabet Σ := {a, b}:

q0

q1

q2

q3

a

b

a

b

a, b

a, b

a, b

(i) (4 Pkte)Welche der folgenden Worte liegen in der von A akzeptierten Sprache L(A), welchenicht? Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz erhalten Sieeinen Punkt, für jedes falsche Kreuz wird ein Punkt abgezogen; wird keine Optionangekreuzt, erhalten Sie keinen Punkt. Ihre Gesamtpunktzahl ist aber mindestens 0.

Wort . . . liegt in L(A)?

abba ja nein

aaab ja nein

aaq2 ja nein

aabb ja nein

(ii) (2 Pkte)Geben Sie eine (mathematische oder umgangssprachliche) Beschreibung der SpracheL(A) an, zum Beispiel in Form eines regulären Ausdrucks.


(c) (6 Pkte)Sei A der folgende nichtdeterministische Automat über dem Alphabet Σ := {a, b}:

1

2

3

a

a, b

ba, b

b

Wandeln Sie den NFA A mit Hilfe der Potenzmengenkonstruktion in einen vollständigenDFA A′ um. Berücksichtigen Sie nur solche Zustände von A′, die vom Startzustand von A′aus erreicht werden können, und geben Sie die graphische Darstellung von A′ an.



(d) (7 Pkte)Geben Sie für jede der folgenden beiden Sprachen an, ob sie regulär ist. Kreuzen Sie allerichtigen Antworten an. Für jedes korrekte Kreuz erhalten Sie einen Punkt, für jedes falscheKreuz wird ein Punkt abgezogen; wird keine Option angekreuzt, erhalten Sie keinenPunkt. Ihre Gesamtpunktzahl ist aber mindestens 0.Beweisen Sie, dass Ihre jeweilige Antwort korrekt ist.

L1 := {anban : n ∈ N}

regulär: ja nein

Beweis:

L2 := {w ∈ {a, b}∗ : |w| ≥ 3}

regulär: ja nein

Beweis:


(e) (i) (3 Pkte)Sei A1 der folgende deterministische Automat über dem Alphabet Σ={a, b, c}:

q2 q1

q4 q3

a, b

c a

b

c

a

bc a, b, c

Geben Sie für die Zustandspaare {q1, q4}, {q2, q4}, {q3, q4} jeweils einen Zeugen für ihreNicht-Äquivalenz bezüglich der Verschmelzungsrelation an.

Erinnerung: Ein Zeuge für die Nicht-Äquivalenz eines Zustandspaares {qi, qj} ist einWort z ∈ Σ∗, sodass δ(qi, z) ∈ F und δ(qj , z) 6∈ F (oder umgekehrt: δ(qi, z) 6∈ F undδ(qj , z) ∈ F ) gilt.




(ii) (5 Pkte)Sei A2 der folgende deterministische Automat über dem Alphabet Σ={a, b, c}:

2

3

4

1

a

b

c a

bc

a

b

c

a

b

c

Minimieren Sie A2, d.h. finden Sie einen vollständigen DFA A′2 mit L(A′2) = L(A2) undminimaler Zustandszahl. Sie müssen keine Zwischenschritte angeben. Geben Sie A′2 ingraphischer Darstellung an.

Minimaler DFA A′2:

Weiterer Platz zur Lösung dieser Aufgabe befindet sich auf der nächsten Seite.



Minimaler DFA A′2 (Fortsetzung):



(a) Die kontextfreie Grammatik G=(Σ, V, S, P ) sei definiert durch die beiden Nicht-TerminaleV := {S,A}, die fünf Terminale

Σ := { _ , sehr , toll , ist , dismod }

und

P := { S → dismod_S_toll | ist | ist_A,A→ sehr | sehr_A }.

(i) (4 Pkte)Welche der folgenden Worte liegen in der von G erzeugten Sprache L(G), welche nicht?Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz erhalten Sie einenPunkt, für jedes falsche Kreuz wird ein Punkt abgezogen; wird keine Optionangekreuzt, erhalten Sie keinen Punkt. Ihre Gesamtpunktzahl ist aber mindestens 0.

Wort . . . liegt in L(G)?

sehr | sehr_A ja nein

dismod_ist_toll_toll ja nein

dismod_ist_sehr_toll ja nein

dismod_dismod_ist_toll_toll ja nein

(ii) (2 Pkte)Geben Sie einen Ableitungsbaum für das Wort dismod_ist_sehr_sehr_toll ∈ L(G)an.



(b) (4 Pkte)Die Sprache L über dem Alphabet Σ := {a, b, 〈, 〉, ?} sei wie folgt rekursiv definiert:Basisregel: (B) Es gilt: a ∈ L und b ∈ L.Rekursive Regeln: (R1) Ist w ∈ L, so ist auch 〈w〉 ∈ L.

(R2) Sind u, v, w ∈ L, so ist auch 〈u ? v ? w〉 ∈ L.Geben Sie eine kontextfreie Grammatik G an, so dass L(G) = L.

G = (Σ, V, S, P )

V =

P =


(c) (6 Pkte)Die Funktion f : N→ N sei für alle n ∈ N wie folgt definiert:

f(n) :={

2 falls n = 0,2 · f(n− 1) + 1 falls n ≥ 1.

Zeigen Sie durch vollständige Induktion, dass f(n) = 3 · 2n − 1 für alle n ∈ N gilt.





Aufgaben der Klausur WS 11/12



(a) (10 Pkte)1 Paul fühlt sich nicht so gut und geht zum Arzt. Nach eingehender Untersuchung kommen fürden Mediziner nur vier Krankheiten in Frage. Möglicherweise leidet Paul unter Hirnversalzungoder Denkinsuffizienz. Gummikauzwang oder eine Sitzanomalie kommen aber auch in Frage.Mit dem Wissen des Facharztes über die Wechselwirkung der Krankheiten steht für dieDiagnose nun Folgendes fest.Fakt 1: Falls Paul keinen Gummikauzwang hat, dann leidet er unter Hirnversalzung oder

Denkinsuffizienz oder gar beidem.Fakt 2: Falls Paul eine Sitzanomalie hat, dann hat er auch Gummikauzwang und Hirnver-

salzung.Fakt 3: Hat Paul jedoch weder eine Sitzanomalie noch Hirnversalzung, dann kann er auch

keine Denkinsuffizienz haben.Paul ist verwirrt. Welche Krankheiten hat er wohl — oder hält ihn der Heilkundige gar füreinen Simulanten ?Formalisieren Sie die drei Aussagen durch je eine aussagenlogische Formel, indem Sie dieatomaren Aussagen D (Paul leidet unter Denkinsuffizienz), G (Paul leidet unter Gummi-kauzwang),H (Paul leidet unter Hirnversalzung) und S (Paul leidet unter einer Sitzanomalie)benutzen.

ϕFakt 1 :=

ϕFakt 2 :=

ϕFakt 3 :=

Stellen Sie eine aussagenlogische Formel ψ auf, die das Wissen um Pauls gesundheitlichenZustand widerspiegelt.

ψ :=

1Die Idee der Aufgabe beruht auf einer Aufgabe, die Dr. Peter Rossmanith und Dr. Clemens Ballarin im Som-mersemester 2002 im Rahmen einer Logikvorlesung an der Technischen Universität München stellten.



Mit dem Blick in die Krankenakte ist klar. Paul hatte als Kind bereits einmal Hirnversalzungund wurde erfolgreich diesbezüglich behandelt. Wie jeder weiß, kann man Hirnversalzungnicht ein zweites Mal bekommen, d.h. es gilt zusätzlich der Fakt, dass Paul nicht unterHirnversalzung leiden kann. Unter Einbeziehung des neuen Wissens stellt sich nun die Frage:Unter welchen Krankheiten leidet Paul und unter welchen leidet er nicht? Zeigen Sie, dassIhre Antwort korrekt ist.



(b) (3 Pkte)Welche der folgenden Aussagen sind wahr? Welche nicht?Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz bekommen Sie einenPunkt, für jedes falsche Kreuz wird ein Punkt abgezogen. Die Gesamtpunktzahl istaber mindestens 0.

Jede aussagenlogische Variable ist auch eine atomare Formel aus AL. wahr falsch

Zu jeder Formel ϕ ∈ AL existiert eine Belegung B, so dass JϕKB = 1. wahr falsch

Da man für ϕ eine zu ϕ äquivalente Formel in DNF aus der Wahrheits-tafel erhält, indem man die erfüllenden Belegungen betrachtet, kann eszu ϕ, falls ϕ unerfüllbar ist, keine äquivalente Formel in DNF geben.

wahr falsch

(c) (4 Pkte)Geben Sie für die aussagenlogische Formel ϕ := ¬((X1 ∧ X2) → (1 ↔ X3)) eine zu ϕäquivalente aussagenlogische Formel ψ in NNF an. Geben Sie auch Ihren Lösungsweg an.




(a) Sei G = (V,E) der ungerichtete Graph mit der folgenden Adjazenzmatrix:

c d e f g h

c 0 1 1 1 1 0d 1 0 1 0 0 0e 1 1 0 0 0 0f 1 0 0 0 0 0g 1 0 0 0 0 1h 0 0 0 0 1 0

(i) Geben Sie die graphische Darstellung von G an. Geben Sie außerdem die KnotenmengeV sowie die Kantenmenge E von G an und repräsentieren Sie G durch eine Adjazenzliste.

graphische Darstellung: (1 Pkt)

c

d e

f

g

h

V = (1 Pkt)

E = (1 Pkt)

Adjazenzliste: (1 Pkt)

(ii) (1 Pkt)Geben Sie Grad(G) an:

(iii) (1 Pkt)Geben Sie eine Kante an, nach deren Wegnahme aus G der entstehendeGraph ein Baum ist:

(iv) (1 Pkt)Geben Sie eine Kante an, die zu G hinzugefügt werden muss, damit derentstehende Graph einen Eulerkreis enthält:



(b) Es seien die folgenden ungerichteten Graphen G1, G2 und G3 gegeben:

a

b c

de

f

g h

i

G1

x

a

b c

de

f

g h

i

G2

x

a

b c

de

f

g h

i

G3

Welche der folgenden Aussagen sind wahr, welche falsch? (3 Pkte)Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz bekommen Sie einenPunkt, für jedes falsche Kreuz wird ein Punkt abgezogen. Die Gesamtpunktzahl istaber mindestens 0.

• G1 ist ein induzierter Teilgraph von G2. wahr falsch

• Jedes Matching in G2 besteht aus höchstens 3 Kanten. wahr falsch

• G2 ist ein Spannbaum von G3 wahr falsch

(c) Betrachten Sie die folgenden vier gerichteten Graphen mit der Knotenmenge V = {1, 2, 3, 4}und fassen Sie diese als 2-stellige Relationen R1, R2, R3 und R4 über V × V auf.

12

3 4

R1

12

3 4

R2

12

3 4

R3

12

3 4

R4


• R1 ist antisymmetrisch. wahr falsch

• R2 ist konnex. wahr falsch

• R3 ist eine Äquivalenzrelation. wahr falsch

• R4 ist eine partielle Funktion. wahr falsch



(d) Betrachten Sie die folgenden gerichteten Graphen G4 und G5:

G4

a

b

c

d

e

f

g

h

G5

2

46

8

1

35

7

(i) (2 Pkte)G4 und G5 sind isomorph. Geben Sie einen Isomorphismus von G4 nach G5 an.

(ii) (1 Pkt)Ist der Graph G5 stark zusammenhängend? Begründen Sie Ihre Antwort.



(e) In wenigen Monaten beginnen die Olympischen Sommerspiele 2012 in London. Die kleineRadiostation KBBL möchte gerne über die folgenden Wettbewerbe berichten: Leichtathletik,Tennis, Segeln, Turnen, Fechten und Schwimmen. Zu jedem dieser Wettbewerbe muss ein Re-porter geschickt werden. Natürlich will KBBL Geld sparen und deshalb so wenige Reporterwie möglich einsetzen. Allerdings kann ein Reporter an einem Tag nur von einem Wettbewerbberichten. Also müssen zu Wettbewerben, die am gleichen Tag stattfinden, verschiedene Re-porter geschickt werden. Bei den Wettbewerben gibt es folgende zeitliche Überschneidungen:

Wettbew

erbe

Schwimmen

Leichtathletik

FechtenTurnen

TennisSegeln

TageMo Di Mi Do Fr Sa So

So können beispielsweise die Wettbewerbe im Tennis und Turnen vom gleichen Reporterbesucht werden, weil sie an verschiedenen Tagen stattfinden. Im Gegensatz dazu benötigen dieWettbewerbe im Segeln und Turnen verschiedene Reporter, da sie sich zeitlich überschneiden.(i) (1 Pkt)Stellen Sie den Konfliktgraphen G auf, in dem eine Kante zwischen zwei Knoten dafür

steht, dass die entsprechenden Wettkämpfe sich zeitlich überschneiden.

Konfliktgraph G:

Fechten

Leichtathletik

Tennis

Turnen

Schwimmen

Segeln



(ii) (2 Pkte)Sei V die Menge der Knoten des Konfliktgraphen G aus Teilaufgabe (i), es gelte al-so V := {Leichtathletik, Tennis, Segeln, Turnen, Fechten, Schwimmen}. Geben Sie einekonfliktfreie Knotenmarkierung m : V → N an, die möglichst wenige verschiedene Mar-kierungen verwendet, d.h. |Bild(m)| soll minimal sein.

(iii) (1 Pkt)Geben Sie eine Aufteilung aller sechs Wettbewerbe auf möglichst wenige verschiedeneReporter an, so dass kein Reporter zwei Wettbewerben zugewiesen wird, die sich zeitlichüberschneiden.

(iv) (2 Pkte)Begründen Sie, warum die von Ihnen in Teilaufgabe (iii) benutzte Anzahl von Reporternbestmöglich ist, d.h. warum es keine konfliktfreie Aufteilung der Wettbewerbe auf einegeringere Anzahl von Reportern geben kann.




(a) Betrachten Sie die folgende Datenbank AMusik, bestehend aus den dargestellten Tabellen˙StückAMusik und <AMusik .Tabelle: ˙StückAMusik

Titel Interpret JahrDas Model Kraftwerk 1978Das Model Rammstein 1997Die Roboter Fleischmann 1994Die Roboter Kraftwerk 1978Fleischwolf Fleischmann 1993

In-A-Gadda-Da-Vida Iron Butterfly 1968Stairway to Heaven Iron Maiden 1981Stairway to Heaven Led Zeppelin 1970

Sweet Dreams Marilyn Manson 1996Sweet Dreams Eurythmics 1983Sweet Dreams Eurythmics 1991

Tabelle: <AMusik

a b1900 19011900 1902...

...1900 21001901 1902...

...2097 21002098 20992098 21002099 2100

Hierbei ist die Tabelle ˙StückAMusik unserer Datenbankinstanz ein Auschnitt aus einer (denk-baren) Datenbanktabelle, welche alle zwischen 1900 und heute veröffentlichten Musikstückeenthält. Die Tabelle <AMusik enthält diejenigen Paare von Wörtern aus ASCII∗, welche wirals Paare von Jahreszahlen zwischen 1900 und 2100 interpretieren, falls die erste Komponen-te des Tupels vor der zweiten liegt. <AMusik gibt uns also eine Reihenfolge auf den Worten,welche wir als Jahreszahlen zwischen 1900 und 2100 betrachten.Die Signatur σMusik besteht aus einem 3-stelligen Relationssymbol ˙Stück, einem 2-stelligenRelationssymbol <, sowie je einem Konstantensymbol ’c’ für jeden möglichen Eintrag c ∈ASCII∗ in der Datenbank.(i) (2 Pkte)Geben Sie eine FO[σMusik]-Anfrage ϕ an, welche alle Interpreten ausgibt, die den Song

„Sweet Dreams“ veröffentlichten.

(1 Pkt)Berechnen Sie das Ergebnis Ihrer Anfrage auf der angegebenen Datenbankinstanz AMusik.



(ii) (2 Pkte)Ein Song gilt als Cover-Version, wenn es einen anderen Song gleichen Titels aus einemfrüheren Jahr in der Datenbank gibt. Geben Sie eine FO[σMusik]-Anfrage ϕ an, welche dieTitel aller Cover-Versionen und die Interpreten der jeweiligen Cover-Version ausgibt.

(1 Pkt)Berechnen Sie das Ergebnis Ihrer Anfrage auf der angegebenen Datenbankinstanz AMusik.

(iii) (3 Pkte)Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz bekommen Sie einenPunkt, für jedes falsche Kreuz wird ein Punkt abgezogen. Die Gesamtpunktzahl istaber mindestens 0.

Es gibt eine FO[σMusik]-Anfrage ϕ, so dass die von ϕ in AMusik definierte Antwortrelation

... alle Titel enthält, die vor dem Jahr 1999 veröffent-licht wurden.

wahr falsch

... zu jeder Cover-Version neben Titel und Interpretenauch den Interpreten des Originals enthält. wahr falsch

... alle Worte aus ASCII∗ ausgibt, welche als Bandna-men noch frei (also bisher als Interpret in der Daten-bank unbenutzt) sind.

wahr falsch



(b) (3 Pkte)Welche der folgenden Aussagen sind wahr, welche sind falsch?Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz bekommen Sie einenPunkt, für jedes falsche Kreuz wird ein Punkt abgezogen. Die Gesamtpunktzahl istaber mindestens 0.

Die Menge der aussagenlogischen Formeln ist eine Teilmenge derMenge der Formeln der Logik erster Stufe. wahr falsch

Zu jeder σ-Struktur A existiert ein FO[σ]-Satz, welcher von A er-füllt wird.

wahr falsch

Jeder σ-Term ist auch eine atomare FO[σ]-Formel. wahr falsch

(c) Sei (5 Pkte)σ = {E} eine Signatur mit einem zweistelligen Relationssymbol E. Betrachten Sie dieσ-Struktur A = (A, EA), welche durch die unten angegebene Abbildung repräsentiert wird.Geben Sie einen FO[σ]-Satz ϕ an, der die Struktur eindeutig beschreibt. D.h. für alle σ-Strukturen B soll gelten: A ∼= B ⇔ B |= ϕ.

A: ab

ϕ :=




(a) Sei Σ ein endliches Alphabet mit Σ := {V, 1, 2, 3, 4, 5, 6, 7, 8, 9,¬,∧,∨,1,0,≡, 6≡}. R sei alsfolgender regulärer Ausdruck über dem Alphabet Σ gegeben:

(¬ | ε ) V ( 1 | 2 | · · · | 9 )((∧ |∨ ) (¬ | ε ) V ( 1 | 2 | · · · | 9 )

)∗(≡ | 6≡ ) ( 1 |0 )

(i) (1,5 Pkte)Welche der folgenden Wörter liegen in der von R definierten Sprache L(R), welche nicht?Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz bekommen Sie einenhalben Punkt, für jedes falsche Kreuz wird ein halber Punkt abgezogen. Die Ge-samtpunktzahl ist aber mindestens 0.

Wort . . . liegt in L(R)?V1 ∧ ¬V1 ≡ 1 ja neinV8 ∨ ¬V9 ∨ ¬V10 6≡ 0 ja neinV3 ∧ V4 ∨ V3 ∧ V4 ∨ V3 ∧ V4 ∨ V3 ≡ 0 ja nein

(ii) (2,5 Pkte)Geben Sie einen deterministischen endlichen Automaten B in graphischer Darstellungan, der genau die Sprache akzeptiert, die vom regulären Ausdruck R definiert wird, d.hes soll gelten, dass L(B) = L(R).Beachten Sie, dass der Automat B nicht vollständig sein muss.



(b) Sei A der folgende nichtdeterministische endliche Automat über dem Alphabet Σ := {a, b}:

q0

q1

q2

q3

a

b

a

b

b

a

(i) (2 Pkte)Geben Sie eine (mathematische oder umgangssprachliche) Beschreibung der SpracheL(A) an, die vom Automaten A akzeptiert wird.

(ii) (4 Pkte)Wandeln Sie den NFA A mit Hilfe der Potenzmengenkonstruktion in einen DFA A′ um.Berücksichtigen Sie dabei nur solche Zustände von A′, die vom Startzustand von A′ auserreicht werden können und geben Sie die graphische Darstellung von A′ an.



(c) (9 Pkte)Geben Sie für jede der folgenden beiden Sprachen L1 und L2 jeweils an, ob es sich umreguläre Sprachen handelt. (Kreuzen Sie alle richtigen Antworten an. Für jedes korrekteKreuz bekommen Sie einen Punkt, für jedes falsche Kreuz wird ein Punkt abgezogen.Die Gesamtpunktzahl dieser Teilaufgabe ist aber mindestens 0.)Beweisen Sie, dass Ihre jeweilige Antwort korrekt ist.

Zur Erinnerung:Um zu beweisen, dass eine Sprache L regulär ist, genügt es, einen endlichen Automaten Aoder einen regulären Ausdruck R anzugeben, so dass L = L(A) bzw. L = L(R) ist.Um zu beweisen, dass eine Sprache nicht regulär ist, können Sie das Pumping-Lemma ausder Vorlesung benutzen:

Sei Σ ein endliches Alphabet. Für jede reguläre Sprache L ⊆ Σ∗ gibt es eine Zahlz ∈ N, so dass für jedes Wort x ∈ L der Länge |x| ≥ z gilt: Es gibt eine Zerlegungvon x in Worte u, v, w ∈ Σ∗, so dass die folgenden vier Bedingungen erfüllt sind:(1) x = uvw

(2) |uv| ≤ z(3) |v| ≥ 1(4) für jedes i ∈ N gilt: uviw ∈ L.

(d.h.: uw ∈ L, uvw ∈ L, uvvw ∈ L, uvvvw ∈ L, . . . )



L1 := {am bn : m,n ∈ N, 3 > m, m < n}

regulär: ja nein

Beweis:



L2 := {am bn : m,n ∈ N, 3 < m, m < n}

regulär: ja nein

Beweis:



Aufgabe 5: (8 Punkte)Betrachten Sie den folgenden Web-Graph G1, der aus den vier Webseiten 1, 2, 3 und 4 besteht,die entsprechend der gerichteten Kanten in der Abbildung untereinander verlinkt sind.

1

2 3

4

G1:

(a) (4 Pkte)Stellen Sie für G1 und den Dämpfungsfaktor d = 12 die Page-Rank-Matrix P (G1, d) auf.

(b) (4 Pkte)Es seien die vier Page-Ranks PR1 = 18 , PR2 = PR3 = 5

16 und PR4 = 14 gegeben. Weisen

Sie nach, dass dies die Page-Ranks für die vier Webseiten 1, 2, 3 und 4 des Web-GraphenG1 bezüglich des Dämpfungsfaktors d = 1

2 sind. Das heißt, weisen Sie nach, dass das TupelPR = (1

8 ,516 ,

516 ,

14) die Page-Rank-Eigenschaft bezüglich d = 1

2 hat.





Aufgabe 6: (16 Punkte)Im Folgenden wird zu jeder Zahl n ∈ N die Sprache SETn über dem Alphabet Σ := {∪,∩, (, )} ∪{{} ∪ {}} ∪ {i : i < n, i ∈ N} rekursiv definiert:Basisregel:

(B) Für jede Zahl i < n mit i ∈ N ist das Wort {i} in SETn.Rekursive Regeln:

(R1) Sind w1 und w2 in SETn, so ist auch (w1 ∩ w2) in SETn.(R2) Sind w1 und w2 in SETn, so ist auch (w1 ∪ w2) in SETn.

(a) (4 Pkte)Welche der folgenden Wörter gehören zur Sprache SET42, welche nicht?Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz bekommen Sie einenPunkt, für jedes falsche Kreuz wird ein Punkt abgezogen. Die Gesamtpunktzahl istaber mindestens 0.

Wort ... liegt in SET42?∅ ja nein{0} ja nein({42} ∪ ({4} ∩ {2})) ja nein({4, 2} ∪ ({4} ∩ {2})) ja nein

(b) (4 Pkte)Geben Sie eine kontextfreie Grammatik G an, so dass L(G) = SET5.



(c) (2 Pkte)Betrachten Sie die von Ihnen in (b) angegebene kontextfreie Grammatik G und geben Sieeinen Ableitungsbaum für das folgende Wort an:

({1} ∪ ({4} ∩ {2}))



Zur Erinnerung wird die bereits zu Beginn der Aufgabe angegebene rekursive Definition derSprache SETn über dem Alphabet Σ := {∪,∩, (, )}∪{{}∪{}}∪{i : i < n, i ∈ N} wiederholt:Basisregel:

(B) Für jede Zahl i < n mit i ∈ N ist das Wort {i} in SETn.Rekursive Regeln:

(R1) Sind w1 und w2 in SETn, so ist auch (w1 ∩ w2) in SETn.(R2) Sind w1 und w2 in SETn, so ist auch (w1 ∪ w2) in SETn.

Für jedes n ∈ N und jedes Wort w aus SETn ist die Funktion fn : SETn → N wie folgtdefiniert:

fn(w) := 1 für w = {i} mit 0 ≤ i < n, i ∈ Nfn(w) := 0 für w = (w1 ∩ w2) mit w1, w2 ∈ SETn

fn(w) := fn(w1) + fn(w2)−min(fn(w1), fn(w2)) für w = (w1 ∪ w2) mit w1, w2 ∈ SETn

Für n > 4 gilt so beispielsweise fn(({4} ∩ {2})) = 0 und fn(({4} ∪ {2})) = 1.Die Funktion |w|SETn berechnet die Kardinalität der Menge, welche man als Ergebnis erhält,wenn man w ∈ SETn als mengenarithmetischen Ausdruck interpretiert. Präzise heißt das:Für ein Wort w ∈ SETn definieren wir die Menge M(w):

M(w) := {i} für w = {i} mit 0 ≤ i < n, i ∈ NM(w) := M(w1) ∩M(w2) für w = (w1 ∩ w2) mit w1, w2 ∈ SETn

M(w) := M(w1) ∪M(w2) für w = (w1 ∪ w2) mit w1, w2 ∈ SETn

Und wir setzen |w|SETn:= |M(w)|.

Für n > 4 gilt so beispielsweise |({4} ∩ {2})|SETn = 0 und |({4} ∪ {2})|SETn = 2.(d) (6 Pkte)Sei n ∈ N beliebig gewählt. Beweisen Sie per Induktion nach dem Aufbau von SETn, dass

für alle Wörter w ∈ SETn gilt:|w|SETn ≥ fn(w)




Aufgaben der Klausur SoSe 2011



(a) (8 Pkte)1 Nachdem Hänsel und Gretel die Hexe in den Ofen gestoßen haben, wollen sie sich über dasKnusperhäuschen hermachen. Doch wie allgemein bekannt ist, muss man beim Verzehr einessolchen Hauses mit äußerster Vorsicht vorgehen, da dieses sonst zur Instabilität neigt. Diebeiden wenden sich zunächst einer Wand zu, welche aus drei Lebkuchen besteht. Da Gretelerfolgreich Knusperhäuschenarchitektur studiert hat, kennt Sie die folgenden Sicherheitsre-geln:Regel 1: Von den beiden ersten Lebkuchen darf höchstens einer entfernt werden.Regel 2: Wenn man den dritten entfernt, muss man auch den zweiten entfernen.Regel 3: Wenn man den zweiten entfernt und den ersten nicht, dann darf man den dritten

nicht entfernen.Formalisieren Sie die drei Aussagen durch je eine aussagenlogische Formel, indem Sie dieatomaren Aussagen E (die beiden entfernen den ersten Lebkuchen), Z (die beiden entfernenden zweiten Lebkuchen) und D (die beiden entfernen den dritten Lebkuchen) benutzen.

ϕRegel 1 :=

ϕRegel 2 :=

ϕRegel 3 :=

Hänsel warnt Gretel davor, den dritten Lebkuchen zu entfernen. Ist seine Sorge berechtigt?Beweisen Sie, dass Ihre Aussage stimmt.

1Diese Aufgabe ist dem Buch Modellierung von Uwe Kastens and Hans Kleine Büning entnommen.



(b) (3 Pkte)Welche der folgenden Formeln ist in Negationsnormalform (NNF), disjunktiver Normalform(DNF) und/oder konjunktiver Normalform (KNF)?Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz bekommen Sie einen halbenPunkt, für jedes falsche Kreuz wird ein halber Punkt abgezogen. Die Gesamtpunktzahlist aber mindestens 0.

¬X2 (((X1 ∨ ¬X2) ∧ ¬X1) ∨ (X2 ∧X3))in NNF? ja nein ja neinin DNF? ja nein ja neinin KNF? ja nein ja nein



(c) (3 Pkte)Welche der folgenden Aussagen sind für alle aussagenlogischen Formeln ϕ und ψ wahr? Welchenicht?Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz bekommen Sie einenPunkt, für jedes falsche Kreuz wird ein Punkt abgezogen. Die Gesamtpunktzahl istaber mindestens 0.

Jede atomare aussagenlogische Formel enthält mindestenseine aussagenlogische Variable. wahr falsch

ϕ ist unerfüllbar gdw. ¬ϕ erfüllbar ist. wahr falsch

Die Syntaxbäume zweier äquivalenter aussagenlogischerFormeln haben gleich viele Blätter. wahr falsch

(d) (2 Pkte)Wann heißt eine aussagenlogische Formel allgemeingültig (bzw. Tautologie)? Geben Sie eineexakte Definition an!

Sei ϕ eine aussagenlogische Formel.ϕ heißt allgemeingültig (bzw. Tautologie), wenn

(e) (4 Pkte)Sei ϕ = ((X1 ∧X2) → (¬X2 ∨ ¬X1)) und ψ = (X1 ∨X2). Gilt ϕ |= ψ ? Begründen Sie IhreAntwort!




(a) Sei G = (V,E) der folgende gerichtete Graph:

a b

cd

(i) Geben Sie die Knotenmenge V und die Kantenmenge E von G an. Repräsentieren Sie Gaußerdem durch eine Adjazenzmatrix.

V = (1 Pkt)

E = (1 Pkt)

Adjazenzmatrix: (1 Pkt)

(ii) (1 Pkt)Geben Sie Ein-GradG(a) an:

(iii) (1 Pkt)Geben Sie den längsten einfachen Weg vom Knoten b zumKnoten c an:

(iv) (1 Pkt)Geben Sie die Kante an, die entfernt werden muss, damit derenstehende Graph nicht mehr stark zusammenhängend ist:



(b) Es seien die folgenden ungerichteten Graphen G1 und G2 sowie der gerichtete Graph G3gegeben:

a

b

c d

e

f

g

h i

j

G1 G2

d

i

f

h

c

a

G3


• G2 ist ein induzierter Teilgraph von G1. wahr falsch

• Die Knoten von G2 lassen sich konfliktfrei mit zwei ver-schiedenen Farben färben.

wahr falsch

• G3 ist ein gerichteter Baum der Höhe 4. wahr falsch

(c) Betrachten Sie die folgenden vier Graphen mit der Knotenmenge V = {1, 2, 3} und fassenSie diese als 2-stellige Relationen R1, R2, R3 und R4 über V × V auf.

1

2 3

R1

1

2 3

R2

1

2 3

R3

1

2 3

R4


• R1 ist konnex. wahr falsch

• R2 ist transitiv. wahr falsch

• R3 ist eine Äquivalenzrelation. wahr falsch

• R4 ist eine Funktion. wahr falsch



(d) Betrachten Sie die folgenden ungerichteten Graphen G4 und G5:

G4

1

2

3

4 5

6

7

G5

f

e

d g

c

a

b

(i) (2 Pkte)G4 und G5 sind isomorph. Geben Sie einen Isomorphismus von G4 nach G5 an.

(ii) (2 Pkte)Enthält der Graph G5 einen Hamilton-Kreis? Begründen Sie Ihre Antwort.



(e) In weniger als zwei Wochen findet das Finale des 56. Eurovision Song Contest in Düsseldorfstatt. Fünf Länder stehen bereits als Finalteilnehmer fest, auch die jeweiligen Musiker sindschon bekannt: Amaury Vassili geht für Frankreich, Raphael Gualazzi für Italien auf die Büh-ne, das Vereinigte Königreich wird von der Gruppe Blue, Spanien von Lucía Pérez vertreten,Deutschland schließlich hofft wieder einmal auf Lena.Um die Show herauszuputzen, kann jeder der fünf Finalteilnehmer sich einen von fünf Büh-neneffekten aussuchen. Zur Wahl stehen eine Lasershow, eine Windmaschine, Feuerwerk, einFlammenwerfer und eine Schneefallsimulation. Um die Langeweile der Zuschauer zu begren-zen, darf jeder Bühneneffekt nur höchstens einmal benutzt werden.Natürlich haben alle Musiker ganz eigene Vorlieben für bestimmte Bühneneffekte, die sichim Einzelnen folgendermaßen darstellen:• Blue sind mit jedem Bühneneffekt zufrieden, der keine Lasershow ist.• Raphael mag Feuerwerk, den Flammenwerfer und die Windmaschine.• Auch Lucía steht auf Flammenwerfer und Windmaschine, außerdem auf die Lasershow.• Amaury schwärmt für die Windmaschine und die Lasershow.• Für Lena kommt nur die Windmaschine in Frage.

(i) (2 Pkte)Stellen Sie den Graphen G6 als ungerichteten Graphen auf, in dem jede Kante zwischeneinem Musiker M und einem Bühneneffekt B verläuft und dafür steht, dass M mit Bzufrieden wäre.

G6:

Amaury

Blue

Lena

Lucía

Raphael

Windmaschine

Flammenwerfer

Lasershow

Feuerwerk

Schneefallsimulation

(ii) (1 Pkt)Handelt es sich bei G6 um einen bipartiten Graphen? Begründen Sie Ihre Antwort.



(iii) (2 Pkte)Geben Sie ein Matching maximaler Größe in G6 an.

Matching maximaler Größe in G6:

Amaury

Blue

Lena

Lucía

Raphael

Windmaschine

Flammenwerfer

Lasershow

Feuerwerk

Schneefallsimulation

(iv) (1 Pkt)Geben Sie eine Zuordnung zwischen Bühneneffekten und Musikern an, so dass jeder Musi-ker genau einen Effekt erhält, jeder Effekt genau einmal zugeordnet wird und alle Musikermit ihrer Zuordnung zufrieden sind.




(a) Sei σ = { ˙Mult, ˙Nach, ˙Eins} eine Signatur mit einem dreistelligen Relationssymbol ˙Mult, einemeinstelligen Funktionssymbol ˙Nach und einem Konstantensymbol ˙Eins. Wir betrachten dieσ-Struktur A := (N, ˙MultA, ˙NachA, ˙EinsA) für die gilt:

˙MultA := {(x, y, z) |x, y, z ∈ N, x · y = z},˙NachA : N→ N mit ˙NachA(x) = x+ 1,˙EinsA := 1.

(i) (2 Pkte)Geben Sie eine Formel ϕ der Logik erster Stufe über der Signatur σ an, die in der σ-Struktur A := (N, ˙MultA, ˙NachA, ˙EinsA) aussagt, dass für die modellierte Multiplikationdas Kommutativgesetz gilt. (Zur Erinnerung: das Kommutativgesetz besagt, dass n ·m =m · n für alle natürliche Zahlen n und m gilt.)

(ii) (2 Pkte)Geben Sie eine Formel ϕ(x) der Logik erster Stufe über der Signatur σ an, die in derσ-Struktur A := (N, ˙MultA, ˙NachA, ˙EinsA) aussagt, dass die natürliche Zahl x eine Qua-dratzahl ist.

(iii) (2 Pkte)Was sagt die Formel

ϕ(x) := ∃y ∃z ( ˙Nach( ˙Eins)=y ∧ ˙Mult(z, y, x))

in der σ-Struktur A := (N, ˙MultA, ˙NachA, ˙EinsA) aus ?



(b) Sei (4 Pkte)σ = {E} eine Signatur mit einem zweistelligen Relationssymbol E.Geben Sie für die Formel

ϕ(x) := ∀y ((¬x=y)→ (E(x, y) ∧ (¬∃zE(y, z)))

eine σ-Struktur A und zwei Interpretationen I1 = (A, β1) und I2 = (A, β2) an, so dass gilt:

I1 |= ϕ und I2 6|= ϕ.

(c) (3 Pkte)Für eine Formel ϕ der Logik erster Stufe ist Var(ϕ) die Menge aller Variablen, die in derFormel ϕ vorkommen und frei(ϕ) die Menge aller Variablen, die mindestens einmal frei in ϕvorkommen. Zusätzlich sei geb(ϕ) die Menge aller Variablen, die mindestens einmal gebundenin ϕ vorkommen.Welche der folgenden Aussagen für Formeln der Logik erster Stufe sind wahr, welche sindfalsch?Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz bekommen Sie einenPunkt, für jedes falsche Kreuz wird ein Punkt abgezogen. Die Gesamtpunktzahl istaber mindestens 0.

Var(ϕ) = frei(ϕ) ∪ geb(ϕ) wahr falsch

Var(ϕ) \ frei(ϕ) = geb(ϕ) wahr falsch

Falls ϕ ein Satz ist, gilt: frei(ϕ) = Var(ϕ) \ geb(ϕ) wahr falsch



Aufgabe 4: (8 Punkte)Betrachten Sie den folgenden Web-Graph G1, der aus den drei Webseiten 1, 2 und 3 besteht, dieentsprechend der gerichteten Kanten in der Abbildung untereinander verlinkt sind.

1

2 3

G1:

(a) (4 Pkte)Stellen Sie für G1 und den Dämpfungsfaktor d = 12 die Page-Rank-Matrix P (G1, d) auf.

(b) (4 Pkte)Es seien die drei Page-Ranks PR1 = 29 , PR2 = 1

3 und PR3 = 49 gegeben. Weisen Sie nach,

dass dies die Page-Ranks für die drei Webseiten 1, 2 und 3 des Web-Graphen G1 bezüglichdes Dämpfungsfaktors d = 1

2 sind. Das heißt, weisen Sie nach, dass das Tupel PR = (29 ,

13 ,

49)

die Page-Rank-Eigenschaft bezüglich d = 12 hat.






(a) (2,5 Pkte)Geben Sie einen regulären Ausdruck R an, der die Sprache aller Wörter über dem AlphabetΣ = {a, b, . . . , z, / ,: , .} definiert, die die URL einer Webseite beschreiben, welche die Form

http:// 3rd-level-label 2nd-level-label . top-level-domain

haben. Dabei ist 3rd-level-label entweder das Wort www. oder die leere Zeichenkette und 2nd-level-label ein nicht-leeres Wort, in dem keines der Zeichen / , : und . (also nur a, b, . . . , z)vorkommt. Die Zeichenkette top-level-domain kann entweder aus de, com oder org bestehen.Wörter dieser Sprache sind also z. B. http://dismod.com und http://www.informatik.de,aber nicht www.uni.com oder http://de.wikipedia.org oder http://www..de.

R =

(b) Sei A der folgende nichtdeterministische endliche Automat über dem Alphabet Σ := {a, b}:

q0

q1

q2

q3

a

b

a

b

a

b

a

(i) (3 Pkte)Welche der folgenden Wörter liegen in der von A akzeptierten SpracheL(A), welche nicht?Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz bekommen Sie einenPunkt, für jedes falsche Kreuz wird ein Punkt abgezogen. Die Gesamtpunktzahl istaber mindestens 0.

Wort . . . liegt in L(A)?bbbab ja neinbbbabb ja neinaaaaaaaaaaa ja nein

(ii) (1,5 Pkte)Geben Sie eine (mathematische oder umgangssprachliche) Beschreibung der SpracheL(A) an, die vom Automaten A akzeptiert wird.



(iii) (4 Pkte)Wandeln Sie den NFA A mit Hilfe der Potenzmengenkonstruktion in einen DFA A′ um.Berücksichtigen Sie dabei nur solche Zustände von A′, die vom Startzustand von A′ auserreicht werden können. Geben Sie die graphische Darstellung von A′ an.

(c) (9 Pkte)Geben Sie für jede der folgenden beiden Sprachen L1 und L2 jeweils an, ob es sich umreguläre Sprachen handelt. (Kreuzen Sie alle richtigen Antworten an. Für jedes korrekteKreuz bekommen Sie einen Punkt, für jedes falsche Kreuz wird ein Punkt abgezogen.Die Gesamtpunktzahl dieser Teilaufgabe ist aber mindestens 0.)Beweisen Sie, dass Ihre jeweilige Antwort korrekt ist.

Zur Erinnerung:Um zu beweisen, dass eine Sprache L regulär ist, genügt es, einen endlichen Automaten Aoder einen regulären Ausdruck R anzugeben, so dass L = L(A) bzw. L = L(R) ist.Um zu beweisen, dass eine Sprache nicht regulär ist, können Sie das Pumping-Lemma ausder Vorlesung benutzen:

Sei Σ ein endliches Alphabet. Für jede reguläre Sprache L ⊆ Σ∗ gibt es eine Zahlz ∈ N, so dass für jedes Wort x ∈ L der Länge |x| ≥ z gilt: Es gibt eine Zerlegungvon x in Wörter u, v, w ∈ Σ∗, so dass die folgenden vier Bedingungen erfüllt sind:(1) x = uvw

(2) |uv| ≤ z(3) |v| ≥ 1(4) für jedes i ∈ N gilt: uviw ∈ L.

(d.h.: uw ∈ L, uvw ∈ L, uvvw ∈ L, uvvvw ∈ L, . . . )



L1 := {bn b k : n, k ∈ N, n = k}

regulär: ja nein

Beweis:



L1 := {bn ak : n, k ∈ N, n = k}

regulär: ja nein

Beweis:




(a) Im Folgenden wird die Menge AT der arithmetischen Terme mit den Variablen a, b und cüber dem Alphabet Σ := {a, b, c,+,−, ·, :, (, )} rekursiv definiert:Basisregel:

(B) Jede der Variablen a, b, c ist in AT.Rekursive Regeln:

(R1) Ist w in AT, so ist auch −w in AT.(R2) Sind w1 und w2 in AT, so sind auch (w1 + w2) und (w1 − w2) in AT.(R3) Sind w1 und w2 in AT, so sind auch (w1 · w2) und (w1 : w2) in AT.

(i) (4 Pkte)Welche der folgenden Wörter gehören zur Sprache AT, welche nicht?Kreuzen Sie alle richtigen Antworten an. Für jedes korrekte Kreuz bekommen Sie einenPunkt, für jedes falsche Kreuz wird ein Punkt abgezogen. Die Gesamtpunktzahl istaber mindestens 0.

Wort ... liegt in AT?−a ja nein(a+ (b− a)) ja nein(b−−−−− a) ja nein(b · (b−+a)) ja nein

(ii) (4 Pkte)Geben Sie eine kontextfreie Grammatik G an, so dass L(G) = AT.



(iii) (2 Pkte)Betrachten Sie die von Ihnen in (b) angegebene kontextfreie Grammatik G und gebenSie einen Ableitungsbaum für das folgende Wort an:

−(a · (b− c))



(b) (6 Pkte)Die zwei Algorithmen A1 und A2 lösen bei Eingabe von mindestens zwei unterschiedlichenWörtern das selbe Problem. Die Laufzeit g1 von A1 bzw. g2 von A2 ist abhängig von derAnzahl n der Eingabewörter und der Länge l des längesten Wortes der Eingabe. Insbesondereist

g1(n) = (1 + l)n und g2(n) = 1 + n · lZeigen Sie, dass der Algorithmus A1 im Allgemeinen langsamer als A2 ist, d.h. zeigen Sie perInduktion über n für n ∈ N>0 mit n ≥ 2, dass für jedes l ∈ N>0 gilt:

g1(n) > g2(n) , d.h. (1 + l)n > 1 + n · l




Documents

Skript zur Vorlesung Diskrete Modellierung · 2020. 9. 22. · Um die richtigen Geisterfallen auszulegen, müssen die Geisterjäger wissen, welche Arten von Geistern dort spuken