Ubung “Grundbegriffe der Informatik”

Karlsruher Institut fur Technologie

Matthias Schulz, Gebaude 50.34, Raum 034

email: schulz@ira.uka.de

1

Huffman-Codierung

Artikel im ...

• Deutschen: der, die, das

.

2

Huffman-Codierung

Artikel im ...

• Deutschen: der, die, das

• Englischen: the

.

3

Huffman-Codierung

Artikel im ...

• Deutschen: der, die, das

• Englischen: the

• Franzosischen: le, la

.

4

Huffman-Codierung

Artikel im ...

• Deutschen: der, die, das

• Englischen: the

• Franzosischen: le, la

• Schwedischen: fattningsformaga

5

Huffman-Codierung

Artikel im ...

• Deutschen: der, die, das

• Englischen: the

• Franzosischen: le, la

• Schwedischen: fattningsformaga

Plausibel?

6

Huffman-Codierung

Artikel im ...

• Deutschen: der, die, das

• Englischen: the

• Franzosischen: le, la

• Schwedischen: fattningsformaga

→ Haufig gebrauchte Worter im Allgemeinen kurz!

7

Huffman-Codierung

w = aabaacabaacaabaaacacaabbaccabbaaaabbaccaaa

aaaabaacaabbabbacaabaacaaccaaaaaaaccaaaaaaaccacc

.

8

Huffman-Codierung

w = aabaacabaacaabaaacacaabbaccabbaaaabbaccaaa

aaaabaacaabbabbacaabaacaaccaaaaaaaccaaaaaaaccacc

• Schritt 1: Wort in Blocke unterteilen (hier: Lange 3):

aab aac aba aca aba aac aca abb acc abb aaa abb acc aaa aaa aba

aca abb abb aca aba aca acc aaa aaa acc aaa aaa acc acc

.

9

Huffman-Codierung

w = aabaacabaacaabaaacacaabbaccabbaaaabbaccaaa

aaaabaacaabbabbacaabaacaaccaaaaaaaccaaaaaaaccacc

• Schritt 1: Wort in Blocke unterteilen (hier: Lange 3):

aab aac aba aca aba aac aca abb acc abb aaa abb acc aaa aaa aba

aca abb abb aca aba aca acc aaa aaa acc aaa aaa acc acc

• Schritt 2: Vorkommen zahlen:

aab− 1, aac− 2, aba− 4, aca− 5, abb− 5, acc− 6, aaa− 7

.

10

Huffman-Codierung

w = aabaacabaacaabaaacacaabbaccabbaaaabbaccaaa

aaaabaacaabbabbacaabaacaaccaaaaaaaccaaaaaaaccacc

• Schritt 1: Wort in Blocke unterteilen (hier: Lange 3):

aab aac aba aca aba aac aca abb acc abb aaa abb acc aaa aaa aba

aca abb abb aca aba aca acc aaa aaa acc aaa aaa acc acc

• Schritt 2: Vorkommen zahlen:

aab− 1, aac− 2, aba− 4, aca− 5, abb− 5, acc− 6, aaa− 7

• Schritt 3: Baum erstellen.

11

Huffman-Codierung

w = aabaacabaacaabaaacacaabbaccabbaaaabbaccaaa

aaaabaacaabbabbacaabaacaaccaaaaaaaccaaaaaaaccacc

• Schritt 4: Codierung der einzelnen Blocke ablesen:

aab− 0000, aac− 0001, aba− 001, aca− 100,

abb− 101, acc− 01, aaa− 11

.

12

Huffman-Codierung

w = aabaacabaacaabaaacacaabbaccabbaaaabbaccaaa

aaaabaacaabbabbacaabaacaaccaaaaaaaccaaaaaaaccacc

• Schritt 4: Codierung der einzelnen Blocke ablesen:

aab− 0000, aac− 0001, aba− 001, aca− 100,

abb− 101, acc− 01, aaa− 11

• Schritt 5: Ubersetzen:

c(w) = 00000001001100001000110010101101111010111

110011001011011000011000111110111110101

.

13

aab,1 aac,2

aba,4

acc,6

aca,5 abb,5

aaa,7

14

aab,1 aac,2

aba,4

acc,6

aca,5 abb,5

aaa,7

3

15

aab,1 aac,2

aba,4

acc,6

aca,5 abb,5

aaa,7

3

7

16

aab,1 aac,2

aba,4

acc,6

aca,5 abb,5

aaa,7

3

7 10

17

aab,1 aac,2

aba,4

acc,6

aca,5 abb,5

aaa,7

3

7 10

13

18

aab,1 aac,2

aba,4

acc,6

aca,5 abb,5

aaa,7

3

7 10

13 17

19

aab,1 aac,2

aba,4

acc,6

aca,5 abb,5

