Folien - Grundbegriffe der Informatik

Grundbegriffe der Informatik
Übung
Simon Wacker
Karlsruher Institut für Technologie
Wintersemester 2015/2016
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
1 / 19
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
2 / 19
Block-Codierung
aabaacabaacaabaaacacaabbaccabb
aaaabbaccaaaaaaabaacaabbabbaca
abaacaaccaaaaaaaccaaaaaaaccacc
Schritt 1: Wort in Blöcke unterteilen (hier: Länge 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 zählen
aab
aac
aba
aca
abb
acc
aaa
1
2
4
5
5
6
7
Schritt 3: Baum erstellen
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
3 / 19
acc, 6
aba, 4
aab, 1
aaa, 7
aca, 5
abb, 5
aac, 2
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
4 / 19
acc, 6
aba, 4
3
aab, 1
aaa, 7
aca, 5
abb, 5
aac, 2
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
5 / 19
7
aba, 4
3
aab, 1
acc, 6
aaa, 7
aca, 5
abb, 5
aac, 2
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
6 / 19
7
aba, 4
3
aab, 1
acc, 6
10
aca, 5
aaa, 7
abb, 5
aac, 2
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
7 / 19
13
7
aba, 4
3
aab, 1
acc, 6
10
aca, 5
aaa, 7
abb, 5
aac, 2
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
8 / 19
13
7
acc, 6
aba, 4
3
aab, 1
17
10
aca, 5
aaa, 7
abb, 5
aac, 2
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
9 / 19
30
13
7
acc, 6
aba, 4
3
aab, 1
17
10
aca, 5
aaa, 7
abb, 5
aac, 2
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
10 / 19
30
0
0
7
0
0 3 1
aab, 1
13
1
1
1
17 1
0
acc, 6
aba, 4
0 10 1
aca, 5
aaa, 7
abb, 5
aac, 2
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
11 / 19
Block-Codierung
Schritt 4: Codierung der einzelnen Blöcke ablesen
aab
aac
aba
aca
abb
acc
aaa
0000
0001
001
100
101
01
11
Schritt 5: Wort codieren
00000001001100001000110010101101
11101011111001100101101100
0011000111110111110101
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
12 / 19
Homomorphismen — Das allgemeine Konzept
V , W Mengen
⊙ : V × V → V , ⊕ : W × W → W binäre Operationen
Abbildung φ : V → W heißt Homomorphismus bezüglich ⊙
und ⊕ genau dann, wenn für jedes u ∈ V und jedes v ∈ V
gilt:
φ(u ⊙ v) = φ(u) ⊕ φ(v)
Homomorphismen sind strukturerhaltende oder
strukturverträgliche Abbildungen
Altgriechisch: “homós” (- gleich) und “morphé” (- Form)
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
13 / 19
Homomorphismen — In dieser Vorlesung
A, B Alphabete
Abbildung h : A∗ → B ∗ heißt Homomorphismus genau dann,
wenn für jedes u ∈ A∗ und jedes v ∈ A∗ gilt:
h(u · v) = h(u) · h(v)
Homomorphismus bezüglich Konkatenation auf A∗ und B ∗
Für jedes n ∈ N0 und jedes w ∈ An gilt:
h(w ) = h(w 0w 1 . . . w n−1 ) = h(w 0 )h(w 1 ) . . . h(w n−1 ),
wobei w i = w (i) für jedes i ∈ Zn
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
14 / 19
Von ternärer zur binärer Darstellung
Frage: Existiert ein Homomorphismus h : Z 3∗ → Z 2∗ derart,
dass gilt:
Für jedes w ∈ Z 3∗ gilt Num2 (h(w )) = Num3 (w ).
(∗)
Antwort: Nein!
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
15 / 19
Von ternärer zur binärer Darstellung
Frage: Existiert ein Homomorphismus h : Z 3∗ → Z 2∗ derart,
dass gilt:
Für jedes w ∈ Z 3∗ gilt Num2 (h(w )) = Num3 (w ).
(∗)
Antwort: Nein!
Beweis: Es sei h eine Abbildung, für die (∗) gilt.
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
15 / 19
Von ternärer zur binärer Darstellung
Frage: Existiert ein Homomorphismus h : Z 3∗ → Z 2∗ derart,
dass gilt:
Für jedes w ∈ Z 3∗ gilt Num2 (h(w )) = Num3 (w ).
(∗)
Antwort: Nein!
Beweis: Es sei h eine Abbildung, für die (∗) gilt.
Beispielsweise gilt (∗) für Trans2,3 = Repr2 ◦ Num3 .
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
15 / 19
Von ternärer zur binärer Darstellung
Frage: Existiert ein Homomorphismus h : Z 3∗ → Z 2∗ derart,
dass gilt:
Für jedes w ∈ Z 3∗ gilt Num2 (h(w )) = Num3 (w ).
(∗)
Antwort: Nein!
Beweis: Es sei h eine Abbildung, für die (∗) gilt.
Beispielsweise gilt (∗) für Trans2,3 = Repr2 ◦ Num3 . Wegen
Num2 (h(11)) = Num3 (11) = 4, gilt h(11) ∈ {0}∗ {100}.
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
15 / 19
Von ternärer zur binärer Darstellung
Frage: Existiert ein Homomorphismus h : Z 3∗ → Z 2∗ derart,
dass gilt:
Für jedes w ∈ Z 3∗ gilt Num2 (h(w )) = Num3 (w ).
(∗)
Antwort: Nein!
Beweis: Es sei h eine Abbildung, für die (∗) gilt.
Beispielsweise gilt (∗) für Trans2,3 = Repr2 ◦ Num3 . Wegen
Num2 (h(11)) = Num3 (11) = 4, gilt h(11) ∈ {0}∗ {100}.
Wegen Num2 (h(1)) = Num3 (1) = 1, gilt h(1) ∈ {0}∗ {1},
also h(1)h(1) ∈ {0}∗ {1}{0}∗ {1}.
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
15 / 19
Von ternärer zur binärer Darstellung
Frage: Existiert ein Homomorphismus h : Z 3∗ → Z 2∗ derart,
dass gilt:
Für jedes w ∈ Z 3∗ gilt Num2 (h(w )) = Num3 (w ).
(∗)
Antwort: Nein!
Beweis: Es sei h eine Abbildung, für die (∗) gilt.
Beispielsweise gilt (∗) für Trans2,3 = Repr2 ◦ Num3 . Wegen
Num2 (h(11)) = Num3 (11) = 4, gilt h(11) ∈ {0}∗ {100}.
Wegen Num2 (h(1)) = Num3 (1) = 1, gilt h(1) ∈ {0}∗ {1},
also h(1)h(1) ∈ {0}∗ {1}{0}∗ {1}. Da
{0}∗ {100} ∩ {0}∗ {1}{0}∗ {1} = ∅, folgt h(11) , h(1)h(1).
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
15 / 19
Von ternärer zur binärer Darstellung
Frage: Existiert ein Homomorphismus h : Z 3∗ → Z 2∗ derart,
dass gilt:
Für jedes w ∈ Z 3∗ gilt Num2 (h(w )) = Num3 (w ).
(∗)
Antwort: Nein!
Beweis: Es sei h eine Abbildung, für die (∗) gilt.
Beispielsweise gilt (∗) für Trans2,3 = Repr2 ◦ Num3 . Wegen
Num2 (h(11)) = Num3 (11) = 4, gilt h(11) ∈ {0}∗ {100}.
Wegen Num2 (h(1)) = Num3 (1) = 1, gilt h(1) ∈ {0}∗ {1},
also h(1)h(1) ∈ {0}∗ {1}{0}∗ {1}. Da
{0}∗ {100} ∩ {0}∗ {1}{0}∗ {1} = ∅, folgt h(11) , h(1)h(1).
Somit ist h kein Homomorphismus!
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
15 / 19
Von hexadezimaler zu binärer Darstellung
Existiert ein bedeutungserhaltender Homomorphismus von
der hexadezimalen in die binäre Darstellung?
∗ → Z ∗ , welcher
Ja, gerade jener Homomorphismus h : Z 16
2
eindeutig festgelegt ist durch:
Für jedes z ∈ Z 16 gilt h(z) = bin4 (num16 (z))
Je vier binäre Ziffern entsprechen einer hexadezimalen
Ziffer:
h(0) = 0000, h(1) = 0001, h(2) = 0010, und so weiter
Das funktioniert so gut, da 24 = 16
Beispiel: h(A · 1) = h(A) · h(1) = 1010 · 0001
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
16 / 19
Bedeutungserhaltung
Beweise durch vollständige Induktion über die Wortlänge:
∗
Für jedes w ∈ Z 16
gilt Num2 (h(w )) = Num16 (w )
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
17 / 19
Bedeutungserhaltung
Beweise durch vollständige Induktion über die Wortlänge:
∗
Für jedes w ∈ Z 16
gilt Num2 (h(w )) = Num16 (w )
Induktionsanfang: Es gilt h(ϵ ) = ϵ. Somit gilt
Num2 (h(ϵ )) = 0 = Num16 (ϵ ).
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
17 / 19
Bedeutungserhaltung
Beweise durch vollständige Induktion über die Wortlänge:
∗
Für jedes w ∈ Z 16
gilt Num2 (h(w )) = Num16 (w )
Induktionsanfang: Es gilt h(ϵ ) = ϵ. Somit gilt
Num2 (h(ϵ )) = 0 = Num16 (ϵ ).
Induktionsschritt: Es sei n ∈ N0 derart, dass gilt:
n
Für jedes u ∈ Z 16
gilt Num2 (h(u)) = Num16 (u).
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
(I.V.)
17 / 19
Bedeutungserhaltung
Beweise durch vollständige Induktion über die Wortlänge:
∗
Für jedes w ∈ Z 16
gilt Num2 (h(w )) = Num16 (w )
Induktionsanfang: Es gilt h(ϵ ) = ϵ. Somit gilt
Num2 (h(ϵ )) = 0 = Num16 (ϵ ).
Induktionsschritt: Es sei n ∈ N0 derart, dass gilt:
n
Für jedes u ∈ Z 16
gilt Num2 (h(u)) = Num16 (u).
(I.V.)
n+1 .
Weiter sei w ∈ Z 16
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
17 / 19
Bedeutungserhaltung
Beweise durch vollständige Induktion über die Wortlänge:
∗
Für jedes w ∈ Z 16
gilt Num2 (h(w )) = Num16 (w )
Induktionsanfang: Es gilt h(ϵ ) = ϵ. Somit gilt
Num2 (h(ϵ )) = 0 = Num16 (ϵ ).
Induktionsschritt: Es sei n ∈ N0 derart, dass gilt:
n
Für jedes u ∈ Z 16
gilt Num2 (h(u)) = Num16 (u).
(I.V.)
n+1 . Es gibt ein u ∈ Z n und ein z ∈ Z so,
Weiter sei w ∈ Z 16
16
16
dass u · z = w.
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
17 / 19
Bedeutungserhaltung
Beweise durch vollständige Induktion über die Wortlänge:
∗
Für jedes w ∈ Z 16
gilt Num2 (h(w )) = Num16 (w )
Induktionsanfang: Es gilt h(ϵ ) = ϵ. Somit gilt
Num2 (h(ϵ )) = 0 = Num16 (ϵ ).
Induktionsschritt: Es sei n ∈ N0 derart, dass gilt:
n
Für jedes u ∈ Z 16
gilt Num2 (h(u)) = Num16 (u).
(I.V.)
n+1 . Es gibt ein u ∈ Z n und ein z ∈ Z so,
Weiter sei w ∈ Z 16
16
16
dass u · z = w. Ferner gibt es a, b, c, d ∈ Z 2 , für welche
h(z) = abcd gilt. Damit gilt
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
17 / 19
Bedeutungserhaltung
Num2 (h(uz))
= Num2 (h(u)h(z))
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
18 / 19
Bedeutungserhaltung
Num2 (h(uz))
= Num2 (h(u)h(z))
= Num2 (h(u)abcd )
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
18 / 19
Bedeutungserhaltung
Num2 (h(uz))
= Num2 (h(u)h(z))
= Num2 (h(u)abcd )
= Num2 (h(u)abc) · 2 + num2 (d )
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
18 / 19
Bedeutungserhaltung
Num2 (h(uz))
= Num2 (h(u)h(z))
= Num2 (h(u)abcd )
= Num2 (h(u)abc) · 2 + num2 (d )
= (Num2 (h(u)ab) · 2 + num2 (c)) · 2 + num2 (d )
= ...
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
18 / 19
Bedeutungserhaltung
Num2 (h(uz))
= Num2 (h(u)h(z))
= Num2 (h(u)abcd )
= Num2 (h(u)abc) · 2 + num2 (d )
= (Num2 (h(u)ab) · 2 + num2 (c)) · 2 + num2 (d )
= ...
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
18 / 19
Bedeutungserhaltung
Num2 (h(uz))
= Num2 (h(u)h(z))
= Num2 (h(u)abcd )
= Num2 (h(u)abc) · 2 + num2 (d )
= (Num2 (h(u)ab) · 2 + num2 (c)) · 2 + num2 (d )
= ...
= Num2 (h(u)) · 16 + num2 (a) · 8 + num2 (b) · 4 + num2 (c) · 2 + num2 (d )
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
18 / 19
Bedeutungserhaltung
Num2 (h(uz))
= Num2 (h(u)h(z))
= Num2 (h(u)abcd )
= Num2 (h(u)abc) · 2 + num2 (d )
= (Num2 (h(u)ab) · 2 + num2 (c)) · 2 + num2 (d )
= ...
= Num2 (h(u)) · 16 + num2 (a) · 8 + num2 (b) · 4 + num2 (c) · 2 + num2 (d )
= Num2 (h(u)) · 16 + ((num2 (a) · 2 + num2 (b)) · 2 + num2 (c)) · 2 + num2 (d )
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
18 / 19
Bedeutungserhaltung
Num2 (h(uz))
= Num2 (h(u)h(z))
= Num2 (h(u)abcd )
= Num2 (h(u)abc) · 2 + num2 (d )
= (Num2 (h(u)ab) · 2 + num2 (c)) · 2 + num2 (d )
= ...
= Num2 (h(u)) · 16 + num2 (a) · 8 + num2 (b) · 4 + num2 (c) · 2 + num2 (d )
= Num2 (h(u)) · 16 + ((num2 (a) · 2 + num2 (b)) · 2 + num2 (c)) · 2 + num2 (d )
= Num2 (h(u)) · 16 + Num2 (abcd )
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
18 / 19
Bedeutungserhaltung
Num2 (h(uz))
= Num2 (h(u)h(z))
= Num2 (h(u)abcd )
= Num2 (h(u)abc) · 2 + num2 (d )
= (Num2 (h(u)ab) · 2 + num2 (c)) · 2 + num2 (d )
= ...
= Num2 (h(u)) · 16 + num2 (a) · 8 + num2 (b) · 4 + num2 (c) · 2 + num2 (d )
= Num2 (h(u)) · 16 + ((num2 (a) · 2 + num2 (b)) · 2 + num2 (c)) · 2 + num2 (d )
= Num2 (h(u)) · 16 + Num2 (abcd )
= Num16 (u) · 16 + Num2 (h(z))
GBI — Grundbegriffe der Informatik
(I.V. und Wahl von abcd)
Karlsruher Institut für Technologie
18 / 19
Bedeutungserhaltung
Num2 (h(uz))
= Num2 (h(u)h(z))
= Num2 (h(u)abcd )
= Num2 (h(u)abc) · 2 + num2 (d )
= (Num2 (h(u)ab) · 2 + num2 (c)) · 2 + num2 (d )
= ...
= Num2 (h(u)) · 16 + num2 (a) · 8 + num2 (b) · 4 + num2 (c) · 2 + num2 (d )
= Num2 (h(u)) · 16 + ((num2 (a) · 2 + num2 (b)) · 2 + num2 (c)) · 2 + num2 (d )
= Num2 (h(u)) · 16 + Num2 (abcd )
= Num16 (u) · 16 + Num2 (h(z))
(I.V. und Wahl von abcd)
= Num16 (u) · 16 + Num16 (z)
(Def. von h)
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
18 / 19
Bedeutungserhaltung
Num2 (h(uz))
= Num2 (h(u)h(z))
= Num2 (h(u)abcd )
= Num2 (h(u)abc) · 2 + num2 (d )
= (Num2 (h(u)ab) · 2 + num2 (c)) · 2 + num2 (d )
= ...
= Num2 (h(u)) · 16 + num2 (a) · 8 + num2 (b) · 4 + num2 (c) · 2 + num2 (d )
= Num2 (h(u)) · 16 + ((num2 (a) · 2 + num2 (b)) · 2 + num2 (c)) · 2 + num2 (d )
= Num2 (h(u)) · 16 + Num2 (abcd )
= Num16 (u) · 16 + Num2 (h(z))
(I.V. und Wahl von abcd)
= Num16 (u) · 16 + Num16 (z)
(Def. von h)
= Num16 (uz)
GBI — Grundbegriffe der Informatik
(Def. von Num16 ).
Karlsruher Institut für Technologie
18 / 19
Trans2,16
Führende Nullen entfernen, aber mindestens eine Ziffer
φ : Z 2∗ → Z 2∗ ,
ϵ 7→ 0,
1·w →
7 1 · w, wobei w ∈ Z 2∗ ,
0·w →
7 φ(w ), wobei w ∈ Z 2∗ .
Es gilt Trans2,16 = φ ◦ h
Trans2,16 (1E5) = φ(h(1E5))
= φ(h(1) · h(E) · h(5))
= φ(bin4 (num16 (1)) · bin4 (num16 (E)) · bin4 (num16 (5)))
= φ(0001 · 1110 · 0101)
= 111100101
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
19 / 19

Download Report