miniatura|La seqüència de de Bruijn per a la mida de l'alfabet i la longitud de la subcadena En general, hi ha moltes seqüències per a una n i k particulars, però en aquest exemple és única, fins i tot amb el cicle. En matemàtiques combinatòries, una seqüència de de Bruijn d'ordre n en un alfabet A de mida k és una seqüència cíclica en què cada cadena de longitud n possible a A apareix exactament una vegada com a subcadena (és a dir, com a subseqüència contigua). Aquesta seqüència es denota per i té longitud que també és el nombre de cadenes diferents de longitud n a A. Cadascuna d'aquestes cadenes diferents, quan es pren com a subcadena de , ha de començar en una posició diferent, perquè les subcadenes que comencen a la mateixa posició no són diferents. Per tant, ha de tenir almenys . I com que té exactament , les seqüències de de Bruijn són òptimament curtes respecte a la propietat de contenir cada cadena de longitud n almenys una vegada.
El nombre de seqüències de Bruijn diferents és
Per a un alfabet binari això és , donant lloc a la següent seqüència per a positius : 1, 1, 2, 16, 2048, 67108864... (successió A016031 a l'OEIS)
Les seqüències porten el nom del matemàtic neerlandès Nicolaas Govert de Bruijn, que va escriure sobre elles el 1946. Com va escriure més tard, l'existència de seqüències de de Bruijn per a cada ordre juntament amb les propietats anteriors va ser demostrada per primera vegada, per al cas d'alfabets amb dos elements, per Camille Flye Sainte-Marie (1984). La generalització a alfabets més grans es deu a Tatyana van Aardenne-Ehrenfest i de Bruijin (1951). Els autòmats per reconèixer aquestes seqüències es denoten com a autòmats de de Bruijn.
En moltes aplicacions, A = {0,1}.
Història El primer exemple conegut d'una seqüència de de Bruijn prové de la prosòdia sànscrita on, des de l'obra de Pingala, cada possible patró de tres síl·labes de síl·labes llargues i curtes rep un nom, com ara "y" per a curt-llarg-llarg i "m" per a llarg-llarg-llarg. Per recordar aquests noms, s'utilitza el mnemotècnic yamātārājabhānasalagām, en què cada patró de tres síl·labes apareix començant pel seu nom: "yamātā" té un patró curt-llarg-llarg, "mātārā" té un patró llarg-llarg-llarg, i així successivament, fins a "salagām" que té un patró curt-curt-llarg. Aquest mnemotècnic, equivalent a una seqüència de de Bruijn en tuples binàries de 3, és d'antiguitat desconeguda, però és almenys tan antic com el llibre de Charles Philip Brown de 1869 sobre prosòdia sànscrita que l'esmenta i el considera "una línia antiga, escrita per Pāṇini".; ; ; ; .
El 1894, A. de Rivière va plantejar la qüestió en un número de la revista francesa L'Intermédiaire des Mathématiciens, de l'existència d'una disposició circular de zeros i uns de mida que conté tot seqüències binàries de longitud El problema es va resoldre (afirmativament), juntament amb el recompte de solucions diferents, per Camille Flye Sainte-Marie el mateix any. Això va ser en gran part oblidat, i va demostrar l'existència d'aquests cicles per a la mida general de l'alfabet en lloc de 2, amb un algoritme per construir-los. Finalment, quan el 1944 Kees Posthumus va conjecturar el recompte per a seqüències binàries, de Bruijn va demostrar la conjectura el 1946, a través de la qual el problema es va fer ben conegut.
Karl Popper descriu aquests objectes de manera independent a la seva obra The Logic of Scientific Discovery (1934), anomenant-los "seqüències aleatòries més curtes".
Exemples Prenent A = {0, 1}, hi ha dos B diferents (2, 3): 00010111 i 11101000, sent un el revers o la negació de l'altre. Dos dels 16 possibles B (2, 4) en el mateix alfabet hi ha 0000100110101111 i 0000111101100101. Dos dels 2048 possibles B (2, 5) en el mateix alfabet hi ha 00000100011001010011101011011111 i 00000101001000111110111001101011.
Construcció miniatura|Un gràfic de de Bruijn. Cada seqüència de quatre dígits es produeix exactament una vegada si es recorre cada aresta exactament una vegada i es torna al punt de partida (un cicle eulerià). Cada seqüència de tres dígits es produeix exactament una vegada si es visita cada vèrtex exactament una vegada (un camí hamiltonià). Les seqüències de de Bruijn es poden construir prenent un camí hamiltonià d'un gràfic de de Bruijn n- dimensional sobre k símbols (o equivalentment, un cicle eulerià d'un gràfic n-1 dimensional de Bruijn.
Una construcció alternativa consisteix a concatenar, en ordre lexicogràfic, totes les paraules de Lyndon la longitud de les quals divideix n.According to , the sequence generated in this way was first described (with a different generation method) by , and the connection between it and Lyndon words was observed by .
Es pot utilitzar una transformada inversa de Burrows-Wheeler per generar les paraules de Lyndon requerides en ordre lexicogràfic.
Les seqüències de de Bruijn també es poden construir utilitzant registres de desplaçament o mitjançant camps finits.
Exemple utilitzant el gràfic de de Bruijn Objectiu: construir una seqüència B (2, 4) de Bruijn de longitud 24 = 16 utilitzant cicle de gràfics Euleriana (n − 1 = 4 − 1 = 3) 3-D de Bruijn.
Cada aresta d'aquest gràfic tridimensional de de Bruijn correspon a una seqüència de quatre dígits: els tres dígits que etiqueten el vèrtex que surt de l'aresta seguits del que etiqueta l'aresta. Si es recorre l'aresta etiquetada amb 1 des de 000, s'arriba a 001, cosa que indica la presència de la subseqüència 0001 a la seqüència de de Bruijn. Recorrer cada aresta exactament una vegada és utilitzar cadascuna de les 16 seqüències de quatre dígits exactament una vegada.
Exemple utilitzant la transformada inversa de Burrows-Wheeler Matemàticament, una transformada inversa de Burrows-Wheeler sobre una paraula genera un conjunt múltiple de classes d'equivalència que consisteixen en cadenes i les seves rotacions. Aquestes classes d'equivalència de cadenes contenen cadascuna una paraula de Lyndon com a element mínim únic, de manera que es pot considerar que la transformada inversa de Burrows-Wheeler genera un conjunt de paraules de Lyndon. Es pot demostrar que si realitzem la transformada inversa de Burrows-Wheeler sobre una paraula que consisteix en l'alfabet de mida k repetit k n −1 vegades (de manera que produirà una paraula de la mateixa longitud que la seqüència de de Bruijn desitjada), el resultat serà el conjunt de totes les paraules de Lyndon la longitud de les quals divideix n . D'això es dedueix que ordenar aquestes paraules de Lyndon en ordre lexicogràfic produirà una seqüència de de Bruijn B ( k, n ), i que aquesta serà la primera seqüència de de Bruijn en ordre lexicogràfic.
Usos miniatura|Una possible B (10, 4) seqüència. Les 2530 subcadenes es llegeixen de dalt a baix i després d'esquerra a dreta, i els seus dígits es concatenen. Perquè la cadena forci un cadenat de combinació, s'afegeixen els tres últims dígits entre parèntesis (000). Per tant, la cadena de 10003 dígits és "0 0001 0002 0003 0004 0005 0006 0007 0008 0009 0011 ... 79 7988 7989 7998 7999 8 8889 8899 89 8999 9 000" (espais afegits per facilitar la lectura).Els cicles de de Bruijn són d'ús general en experiments de neurociència i psicologia que examinen l'efecte de l'ordre dels estímuls sobre els sistemes neuronals, i es poden dissenyar especialment per al seu ús amb ressonància magnètica funcional.
Detecció d'angle Els símbols d'una seqüència de de Bruijn escrits al voltant d'un objecte circular (com ara la roda d'un robot) es poden utilitzar per identificar el seu angle examinant els n símbols consecutius que miren cap a un punt fix. Aquest problema de codificació d'angles es coneix com el "problema del tambor giratori". Els codis Gray es poden utilitzar com a mecanismes de codificació posicional rotativa similars, un mètode que es troba habitualment en els codificadors rotatius.
Trobar el bit de conjunt menys o més significatiu en una paraula Una seqüència de de Bruijn es pot utilitzar per trobar ràpidament l'índex del bit de conjunt menys significatiu ("1 de més a la dreta") o del bit de conjunt més significatiu ("1 de més a l'esquerra") en una paraula mitjançant operacions bit a bit i multiplicació.
Atacs de força bruta a panys Una seqüència de de Bruijn es pot utilitzar per escurçar un atac de força bruta a un pany de codi tipus PIN que no té una tecla "enter" i accepta els darrers n dígits introduïts. Per exemple, un pany de porta digital amb un codi de 4 dígits (cada dígit té 10 possibilitats, del 0 al 9) tindria B. (10, 4) solucions, amb una longitud . Per tant, només calen com a màxim (ja que les solucions són cícliques) premses per obrir el pany, mentre que provar tots els codis per separat requeriria premses.
Referències
Categoria:Successions Categoria:Combinatòria