Blatt 1 - Professur für Theoretische Informatik

Diskrete Modellierung
Wintersemester 2015/2016
Dipl.-Inf. Bert Besser
Mario Holldack
Prof. Dr. Georg Schnitger
Hannes Seiwert, M.Sc.
Institut für Informatik
AG Theoretische Informatik
Ausgabe: 15.10.15
Abgabe: 22.10.15 bis 8:15 Uhr
Übung 1
• Bitte schreiben Sie Ihren Namen, Ihre Matrikelnummer, den Namen Ihres Tutors und die Gruppennummer sowie den Namen der Veranstaltung gut lesbar auf Ihre Abgaben. (Redundante
Informationen helfen uns, Irrläufer zu entdecken.)
• Bitte tackern Sie Ihre abgegebenen Blätter zusammen.
• Alle Antworten sind zu begründen, außer der Aufgabentext erlaubt eine Begründung entfallen
zu lassen.
• Bonuspunkte werden nur dann für die Klausur angerechnet, wenn Sie mindestens einmal im
Semester eine Lösung zu einer Aufgabe in Ihrem Tutorium präsentieren.
Viel Spaß!
Aufgabe 1.1. Mit Definitionen arbeiten
(25 Punkte)
Die Geschwister Konnie, Katie und Peter haben sehr unterschiedliche Hobbys. Während sich Konnie
leidenschaftlich für Mathematik interessiert und Katie am liebsten die ganze Welt programmieren
würde, ist ihr jüngerer Bruder Peter, den sie auch „der kleene1 Piet“ nennen, ein begnadeter Astronom. Am liebsten zählt der kleene Piet Himmelskörper wie Sterne, Planeten, Monde oder Kometen
und erstellt für diesen Zweck lange Listen. Mit der Zeit hat er sich eine ausgeklügelte Notation
ausgedacht. Jeder Himmelskörpertyp erhält ein spezielles Symbol:
• g für Galaxie,
• m für Mond,
• s für Stern und
• k für Komet,
• p für Planet,
• N für Supernova.
Wenn er lange wach bleiben darf, sitzt er im Garten, zählt jedes leuchtende Objekt am Himmel
und notiert seine Beobachtungen in seinem DisMond-Logbuch. Beispielsweise steht die Zeichenkette
mpNggsssssm dafür, dass der kleene Piet zuerst einen Mond, dann einen Planeten, eine Supernova,
zwei Galaxien, fünf Sterne und letztlich einen weiteren Mond entdeckt hat. In manchen Nächten
zählt der kleene Piet fast ausschließlich Sterne und hat dementsprechend lange Listen der Form
ssss...sss. Als Katie die Vorliebe ihres Bruders für Wiederholungen und Zeichenketten bemerkt,
beginnt sie sogleich mit der Planung des computergestützten DisMond-Logbuchs cgdl. Konnie schaltet sich ebenfalls ein und schlägt vor, dass man zur einfacheren Eingabe und Verwaltung der langen
Zeichenketten mathematische Operatoren verwenden könne. Zusammen einigen sich die drei Geschwister, dass in der ersten Version von cgdl zwei Operatoren zur Verfügung stehen sollen:
Definition 1 (KonKat). Der KonKat-Operator ⊕, benannt nach Konnie und Katie, bildet zwei
Zeichenketten u und v auf uv ab:
(u ⊕ v) := uv
Bitte wenden!
1
plattdeutsch für „klein“
Definition 2 (Der kleene Stern). Der kleene Stern ∗, benannt nach dem kleenen Piet und seiner
Vorliebe für Sterne, bildet eine Zeichenkette u und eine positive natürliche Zahl k auf die k-fache
Wiederholung von u ab:
(u ∗ k) := uu
. . . u}
| {z
k-mal
So kann in cgdl beispielsweise die Zeichenkette sNsNsNsNsNsNm kurz als
((sN ∗ 6) ⊕ m) = (sNsNsNsNsNsN ⊕ m) = sNsNsNsNsNsNm
(1)
dargestellt werden. Wir nennen sNsNsNsNsNsNm die Auswertung von ((sN ∗ 6) ⊕ m).
a) Werten Sie folgende Ausdrücke wie in Gleichung (1) aus. Geben Sie alle Zwischenschritte an.
i) ((gms ∗ 3) ⊕ ppN)
ii) ((kp ∗ 3) ∗ 2)
iii) ((m ∗ 1) ⊕ (N ∗ 2))
b) Seien u und v Zeichenketten und k, l ∈ N>0 . Sind die folgenden Aussagen für jede Wahl von
u, v, k und l wahr? Begründen Sie jeweils Ihre Antwort. Für eine falsche Aussage genügt die
Angabe eines Gegenbeispiels.
i) ((u ∗ k) ⊕ (u ∗ l)) = (u ∗ (k + l))
ii) ((u ∗ k) ⊕ (v ∗ k)) = ((u ⊕ v) ∗ k)
c) Piet benutzt nun auch die Ziffern 0, 1, 2 und 3 als Symbole für Himmelsobjekte. Werten Sie
auch die folgenden Ausdrücke aus:
i) ((2 ∗ 2) ⊕ 2)
ii) ((3 ⊕ 1) ∗ 4)
iii) (((0 ∗ 4) ⊕ 1) ∗ 2)
Aufgabe 1.2. Beweise führen
(23 Punkte)
Beweisen Sie, dass für beliebige Mengen M, N und P gilt:
M ∩ (N ∪ P ) = (M ∩ N ) ∪ (M ∩ P )
Hinweis: Seien X und Y Mengen.
• Um die Inklusion X ⊆ Y nachzuweisen, genügt es, für ein beliebiges Element x der Menge X zu zeigen,
dass x auch ein Element der Menge Y ist.
• Um die Mengengleichheit X = Y zeigen, genügt der Nachweis der beiden Inklusionen X ⊆ Y und
Y ⊆ X.
Aufgabe 1.3. Mit Mengen arbeiten
(27 Punkte)
Geben Sie an, welche der Aussagen richtig und welche falsch sind. Geben Sie jeweils auch eine kurze
Begründung an.
a) {∅} ⊇ ∅
b) ∅ ∈ ∅
c) {∅, 0} \ ∅ = {0, ∅}
d) {1, 1, 3} \ {1, 3} = {1}
e) {1, {1, 3}} \ {1, 3} = {1}
f) ∅
g) {1} ∈ {{{1}}} ∪ {1}
h) {1, 2, 3}
i) {∅} ⊆ {{∅}} ∩ {∅}
Bitte wenden!
{1, 2, 3, 4}
{{1, 2}}
Aufgabe 1.4. Freunde zählen
(25 Punkte)
Dirk Modenbach (Nickname DirkMod) verwaltet seine Freunde in den sozialen Netzwerken Facelook,
Goggle und Instegräm: die jeweilige Menge seiner eingetragenen Freunde bezeichnen wir mit F, G
bzw. I. Die Anzahlen von DirkMods Freunden im jeweiligen Netzwerk sind
|F | = 537, |G| = 286 bzw. |I| = 187 .
Auf seinem Smartphone verwaltet DirkMod seine Freunde mit der App FreuStat. Diese App stellt
fest, dass 196 von DirkMods Freunden sowohl bei Facelook als auch bei Goggle eingetragen sind:
es gilt also |F ∩ G| = 196. Analog zeigt FreuStat die folgenden statistischen Werte an:
• |F ∩ G| = 196 (der Übersichtlichkeit halber wiederholt),
• |G ∩ I| = 101,
• |F ∩ G ∩ I| = 24 und
• |F ⊕ I| = 584.
Leider hat DirkMod die kostenlose, mit Werbung überfüllte Variante von FreuStat installiert, die
sich weigert, die Gesamtanzahl seiner Freunde zu berechnen. DirkMod will diese Zahl aber unbedingt
wissen, um sie in allen Netzwerken zu posten und so bei seinen Freunden anzugeben. Leider surft
DirkMod so lange sinnlos in diesen Netzwerken herum, dass er keine Zeit zum Lernen hat und selbst
nicht in der Lage ist, die Gesamtanzahl auszurechnen.
Bitte helfen Sie DirkMod!
a) Bestimmen Sie zuerst |F ∩ I| und dann
b) |F ∪ G ∪ I|.
c) Wie viele Freunde hat DirkMod, die in genau einem der drei Netzwerke mit ihm verbunden
sind? Beispielsweise sind seine Freunde, die nur in Instegräm vorhanden sind, genau die Elemente der Menge I \ (F ∪ G).
Hinweis: Zur Lösung können Sie ein Venn-Diagramm wie das folgende verwenden:
I
F
G

Download Report