2014 Einsendearbeit 1 7 Mit Lösungen PDF

Preview

Summary

EINGANGSSTEMPEL Bitte hier unbedingt Matrikelnummer und Adresse eintragen, sonst keine Bearbeitung M Postanschrift: D 58084 Hagen Name Bitte an: in Hagen D 58084 Hagen PLZ, Ort Bestimmungsland (nur bei Anschriften Deutschlands) Mathematik und Informatik Kurs (LG Prof. 01142 Algorithmische Mathematik...

Description

EINGANGSSTEMPEL FERNUNIVERSITÄT

Bitte hier unbedingt Matrikelnummer und Adresse eintragen, sonst keine Bearbeitung möglich.

M

Postanschrift: FernUniversität D – 58084 Hagen

Name Straße

Bitte zurück an: FernUniversität in Hagen D – 58084 Hagen

PLZ, Ort Bestimmungsland (nur bei Anschriften außerhalb Deutschlands)

Fakultät für Mathematik und Informatik Kurs

(LG Prof. Hochstättler)

01142 Algorithmische Mathematik

Kurseinheit 1 Einsendeaufgaben A. Hinweise zur Bearbeitung 0. Benutzen Sie bitte für Ihre Lösungen Papier im Format DIN A4. 1. Schreiben Sie bitte auf jedes Blatt Ihren Namen mit Matrikelnummer. 2. Schreiben Sie bitte deutlich, lassen Sie einen breiten Rand (ca. 4–5cm) und nummerieren Sie zum Schluss Ihre Lösungsblätter durch. 3. Schicken Sie Ihre Lösungsblätter sowie das (grüne) Deckblatt komplett und zusammengeklammert zurück. 4. Kreuzen Sie bitte in der Zeile „bearbeitet“ die von Ihnen bearbeiteten Aufgaben an. B. Hinweise zur Bewertung 1. Bei jeder Aufgabe bzw. Teilaufgabe ist die erreichbare Punktzahl vermerkt, sofern Punktwertung vorgenommen wird. 2. Insgesamt sind 77 Punkte erreichbar. 3. Die Einsendearbeit umfasst 6 Aufgaben.

Letzter Einsendetag:

Aufgabe

14.04.2014

(Datum des Poststempels)

1

2

3

4

5

6

7

8

bearbeitet erreichte Punktzahl

Datum:

Korrektur: c 2014 FernUniversität in Hagen 

Alle Rechte vorbehalten

9

10

Summe

1142E114

AlMa, E 1 Algorithmische Mathematik, SS 2014 Kurseinheit 1: Einsendeaufgaben Einsendetermin: 14.04.2014 Allgemeiner Hinweis: Besonders anspruchsvolle Aufgaben sind mit einem Sternchen gekennzeichnet.

E 1.1

Sei A := {1, 2, 3, 4, 5, 6, 7, 8, 9} . Welche der folgenden Abbildungen ist surjektiv bzw. injektiv? Falls es sich um eine Permutation handelt, wie lautet dann die Zerlegung in Zykeln? (a) f1 : A −→ A,

x 7−→ 10 − x .

(b) f2 : A −→ A,

x 7−→ min{4x − 3, 9} .

(c) f3 : {1, 2, 3} −→ A,

x 7−→ x2 .

(d) f4 : N \ {0} −→ A,

x 7−→ erste Ziffer von x in Dezimaldarstellung.

(e) f5 : Z −→ A ∪ {0},

x 7−→ Rest bei Division von x durch 8.

(f) f6 : A −→ A , 1 7−→ 2 , 2 7−→ 4 , 7 7−→ 1 , 8 7−→ 6 , 9 7−→ 3 .

3 7−→ 9 ,

4 7−→ 7 ,

5 7−→ 8 ,

6 7−→ 5 ,

[4 + 2 + 2 + 2 + 2 + 4 = 16 Punkte] E 1.2

Seien a, b, c, d ∈ R und a, b, c, d > 0 . Zeigen Sie, dass unter diesen Voraussetzungen gilt: na c o na c o a + c ≥ min , max , ≥ b d b d b+d Ist dies auch noch richtig, wenn man auf die Voraussetzung a, b, c, d > 0 verzichtet und nur voraussetzt, dass b 6= 0 , d 6= 0 und b + d 6= 0 ? [7 Punkte]

E 1.3

Zeigen Sie, dass für alle n ∈ N gilt: (a) 3 teilt 4n − 1 . (b) 9 teilt 3n · 4n+1 − 4n+1 + 4 . [4 + 7 = 11 Punkte]

E 1.4

Vor einiger Zeit kursierten Kettenbriefe, die auf ein besonderes Ereignis hinwiesen. Eine Quelle aus dem Internet beschreibt dieses Ereignis etwa mit den Worten:

1142E114

–2–

AlMa, E 1

Nehmen Sie Stellung zur Häufigkeit des Auftretens des Ereignisses. [10 Punkte] E 1.5

Zeigen Sie jeweils mit einer Beweismethode Ihrer Wahl (ohne einen Taschenrechner oder Computer zu benutzen): (a) Für alle n ∈ N gilt n

  n+1 (3k + 2k + 1) = n + 5 + 1. ∑ 2 k=0 2

3

(b) Die Anzahl der verschiedenen (nicht notwendigerweise sinnvollen) Wörter der Länge 11, die aus den Buchstaben des Wortes LENNEQUELLE gebildet werden können, wobei die Buchstaben in jeweils der richtigen Vielfachheit vorkommen sollen, ist größer als 40000 und kleiner als 1000000. (c) Für alle n, ℓ, k ∈ N \ {0} mit k < n − 1 gilt  (ℓ+1)! n ℓ!·ℓ  (k + 1)(ℓ+1)! k n . ℓ! =  n (n − k)(ℓ+1)! k + 1 k+1 [5 + 5 + 5 = 15 Punkte] E 1.6

Drei platonische Körper , das sind konvexe Körper, die durch flächengleiche regelmäßige n -Ecke beschränkt sind, siehe Abbildung 1, werden zum Würfeln benutzt. Auf jeder Fläche der Körper steht genau eine ganze (nicht notwendigerweise positive) Zahl. Die

1142E114

–3–

AlMa, E 1

Zahlen auf den Flächen eines Körpers sind paarweise verschieden, können aber auf einem anderen Körper evtl. vorkommen. Der erste Körper ist ein Hexaeder (oder Würfel im üblichen Sinne, hat also 6 Flächen), der zweite Körper ist ein Dodekaeder (hat also 12 Flächen). Die Anzahl der auf irgendwelchen der drei Körper vorkommenden Zahlen beträgt 24. Die Anzahl der Zahlen, die auf jedem der Körper vorkommen, beträgt 3. Die Anzahl der auf dem ersten und zweiten Körper vorkommenden Zahlen beträgt 4, die Anzahl der auf dem ersten und dritten vorkommenden Zahlen beträgt 5 und die Anzahl der auf dem zweiten und dritten vorkommenden Zahlen beträgt 8.

Tetraeder

Würfel (Hexaeder)

Dodekaeder

Oktaeder

Ikosaeder

Abbildung 1: Die fünf platonischen Körper (a) Beantworten Sie die folgende Fragen oder begründen Sie, dass zu wenige Informationen gegeben sind, um die jeweilige Frage zu beantworten. (i) Wieviele Flächen hat der dritte Körper? (ii) Welche Zahlen kommen auf dem ersten Körper vor, aber weder auf dem zweiten noch auf dem dritten? (iii) Wieviele Zahlen kommen auf genau einem der Körper vor? (iv) Welches ist die kleinste, auf dem dritten Körper vorkommende Zahl? (b*) Sie dürfen annehmen, dass die Körper eine absolut homogene Dichteverteilung haben, es sich also um faire „Würfel“ handelt. Wir würfeln mit den drei Körpern. Betrachten Sie folgende Ereignisse:

1142E114

–4–

AlMa, E 1

A sei das Ereignis, dass eine Zahl, die sich auf allen drei Körpern befindet, von mindestens einem der Körper ausgewürfelt wird. B sei das Ereignis, dass eine Zahl, die sich auf genau zweien der Körper befindet, von diesen beiden Körpern ausgewürfelt wird. C sei das Ereignis, dass keine Zahl, die sich auf allen drei Körpern befindet, von einem der Körper ausgewürfelt wird. Berechnen Sie die Wahrscheinlichkeit des Eintretens des Ereignisses A , B bzw. C und (sofern sinnvoll) die bedingten Wahrscheinlichkeiten p(A|B) , p(B|A) , p(A|C) , p(C|A) , p(B|C) und p(C|B) . Welche der Paare von Ereignissen sind unabhängig? [8 + 10 = 18 Punkte]

EINGANGSSTEMPEL FERNUNIVERSITÄT

Bitte hier unbedingt Matrikelnummer und Adresse eintragen, sonst keine Bearbeitung möglich.

M

Postanschrift: FernUniversität D – 58084 Hagen

Name Straße

Bitte zurück an: FernUniversität in Hagen D – 58084 Hagen

PLZ, Ort Bestimmungsland (nur bei Anschriften außerhalb Deutschlands)

Fakultät für Mathematik und Informatik Kurs

(LG Prof. Hochstättler)

01142 Algorithmische Mathematik

Kurseinheit 2 Einsendeaufgaben A. Hinweise zur Bearbeitung 0. Benutzen Sie bitte für Ihre Lösungen Papier im Format DIN A4. 1. Schreiben Sie bitte auf jedes Blatt Ihren Namen mit Matrikelnummer. 2. Schreiben Sie bitte deutlich, lassen Sie einen breiten Rand (ca. 4–5cm) und nummerieren Sie zum Schluss Ihre Lösungsblätter durch. 3. Schicken Sie Ihre Lösungsblätter sowie das (grüne) Deckblatt komplett und zusammengeklammert zurück. 4. Kreuzen Sie bitte in der Zeile „bearbeitet“ die von Ihnen bearbeiteten Aufgaben an. B. Hinweise zur Bewertung 1. Bei jeder Aufgabe bzw. Teilaufgabe ist die erreichbare Punktzahl vermerkt, sofern Punktwertung vorgenommen wird. 2. Insgesamt sind 77 Punkte erreichbar. 3. Die Einsendearbeit umfasst 6 Aufgaben.

Letzter Einsendetag:

Aufgabe

28.04.2014

(Datum des Poststempels)

1

2

3

4

5

6

7

8

bearbeitet erreichte Punktzahl

Datum:

Korrektur: c 2014 FernUniversität in Hagen 

Alle Rechte vorbehalten

9

10

Summe

1142E214

AlMa, E 2 Algorithmische Mathematik, SS 2014 Kurseinheit 2: Einsendeaufgaben Einsendetermin: 28.04.2014

E 2.1

Betrachten Sie folgenden Graphen. 1

2

5

3

4

6

(a) Führen Sie die Tiefensuche, vom Knoten 1 startend, unter Beachtung der natürlichen aufsteigenden Sortierung der Knoten, aus und bestimmen Sie die Vorgänger jedes Knotens und den dadurch definierten Graphen (d.h. den Tiefensuchbaum). (b) Führen Sie die Breitensuche, vom Knoten 1 startend, unter Beachtung der natürlichen aufsteigenden Sortierung der Knoten, aus und bestimmen Sie die Vorgänger jedes Knotens und den dadurch definierten Graphen (d.h. den Breitensuchbaum). (c) Geben Sie eine Adjazenzmatrix und eine Inzidenzmatrix des Graphen an. (d) Berechnen Sie die Anzahl der Spaziergänge (i) der Länge 4 vom Knoten 1 zum Knoten 6 bzw. (ii) der Länge 5 vom Knoten 2 zum Knoten 2. [2 + 2 + 2 + 4 = 10 Punkte] E 2.2

Welche der folgenden Sequenzen sind Valenzsequenzen eines Graphen? (a) (14, 9, 8, 6, 5, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2) (b) (14, 9, 9, 9, 9, 9, 9, 3, 3, 2, 2, 2, 2, 2, 2) (c) (8, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1) Geben Sie, falls möglich, jeweils einen Graphen mit der angegebenen Valenzsequenz an. [6 + 3 + 6 = 15 Punkte]

1142E214 E 2.3

–2–

AlMa, E 2

In einer Chemiefabrik gibt es folgendes Rohrleitungsnetzwerk: 0

1

2

3

4

7

5

8

6

9

Dieses soll von einem Rohrreinigungroboter in möglichst kurzer Zeit gereinigt werden, d.h. der Roboter muss durch jedes Rohr mindestens einmal fahren. Der Roboter fährt mit konstanter Geschwindigkeit durch die Rohre, aufgrund von Ventilen sind sämtliche Rohre, wie in der Zeichnung angegeben, nur in einer Richtung passierbar. Der Roboter wird an einem Knotenpunkt eingesetzt und am Ende an möglicherweise einem anderen Knotenpunkt herausgenommen. Da das Einsetzen sehr zeitaufwendig ist, sollte es nur einmal am Anfang geschehen. An welchem Knotenpunkt sollte man den Roboter einsetzen? In welcher Weise können die Rohre am effizientesten gereinigt werden? [9 Punkte] E 2.4

Seien m, n ∈ N . (a) Sei n ≥ 3 und v ein Knoten und e eine Kante des Kreisgraphen Cn . Für welche n ist Cn \ v , Cn \ e bzw. Cn %e zusammenhängend bzw. 2-zusammenhängend? (b) Sei v ein Knoten und e eine Kante des vollständigen Graphen Kn . Für welche n ist Kn \ v , Kn \ e bzw. Kn %e zusammenhängend bzw. 2-zusammenhängend? (c) Sei v ein Knoten und e eine Kante des vollständigen bipartiten Graphen Km,n . Für welche (m, n) ist Km,n \ v , Km,n \ e , Km,n %e bzw. Km,n /e zusammenhängend bzw. 2-zusammenhängend? Wann ist die Antwort nicht eindeutig? (d) Sei n ≥ 1 und v ein Knoten und e eine Kante des Weges Pn . Für welche n ist Pn \ v , Pn \ e bzw. Pn %e zusammenhängend bzw. 2-zusammenhängend? Wann ist die Antwort nicht eindeutig? [3 + 4 + 7 + 3 = 17 Punkte]

1142E214 E 2.5

–3–

AlMa, E 2

Sei n ∈ N und G = (V, E) ist ein Graph mit |V | = 2n Knoten, von denen jeder den Knotengrad n habe. Zeigen Sie, dass für alle k ∈ N mit n + 2 ≤ k ≤ 2n − 1 gilt, dass G keine Kreise Ck der Länge k als induzierten Teilgraph enthält. Zusatzfrage: Kann man ebenfalls zeigen, dass G keine Kreise C2n der Länge 2n enthält? [10 Punkte]

E 2.6

Sei (P, ≤) eine Partialordnung und A ⊆ P . Ein Element s ∈ P heißt Supremum, wenn gilt: • a ≤ s für alle a ∈ A und • wenn für ein Element s′ ∈ P gilt a ≤ s′ für alle a ∈ A , dann gilt s ≤ s′ . Ein Infimum einer Teilmenge A ⊆ P wird analog definiert, nur mit ≥ an allen Stellen, wo ≤ auftritt. (a) Zeigen Sie, dass eine Teilmenge A ⊆ P höchstens ein Supremum und ein Infimum besitzt. Auf Grund dieses Ergebnisses können wir nun das Supremum von der Menge A im Falle der Existenz mit sup(A) bezeichnen und das Infimum von A mit inf(A) . (b) Welches Element ist das Supremum der leeren Menge (sofern existent)? (c) Finden Sie ein Beispiel einer Partialordnung, in dem jede nicht leere Menge ein Infimum hat, es aber eine nicht leere Menge gibt, die kein Supremum besitzt. (d) Sei nun X eine endliche Menge und P = 2X ihre Potenzmenge, d.h. die Menge ihrer Teilmengen. Sei die Ordnungsrelation ≤ wie in 3.1.11 als Teilmengenrelation ⊆ definiert. Zeigen Sie, dass für alle A ⊆ P ein Infimum und ein Supremum existiert. Wie lauten diese im Fall, dass A zweielementig ist? [4 + 3 + 3 + 6 = 16 Punkte]

EINGANGSSTEMPEL FERNUNIVERSITÄT

Bitte hier unbedingt Matrikelnummer und Adresse eintragen, sonst keine Bearbeitung möglich.

M

Postanschrift: FernUniversität D – 58084 Hagen

Name Straße

Bitte zurück an: FernUniversität in Hagen D – 58084 Hagen

PLZ, Ort Bestimmungsland (nur bei Anschriften außerhalb Deutschlands)

Fakultät für Mathematik und Informatik Kurs

(LG Prof. Hochstättler)

01142 Algorithmische Mathematik

Kurseinheit 3 Einsendeaufgaben A. Hinweise zur Bearbeitung 0. Benutzen Sie bitte für Ihre Lösungen Papier im Format DIN A4. 1. Schreiben Sie bitte auf jedes Blatt Ihren Namen mit Matrikelnummer. 2. Schreiben Sie bitte deutlich, lassen Sie einen breiten Rand (ca. 4–5cm) und nummerieren Sie zum Schluss Ihre Lösungsblätter durch. 3. Schicken Sie Ihre Lösungsblätter sowie das (grüne) Deckblatt komplett und zusammengeklammert zurück. 4. Kreuzen Sie bitte in der Zeile „bearbeitet“ die von Ihnen bearbeiteten Aufgaben an. B. Hinweise zur Bewertung 1. Bei jeder Aufgabe bzw. Teilaufgabe ist die erreichbare Punktzahl vermerkt, sofern Punktwertung vorgenommen wird. 2. Insgesamt sind 77 Punkte erreichbar. 3. Die Einsendearbeit umfasst 6 Aufgaben.

Letzter Einsendetag:

Aufgabe

12.05.2014

(Datum des Poststempels)

1

2

3

4

5

6

7

8

bearbeitet erreichte Punktzahl

Datum:

Korrektur: c 2014 FernUniversität in Hagen 

Alle Rechte vorbehalten

9

10

Summe

1142E314

AlMa, E 3 Algorithmische Mathematik, SS 2014 Kurseinheit 3: Einsendeaufgaben Einsendetermin: 12.05.2014

E 3.1

Untersuchen Sie, welche der drei unten abgebildeten Bäume isomorph sind. 1

3

2

1

2

4

5

6

8

3

7

9

10

13

14

4

11

12

5 6

15 7

1

16

8

9

10

13

14

2

11

3

4

5

12

6

7

8

9

10

11

12

13

15 14

15

16

16

[9 Punkte] E 3.2

Betrachten

Sie

die

folgenden

beiden

Graphen

mit

Knotenmenge

jeweils

{1, 2, 3, 4, 5, 6, 7, 8} und Kantengewichten wie folgt: Kante {i, j} habe das Gewicht i+ j. 2

3

4

7

1

4

1

2

8

5

6

5

7

6

3

8

(a) Bestimmen Sie für jeden Graphen einen minimalen aufspannenden Baum. (b) Sind Ihre beiden in (a) erhaltenen Bäume jeweils eindeutig? (c) Zeigen oder widerlegen Sie: Die beiden aufspannenden Bäume aus (a) sind isomorph. [8 + 5 + 2 = 15 Punkte]

1142E314 E 3.3

–2–

AlMa, E 3

Weit draußen im Meer befinden sich 7 kleine Inseln, bislang ohne Stromversorgung. Auf Insel 1 wird ein Kraftwerk errichtet und auf den übrigen sechs Inseln jeweils ein Umspannwerk. Außerdem gibt es auf den Inseln noch eine gewisse Anzahl an Bauernhöfen. Die Anzahl B(i) der Bauernhöfe auf Insel i ist jeweils in der folgenden Tabelle aufgetragen. i B(i)

1 2 3 4 5 6 7 1 2 1 4 3 7 4

Nun soll jedes Umspannwerk und jeder Bauernhof so mit Stromleitungen an das Kraftwerk (evtl. auf Wegen über andere Bauernhöfe und Umspannwerke) angeschlossen werden, dass es genau einen Stromleitungsweg von dem betreffenden Bauwerk zum Kraftwerk gibt. Das Stromnetz soll also keine Kreise enthalten. Für den Bau des Stromnetzes gibt es folgende Möglichkeiten. Auf einer Insel hat man für jedes Paar (b1 , b2 ) von Bauwerken (Kraftwerk, Umspannwerk bzw. Bauernhof), welche sich auf dieser Insel befinden, die Möglichkeit, eine Stromleitung von b1 nach b2 zu bauen oder nicht zu bauen. Desweiteren hat man folgende Möglichkeiten, Umspannwerke mit Umspannwerken anderer Inseln bzw. Kraftwerk zu verbinden: die Verbindungsmöglichkeiten sind als gestrichelte Kanten in der folgenden Landkarte der Inseln eingezeichnet. Da es sich dabei um Starkstromverbindungen handelt, dürfen diese Verbindungen keine Bauernhöfe beinhalten.

2 1

3

4

5

7 6

1142E314

–3–

AlMa, E 3

Wir nennen zwei mögliche Stromnetze unterschiedlich, wenn zwei Bauwerke existieren, die in dem einen Netz durch eine direkte Stromleitung verbunden sind, in dem anderen aber nicht. Als Ingenieurbüro, welches das Stromnetz bauen soll, wollen Sie sich einen Überblick über die Anzahl der Möglichkeiten verschaffen, die Sie haben. Wie viele unterschiedliche mögliche Stromnetze gibt es? [10 Punkte] E 3.4

Seien n ∈ N und G = (V, E) ein Graph mit |V | = 2n Knoten, von denen jeder den Knotengrad n habe. Enthalte G ferner keine induzierten Kreise C2k+1 der Längen 2k + 1   für k ∈ N mit 0 ≤ k ≤ 2n . Zeigen Sie, dass G = Kn,n gilt (wobei Kn,n den vollständigen bipartiten Graphen mit zwei Partitionen von je n Knoten bezeichnet). Tipp: Es ist hilfreich, eine Aufgabe aus den Einsendeaufgaben einer früheren Kurseinheit zu benutzen. [12 Punkte]

E 3.5

Betrachten Sie folgenden bipartiten Graphen G (linke Abbildung) und die Kantenmenge M0 := {B2, E5, F6} (dick gezeichnete Kanten in rechter Abbildung) in G . A B C D E F G

1 2 3 4 5 6 7

G

A B C D E F G

1 2 3 4 5 6 7

M0 (dicke Kanten)

(a) Zeigen oder widerlegen Sie: M0 ist ein Matching. (b) Zeigen oder widerlegen Sie: M0 ist ein maximales Matching von G . (c) Zeigen oder widerlegen Sie: Es existiert ein perfektes Matching in G . (d) Bestimmen Sie ein maximales Matching in G . (e) Bestimmen Sie eine minimale Knotenüberdeckung in G . [1 + 3 + 6 + 4 + 4 = 18 Punkte]

1142E314 E 3.6

–4–

AlMa, E 3

7 Praktikanten (w/m) sollen in einer großen Firma auf 7 verschiedene Abteilungen verteilt werden, je einer pro Abteilung. Die Praktikanten A, B,C, D, E, F, G geben als Präferenzliste für Ihren gewünschten Arbeitsplatz folgendes an, wobei von links nach rechts abnehmende Präferenz gelten soll: A : (1, 2, 3, 4, 5, 6, 7) B : (1, 3, 5, 7, 2, 4, 6) C : (2, 3, 6, 5, 1, 4, 7) D : (3, 2, 5, 6, 7, 4, 1) E : (2, 6, 3, 5, 1, 4, 7) F : (7, 6, 5, 4, 3, 2, 1) G : (2, 1, 3, 6, 5, 4, 7) Die Abteilungsleiterinnen (m/w) von Abteilung i geben als Präferenzliste für den gewünschten Praktikanten folgendes an, wobei wieder links die am meisten gewünschten Bewerber stehen: 1 : (C,...