Bitonisches Zählen und Zusammenfügen (II)

Induktionsschritt:

M2n($ \vec{{x}} $,$ \vec{{y}} $) = $ \left\{\vphantom{
\begin{array}{l}
M_n(\operatorname{odd}\vec{x},\operatorname...
...rname{odd}\vec{y}); \\
V(x_1,x_2);\ldots; V(y_{n-1},y_n)
\end{array}}\right.$$ \begin{array}{l}
M_n(\operatorname{odd}\vec{x},\operatorname{even}\vec{y}) ;\\...
...\operatorname{odd}\vec{y}); \\
V(x_1,x_2);\ldots; V(y_{n-1},y_n)
\end{array}$


mit V(p, q) = Verteiler, odd(x1, x2,…) = (x1, x3,…), even(x1, x2,…) = (x2, x4,…).


Satz: jedes solche Mn erfüllt die Spezifikation.


Übung: konstruiere C4, M4

Übung: Beweis für M8 mit Eingangsfolge (3, 3, 2, 2;4, 3, 3, 3), unter der Annahme, daß der Satz für M4 gilt.

Übung: Beweis für M2n mit beliebiger Eingangsfolge,
unter der Annahme, daß der Satz für Mn gilt.



Johannes Waldmann 2013-06-18