View
118
Download
4
Category
Preview:
Citation preview
1
Klausur „Diskrete Mathematik II“
Musterlösung zu den Vorbereitungsaufgaben
2
Aufgabe 1: Umkehren einer Liste (Pseudocode auf hohem Niveau)Eingabe: Eine einfach verkettete Liste
Ausgabe: Eine einfach verkettete Liste, die die Elemente er Eingabeliste in umgekehrter Reihenfolge enthält
Programm:
Durchlaufe die Eingabeliste beginnend mit dem Kopf. Jedes Element wird kopiert, und die Kopie wird jeweils vorne (d.h. an der Kopfseite) in eine neue Liste eingehängt. Der Kopf der neuen Liste ist das zuletzt eingehängte Element.
3
Aufgabe 1: Umkehren einer Liste (Alternative, eher an Java angelehnt)
// Die folgende Lösung verwendet die Klasse "Element" aus der // Vorlesung. Die Lösung mit "Element" und "Liste" ist analog.
Element Kopf = ...; //Kopf der zu invertierenden Liste
Element aktuell = Kopf;
Element neuerKopf = NULL; //Kopf der invertierten Liste
while( aktuell != NULL )
{
Element Neu = new Element(aktuell.Wert); //Erzeugen einer Kopie
Neu.Weiter = neuerKopf;
neuerKopf = Neu;
aktuell = aktuell.Weiter;
}
4
Aufgabe 2: Multiplikation einer Matrix mit einem Vektor
int n = ...; //Länge des Vektors bzw. Anzahl der Spalten
int m = ...; // Anzahl der Zeilen
double [ ] vek = new double[n]; // vek ist der Vektor
double [ ][ ] mat = new double[m,n]; // mat ist die Matrix
double [] ergebnis = new double [m] ; //Produkt von vek und mat
ergebnis = {0,0,0...} //Initialisierung mit 0
vek = ...; mat = ...; // Belegung von vek und mat
for ( int i = 1 ; i <= m ; i++ )
for ( int j = 1 ; j <= n ; j++ )
{
ergebnis[i] = ergebnis[i] + mat[i,j] * vek[j];
}
5
Aufgabe 3: Umgekehrte Polnische Notation
Prozedur zur Erzeugung der Umgekehrten Polnischen Notation aus einem Syntaxbaum:
upn() { upn(wurzel); }
upn(Knoten W) {
if(W = NULL) return;
print(W);print("(");
upn(W.LinkerNachfolger);
print(",");
upn(W.RechterNachfolger);
print(")");
}
Bemerkung: Die Prozedur "upn()" ist fast identisch zu der Prozedur "PreOrder()" (Mathe 8, 1. Semester). Dort fehlen nur die Befehle zur Ausgabe der Klammern und des Komma (print("("); print(","); print(")")).
6
Aufgabe 4.1: Algorithmus zum Entfernen eines Knotens aus einem binären Suchbaum:Durchsuche den Baum solange, bis der zu löschende Knoten gefunden ist (z.B. mit Breiten- oder Tiefensuche); dieser sei L; merke Dir den Zeiger auf L vom Vorgänger im Baum; dieser sei zL
• falls L keine Nachfolger hat, lösche L, setzt zL auf Null und beende die Prozedur
andernfalls suche den Ersatzknoten E für L wie folgt:
• falls L einen linken Nachfolger hat, gehe einmal nach links und dann solange nach rechts, wie rechte Nachfolger vorhanden sind. Der gefundene Knoten sei E.
• falls L keinen linken Nachfolger hat, gehe einmal nach rechts und dann solange nach links, wie linke Nachfolger vorhanden sind. Der gefundene Knoten sei E.
ersetze L durch E: dazu wird zL auf E gesetzt, und der linke und rechte Nachfolgen von L wird dem linken und rechten Nachfolger von E zugewiesen;
lösche L und ersetze das alte Vorkommen von E durch den linken/rechten Nachfolger F von E
7
Aufgabe 4.1: Beispiel: Löschen des Knotens mit Nr. 84 (dient nur zur Veranschaulichung, gehört nicht zur Musterlösung)
5716
8444
65
67 99
70 90
888 34 55 60
804 50 56
75
96
7774
L
E
zL
73
72
F
8
Aufgabe 4.1: Beispiel: Löschen des Knotens mit Nr. 84 (dient nur zur Veranschaulichung, gehört nicht zur Musterlösung)
5716
8044
65
67 99
70 90
888 34 55 60
4 50 56 75 96
7774
EzL
73
72 F
9
Aufgabe 4.1 (Fortsetzung): Der schwierige Fall im Algorithmus ist der, dass der zu löschende Knoten L Nachfolger hat, d.h. kein Blatt ist.
Aufgabe 4.2: Korrektheit des Algorithmus
Gezeigt werden muss, dass das Ergebnis wieder ein binärer Suchbaum ist. Dazu muss gezeigt werden, dass die Ersetzung von L durch E und von E durch F die Suchbaumeingenschaft nicht zerstört
• Ersetzung von L durch E: E muss der größte (kleinste) Knoten im linken (rechten) Teilbaum unter L sein: Man betrachtet den Pfad, der von E zu L führt. Alle Knoten auf diesem Pfad sind kleiner als E (da E links von diesen Knoten liegt), und alle linken Teilbäume dieser Knoten sind ebenfalls kleiner als E. Folglich ist E der größte Knoten im linken Teilbaum unter L. Der Beweis, dass E der kleinste Knoten im rechten Teilbaum unter L ist, verläuft analog.
• Ersetzung von E durch F: Wenn E rechter (linker) Nachfolger eines Knotens K ist, d.h. E > K (E < K), dann ist auch jeder Knoten des Teilbaumes unter E größer (kleiner) als K.
10
D
E
A
B
C
30
10
1040
Aufgabe 5: Anwendung des Algorithmus von Dijkstra
90
2040
100
11
D
E
A
B
C
30
10
1040
Schritt 1
90
2040
100
30
100
90
Grüner Knoten mit minimalen Kosten ist E (30)
12
D
E
A
B
C
30
10
1040
Schritt 2
90
2040
100
30
70
90
40Grüner Knoten mit minimalen Kosten ist D (40)
30 + 40 = 70 < 100AEC statt AC
13
D
E
A
B
C
30
10
1040
Schritt 3
90
2040
100
30
70
50
40Grüner Knoten mit minimalen Kosten ist B (50)
30 + 10 + 10 = 50 < 90AEDB statt AB
14
D
E
A
B
C
30
10
1040
Schritt 4
90
2040
100
30
70
50
40Grüner Knoten mit minimalen Kosten ist C (70)
30 + 40 = 70 < 30 + 10 + 10 = 70AEC bleibt (statt AEDB)
15
D
E
A
B
C
30
10
1040
Schritt 5
90
2040
100
30
70
50
40
16
D
E
A
B
C
30
10
1040
Alternative Lösung
90
2040
100
30
70
50
40
17
Aktuell bearb. Liste der grünen KnotenKnoten
(A,0)
(A,0) (E,30), (C,100), (B,90)
(E,30) (D,40), (C,70), (B,90)
(D,40) (C,70), (B,50)
(B,50) (C,70)
(C,70)
So könnte die Lösung auch aussehen:
18
Aufgabe 6: Dijkstra: Unterscheidung Entfernung und Fahrzeit
• Beides sind Kosten
• Zwei Attribute an Kanten; Dijkstra muss wissen, welches verwendet werden soll
19
Aufgabe 7.1: Heap7
22 9
23 27 11 30
90 28 33 80 19 70
7 22 9 23 27 11 30 90 28 33 80 19 70
20
Aufgabe 7.2:7
22 9
23 27 11 30
90 28 33 80 19 70
7 22 9 23 27 11 30 90 28 33 80 19 70
8
8
21
Aufgabe 7.2:7
22 9
23 27 11 8
90 28 33 80 19 70
7 22 9 23 27 11 8 90 28 33 80 19 70
30
30
22
Aufgabe 7.2:7
22 8
23 27 11 9
90 28 33 80 19 70
7 22 8 23 27 11 9 90 28 33 80 19 70
30
30
23
Aufgabe 7.3: Wie gut ist Array-Repräsentation auch für AVL-Bäume geeignet?
Nicht gut.
• Lücken in Array (AVL-Baum nicht ausgeglichen)
• Einfügen/Löschen von Knoten erfordert Rotationen: Fast jedes Arrayelement muss verschoben werden: O(n)=> Beispiel L-Rotation (die folgende Animation ist zur Lösung der Aufgabe nicht erforderlich; sie dient nur der Veranschaulichung)
24
T1
T2 T3
k1
k2
0
+1
L-Rotation
25
T1
T2 T3
k1
k2
x
+1
+2
L-Rotation: Einfügen von x
26
L-Rotation
T1
T2 T3
k1
k2
x
+1
+2
27
T1
T2 T3
k1
k2
x
+1
+2
L-Rotation
28
T1
k1
k2
x
0
T2
T3
0
L-Rotation
29
T1
k1
k2
x
0
T2
T3
0
L-Rotation
Position jedes Arrayelementsverändert
30
Aufgabe 8: Zusammenhang eines Graphen4 Alternative Lösungen: • Tiefensuche: Graph zusammenhängend, wenn alle Knoten durchlaufen werden• Breitensuche (wie Tiefensuche)• Dijkstra (beliebige Kosten > 0, wie Tiefensuche)• Floyd (beliebige Kosten > 0), Graph zusammenhängend, wenn kein in Matrix
Ein Problem ergibt sich daraus, dass die Definition "zusammenhängend" in der Aufgabenstellung von ungerichteten Graphen ausgeht, die vier Verfahren jedoch von gerichteten. Der unten gezeigte gerichtete Graph ist zusammenhängend; mit Startknoten B würde jedoch Dijkstra niemals A erreichen. Eine Lösung dieses Problems besteht darin, bei gerichteten Graphen zu jeder Kante eine Kante mit entgegengesetzter Orientierung zu ergänzen. Ungerichtete Kanten müssen durch zwei gerichtete Kanten mit entgegengesetzter Orientierung ersetzt werden.
A B
31
D ADC
ADBC
ACD
AC
CA
ADC
D
B
C
A
ADC
Aufgabe 9: Anwendung von Scan-Line
Schnittpunkterkannt
Schnittpunkterkannt (bereits
vorhanden)
Schnittpunkterkannt
Recommended