Folien - Grundbegriffe der Informatik

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

Download Report