Klausur „Einführung in die Informatik“ (MIB, DB 1110), Hinrichs Matr.

-Nr:

Aufgabe 1 (Petri-Netze, 15 Punkte)

Sie arbeiten als Kuchenbäcker*in in einer Konditorei. Modellieren Sie Ihren Arbeitsablauf als Petri-Netz
entsprechend der folgenden Vorgaben:
Wenn Sie startklar sind, legen Sie Equipment und Zutaten bereit (1 Schritt). Wenn die Teigzutaten bereit
liegen, bereiten Sie den Teig zu. Parallel dazu fetten Sie die ebenfalls bereitliegende Backform ein. Wenn
der Teig fertig und die Backform eingefettet ist, füllen Sie den Teig in die Backform. Wenn der Teig in der
Backform und der Ofen vorgeheizt ist (das Einschalten des Ofens muss nicht modelliert werden), starten Sie
den Backvorgang. Nachdem Sie auf das Erreichen der Backzeit gewartet haben, beenden Sie den
Backvorgang. Der Kuchen ist nun fertig und kann in die Vitrine des Verkaufsraums gelegt werden.
Anschließend sind Sie startklar für den nächsten Kuchen.
Hinweise: Bitten beachten Sie, dass es nebenläufige Teilprozesse gibt. Überlegen Sie genau, was Sie als
Stellen und was Sie als Transitionen modellieren, und achten Sie auf eine prägnante Benennung. Denken
Sie auch daran, in die richtige(n) Stelle(n) Marke(n) zu setzen. Hier eine kleine Starthilfe:

Aufgabe 2 (ER-Modell, 15 Punkte)

Die Konditorei, für die Sie nicht nur als Kuchenbäcker*in, sondern auch als Software-Entwickler*in tätig
sind, möchte ihre Rezepte in einer Datenbank verwalten. Erstellen Sie hierfür ein ER-Modell (inkl.
Entitätstypen, Attributen, Schlüssel, Beziehungen und Kardinalitäten) anhand folgender Angaben:
• Jedes Rezept wird durch eine Nummer identifiziert und hat einen Namen, einen Schwierigkeitsgrad
und eine Dauer.
• Jedes Rezept gehört zu einer Kategorie (z. B. „Torten“). Jede Kategorie hat einen eindeutigen
Namen und eine Beschreibung.
• Jedes Rezept besteht aus beliebig vielen Schritten. Jeder Schritt hat eine laufende Nummer, eine
Beschreibung und beliebig viele Bilder.
• Jedes Bild hat eine eindeutige Kennung, einen Dateipfad, eine Höhe sowie eine Breite. Jedes Bild ist
genau einem Schritt eines Rezepts zugeordnet.
• Darüber hinaus werden Zutaten verwaltet. Jede Zutat hat einen eindeutigen Namen (z. B. „Mehl
Typ 405“) und eine Maßeinheit (z. B. „Gramm“).
• Für jedes Rezept werden bestimmte Zutaten in einer bestimmten Menge benötigt (z. B. 500g Mehl
Typ 405). Eine bestimmte Zutat kann in verschiedenen Rezepten Verwendung finden.
• Zu jedem Rezept kann es Kundenfeedback geben. Jedes Kundenfeedback hat eine eindeutige
Nummer, eine Wertung (z. B. 5 Sterne) und eine Bemerkung.
Bitte modellieren Sie nichts, was über die obigen Angaben hinausgeht.

1
Klausur „Einführung in die Informatik“ (MIB, DB 1110), Hinrichs Matr.-Nr:

Aufgabe 3 (Ganze Zahlen, 5 * 3 = 15 Punkte)

Geben Sie bei den folgenden Aufgaben unbedingt die Rechenschritte mit an.

a. Konvertieren Sie die Zahl (-112)10 in eine Zweierkomplement-Darstellung zur Basis 2 mit 8 Stellen.

b. Konvertieren Sie das in Zweierkomplement-Darstellung gegebene Byte 1101 10102 in eine

Dezimalzahl.

c. Konvertieren Sie das in Zweierkomplement-Darstellung gegebene Byte 0100 01112 in eine

Hexadezimalzahl.

d. Addieren Sie die beiden in Zweierkomplement-Darstellung gegebenen Zahlen und interpretieren

Sie das Ergebnis: 1110 10112 + 0001 00112

e. Addieren Sie die beiden in Zweierkomplement-Darstellung gegebenen Zahlen und interpretieren

Sie das Ergebnis: 0111 11002 + 0011 10112

Aufgabe 4 (Fließkommazahlen, 8 + 8 = 16 Punkte)