aaa,7

3

7 10

13 17

30

20

aab,1 aac,2

aba,4

acc,6

aca,5 abb,5

aaa,7

3

0 1

7

0 1

10

0 1

13

0 1

17

0 1

30

0 1

21

Graphen

Gesucht: Moglichst viele gerichtete Baume mit 4 Knoten,

von denen keine zwei isomorph sind.

.

22

Graphen

Gesucht: Moglichst viele gerichtete Baume mit 4 Knoten,

von denen keine zwei isomorph sind.

Also: Knotenbeschriftungen weglassen!

.

23

Graphen

Gesucht: Moglichst viele gerichtete Baume mit 4 Knoten,

von denen keine zwei isomorph sind.

Beispiel fur isomorphe Graphen:

24

Graphen

Gesucht: Moglichst viele gerichtete Baume mit 4 Knoten,

von denen keine zwei isomorph sind.

Uberlegung: Betrachte erstmal alle ungerichteten Baume

mit vier Knoten.

.

25

Graphen

Gesucht: Moglichst viele gerichtete Baume mit 4 Knoten,

von denen keine zwei isomorph sind.

Uberlegung: Betrachte erstmal alle ungerichteten Baume

mit vier Knoten.

26

Graphen

Gesucht: Moglichst viele gerichtete Baume mit 4 Knoten,

von denen keine zwei isomorph sind.

Uberlegung: Welche Knoten sind “gleichwertig”?

27

Graphen

Gesucht: Moglichst viele gerichtete Baume mit 4 Knoten,

von denen keine zwei isomorph sind.

Uberlegung: Welche Knoten sind “gleichwertig”?

1 2 2 1

3 4 3

3

28

Graphen

Gesucht: Moglichst viele gerichtete Baume mit 4 Knoten,

von denen keine zwei isomorph sind.

Pro gleichwertigen Knoten v: Ein Baum mit Wurzel v.

1 2 2 1

3 4 3

3

29

Graphen

Gesucht: Moglichst viele gerichtete Baume mit 4 Knoten,

von denen keine zwei isomorph sind.

Pro gleichwertigen Knoten v: Ein Baum mit Wurzel v.

30

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeichne G6, G8, G9.

.

31

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeichne G6, G8, G9.

Schritt 1: Knoten halbwegs ubersichtlich anordnen.

.

32

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeichne G6, G8, G9.

Schritt 1: Knoten halbwegs ubersichtlich anordnen.

→ Guter Start: (Halbwegs) Regelmaßiges |V |-Eck.

.

33

G6:

0

1 2

3

45

34

G8:

0

1 2

3

4

56

7

35

G9:

0

1

23

4

5

67

8

36

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeichne G6, G8, G9.

Schritt 2: Wahle Knoten x fest. Suche alle y mit {x, y} ∈ E.

.

37

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeichne G6, G8, G9.

Schritt 2: Wahle Knoten x fest. Suche alle y mit {x, y} ∈ E.

Beispiel: G6, x = 0, y ∈ {1,5}

.

38

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeichne G6, G8, G9.

Schritt 2: Wahle Knoten x fest. Suche alle y mit {x, y} ∈ E.

Beispiel: G8, x = 2, y ∈ {1,3,5,7}

.

39

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeichne G6, G8, G9.

Schritt 2: Wahle Knoten x fest. Suche alle y mit {x, y} ∈ E.

Beispiel: G9, x = 5, y ∈ {0,1,3,4,6,7}

.

40

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeichne G6, G8, G9.

Schritt 3: Verbinde x mit allen y, fur die {x, y} ∈ E gilt.

.

41

G6:

0

1 2

3

45

42

G8:

0

1 2

3

4

56

7

43

G9:

0

1

23

4

5

67

8

44

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeichne G6, G8, G9.

Schritt 4: Wiederhole Schritte 2, 3 fur alle Knoten.

.

45

G6:

0

1 2

3

45

46

G8:

0

1 2

3

4

56

7

47

G9:

0

1

23

4

5

67

8

48

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeigen Sie fur alle n ∈ N+ : n ≥ 3 ⇒ Gn ist Teilgraph von

Gn2.

.

49

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeigen Sie fur alle n ∈ N+ : n ≥ 3 ⇒ Gn ist Teilgraph von

Gn2.

Schritt 1: Fur n ≥ 3 gilt n2 ≥ n ⇒ Gn ⊆ Gn2 ⇒ Vn ⊆ Vn2.

.

50

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeigen Sie fur alle n ∈ N+ : n ≥ 3 ⇒ Gn ist Teilgraph von

Gn2.

Schritt 2: En ⊆ En2:

Sei {x, y} ∈ En ⇒ ggt(|x− y|, n) = 1.

.

