Sitzung: Jeden Freitag in der Vorlesungszeit ab 16 Uhr c. t. im MAR 0.005. In der vorlesungsfreien Zeit unregelmäßig (Jemensch da?). Macht mit!

Informatik 3/Gedächtnisprotokoll Klausur SS07: Unterschied zwischen den Versionen

(Aufgabe 4: Graphen)
K (Formatierung korrigiert, Kategorisiert)
 
(36 dazwischenliegende Versionen von 8 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
== 1. Aufgabe: Multiple Choice ==
+
== Aufgabe 1: Multiple Choice (7 Punkte) ==
  
* ..
+
Kreuzen Sie jeweils wahr bzw. falsch an:
 +
* Ein zusammenhängender, ungerichteter Graph mit |V| Knoten hat immer |V| * (|V| - 1) / 2 Kanten.  
 
* Traversierung mit Breitensuche erzeugt einen aufspannenden Baum.
 
* Traversierung mit Breitensuche erzeugt einen aufspannenden Baum.
 
* Die Höhe eines binären Suchbaumes ist immer um 1 größer, als das Maximum der Höhen seiner Teilbäume.
 
* Die Höhe eines binären Suchbaumes ist immer um 1 größer, als das Maximum der Höhen seiner Teilbäume.
 
* Für jedes endliche Optimierungsproblem kann man einen Backtrackingalgorithmus finden der dieses löst.
 
* Für jedes endliche Optimierungsproblem kann man einen Backtrackingalgorithmus finden der dieses löst.
 
* Für jedes endliche Optimierungsproblem kann man einen Greedy-algorithmus finden der dieses löst.
 
* Für jedes endliche Optimierungsproblem kann man einen Greedy-algorithmus finden der dieses löst.
<br>
 
  
== HashTables ==
+
Worst Case Aufwand von:
 +
* Wert in eine Hashliste mit Separate Chaining einfuegen
 +
* Einen Wert in einer Skipliste finden
 +
* Rotieren in einem AVL-Baum
 +
* Tiefensuch
 +
* Kruskal
 +
* Edmonds Karp Alg
 +
 
 +
== Aufgabe 2: HashTables (7 Punkte) ==
  
 
Hashtabelle der Größe 4.
 
Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
+
* Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
+
* Kollisonsauflösung: z.B. "double hashing" a(k) = k+2
<br>
+
* Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.
Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.
+
 
 
(A,5) (B,11) (C,9) (D,14)
 
(A,5) (B,11) (C,9) (D,14)
 +
 +
Lösung:
 
A -> 1
 
A -> 1
 
B -> 3
 
B -> 3
C -> 1, 3, 1 , 3 .. (kann nicht eingefügt werden)
+
C -> 1,0
 
D -> 2
 
D -> 2
0 blieb leer.
+
 
<br>
 
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
<br>
 
  
== AVL-Bäume ==
+
== Aufgabe 3: Suchbäume (11 Punkte) ==
*Einfügen in AVL-Baum
 
*Einfügen in AVL-Baum
 
*Löschen aus AVL-Baum
 
<br>
 
  
== Rot-Schwaz-Bäume ==
+
'''AVL-Bäume'''
*Einfügen in RS-Baum
+
*Einfügen von 3 in den folgenden AVL-Baum:
*Java-Programm schreiben für Höhenberechnung eines Rot-Schwarz-Baumes getBlackHeight(Node root)
+
[[Bild:Info3-ss2007-3-avltree.png]]
 +
 
 +
*Löschen von 10 aus dem folgenden AVL-Baum:
 +
[[Bild:Info3-ss2007-3-avltree.png]]
 +
 
 +
'''Rot/Schwarz-Bäume'''
 +
*Einfügen von '9' in den folgenden Rot/Schwarz-Baum:
 +
[[Bild:Info3-ss2007-3-rbtree.png]]
 +
 
 +
*Java-Programm schreiben für Höhenberechnung eines Rot-Schwarz-Baumes: int getBlackHeight(Node root)
 
** Rot-Schwarz-Baum als gültig vorausgesetzt.
 
** Rot-Schwarz-Baum als gültig vorausgesetzt.
 
** Vorgegebene Implementation:
 
** Vorgegebene Implementation:
*** isRed(Node node);
+
*** boolean isRed(Node node);
*** isBlack(Node node);
+
*** boolean isBlack(Node node);
 
*** class Node{ int color; Node left; Node right; }
 
*** class Node{ int color; Node left; Node right; }
<br>
 
  
== B-Baum ==
+
'''B-Baum'''
 
* Element in B-Baum einfügen.
 
* Element in B-Baum einfügen.
 +
[[Bild:Info3-ss2007-3-btree.png]]
  
 +
== Aufgabe 4: Graphen (10 Punkte) ==
  
== Aufgabe 4: Graphen ==
 
 
a) Baue eine Adjazenzmatrix zu folgendem Graphen:
 