Geben Sie bei den folgenden Aufgaben unbedingt die Rechenschritte mit an.

a. Konvertieren Sie die Zahl (-2,34)10 in eine 1.2.5-Fließkommazahl (also 8 Bit) nach IEEE 754.

b. Konvertieren Sie die 1.2.5-Fließkommazahl 011101002,IEEE754 in eine Dezimalzahl.

Aufgabe 5 (Algorithmen, 9 + 2 * 3 = 15 Punkte)

Eine ganzzahlige Division ohne Rest, also z = x div y mit x, y, z   und y > 0, kann man durch eine
wiederholte Subtraktion berechnen. Anschaulich gesprochen, zählt man dabei mit, wie oft der Divisor y in
den Dividenden x passt.

a. Vervollständigen Sie das folgende Flussdiagramm, so dass es einen Algorithmus für die ganzzahlige
Division ohne Rest beschreibt. Nehmen Sie an, dass die natürlichen Zahlen x und y (mit y > 0) die
Eingaben des Algorithmus sind. Ausgegeben werden soll das Ergebnis z.

Hinweis: Sie müssen lediglich die vorhandenen Knoten ausfüllen und die Kanten beschriften (soweit
erforderlich). Es müssen keine Knoten oder Kanten hinzugefügt werden.

2
Klausur „Einführung in die Informatik“ (MIB, DB 1110), Hinrichs Matr.-Nr:

b. Sei n = x div y für die Eingabewerte x und y. Geben Sie

1. die Laufzeitkomplexität

2. die Speicherkomplexität

des Algorithmus in O-Notation in Abhängigkeit von n an. Begründen Sie jeweils kurz Ihre Antwort.

Aufgabe 6 (Datenstrukturen, 10 Punkte)

Wählen Sie 10 beliebige Zahlen zwischen 1 und 100 in beliebiger (unsortierter!) Reihenfolge und schreiben
Sie diese als kommagetrennte Liste auf.

Gehen Sie Ihre Liste von links nach rechts durch und fügen Sie die Zahlen nacheinander in einen anfangs
leeren binären Suchbaum ein (grafische Darstellung).

Sie brauchen nicht für jeden Schritt eine neue Skizze zu machen - es reicht der finale Baum nach allen
Einfügeoperationen.

Aufgabe 7 (von-Neumann-Rechner, 10 + 2 + 2 = 14 Punkte)

Gegeben sei folgender Befehlssatz eines von-Neumann-Rechners:

• LOAD x: Lädt (kopiert!) den Inhalt von Speicherzelle x in den Akkumulator des Rechenwerks.
• STORE x: Speichert (kopiert!) den Inhalt des Akkumulators in Speicherzelle x.
• ADD x: Addiert den Inhalt von Speicherzelle x zum Inhalt des Akkumulators.
• SUB x: Subtrahiert den Inhalt von Speicherzelle x vom Inhalt des Akkumulators.
• JUMP x: Springt zum Befehl in Speicherzelle x.
• JUMPNEGATIVE x: Springt zum Befehl in Speicherzelle x, wenn der aktuelle Inhalt des Akkumulators
kleiner als 0 ist.
• STOP: Beendet das Programm.

3
Klausur „Einführung in die Informatik“ (MIB, DB 1110), Hinrichs Matr.-Nr:

a. Dokumentieren Sie in der untenstehenden Tabelle, wie das folgende Assemblerprogramm im von-
Neumann-Rechner abgearbeitet wird. Dazu ist in die linke Spalte der gerade ausgeführte Befehl
einzutragen. In die anderen Spalten sollen jeweils die Werte eingefügt werden, die nach der
Ausführung des Befehls in den einzelnen Speicherzellen bzw. Registern stehen.

100 LOAD 110

101 SUB 111
102 JUMPNEGATIVE 108
103 STORE 110
104 LOAD 109
105 ADD 112
106 STORE 112
107 JUMP 100
108 STOP
109 1
110 8
111 4
112 0

Befehlsregister Befehlszähler Akkumulator 109 110 111 112

<leer> 100 0 1 8 4 0
LOAD 110

4
Klausur „Einführung in die Informatik“ (MIB, DB 1110), Hinrichs Matr.-Nr:

b. Füllen Sie die Lücken in folgendem Satz:

Das Programm berechnet c = a _______ b mit a in Speicherzelle _____, b in _____ und c in _____.

c. Füllen Sie die Lücken in folgendem Satz:

Während der Befehl STORE 110 ausgeführt wird, kann bereits der Befehl LOAD 109
_____________________ und der Befehl ADD 112 __________________ werden. Diese als
_____________________ bezeichnete Vorgehensweise ________________________ die
Programmausführung.