De-Bruijn-Folge

De-Bruijn-Folge für k = 2 und n = 2.

Eine De-Bruijn-Folge ${\displaystyle B(k,n)}$ ist ein Wort eines Alphabets ${\displaystyle A}$ mit ${\displaystyle k}$ Symbolen mit folgender Eigenschaft: Jedes mögliche Wort der Länge ${\displaystyle n}$ gebildet aus den Symbolen in ${\displaystyle A}$ taucht als zusammenhängendes Teilwort von ${\displaystyle B}$ auf, und ${\displaystyle B}$ ist das kürzeste Wort mit dieser Eigenschaft. ${\displaystyle n}$ wird die Ordnung von ${\displaystyle B}$ genannt. Dabei werden verschiedene ${\displaystyle B}$, die durch zyklische Vertauschung der Symbole auseinander hervorgehen, nicht unterschieden. Eine De-Bruijn-Folge enthält also alle Wörter der Länge ${\displaystyle n}$ aus ${\displaystyle k}$ Symbolen (in zusammenhängender Form) genau einmal, wobei das Wort zyklisch betrachtet wird, das heißt die Symbole am Ende dürfen mit denen am Anfang fortgesetzt werden, um ein Teilwort zu bilden.

Hauptteil

De-Bruijn-Folgen existieren für jedes ${\displaystyle (n,k)}$. Ein Beispiel ist für ${\displaystyle k=2}$ (Alphabet aus zwei Symbolen, 0 und 1) und ${\displaystyle n=2}$ die De-Bruijn-Folge ${\displaystyle B=(0,0,1,1)}$. Hierin kommen alle Wörter der Länge ${\displaystyle n=2}$ vor: ${\displaystyle (0,0),(0,1),(1,1),(1,0)}$. Für ${\displaystyle n=3}$ gibt es zwei mögliche De-Bruijn-Folgen: ${\displaystyle (00010111)}$ und ${\displaystyle (11101000)}$. Jede De-Bruijn-Folge hat die Länge ${\displaystyle k^{n}}$, und es gibt ${\displaystyle {\frac {(k!)^{k^{n-1}}}{k^{n}}}}$ verschiedene De-Bruijn-Folgen der Ordnung ${\displaystyle n}$.

De-Bruijn-Folgen lassen sich graphisch als Eulerwege oder Hamiltonpfade eines De-Bruijn-Graphen darstellen. Das sind gerichtete Graphen, deren ${\displaystyle k^{n}}$ Knoten alle Wörter der Länge ${\displaystyle n}$ aus dem Alphabet mit ${\displaystyle k}$ Symbolen darstellen, und deren Knoten verbunden sind, falls diese Wörter überlappen^[1]. Für ${\displaystyle k=2}$ und ${\displaystyle n=2}$ sind beispielsweise alle Knoten bis auf ${\displaystyle (0,0)}$ und ${\displaystyle (1,1)}$ miteinander verbunden.

De-Bruijn-Folgen haben Anwendungen z. B. in der Konstruktion von Kartentricks, in der Kryptographie, Genetik und Bioinformatik (zum Beispiel Pavel Pevzner), bei Telegraphen, fehlerkorrigierenden Codes, Computerspeicher-Hashing und Maschinellem Sehen.^[2][3] Sie lassen sich auch durch Schieberegisterfolgen erzeugen.

Verallgemeinerung

Analoge Objekte können für höhere Dimensionen ${\displaystyle d}$ definiert und konstruiert werden, speziell der Fall ${\displaystyle d=2}$ wurde von mehreren Autoren untersucht und dieser heißt De-Bruijn-Torus.^[4][5]

Es ist eine Matrix mit Einträgen aus einem Alphabet (oft nur die beiden Symbole 0 und 1), die alle möglichen ${\displaystyle m\times n}$ Untermatrizen (auch: Sub-matrizen) genau einmal enthält. Gegenüberliegende Seiten der Matrix werden miteinander identifiziert, deshalb der Name Torus. Für ${\displaystyle n=1}$ erhält man De-Bruijn-Folgen als Spezialfall.

Wenn man sich auf quadratische, binäre Tori beschränkt, lassen sich ${\displaystyle (4,4;2;2)_{2}}$ De-Bruijn-Tori, die alle ${\displaystyle 2\times 2}$ binären Untermatrizen enthalten, leicht konstruieren. Der nächste quadratische De-Bruijn-Torus ist ${\displaystyle (256,256;4;4)_{2}}$ und wurde von W.-C. Shiu induktiv konstruiert.^[6]

De-Bruijn-Torus