a) Baue eine Adjazenzmatrix zu folgendem Graphen:
  
Zeile 61: Zeile 74:
  
 
e) Erstelle den Restflussgraphen zu folgendem Flussgraphen:
 
e) Erstelle den Restflussgraphen zu folgendem Flussgraphen:
 +
 
[[Bild:Info3-ss2007-4e.png]]
 
[[Bild:Info3-ss2007-4e.png]]
  
== Aufgabe 5: Übungsorganisation ==
+
== Aufgabe 5: Übungsorganisation (4 Punkte) ==
Hab ich, trag ich gleich ein [[Benutzer:TomyLobo|TomyLobo]]
+
 
 +
Es herrscht grosser Andrang bei der Sprechstunde. Keiner der wartenden Studierenden erinnert sich an die genaue Ankunftsreihenfolge. Einige erinnern sich jedoch noch an die Leute die bereits warteten. Es soll eine ungefähre Ankunftsreihenfolge bestimmt werden.
 +
 
 +
{| class="prettytable"
 +
! Name      || wartete bereits
 +
|-
 +
| Annett    || Daniel, Edeltraut
 +
|-
 +
| Bert      || Anett, Daniel, Claudia
 +
|-
 +
| Claudia  || -
 +
|-
 +
| Daniel    || Claudia
 +
|-
 +
| Edeltraut || Claudia
 +
|}
 +
 
 +
a) Erstelle einen Graph aus den Erinnerungen der wartenden Studierenden.
 +
 
 +
b) Nun soll die ungefähre Reihenfolge der Studierenden berechnet werden.
 +
 
 +
Algorithmus:
 +
 
 +
Ablauf:
 +
 
 +
== Aufgabe 6: Dynamisches Programmieren (5 Punkte) ==
 +
 
 +
[[Bild:Info3-ss2007-6.png]]
 +
<!-- Das Bild wurde gerendert mit freundlicher, allerdings unwissender, Unterstützung der deutschen Wikipedia.
 +
Hier der TeX-Quellcode des obenstehenden Bildes:
 +
<math>g(m, n) = \left\lbrace\begin{matrix} 42 & m = 0 \or n=0 \\ g(m-1, n-1) + g(m, n-1) & m > 0 \and n > 0 \end{matrix}\right.</math>
 +
-->
 +
 
 +
a) Geben Sie eine nicht-rekursive Java-Methode an, die g(m,n) für m, n e N berechnet. Die Methode soll dafür polynomielle Laufzeit benötigen
 +
 
 +
b) Kleinste worst-case-Laufzeitklasse angeben:
 +
 
 +
O( .... )
 +
 
 +
== Aufgabe 7: Geld wechseln (6 Punkte) ==
 +
 
 +
Gegeben ist ein Betrag, welcher durch möglichst wenige Geldstücke der Grössen { 200, 100, 50, 20, 10, 5, 2, 1 } dargestellt werden werden soll.
 +
 
 +
a) Geben Sie eine günstige Kodierung für die Geldstücke an
 +
 
 +
b) Geben Sie eine Zielfunktion und eine Optimierungsrichtung (max/min) an.
 +
 
 +
c) Geben Sie ein Greedy-Verfahren zur Lösung des Optimierungsproblems an (als Pseudocode oder verbal).
 +
 
 +
Diese Aufgabe war auch als Hausaufgabe im WS 06/07 im 7. Übungsblatt Aufgabe 7.6 als 'Theorie' zu lösen
 +
 
 +
== Siehe auch ==
  
== Aufgabe 6: Dynamisches Programmieren ==
+
[[Informatik 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2007]]
Hab ich, trag ich gleich ein [[Benutzer:TomyLobo|TomyLobo]]
 
  
== Aufgabe 7: Geld wechseln ==
+
[[Kategorie: Prüfungsprotokolle]]
Hab ich, trag ich gleich ein [[Benutzer:TomyLobo|TomyLobo]]
+
[[Kategorie: Informatik]]
 +
[[Kategorie: StuPO90]]

Aktuelle Version vom 24. Februar 2013, 13:07 Uhr

Aufgabe 1: Multiple Choice (7 Punkte)

