P03 - Klausurrelevant PDF

Preview

Summary

Klausurrelevant...

Description

Modellierung – WS 2020/2021

Hinweis: In der Präsenzübung haben Sie die Möglichkeit, das Entwickeln von Lösungen unter Anleitung Ihres Tutors zu üben sowie Fragen zu klären. Jeder Präsenzübungszettel enthält eine Auswahl an Aufgaben, von denen ein Teil in der Präsenzübung besprochen wird. Es ist nicht das Ziel der Präsenzübung, Musterlösungen vorzurechnen. Aufgabe 1 (Graphen) Die unten gezeigte Abbildung stellt den Grundriss eines automatisch generierten, virtuellen Irrgartens in einem VR-Spiel dar. Die magischen Barrieren in diesem Spiel können nur in Pfeilrichtung (siehe Abbildung) durchschritten werden. Die Spielregeln besagen, dass das Ziel sowohl vom Start als auch von jedem Raum aus erreichbar sein muss. Start

1

2

3

5

4

6 7 8

9 10

12

11

13

14

Ziel

a) Zeichnen Sie einen Graphen, der den Irrgarten repräsentiert. b) Formulieren Sie die Spielregeln mit Begriffen der Graphentheorie. c) Zeigen Sie, dass der abgebildete Irrgarten nicht den Spielregeln entspricht. d) Zwischen welchen Räumen würden Sie eine weitere Barriere einbauen, um das Problem zu lösen.

Seite 1 von 2

e) Zeigen Sie, dass der Irrgarten jetzt (mit der in d) getätigten Modifikation) den Spielregeln entspricht. f) Bestimmen Sie eine topologische Sortierung des Graphen der den Irrgarten repräsentiert und markieren Sie einen kritischen Pfad.

Aufgabe 2 (Modellierung) Für sieben Vorlesungen stehen am Semesterende Abschlussklausuren an. Bei der Terminplanung ist darauf zu achten, dass kein Student mehr als eine Klausur pro Tag schreibt. Ein „+“-Eintrag im Feld (i, j) untenstehender Tabelle bedeutet, dass die Vorlesungen i und j mindestens einen Studenten gemeinsam haben - die Klausuren für diese Vorlesungen dürfen also nicht am selben Tag stattfinden. 1 1 2 3 4 5 6 7

2 +

+

3

4 +

+ +

+

5

6 +

7

+ +

+

+

+

+

+

+

+ +

+

1. Modellieren Sie das Problem graphentheoretisch. 2. Wie viele Tage sind zur Durchführung aller Klausuren mindestens notwendig? 3. Geben Sie einen möglichen Terminplan an.

Aufgabe 3 (Modellierung) Claudia veranstaltet eine Cocktailparty und hat als Begrüßung unter anderem 7 verschiedene Cocktails vorbereitet: Bloody Mary, Daiquiri, Green Spider, Harvey Wallbanger, Lady Killer, Tequilla Sunrise und Whiskey Sour Madisson. Zu Ihrer Party lädt sie ihre 6 Freunde Andrea, Bernd, Christiane, Dennis, Elizabeth und Frank ein. Diese haben jedoch in punkto Cocktails spezielle Vorlieben: • Andrea mag Bloody Mary und Daiquiri. • Bernd mag Green Spider, Bloody Mary und Harvey Wallbanger. • Christiane mag Daiquiri, Harvey Wallbanger und Green Spider. • Dennis mag Lady Killer, Bloody Mary, Tequilla Sunrise und Daiquiri. • Elizabeth mag Harvey Wallbanger, Daiquiri, Bloody Mary und Green Spider. • Frank mag Daiquiri, Green Spider und Bloody Mary. 1. Stellen Sie die Vorlieben der einzelnen Gäste mit Hilfe eines Graphen dar. 2. Können alle Gäste eines ihrer Lieblingsgetränke bekommen?

Seite 2 von 2...