Höhere De-Bruijn-Tori sind noch nicht bekannt, z. B. für alle ${\displaystyle 6\times 6}$ binären Untermatrizen (${\displaystyle 2^{36}=68719476736}$ Möglichkeiten) würde man ${\displaystyle (262144,262144;6;6)_{2}}$ brauchen, das liegt gerade noch im Bereich des Realisierbaren: wenn die Darstellung 0,1 mm per Pixel (Matrixeintrag) benötigt, bräuchte man eine Fläche von ca. 26 Quadratmetern.

Namensgebung

De-Bruijn-Folgen sind nach Nicolaas Govert de Bruijn benannt, der darüber 1946 veröffentlichte^[7] und 1951 mit Tatjana van Aardenne-Ehrenfest^[8]. De Bruijn wiederum gibt an^[9], dass sie zuerst in Fall k=2 von Camille Flye Sainte-Marie 1894 behandelt wurden.^[10] Erste De-Bruijn-Folgen tauchten aber schon im alten Indien auf in Zusammenhang mit Sanskrit-Prosodie.^[11] Es gab auch weitere Veröffentlichungen vor De Bruijn, so von M. H. Martin^[12] (in Zusammenhang mit Dynamik), I. J. Good (1946)^[13], Karl Popper (1934)^[14], N. M. Korobov^[15], durch den Telegrapheningenieur Émile Baudot (1888). Unter Zauberern waren sie ebenfalls bekannt, allerdings wurden sie von diesen oft fälschlicherweise Gray-Codes genannt.^[16]

Literatur

• Donald Knuth The art of computer programming, 4 A, Teil 1, Addison-Wesley 2011
• Hal Frederickson, Anthony Ralston A survey of full length nonlinear shift register cycle algorithms, SIAM Review, Band 24, 1982, S. 195–221
• Anthony Ralston De Bruijn Sequences - a model example of the interaction of discrete mathematics and computer science, Mathematics Magazine, Band 55, 1982, S. 131–143
• Sherman K. Stein Mathematics, the man made universe, Freeman 1963, Dover 1999, Kapitel 9 (Memory Wheels), mit weiteren historischen Hinweisen
  • Das Kapitel beruht auf einer früheren Version: Sherman K. Stein The mathematician as an explorer, Scientific American, Mai 1961, S. 149–158

Einzelnachweise

1. De Bruijn Graph, Mathworld
2. Persi Diaconis, Ron Graham Magical Mathematics, Princeton University Press 2012
3. Sherman Stein Mathematics, the man made universe
4. C. T. Fan, S. M. Fan, S. L. Ma, M. K. Siu On de Bruijn arrays, Ars Combinatoria, Band 19, 1985, S. 205–213
5. F. Chung, Persi Diaconis, Ronald Graham Universal cycles for combinatorial structures, Discrete Mathematics, Band 110, 1992, S. 43–59
6. Wai-Chee Shiu Decoding de Bruijn arrays constructed by the FFMS method, Ars Combinatoria, Band 47, 1997, S. 33–48
7. De Bruijn A combinatorial problem, Koninklijke Nederlandse Akademie van Wetenschappen, Band 49, 1946, 758–764. Das Problem wurde vom niederländischen Telefoningenieur K. Posthumus gestellt. Die Arbeiten von De Bruijn sind Online auf seiner Homepage
8. De Bruijn, Van Aardenne-Ehrenfest Circuits and trees in oriented linear graphs, Simon Stevin, Band 28, 1951, S. 203–217
9. Report TU Eindhoven 1975
10. Sainte-Marie Solution to question Nr.48, L’Intermédiaire des Mathématiciens, Band 1, 1894, S. 107–110
11. Rachel Hall Math for Poets and Drummers, 2007, pdf. Siehe auch Sherman Stein Mathematics, the man made universe, Kapitel 9. Er verweist auf eine Erwähnung in Curt Sachs Rhythm and Tempo, Norton 1953, S. 98–101
12. Martin A problem of arrangements, Bulletin AMS, Band 40, 1934, S. 859–864
13. Good Normal recurring decimals, J. London Math. Soc., Band 21, 1946, S. 167–169, sowie Notiz dazu von D. Rees, ibid., S. 169–172
14. Er erwähnt sie auch in The Logic of Scientific Discovery, Basic Books 1959, S. 162/163, 292
15. Korobov Normal periodic sequences, AMS Translations, Band 4, S. 31–58, zuerst russisch 1951
16. Diaconis, Graham Magical Mathematics, Princeton University Press, S. 25. In Kapitel 2 des Buches wird ein bemerkenswerter Kartentrick beschrieben, der auf den Zaubertrick-Erfinder und Hühnerfarmer Charles T. Jordan (1888–1944) in einer Veröffentlichung von 1919 (Thirty Card Mysteries) zurückgeht (von ihm Coluria genannt), seine Biographie und Foto findet sich in dem Buch S. 189f.