Kreuzen Sie jeweils wahr bzw. falsch an:

  • Ein zusammenhängender, ungerichteter Graph mit |V| Knoten hat immer |V| * (|V| - 1) / 2 Kanten.
  • Traversierung mit Breitensuche erzeugt einen aufspannenden Baum.
  • Die Höhe eines binären Suchbaumes ist immer um 1 größer, als das Maximum der Höhen seiner Teilbäume.
  • Für jedes endliche Optimierungsproblem kann man einen Backtrackingalgorithmus finden der dieses löst.
  • Für jedes endliche Optimierungsproblem kann man einen Greedy-algorithmus finden der dieses löst.

Worst Case Aufwand von:

  • Wert in eine Hashliste mit Separate Chaining einfuegen
  • Einen Wert in einer Skipliste finden
  • Rotieren in einem AVL-Baum
  • Tiefensuch
  • Kruskal
  • Edmonds Karp Alg

Aufgabe 2: HashTables (7 Punkte)

Hashtabelle der Größe 4.

  • Hashfunktion: h(k) = k mod 4
  • Kollisonsauflösung: z.B. "double hashing" a(k) = k+2
  • Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.

(A,5) (B,11) (C,9) (D,14)

Lösung: A -> 1 B -> 3 C -> 1,0 D -> 2

Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.

Aufgabe 3: Suchbäume (11 Punkte)

AVL-Bäume

  • Einfügen von 3 in den folgenden AVL-Baum:

Info3-ss2007-3-avltree.png

  • Löschen von 10 aus dem folgenden AVL-Baum:

Info3-ss2007-3-avltree.png

Rot/Schwarz-Bäume

  • Einfügen von '9' in den folgenden Rot/Schwarz-Baum:

Info3-ss2007-3-rbtree.png

  • Java-Programm schreiben für Höhenberechnung eines Rot-Schwarz-Baumes: int getBlackHeight(Node root)
    • Rot-Schwarz-Baum als gültig vorausgesetzt.
    • Vorgegebene Implementation:
      • boolean isRed(Node node);
      • boolean isBlack(Node node);
      • class Node{ int color; Node left; Node right; }

B-Baum

  • Element in B-Baum einfügen.

Info3-ss2007-3-btree.png

Aufgabe 4: Graphen (10 Punkte)

a) Baue eine Adjazenzmatrix zu folgendem Graphen:

Info3-ss2007-4a.png

b) Dijkstra auf folgendem Graph ausführen:

Info3-ss2007-4b.png

c) Definiere (formal oder als Text) den Begriff "aufspannender Baum".

d) Führe union(D,F) auf folgender, als Wald realisierter disjunkter Menge aus:

Info3-ss2007-4d.png

e) Erstelle den Restflussgraphen zu folgendem Flussgraphen:

Info3-ss2007-4e.png

Aufgabe 5: Übungsorganisation (4 Punkte)

Es herrscht grosser Andrang bei der Sprechstunde. Keiner der wartenden Studierenden erinnert sich an die genaue Ankunftsreihenfolge. Einige erinnern sich jedoch noch an die Leute die bereits warteten. Es soll eine ungefähre Ankunftsreihenfolge bestimmt werden.

Name wartete bereits
Annett Daniel, Edeltraut
Bert Anett, Daniel, Claudia
Claudia -
Daniel Claudia
Edeltraut Claudia

a) Erstelle einen Graph aus den Erinnerungen der wartenden Studierenden.

b) Nun soll die ungefähre Reihenfolge der Studierenden berechnet werden.

Algorithmus:

Ablauf:

Aufgabe 6: Dynamisches Programmieren (5 Punkte)

Info3-ss2007-6.png

a) Geben Sie eine nicht-rekursive Java-Methode an, die g(m,n) für m, n e N berechnet. Die Methode soll dafür polynomielle Laufzeit benötigen

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

Aufgabe 7: Geld wechseln (6 Punkte)

Gegeben ist ein Betrag, welcher durch möglichst wenige Geldstücke der Grössen { 200, 100, 50, 20, 10, 5, 2, 1 } dargestellt werden werden soll.

a) Geben Sie eine günstige Kodierung für die Geldstücke an

b) Geben Sie eine Zielfunktion und eine Optimierungsrichtung (max/min) an.

c) Geben Sie ein Greedy-Verfahren zur Lösung des Optimierungsproblems an (als Pseudocode oder verbal).

Diese Aufgabe war auch als Hausaufgabe im WS 06/07 im 7. Übungsblatt Aufgabe 7.6 als 'Theorie' zu lösen

Siehe auch

Informatik 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2007