In der zweiten Vorlesung beschäftigen wir uns mit der rekursiven Erzeugung von binären Mengendarstellungen mit Hilfe des Gray Codes.
| Skript-Anfang | manuscript – Seite 11 |
|---|---|
| Skript-Ende | manuscript – Seite 18 |
Gray Code
Einleitung
Wie viele Teilmengen gibt es?
Anzahl der Teilmengen einer n-elementigen Teilmenge: 2n
Beispiel
Teilmenge V = {0,1,2}
n=3
23 = 8 = ∅ {0} {1} {2} {0,1} {0,2} {1,2} {0,1,2}
Wie kann man diese Menge im Rechner repräsentieren?
- Listendarstellung
- Bitfolge (Menge als binärer Vektor)
Wie erfolgt die Darstellung über Bitfolgen?
V = {0,1,…,n-1} (Index)
[x0,x1,…,xn-1], xi = \( \left\{\begin{matrix} 1 & i \in S\ 0 & sonst \end{matrix}\right. \)
| Menge | Vektordarstellung |
|---|---|
| ∅ | 000 |
| {0} | 100 |
| {1} | 010 |
| {2} | 001 |
| {0,1} | 110 |
| {0,2} | 101 |
| {1,2} | 011 |
| {0,1,2} | 111 |
Systematische Erzeugung
Welche Operationen gibt es auf Mengen?
- Komplement: \( \ S \hat{=} [a_0,…,a_{n-1}] \Rightarrow \overline{S} = V\setminus S \hat{=} [\neg a_0,…,\neg a_{n-1}] \)
- Kardinalität: \( \ S \hat{=} a = [a_0,…,a_{n-1}] \ \left | S \right | = w_Ha \text{ (Hamming-Gewicht)} \)
- Einfügen/Löschen 0(1): AND mit 0 an der Stelle i, um etwas zu löschen oder OR mit 1, um etwas einzufügen
- Membership-Test: Prüfe, ob \( a_i = 1 (i \in S \Leftrightarrow a_i = 1) \)
- Vereinigung: \( \ S \hat{=} [a_0,…,a_{n-1}] \ T \hat{=} [b_0,…,b_{n-1}] \ \Rightarrow S \cup T \hat{=} [a_0 \cup b0,…,a_{n-1} \cup b_{n-1}] \)
- Schnitt: \( S \cap T \hat{=} [a_0 \wedge b0,…,a_{n-1} \wedge b_{n-1}] \)
Wie kann man den Vektor V (binäre Darstellung) geschickt durchlaufen?
- x ist eine Menge von Objekten
- Definiere eine Reihenfolge
- rank: Ermittle die Position eines Elements
- unrank: Ermittle das Elements einer Position
- successor: Ermittle den Nachfolger eines Elements
- predecessor: Ermittle den Vorgänger eines Elements
Wie werden die Funktionen formal definiert?
- rank: \( x \rightarrow \left \{ 0,1,…,\left | x \right |-1 \right \} \)
- unrank: \( \left \{ 0,1,…,\left | x \right |-1 \right \} \rightarrow x \)
- succ: \( x \rightarrow x \cup \left \{ \perp \right \} \)
- pred: \( x \rightarrow x \cup \left \{ \perp \right \} \)
Wie hängen die Funktionen zusammen?
\( \ rank(x)=i \Leftrightarrow unrank(i)=x \ \Rightarrow unrank(rank(x))=x \ \Rightarrow rank(unrank(i))=i \ succ(x) = \left\{\begin{matrix} unrank(rank(x))+1 & \text{falls } 0 \leq rank(x) \leq \left | x \right |-1 \ \perp & \text{falls } rank(x) = \left | x \right |-1 \end{matrix}\right. \ pred(x) = \left\{\begin{matrix} unrank(rank(x))-1 & \text{falls } 0 < rank(x) \leq \left | x \right |-1 \ \perp & \text{falls } rank(x) = 0 \end{matrix}\right. \)
Die Erweiterung um \( \perp \) dient als Bedingung für das Erreichen einer Grenze.
Was ist die Standardreihenfolge?
Diese Anordnung entspricht der big endian Darstellung (von links nach rechts).
| Menge | Charakteristischer Vektor | Rank |
|---|---|---|
| ∅ | 000 | 0 |
| {0} | 100 | 1 |
| {1} | 010 | 2 |
| {0,1} | 110 | 3 |
| {2} | 001 | 4 |
| {0,2} | 101 | 5 |
| {1,2} | 011 | 6 |
| {0,1,2} | 111 | 7 |
Welche Funktionen gibt es für die Standardreihenfolge?
- rank([a0,a1,a2]) = \( \sum_{i=0}^{2}a_i2^i \)
- succ([a0,a1,a2]) = ([b0,b1,b2]) mit \( \sum_{i=0}^{2}b_i2^i = (\sum_{i=0}^{2}a_i2^i)+1 \)
Das iterative Durchlaufen dieser Reihenfolge ist suboptimal, da mehrere Bitänderungen bei einem Schritt durchgeführt werden.
Wie kann man eine Menge geschickter durchlaufen?
Indem beim Durchlauf nur Schritte über Elemente mit minimaler Änderung gemacht werden.
Beispiel
\( \ 000 \ 100 \ 110 \ 010 \ 011 \ 111 \ 101 \ 001 \)
Diese Elemente sind sogar zyklisch. Dies bedeutet, dass das letzte Element nur eine minimale Änderung vom ersten Element entfernt ist.
Wie kann man diese binären Vektoren mit minimaler Änderung erzeugen?
Über rekursive Funktionen, wie den Gray Code.
\( \left.\begin{matrix} \Omega = a^{0},a^{1}…,a^{l-1} &, a^{i} = a^{i}_{0}…a^{i}_{n-1} \ \Gamma = b^{0},b^{1}…,b^{m-1} & \end{matrix}\right\} \) gegeben
\( \Omega \) ist eine Liste von Vektoren und \( a^i \) ist eine binäre Darstellung eines Vektors mit der Länge n.
Welche Operationen gibt es auf Vektoren?
- Verknüpfung: \( \Omega \mid \Gamma = a^{(0)}a^{(l-1)},b^{(0)}b^{(m-1)} \)
- Spiegelung: \( \Omega^{R} = a^{(l-1)},…,a^{0} \)
- Verlängerung: \( \begin{matrix} \Omega 0 = a^{0}0,…,a^{l-1}0 \ \Omega 1 = a^{0}1,…,a^{l-1}1 \end{matrix} \Rightarrow a^{i}x = a^{i}_{0}…a^{i}_{n-1}x \)
Beispiele
\( \ \Omega = 11,00,01 \ \Gamma = 11,00,01 \ \Omega \mid \Gamma = 11,00,01,01,11,01,10 \ \Omega^{R} = 01,00,11 \ \Omega0 = 110,000,010 \ \Omega1 = 111,001,011 \)
Annahme zur rekursiven Erzeugung mittels Gray Code
\( \Omega \) hat eine minimale Änderung. Mit \( \Omega 0 \mid \Omega^{R}1 \) wird ebenfalls eine minimale Änderung geliefert. Hier wird zuerst eine Null an den originalen Vektor angehängt. Eine Kopie des originalen Vektors wird gespiegelt, mit einer 1 verlängert und dann werden diese neuen Vektoren verknüpft. Durch das Anhängen ergibt sich am Übergang der Verknüpfung eine minimale Änderung.
\( \ \Omega = a^{0},…,a^{l-1} \ \Omega0 = a^{0}0,…,a^{n-1}0 \ \Omega^{R}1 = a^{n-1}0,…,a^{0}1 \)
Beispiele
\( \ \Omega^{0} = 0,1 \ \Omega^{1} = 0\underline{0},1\underline{0},1\underline{1},0\underline{1} \ \Omega^{2} = 00\underline{0},10\underline{0},11\underline{0},01\underline{0},01\underline{1},11\underline{1},10\underline{1},00\underline{1} \ \Gamma^{0}=1,0 \ \Gamma^{1}=1\underline{0},0\underline{0},0\underline{1},1\underline{1} \ \Gamma^{2}=10\underline{0},00\underline{0},01\underline{0},11\underline{0},11\underline{1},01\underline{1},00\underline{1},10\underline{1} \)
Welche Konstruktionsmöglichkeiten gibt es noch?
\( \ \Omega^{R} 0 \mid \Omega 1 \ \Omega1 \mid \Omega^{R} 0 \ \Omega^{R} 1 \mid \Omega0 \ \Omega0 \mid \Omega^{R} 1 \)
Wie prüft man, ob alle Teilmengen einer Menge erzeugt wurden?
Die Anzahl der Teilmengen muss 2n groß sein.