Transcript
Grundbegriffe der Informatik Übung
S. Wacker/T. Worsch Karlsruher Institut für Technologie
Wintersemester 2015/2016
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
1 / 17
Welcher Graph hat die Einheitsmatrix als Adjazenzmatrix? 1 0 0 *. 0 1 0 .. .. 0 0 1 .. 0 0 0 , 0 0 0
GBI — Grundbegriffe der Informatik
0 0 0 1 0
0 0 0 0 1
+/ // // // -
Karlsruher Institut für Technologie
2 / 17
Welcher Graph hat die Einheitsmatrix als Adjazenzmatrix? 1 0 0 *. 0 1 0 .. .. 0 0 1 .. 0 0 0 , 0 0 0
0 0 0 1 0
0 0 0 0 1
+/ // // //
0 1
2 3 4
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
2 / 17
Wie verändert sich die Adjazenzmatrix, wenn man alle Pfeilrichtingen umkehrt?
0 3
1 4
2
0 1 1 *. .. 0 0 1 .. 0 0 0 .. 0 0 0 , 0 0 0
1 1 1 0 0
1 1 1 1 0
+/ // // // -
0 3
1 4
GBI — Grundbegriffe der Informatik
2 Karlsruher Institut für Technologie
3 / 17
Wie verändert sich die Adjazenzmatrix, wenn man alle Pfeilrichtingen umkehrt? Spiegelung an Hauptdiagonale
0 3
1 4
2 0
3
1 4
GBI — Grundbegriffe der Informatik
2
0 1 1 *. .. 0 0 1 .. 0 0 0 .. 0 0 0 , 0 0 0
1 1 1 0 0
0 *. .. 1 .. 1 .. 1 , 1
0 0 0 0 1
0 0 1 1 1
0 0 0 1 1
1 1 1 1 0
+/ // // // -
0 0 0 0 0
+/ // // // -
Karlsruher Institut für Technologie
3 / 17
Wie verändert sich die Adjazenzmatrix, wenn man alle Pfeilrichtingen umkehrt? G = (V , E) vor und G 0 = (V , E 0 ) nach Umkehrung der Pfeile A, A0 Adjazenzmatrizen von G bzw. G 0 Ai,0 j = 1 gdw. (i, j) ∈ E 0 gdw. (j, i) ∈ E gdw. A j,i = 1 A0 = At ... Spiegeln an Hauptdiagonale!
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
4 / 17
Wie ändert sich die Adjazenzmatrix, wenn für jede gerichtete Kante die entgegengesetzte hinzukommt?
0 3
1 4
2
0 1 1 *. .. 0 0 1 .. 0 0 0 .. 0 0 0 , 0 0 0
1 1 1 0 0
1 1 1 1 0
+/ // // // -
0 3
1 4
GBI — Grundbegriffe der Informatik
2 Karlsruher Institut für Technologie
5 / 17
Wie ändert sich die Adjazenzmatrix, wenn für jede gerichtete Kante die entgegengesetzte hinzukommt?
0 3
1 4
2 0
3
1 4
GBI — Grundbegriffe der Informatik
2
0 1 1 *. .. 0 0 1 .. 0 0 0 .. 0 0 0 , 0 0 0
1 1 1 0 0
0 *. .. 1 .. 1 .. 1 , 1
1 1 1 0 1
1 0 1 1 1
1 1 0 1 1
1 1 1 1 0
+/ // // // -
1 1 1 1 0
+/ // // // -
Karlsruher Institut für Technologie
5 / 17
Wie ändert sich die Adjazenzmatrix, wenn für jede gerichtete Kante die entgegengesetzte hinzukommt? G = (V , E) vor und G 0 = (V , E 0 ) nach Aktion A, A0 Adjazenzmatrizen von G bzw. G 0 Ai,0 j = 1 gdw. (i, j) ∈ E 0 gdw. (i, j) ∈ E ∨ (j, i) ∈ E gdw. Ai, j = 1 ∨ A j,i = 1
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
6 / 17
Exkurs: Planare Graphen Definition Ein Graph heißt planar, wenn man ihn kreuzungsfrei zeichnen kann.
Definition Für jedes n ∈ N+ ist Kn = (Zn , {{x, y} ∈ 2Zn | x , y}).
0
1
2
3 K4
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
7 / 17
Exkurs: Planare Graphen Definition Ein Graph heißt planar, wenn man ihn kreuzungsfrei zeichnen kann.
Definition Für jedes n ∈ N+ ist Kn = (Zn , {{x, y} ∈ 2Zn | x , y}).
0
1
0
1 3
3
2
2
K4 man sieht: K 4 ist planar GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
7 / 17
Exkurs: Planare Graphen Definition Ein Graph heißt planar, wenn man ihn kreuzungsfrei zeichnen kann.
Definition Für jedes n ∈ N+ ist Kn = (Zn , {{x, y} ∈ 2Zn | x , y}).
0
1
0 3
3
2
0
1 3
1
2
K4 man sieht: K 4 ist planar
4
2
K 5 ist nicht planar GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
7 / 17
Exkurs: Planare Graphen Behauptung K 5 ist nicht planar.
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
8 / 17
Exkurs: Planare Graphen Behauptung K 5 ist nicht planar.
vage „Beweis“-Skizze Zeichne 5 Knoten v4
v3
v0
v1
v2 GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
8 / 17
Exkurs: Planare Graphen Behauptung K 5 ist nicht planar.
vage „Beweis“-Skizze Zeichne 5 Knoten Verbinde v 0 mit allen anderen Knoten
v4
v3
v0
v1
v2 GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
8 / 17
Exkurs: Planare Graphen Behauptung K 5 ist nicht planar.
vage „Beweis“-Skizze Zeichne 5 Knoten Verbinde v 0 mit allen anderen Knoten
v4
Verbinde v 1 mit v 3 v3
v0
v1
v2
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
8 / 17
Exkurs: Planare Graphen Behauptung K 5 ist nicht planar.
vage „Beweis“-Skizze Zeichne 5 Knoten Verbinde v 0 mit allen anderen Knoten
v4
Verbinde v 1 mit v 3 Nun ist keine kreuzungsfreie Kante mehr zwischen v 2 und v 4 möglich
v3
v0
v1
v2
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
8 / 17
Adjazenzmatrizen der Zusammenhangskomponenten
6 4
1
7
2 5
3
*. .. .. .. .. .. .. . ,
0 0 0 1 0 1 0 0
0 0 0 0 1 0 1 1
0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 1 1 0 1 0 0 0
+/ // // // // // // / -
0
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
9 / 17
Adjazenzmatrizen der Zusammenhangskomponenten bei geschickter Knotennummerierung
0 4
1
3
2 5
7
*. .. .. .. .. .. .. . ,
0 1 0 0 0 0 0 0
1 0 0 1 1 0 0 0
0 0 0 1 0 0 0 0
0 1 1 0 1 0 0 0
0 1 0 1 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 0
+/ // // // // // // / -
6
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
9 / 17
Adjazenzmatrizen der Zusammenhangskomponenten bei geschickter Knotennummerierung
0 4
1
3
2 5
7
*. .. .. .. .. .. .. . ,
0 1 0 0 0 0 0 0
1 0 0 1 1 0 0 0
0 0 0 1 0 0 0 0
0 1 1 0 1 0 0 0
0 1 0 1 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 0
+/ // // // // // // / -
6
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
9 / 17
Adjazenzmatrizen der Zusammenhangskomponenten bei geschickter Knotennummerierung
0 4
1
3
2 5
7
6
GBI — Grundbegriffe der Informatik
0 1 0 *. .. 1 0 0 .. 0 0 0 .. 0 1 1 , 0 1 0
0 1 1 0 1
0 1 0 1 0
+/ // // // -
0 1 0 *. + . 1 0 1 // , 0 1 0 Karlsruher Institut für Technologie
9 / 17
Wegematrix eines zusammenhängenden ungerichteten Graphen
0 4
1
3
2
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
10 / 17
Wegematrix eines zusammenhängenden ungerichteten Graphen
0 4
1
3
1 1 1 *. .. 1 1 1 .. 1 1 1 .. 1 1 1 , 1 1 1
1 1 1 1 1
1 1 1 1 1
+/ // // // -
2
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
10 / 17
Wegematrix eines unzusammenhängenden ungerichteten Graphen, geschickte Nummerierung
0 4
1
3
2
5
6
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
11 / 17
Wegematrix eines unzusammenhängenden ungerichteten Graphen, geschickte Nummerierung
0 4
1
3
2
5
6
GBI — Grundbegriffe der Informatik
*. .. .. .. .. .. . ,
1 1 1 1 1 0 0
1 1 1 1 1 0 0
1 1 1 1 1 0 0
1 1 1 1 1 0 0
1 1 1 1 1 0 0
0 0 0 0 0 1 1
0 0 0 0 0 1 1
+/ // // // // // / -
Karlsruher Institut für Technologie
11 / 17
Wegematrix eines unzusammenhängenden ungerichteten Graphen, geschickte Nummerierung
0 4
1
3
2
5
6
GBI — Grundbegriffe der Informatik
*. .. .. .. .. .. . ,
1 1 1 1 1 0 0
1 1 1 1 1 0 0
1 1 1 1 1 0 0
1 1 1 1 1 0 0
1 1 1 1 1 0 0
0 0 0 0 0 1 1
0 0 0 0 0 1 1
+/ // // // // // / -
geschickt nummeriert: alle Knoten einer Zusammenhangskomponente haben aufeinanderfolgende Nummern Karlsruher Institut für Technologie
11 / 17
Erreichbarkeitsmatrizen 0 4
1
3
2
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
12 / 17
Erreichbarkeitsmatrizen
0 4
1
3
2
1 0 0 *. 0 1 0 .. 0 A = .. 0 0 1 .. 0 0 0 , 0 0 0
0 0 0 1 0
0 0 0 0 1
+/ // // // -
(A0 )i, j , 0 gdw. i = j gdw. (i, j) ∈ E 0
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
12 / 17
Erreichbarkeitsmatrizen
0 4
1
3
2
GBI — Grundbegriffe der Informatik
0 1 0 *. .. 0 0 0 1 A = .. 0 0 0 .. 0 0 0 , 1 0 0
0 1 1 0 0
0 1 0 1 0
+/ // // // -
(A1 )i, j , 0 gdw. (i, j) ∈ E 1
Karlsruher Institut für Technologie
12 / 17
Erreichbarkeitsmatrizen
0 4
1
3
2
0 0 0 *. .. 1 0 0 2 A = .. 0 0 0 .. 1 0 0 , 0 1 0 (A2 )i, j , 0 gdw.
X
1 0 0 0 0
1 1 1 0 0
+/ // // // -
Ai,k Ak, j , 0
k ∈Z5
gdw. ∃k ∈ Z5 : Ai,k Ak, j , 0 gdw. ∃k ∈ Z5 : Ai,k , 0 ∧ Ak, j , 0 gdw. ∃k ∈ Z5 : (i, k ) ∈ E ∧ (k, j) ∈ E gdw. (i, j) ∈ E 2 GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
12 / 17
Erreichbarkeitsmatrizen Für jedes n ∈ N0 gilt (An )i, j , 0 gdw. (i, j) ∈ E n
0 4
1
3
Beweis durch vollständige Induktion
2
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
12 / 17
Wegematrix
A0 + A1 + · · · + A4
0 4
1
3
2
3 2 0 *. . 2 3 0 = ... 1 1 1 .. 1 1 0 , 2 1 0
1 2 1 2 1
2 3 1 2 3
+/ // // // -
Längster wiederholungsfreier Pfad, der kein Zyklus ist, hat Länge 4
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
13 / 17
Wegematrix
A0 + A1 + · · · + A4
0 4
1
3
2
Längster wiederholungsfreier Pfad, der kein Zyklus ist, hat Länge 4
GBI — Grundbegriffe der Informatik
3 2 0 *. . 2 3 0 = ... 1 1 1 .. 1 1 0 , 2 1 0 1 1 0 *. . 1 1 0 W = ... 1 1 1 .. 1 1 0 , 1 1 0
1 2 1 2 1
2 3 1 2 3
+/ // // // -
1 1 1 1 1
1 1 1 1 1
+/ // // // -
Karlsruher Institut für Technologie
13 / 17
Alte Klausuraufgabe Zeichnen Sie alle gerichteten Graphen G = (Z4 , E), für deren Adjazenzmatrix A gilt: 1 0 *. 0 0 A2 = .. . 0 0 , 0 0
GBI — Grundbegriffe der Informatik
0 0 0 0
0 0 0 1
+/ // / -
Karlsruher Institut für Technologie
14 / 17
Alte Klausuraufgabe Zeichnen Sie alle gerichteten Graphen G = (Z4 , E), für deren Adjazenzmatrix A gilt: 1 0 *. 0 0 A2 = .. . 0 0 , 0 0
0
1
2
3
GBI — Grundbegriffe der Informatik
0 0 0 0
0 0 0 1
+/ // / -
Karlsruher Institut für Technologie
14 / 17
Alte Klausuraufgabe Zeichnen Sie alle gerichteten Graphen G = (Z4 , E), für deren Adjazenzmatrix A gilt: 1 0 *. 0 0 A2 = .. . 0 0 , 0 0
0 0 0 0
0 0 0 1
+/ // / -
0
1
0
1
2
3
2
3
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
14 / 17
Alte Klausuraufgabe Zeichnen Sie alle gerichteten Graphen G = (Z4 , E), für deren Adjazenzmatrix A gilt: 1 0 *. 0 0 A2 = .. . 0 0 , 0 0
0 0 0 0
0 0 0 1
+/ // / -
0
1
0
1
2
3
2
3
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
14 / 17
Alte Klausuraufgabe Zeichnen Sie alle gerichteten Graphen G = (Z4 , E), für deren Adjazenzmatrix A gilt: 1 0 *. 0 0 A2 = .. . 0 0 , 0 0
0 0 0 0
0 0 0 1
+/ // / -
0
1
0
1
2
3
2
3
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
14 / 17
Ausführungen zählen (1) Wie oft wird P0 ausgeführt? for i ← 0 to n − 1 do for j ← 0 to n − 1 do P0 od od
n−1 X n−1 X
1
i=0 j=0
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
15 / 17
Ausführungen zählen (1) Wie oft wird P0 ausgeführt? for i ← 0 to n − 1 do for j ← 0 to n − 1 do P0 od od
n−1 X n−1 X
1
i=0 j=0
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
15 / 17
Ausführungen zählen (1) Wie oft wird P0 ausgeführt? for i ← 0 to n − 1 do for j ← 0 to n − 1 do P0 od od
n−1 X n−1 X
1
i=0 j=0
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
15 / 17
Ausführungen zählen (1) Wie oft wird P0 ausgeführt? for i ← 0 to n − 1 do for j ← 0 to n − 1 do P0 od od
n−1 X n−1 X
1
i=0 j=0
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
15 / 17
Ausführungen zählen (1) Wie oft wird P0 ausgeführt? for i ← 0 to n − 1 do for j ← 0 to n − 1 do P0 od od
n−1 X n−1 n−1 X X 1= n i=0 j=0
GBI — Grundbegriffe der Informatik
i=0
Karlsruher Institut für Technologie
15 / 17
Ausführungen zählen (1) Wie oft wird P0 ausgeführt? for i ← 0 to n − 1 do for j ← 0 to n − 1 do P0 od od
n−1 X n−1 n−1 X X 1= n i=0 j=0
i=0
=n ·n
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
15 / 17
Ausführungen zählen (1) Wie oft wird P0 ausgeführt? for i ← 0 to n − 1 do for j ← 0 to n − 1 do P0 od od
n−1 X n−1 n−1 X X 1= n i=0 j=0
i=0
=n ·n = n2 GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
15 / 17
Einschub Wieviel ist 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 ?
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
16 / 17
Einschub Wieviel ist 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 ? Idee des kleinen Gauß: die Hälfte von
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
16 / 17
Einschub Wieviel ist 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 ? Idee des kleinen Gauß: die Hälfte von 0+1+2+3+4+5+6+7+8+9 +9+8+7+6+5+4+3+2+1+0
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
16 / 17
Einschub Wieviel ist 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 ? Idee des kleinen Gauß: die Hälfte von 0+1+2+3+4+5+6+7+8+9 +9+8+7+6+5+4+3+2+1+0 = 9 + 9 + 9 + 9 + 9 + 9 + 9 + 9 + 9 + 9 = 90
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
16 / 17
Einschub Wieviel ist 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 ? Idee des kleinen Gauß: die Hälfte von 0+1+2+3+4+5+6+7+8+9 +9+8+7+6+5+4+3+2+1+0 = 9 + 9 + 9 + 9 + 9 + 9 + 9 + 9 + 9 + 9 = 90 also 45
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
16 / 17
Ausführungen zählen (2) Wie oft wird P0 ausgeführt? for i ← 0 to n − 1 do for j ← 0 to i − 1 do P0 od od
n−1 X i−1 X i=0 j=0
GBI — Grundbegriffe der Informatik
1=
n−1 X
i
i=0
Karlsruher Institut für Technologie
17 / 17
Ausführungen zählen (2) Wie oft wird P0 ausgeführt? for i ← 0 to n − 1 do for j ← 0 to i − 1 do P0 od od
n−1 X i−1 X i=0 j=0
GBI — Grundbegriffe der Informatik
1=
n−1 X i=0
i=
n−1 n−1 X 1 X ( i+ i) 2 i=0 i=0
Karlsruher Institut für Technologie
17 / 17
Ausführungen zählen (2) Wie oft wird P0 ausgeführt? for i ← 0 to n − 1 do for j ← 0 to i − 1 do P0 od od
n−1 X i−1 X i=0 j=0
GBI — Grundbegriffe der Informatik
1=
n−1 X i=0
i=
n−1 n−1 n−1 n−1 X X 1 X 1 X ( i+ i) = ( i + n − 1 − i) 2 i=0 2 i=0 i=0 i=0
Karlsruher Institut für Technologie
17 / 17
Ausführungen zählen (2) Wie oft wird P0 ausgeführt? for i ← 0 to n − 1 do for j ← 0 to i − 1 do P0 od od
n−1 X i−1 X i=0 j=0
1=
n−1 X i=0
i=
n−1 n−1 n−1 n−1 X X 1 X 1 X ( i+ i) = ( i + n − 1 − i) 2 i=0 2 i=0 i=0 i=0
n−1 1 X = ( i + (n − 1 − i)) 2 i=0 GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
17 / 17
Ausführungen zählen (2) Wie oft wird P0 ausgeführt? for i ← 0 to n − 1 do for j ← 0 to i − 1 do P0 od od
n−1 X i−1 X i=0 j=0
1=
n−1 X i=0
i=
n−1 n−1 n−1 n−1 X X 1 X 1 X ( i+ i) = ( i + n − 1 − i) 2 i=0 2 i=0 i=0 i=0
n−1 n−1 1 X 1X = ( i + (n − 1 − i)) = n−1 2 i=0 2 i=0 GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
17 / 17
Ausführungen zählen (2) Wie oft wird P0 ausgeführt? for i ← 0 to n − 1 do for j ← 0 to i − 1 do P0 od od
n−1 X i−1 X i=0 j=0
1=
n−1 X i=0
i=
n−1 n−1 n−1 n−1 X X 1 X 1 X ( i+ i) = ( i + n − 1 − i) 2 i=0 2 i=0 i=0 i=0
n−1 n−1 1 X 1X 1 = ( i + (n − 1 − i)) = n − 1 = n(n − 1) 2 i=0 2 i=0 2 GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
17 / 17
