Episódio De Bruijn
Uma sequência De Bruijn é uma palavra de um alfabeto com símbolos com a seguinte propriedade: Cada palavra possível de comprimento formada a partir dos símbolos em aparece como uma palavra parcial conectada de e é a palavra mais curta com esta propriedade. é chamado de ordem de . Não há distinção entre os diferentes que emergem uns dos outros por meio da troca cíclica dos símbolos. Uma sequência De Bruijn, portanto, contém todas as palavras de comprimento de símbolos (na forma conectada) exatamente uma vez, em que a palavra é vista ciclicamente, isto é, os símbolos no final podem ser continuados com aqueles no início para formar uma palavra parcial.
Massa
Existem sequências de De Bruijn para cada um . Um exemplo é para (alfabeto de dois símbolos, 0 e 1) e a sequência De Bruijn . Aqui todas as palavras são o comprimento antes: . Pois existem duas possíveis sequências de Bruijn: e . Cada sequência De Bruijn tem comprimento e existem diferentes sequências de ordem De Bruijn .
As sequências de De Bruijn podem ser representadas graficamente como caminhos de Euler ou caminhos de Hamilton de um gráfico de De Bruijn . Esses são gráficos direcionados cujos nós representam todas as palavras de comprimento do alfabeto com símbolos e cujos nós estão conectados se essas palavras se sobrepõem. Para e todos os nós são, por exemplo, até e conectados uns aos outros.
Os episódios de De Bruijn têm aplicações, por exemplo B. na construção de truques de cartas, em criptografia , genética e bioinformática (por exemplo, Pavel Pevzner ), com telégrafos, códigos de correção de erros , hash de memória de computador e visão de máquina . Eles também podem ser gerados por sequências de registro de deslocamento .
generalização
Objetos analógicos podem ser definidos e construídos para dimensões superiores , especialmente o caso foi investigado por vários autores e isso é denominado De-Bruijn-Torus .
É uma matriz com entradas de um alfabeto (frequentemente apenas os dois símbolos 0 e 1 ) que contém todas as submatrizes possíveis (também: submatrizes) exatamente uma vez. Os lados opostos da matriz são identificados um com o outro, daí o nome toro . Pois se recebe as sequências de De Bruijn como um caso especial.
Se alguém se restringir a tori quadrático e binário, De Bruijn tori, que contém todas as submatrizes binárias, pode ser facilmente construído. O torus De Bruijn quadrado mais próximo é e foi projetado por W.-C. Shiu construído indutivamente .
Higher De Bruijn Tori ainda não são conhecidos, por ex. B. para todas as submatrizes binárias ( possibilidades) necessárias, isso está apenas dentro do reino do realizável: se a representação precisa de 0,1 mm por pixel (entrada da matriz), seria necessária uma área de aproximadamente 26 quadrados metros .
Nomeação
Os episódios de De Bruijn têm o nome de Nicolaas Govert de Bruijn , que publicou sobre eles em 1946 e em 1951 com Tatjana van Aardenne-Ehrenfest . De Bruijn, por sua vez, afirma que foram tratados pela primeira vez no caso k = 2 por Camille Flye Sainte-Marie em 1894. Os primeiros episódios de Bruijn apareceu na antiga Índia em conexão com sânscrito - prosódia . Houve também outras publicações antes de De Bruijn, como MH Martin (em conexão com a dinâmica), IJ Good (1946), Karl Popper (1934), NM Korobov, do engenheiro telegráfico Émile Baudot (1888). Eles também eram conhecidos pelos magos, mas frequentemente eram chamados erroneamente de códigos Gray .
literatura
- Donald Knuth A arte da programação de computadores , 4 A, Parte 1, Addison-Wesley 2011
- Hal Frederickson, Anthony Ralston Uma pesquisa de algoritmos de ciclo de registro de deslocamento não linear de comprimento total , SIAM Review, Volume 24, 1982, pp. 195-221
- Anthony Ralston De Bruijn Sequences - um exemplo de modelo da interação de matemática discreta e ciência da computação , Mathematics Magazine, Volume 55, 1982, pp. 131-143
- Sherman K. Stein Mathematics, the man made universe , Freeman 1963, Dover 1999, Capítulo 9 (Memory Wheels), com outras referências históricas
- O capítulo é baseado em uma versão anterior: Sherman K. Stein The mathematician as a explorer , Scientific American, maio de 1961, pp 149-158
Evidência individual
- ^ Gráfico De Bruijn, Mathworld
- ↑ Persi Diaconis , Ron Graham Magical Mathematics , Princeton University Press 2012
- ^ Sherman Stein Matemática, o universo artificial
- ↑ CT Fan, SM Fan, SL Ma, MK Siu On de Bruijn arrays , Ars Combinatoria, Volume 19, 1985, pp. 205-213
- ↑ F. Chung, Persi Diaconis, Ciclos universais de Ronald Graham para estruturas combinatórias , Discrete Mathematics, Volume 110, 1992, pp. 43-59
- ^ Wai-Chee Shiu Decoding de Bruijn arrays construídos pelo método FFMS , Ars Combinatoria, Volume 47, 1997, pp. 33-48
- ^ De Bruijn A combinatorial problem , Koninklijke Nederlandse Akademie van Wetenschappen, Volume 49, 1946, 758-764. O problema foi colocado pelo engenheiro de telefonia holandês K. Posthumus. O trabalho de De Bruijn está online em sua página inicial
- ^ De Bruijn, Van Aardenne-Ehrenfest Circuits and trees in oriented linear graphs , Simon Stevin, Volume 28, 1951, pp. 203-217
- ^ Relatório TU Eindhoven 1975
- ↑ Solução de Sainte-Marie para a questão nº 48 , L'Intermédiaire des Mathématiciens, Volume 1, 1894, pp. 107-110
- ^ Rachel Hall Math para Poetas e Bateristas , 2007, pdf . Ver também Sherman Stein Mathematics, the man made universe , capítulo 9. Ele se refere a uma menção em Curt Sachs Rhythm and Tempo , Norton 1953, pp. 98-101
- ↑ Martin Um problema de arranjos , Boletim AMS, Volume 40, 1934, pp. 859-864
- ↑ Good Normal recorrente decimals , J. London Math. Soc., Volume 21, 1946, pp. 167-169, e uma nota sobre este por D. Rees, ibid., Pp. 169-172
- ↑ Ele também os menciona em The Logic of Scientific Discovery , Basic Books 1959, pp. 162/163, 292
- ↑ Sequências periódicas normais de Korobov , AMS Translations, Volume 4, pp. 31-58, primeiro em russo 1951
- ↑ Diaconis, Graham Magical Mathematics , Princeton University Press, p. 25. O capítulo 2 do livro descreve um notável truque de cartas referindo-se ao inventor do truque de mágica e criador de galinhas Charles T. Jordan (1888-1944) em uma publicação de 1919 ( Thirty Card Mistérios ) (por ele denominada Colúria), sua biografia e foto podem ser encontradas no livro p. 189f.