Tor de De Bruijn
En matemàtica combinatòria, un tor de De Bruijn, anomenat així en honor de Nicolaas Govert de Bruijn, és una matriu de símbols d'un alfabet (sovint només 0 i 1) que conté totes les matrius m-per-n exactament una vegada. És un tor perquè les vores es consideren embolicades amb el propòsit de trobar matrius. El seu nom prové de la seqüència De Bruijn, que es pot considerar un cas especial on n és 1 (una dimensió).
Una de les principals qüestions obertes sobre el tori de De Bruijn és si es pot construir un tor de De Bruijn per a una mida de l'alfabet determinat per a una determinada m i n. Se sap que aquests sempre existeixen quan n = 1, des de llavors simplement obtenim les seqüències de De Bruijn, que sempre existeixen. També se sap que tori "quadrat" existeix sempre que m = n i parell (per al cas estrany, el tori resultant no pot ser quadrat).[1][2][3]
El "quadrat" binari més petit possible de Bruijn, representat a dalt a la dreta, denotat com a (4,4; 2,2) 2 de Bruijn tor (o simplement com a B2), conté les 2 × 2 matrius binàries.
B2
[modifica]A part de "translació", "inversió" (intercanviant 0s i 1s) i "rotació" (en 90 graus), no és possible cap altre (4,4; 2,2) 2 tor de De Bruijn : això es pot demostrar mitjançant una inspecció completa de totes les 216 matrius binàries (o subconjunt que compleixen limitacions com ara nombres iguals de 0 i 1s).[4]
Exemple més gran: B4
[modifica]_2_de_Bruijn_torus.svg)
Un exemple del proper possible "quadrat" binari de Bruijn tor, (256.256; 4,4) 2 (abreujat com B4), ha estat construït explícitament.[5]
La imatge mostra un exemple d'un tor / matriu de Bruijn (256.256; 4.4) 2, on els zeros s'han codificat com a blancs i els com a píxels vermells respectivament
De Bruijn tors binaris més grans (B6 & B8)
[modifica]El document en el qual es va construir un exemple del tor (256.256; 4,4) 2 de Bruijn contenia més de 10 pàgines binàries, malgrat la seua reduïda mida de lletra, feien falta tres línies per fila de matriu.
El següent binari possible de Bruijn tor, que conté totes les matrius binàries 6 × 6, tindria 236 = 68.719.476.736 entrades, produint una matriu quadrada de dimensió 262.144x262.144, denotada un (262144.262144; 6,6) 2 de Bruijn tor o simplement B6. Això es podia emmagatzemar fàcilment en un ordinador; si s'imprimeix amb píxels de costat 0,1 mm, una matriu requeriria una superfície d'aproximadament 26 × 26 metres quadrats.
L'objecte B8, que conté totes les matrius binàries 8 × 8 i que es denoten (4294967296,4294967296; 8,8) 2, té un total de 264 ≈ 18.447 × 1018 entrades: l'emmagatzematge d'aquesta matriu requeriria 18,5 exabit, o 2,3 Exabyte d'emmagatzematge, un ordre de magnitud per sobre dels centres de dades moderns.
Altres grafs De Bruijn
[modifica]- Seqüència De Bruijn
- Graf De Bruijn
Referències
[modifica]- ↑ «On de Bruijn arrays.». Ars Combinatoria A, 19, 1985, pàg. 205–213.
- ↑ «Universal cycles for combinatorial structures.». Discrete Mathematics, 110, 1, 1992, pàg. 43–59. DOI: 10.1016/0012-365x(92)90699-g.
- ↑ ; Stevens, Brett; Hurlbert, Glenn «Research problems on Gray codes and universal cycles». Discrete Mathematics, 309, 17, 9-2009, pàg. 5341–5348. DOI: 10.1016/j.disc.2009.04.002.
- ↑ «The Binatorix B2.». Private communication, 1990.
- ↑ «Decoding de Bruijn arrays constructed by the FFMS method.». Ars Combinatoria, 47, 17, 1997, pàg. 33–48.