De-Bruijn-Folge
Eine De-Bruijn-Folge ist ein Wort eines Alphabets mit Symbolen mit folgender Eigenschaft: Jedes mögliche Wort der Länge gebildet aus den Symbolen in taucht als zusammenhängendes Teilwort von auf, und ist das kürzeste Wort mit dieser Eigenschaft. wird die Ordnung von genannt. Dabei werden verschiedene , die durch zyklische Vertauschung der Symbole auseinander hervorgehen, nicht unterschieden. Eine De-Bruijn-Folge enthält also alle Wörter der Länge aus 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 . Ein Beispiel ist für (Alphabet aus zwei Symbolen, 0 und 1) und die De-Bruijn-Folge . Hierin kommen alle Wörter der Länge vor: . Für gibt es zwei mögliche De-Bruijn-Folgen: und . Jede De-Bruijn-Folge hat die Länge , und es gibt verschiedene De-Bruijn-Folgen der Ordnung .
De-Bruijn-Folgen lassen sich graphisch als Eulerwege oder Hamiltonpfade eines De-Bruijn-Graphen darstellen. Das sind gerichtete Graphen, deren Knoten alle Wörter der Länge aus dem Alphabet mit Symbolen darstellen, und deren Knoten verbunden sind, falls diese Wörter überlappen[1]. Für und sind beispielsweise alle Knoten bis auf und 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 definiert und konstruiert werden, speziell der Fall 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 Untermatrizen (auch: Sub-matrizen) genau einmal enthält. Gegenüberliegende Seiten der Matrix werden miteinander identifiziert, deshalb der Name Torus. Für erhält man De-Bruijn-Folgen als Spezialfall.
Wenn man sich auf quadratische, binäre Tori beschränkt, lassen sich De-Bruijn-Tori, die alle binären Untermatrizen enthalten, leicht konstruieren. Der nächste quadratische De-Bruijn-Torus ist und wurde von W.-C. Shiu induktiv konstruiert.[6]
Höhere De-Bruijn-Tori sind noch nicht bekannt, z. B. für alle binären Untermatrizen ( Möglichkeiten) würde man 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
- ↑ De Bruijn Graph, Mathworld
- ↑ Persi Diaconis, Ron Graham Magical Mathematics, Princeton University Press 2012
- ↑ Sherman Stein Mathematics, the man made universe
- ↑ C. T. Fan, S. M. Fan, S. L. Ma, M. K. Siu On de Bruijn arrays, Ars Combinatoria, Band 19, 1985, S. 205–213
- ↑ F. Chung, Persi Diaconis, Ronald Graham Universal cycles for combinatorial structures, Discrete Mathematics, Band 110, 1992, S. 43–59
- ↑ Wai-Chee Shiu Decoding de Bruijn arrays constructed by the FFMS method, Ars Combinatoria, Band 47, 1997, S. 33–48
- ↑ 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
- ↑ De Bruijn, Van Aardenne-Ehrenfest Circuits and trees in oriented linear graphs, Simon Stevin, Band 28, 1951, S. 203–217
- ↑ Report TU Eindhoven 1975
- ↑ Sainte-Marie Solution to question Nr.48,L´Intermédiaire des Mathématiciens, Band 1, 1894, S. 107–110
- ↑ 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
- ↑ Martin A problem of arrangements, Bulletin AMS, Band 40, 1934, S. 859–864
- ↑ Good Normal recurring decimals, J. London Math. Soc., Band 21, 1946, S. 167–169, sowie Notiz dazu von D. Rees, ibid., S. 169–172
- ↑ Er erwähnt sie auch in The Logic of Scientific Discovery, Basic Books 1959, S. 162/163, 292
- ↑ Korobov Normal periodic sequences, AMS Translations, Band 4, S. 31–58, zuerst russisch 1951
- ↑ 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.
