In der heutigen Vorlesung beschäftigen wir uns mit der Bestimmung von k-Teilmengen und dem Revolving Door Algorithmus.
| Skript-Anfang | Skript – Seite 19 |
|---|---|
| Skript-Ende | Skript – Seite 23 |
k-Teilmengen
Fragestellungen
Wie viele k-Teilmengen gibt es?
Die Berechnung kann mittels Binomialkoffizient durchgeführt werden.
\( \binom{n}{k} = \frac{n!}{k!*(n-k)!} \)
Beispiel
Gesucht sind die 3-Teilmengen von V={0,1,2,3}.
\(\binom{4}{3} = \frac{4!}{3!*(4-3)!} = \frac{24}{3!*1!} = \frac{24}{6} = 4 \)
Beispiel
Welche k-Teilmengen gibt es in der Teilmenge V?
\( \binom{V}{3} = \begin{matrix}\{0,1,2\} \ \{0,1,3\} \ \{0,2,3\} \ \{1,2,3\} \end{matrix} \)
Das Verfahren zu deren Bestimmung wird in den nächsten Abschnitten näher erläutert.
Pascalsche Identität
Was ist die Pascalsche Identität?
Eine Eigenschaften der Binomialkoeffizienten, die später zur rekursiven Erzeugung genutzt werden kann. Weiterhin ist sie die Basis für eine geometrische Anordnung der Binomialkoeffizienten in Form eines Dreiecks.
\( \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \)
Randbedingungen für die Rekursion
Abbruch der Rekursion, wenn \( \binom{n}{n} = 1 = \binom{n}{0} \)
Wie lässt sich die k-Teilmenge mit dem Pascalschen Dreieck bestimmen?
Systematische Erzeugung
Bestimmung der Teilmengen von V mit k- Elementen
\( \binom{V}{k} = \{ S\subseteq \left | S \right | =k \} \)
Entnimmt man der Teilmenge V = {0,1,…,n-1} das Element n-1, so ergibt sich die neue Teilmenge Teilmenge V‘ = {0,1,…,n-2}. Die Anzahl der Elemente ändert sich dabei wie folgt.
\( \ |V| = n \ |V’| = n-1 \ \left | \binom{V}{k} \right | = \binom{n}{k} \)
Partitionierung der Mengen
\( \binom{V}{k} = \binom{V‘}{k} \cup \left \{ S \cup \left \{ n-1 \right \} \mid S \in \binom{V‘}{k-1} \right \} \)
k-Teilmengen von V, die nicht das Element n-1 enthalten: \( \binom{V‘}{k}\)
k-Teilmengen von V, die das Element n-1 enthalten: \( S \cup \left \{ n-1 \right \} \)
Teilmengen von 0 bis n-2 = {0,…,n-2} = \( \left\{\begin {matrix}\Gamma = S^{(0)},…,S^{(l-1)}\ \Omega= T^{(0)},…,T^{(m-1)} \end{matrix}\right.\)
Operationen auf Mengen
Zusammenfügen: \( \Gamma \mid \Omega := S^{(0)},…,S^{(l-1)} \mid T^{(0)},…,T^{(l-1)} \)
Umdrehen: \( \Gamma^{R}=S^{(l-1)},…,S^{(0)} \)
Erweitern: \( \Gamma^{E} = S^{(0)}\cup \left \{ n-1 \right \},…,S^{(l-1)} \cup \left \{ n-1 \right \} \)
Systematische Erzeugung aller k- Teilmengen
Folge Aller k-Teilmengen von {0,1,…,n-1}: \( \Omega_{n,k} \)
\( \ \Omega_{n,n} = \{0,1,…,n-1\} \ \Omega_{n,0} = \emptyset \ \Omega_{n,k} = \Omega_{n-1,k} \mid \Omega^{E}_{n-1,k-1} \)
Beispiel
\( \ \Omega_{1,0} = \emptyset \ \Omega_{1,1} = \{0 \}\ \Omega_{2,1} = \Omega_{1,1} \mid \Omega^{E}_{1,0} = \{0\},\mid \{1\} \ \Omega_{3,1} = \Omega_{2,1} \mid \Omega^{E}_{2,0} = \{0\},\{1\}, \mid\{2\} \ \Omega_{3,2} = \Omega_{2,2} \mid \Omega^{E}_{2,1} = \{0,1\},\mid \{0,2\},\{1,2\} \ \Omega_{4,2} = \Omega_{3,2} \mid \Omega^{E}_{3,1} = \{0,1\}, \{0,2\},\{1,2\},\mid \{0,3\},\{1,3\},\{2,3\} \ \)
Wie lässt sich dies auf Vektoren übertragen?
\( \ \Delta_{n,n} = 1^{n} = 111..111 \text{ (entspricht n- Einsen)} \ \Delta_{n,0} = 0^{n} = 000..000\text{ (entspricht n-Nullen)} \ \Delta_{n,k} = \Delta_{n-1,k}0 \mid \Delta_{n-1,k-1} 1 \)
\( \Delta_{n-1,k} \) ist ein Element kürzer als \( \Delta_ {n,k} \), weshalb man eine Null dran hängt.
Beispiel
\( \begin{align} \Delta_{4,2} &= \Delta_{3,2}0 \mid \Delta_{3,1}1\ &=1100,1010,0110,\mid 1001,0101,0011 \end{align} \)
Wie lässt sich die Folge optimieren?
Mit Hilfe von Gray Code lässt sich eine Folge mit minimaler Änderung erzeugen.
\( \ \Gamma_{n,n} = 1^n \ \Gamma_{n,0} = 0^n \)
\( \Gamma_{n,k} = \Gamma_{n-1,k}0 \mid \Gamma^{R}_{n-1,k-1}1 \ \) ist eine Folge mit minimaler Änderung.
Wie lässt sich beweisen, dass dies wirklich eine Folge mit minimaler Änderung ist?
Mit Hilfe von Induktion ist ein solcher Nachweis möglich.
Annahme
\( \Gamma_{n-1,k} \) ist eine Folge mit minimaler Änderung, dann hat \( \Gamma_{n-1,k}0 \) ebenfalls nur eine minimale Änderung. Daraus folgt, dass \( \Gamma_{n-1,k-1} \) und wiederum \( \Gamma^{R}_{n-1,k-1} \) und \( \Gamma^{R}_{n- 1,k-1}1 \) ebenfalls nur eine minimale Änderung haben. Es muss folglich nur der Übergang geprüft werden.
Übergang
\( \ \text{Erstes Element: } \Gamma_{n,k} = 1^{k}0^{n-k} \ \text{Letztes Element: } \Gamma_{n,k} \ \hat{=} \text{ erstes Element von } \Gamma_{n-1,k-1}1 \ \hat{=} 1^{k-1}0^{(n-1) – (k-1)}1 \)
Randnotiz
\( \Gamma^{R}_{n-1,k-1}1 = (\Gamma_{n-1,k-1}1)^{R} \)