WS 2002/2003                   Übung 13                          H. Schweppe
                                        

        Ausgabe: 24.1.12. 2002
        Abgabe:   4. 2. 2003  15.00

        Letztes bewertetes Übungsblatt:

Aufgabe 13.1 ( 8 P)

Zeigen Sie:
b) (2 P) Das maximale Element in einem Heap ist ein Blatt.
c) ( 2 P) Ein Heap mit n Elementen besitzt én/2ù Blätter (Hinweis: Induktion).

d)  (2 P) Schreiben Sie eine Methode Comparable getMax(), die den maximalen Wert in einem MinHeap (kleinstes Element in der Wurzel) bestimmt, und dabei eine möglichst kleine Anzahl von Vergleichen macht.
Die Klasse heap sei wie folgt definiert:

public class BinaryHeap {
Comparable[] arrayBT;        // Feldrepräsentation eines Heap
 protected int count;            //number of nodes
 protected int size;

          ...
Comparable getMax(){ ...}
}
e) (2 P) Suchmaschinen gewichten gefundene Dokumente nach Relevanz. Die   k  Dokumente mit größtem Gewicht sollen sortiert  ausgegeben werden. Im allgemeinen ist die Gesamtzahl gefundener Dokumente N sehr groß im Vergleich zu k (N >> k).
Gesucht ist ein Verfahren, das die k Dokumente mit größtem Gewicht in O(N*log(k)) Schritten  ermittelt (Pseudocode).  Verwenden Sie einen Heap.

Aufgabe 13.2 (  6 P)

a) In welchen Fällen würden Sie eine Adjazenzliste (Adjazenzmatrix) zur Repräsentation eines Graphen nehmen (Bitte begründen):
1. Der Graph hat ca. 10³ Knoten und 2*10³ Kanten, es soll möglichst wenig Platz verbraucht werden.
2. 10⁴ Knoten, 20⁶ Kanten, geringer Platzbedarf gefordert.
3. Es soll möglichst schnell ermittelt werden, ob Knoten a adjazent zu Knoten b ist. Der Platzbedarf spielt keine Rolle.

Aufgabe 13.3 (  8 P)

a) (4 P) Welchen Graph-Algorithmus würden Sie für die folgenden Aufgaben wählen: Tiefensuche oder Breitensuche (bzw. keine Präferenz). Der Graph ist ungerichtet und zusammenhängend.  Begründen Sie Ihre Wahl.
(i)      Test auf Zyklen
(ii)     Finden eines Knotens, von dem bekannt ist, dass er in der Nähe des Startknotens liegt.
(iii)    Finden der Zusammenhangskomponenten des Graphen.

b) (4 P) ein Graph heißt 3-zusammenhängend, wenn man mindestens 3 Knoten entfernen muss, damit der verbleibende Graph nicht zusammenhängend ist. Konstruieren Sie für die folgenden Fälle 3-zusammenhängende Graphen oder begründen Sie, warum es keinen gibt:
    (i)     5 Knoten, 8 Kanten
    (ii)    5 Knoten, 6 Kanten
    (iii)   8 Knoten, 14 Kanten.

Aufgabe 13.4 (  10 P)
a) (5 P) Bestimmen Sie mit dem Dijkstra-Algorithmus alle kürzesten Wege mit Startknoten A.  

Geben Sie in jedem Schritt die bisher gefundenen besten Wege und  deren Länge an.

b) ( 5 P) Prof. S. Tupid hat den Dijkstra-Algorithmus für gerichtete Graphen auf negative Kantengewichte verallgemeinert. Wenn  w das kleinste Kantengewicht ist (w ist negativ), dann addiert er zu jedem ursprünglichen Kantengewicht den (-w+1). Damit sind alle Kantengewichte positiv und der Dijkstra-Algorithmus ist anwendbar.

Geben Sie ein Gegenbeispiel mit möglichst wenigen Knoten und Kanten an und begründen Sie,  warum die Lösung falsch ist.

32 Punkte