51

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeigen Sie fur alle n ∈ N+ : n ≥ 3 ⇒ Gn ist Teilgraph von

Gn2.

Schritt 2: En ⊆ En2:

Sei {x, y} ∈ En ⇒ ggt(|x− y|, n) = 1.

Sei g = ggt(|x− y|, n2). Angenommen, g 6= 1.

.

52

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeigen Sie fur alle n ∈ N+ : n ≥ 3 ⇒ Gn ist Teilgraph von

Gn2.

Schritt 2: En ⊆ En2:

Sei {x, y} ∈ En ⇒ ggt(|x− y|, n) = 1.

Sei g = ggt(|x− y|, n2). Angenommen, g 6= 1.

Sei p eine Primzahl, die g teilt.

53

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeigen Sie fur alle n ∈ N+ : n ≥ 3 ⇒ Gn ist Teilgraph von

Gn2.

Schritt 2: En ⊆ En2:

Sei {x, y} ∈ En ⇒ ggt(|x− y|, n) = 1.

Sei g = ggt(|x− y|, n2). Angenommen, g 6= 1.

Sei p eine Primzahl, die g teilt. Dann teilt p |x− y| und n2.

54

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeigen Sie fur alle n ∈ N+ : n ≥ 3 ⇒ Gn ist Teilgraph von

Gn2.

Schritt 2: En ⊆ En2:

Sei {x, y} ∈ En ⇒ ggt(|x− y|, n) = 1.

Sei g = ggt(|x− y|, n2). Angenommen, g 6= 1.

Sei p eine Primzahl, die g teilt. Dann teilt p |x− y| und n2.

Dann teilt p |x− y| und n ⇒ ggt(|x− y|, n) ≥ p 6= 1.

55

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeigen Sie fur alle n ∈ N+ : n ≥ 3 ⇒ Gn ist Teilgraph von

Gn2.

Schritt 2: En ⊆ En2:

Sei {x, y} ∈ En ⇒ ggt(|x− y|, n) = 1.

Sei g = ggt(|x− y|, n2). Angenommen, g 6= 1.

Dies fuhrt zu einem Widerspruch, und es folgt ggt(|x −y|, n2) = 1

56

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeigen Sie fur alle n ∈ N+ : n ≥ 3 ⇒ Gn ist Teilgraph von

Gn2.

Schritt 2: En ⊆ En2:

Sei {x, y} ∈ En ⇒ ggt(|x− y|, n) = 1.

Es folgt ggt(|x− y|, n2) = 1 und damit {x, y} ∈ En2.

57

Graphen

Gn = (Vn, En)

Vn = Gn

En = {{x, y} | ggt(|x− y|, n) = 1}

Zeigen Sie fur alle n ∈ N+ : n ≥ 3 ⇒ Gn ist Teilgraph von

Gn2.

Schritt 2: En ⊆ En2:

Sei {x, y} ∈ En ⇒ ggt(|x− y|, n) = 1.

Es folgt ggt(|x− y|, n2) = 1 und damit {x, y} ∈ En2.

Daraus folgt die Behauptung.

58

Nachtrag

Braucht man so etwa wie F : BA × A → BA in der Praxis?

.

59

Nachtrag

Braucht man so etwa wie F : BA × A → BA in der Praxis?

Beispiel: Integral!

.

60

Nachtrag

Braucht man so etwa wie F : BA × A → BA in der Praxis?

Beispiel: Integral!

F : RR × R → RR

(f, a) 7→ (x 7→∫ xa f(u) du) oder

∀f ∈ RR∀a ∈ R∀x ∈ R : (F(f, a))(x) =∫ xa f(u) du

.

61

Aufgabe 4.3

(S ⇒∗ w) ⇒ NS(w) +Na(w) > Nb(w)

.

62

Aufgabe 4.3

∀i ∈ N0 : (S ⇒i w) ⇒ NS(w) +Na(w) > Nb(w)

Induktionsanfang: i = 0: Klar.

.

63

Aufgabe 4.3

∀i ∈ N0 : (S ⇒i w) ⇒ NS(w) +Na(w) > Nb(w)

Induktionsvoraussetzung: (S ⇒i w) ⇒ NS(w) + Na(w) >

Nb(w).

.

64

Aufgabe 4.3

∀i ∈ N0 : (S ⇒i w) ⇒ NS(w) +Na(w) > Nb(w)

Induktionsschluss: (S ⇒i+1 w′) ⇒ NS(w) +Na(w) > Nb(w):

(S ⇒i+1 w′) ⇒ S ⇒i w ⇒ w′

⇒ ∃w1, w2 ∈ {a, b, S}∗ : w = w1Sw2∧w′ ∈ {w1aw2, w1aSbw2, w1aSw2}.

Fur jeden Fall mit IV Behauptung zeigen.

.

65