Sekvence de bruijn

De Bruijnova posloupnost [1] je cyklický řád, jehož prvky patří do dané konečné množiny (za množinu se obvykle považuje ), takže všechny její podposloupnosti [2] dané délky jsou různé. $a_{1},\;\ldots ,\;a_{t}$ $\{0,\;1,\;\ldots ,\;k-1\}$ $a_{{i+1}},\;\ldots ,\;a_{{i+n}}$ $n$

Často jsou uvažovány periodické sekvence s periodou obsahující různé podsekvence , tj. takové periodické sekvence, ve kterých je libovolný segment délky de Bruijnovou sekvencí se stejnými parametry a . $T$ $T$ $a_{{i+1}},\;\ldots ,\;a_{{i+n}}$ $T+n-1$ $n$ $k$

Cykly jsou pojmenovány po nizozemském matematikovi Nicholasi de Bruijnovi , který je studoval v roce 1946 [3] , ačkoli byly studovány již dříve [4] .

Vlastnosti

Je zřejmé, že délka (perioda) takového cyklu nemůže překročit - počet všech různě dlouhých vektorů s prvky od ; Je snadné prokázat, že tohoto odhadu bylo dosaženo. Cykly této maximální možné délky se obvykle nazývají de Bruijnovy cykly (někdy se však tento termín používá i pro cykly kratší délky). $k^{n}$ $n$ $\{0,\;1,\;\ldots ,\;k-1\}$

Pro , existují takové de Bruijnovy cykly s délkou o jednu menší, než je maximum, které jsou vyjádřeny lineárními rekurentními vztahy řádu Na základě takových sekvencí je sestaven zejména cyklický redundantní kód CRC32 (EDB88320). $k=2$ $n$ $n=3$ $x_{n}=x_{{n-2}}+x_{{n-3}}{\pmod 2}$

Příklady

Příklady de Bruijnových cyklů pro období 2, 4, 8, 16: $k=2$

01 (obsahuje podsekvence 0 a 1)
0011 (obsahuje podsekvence 00, 01, 11, 10)
00010111 (000, 001, 010, 101, 011, 111, 110, 100)
0000100110101111

Počet de Bruijnových cyklů

Počet de Bruijnových cyklů s parametry je také ( zvláštním případem de Bruijnovy věty je věta BEST , pojmenovaná podle jmen de Bruijn, Tatiana Ehrenfest , Cedric Smith a William Tutt ). $n$ $k$ $k!^{{k^{{(n-1)}}}}/k^{n}$

Comte de Bruyne

Existuje výhodná interpretace de Bruijnových sekvencí a cyklů na základě tzv. de Bruijnova grafu — orientovaného grafu s vrcholy odpovídajícími různým množinám délek s prvky od , ve kterém hrana vede z vrcholu do vrcholu tehdy a jen tehdy ( ); v tomto případě může být samotná hrana spojena se sadou délek : . U takového grafu odpovídají Eulerovy cesty ( Eulerovské cykly ) , které neprocházejí dvakrát stejnou hranou , de Bruijnovi posloupnosti (cyklu) s parametry a a Hamiltonovské cesty ( Hamiltonovské cykly ) , které neprocházejí dvakrát stejným vrcholem. do sekvence (cyklu) de Bruijn s parametry a . $k^{n}$ $k^{n}$ $n$ $\{0,\;1,\;\ldots ,\;k-1\}$ $(x_{1},\;\ldots ,\;x_{n})$ $(y_{1},\;\ldots ,\;y_{n})$ $x_{i}=y_{{i-1}}$ $i=2,\;\ldots ,\;n$ $n+1$ $(x_{1},\;\ldots ,\;x_{n},\;y_{n})=(x_{1},\;y_{1},\;\ldots ,\;y_{n} )$ $n+1$ $k$ $n$ $k$

De Bruijnův graf je široce používán v bioinformatice při úlohách sestavení genomu .

Poznámky

↑ Existují také hláskování „de Bruyn“ a „de Bruyn“.
↑ Pokud , pak je prvek s indexem vybrán v cyklickém pořadí $j>t$ $j{\bmod {t))$
↑ de Bruijn NG Kombinatorický problém // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. - v. 49.-str. 758-764.
↑ Flye Sainte-Marie C. Otázka 48 // L'intermédiaire math. - 1894. - v. 1.-pp. 107-110.

Sekvence a řádky
Sekvence	Číselná posloupnost Základní posloupnost Lineární rekurentní sekvence Fibonacciho čísla složená čísla Faktorový Barkerova sekvence sekvence de bruijn
Řádky, základní	Součet řádků Zbytek řady Podmíněná konvergence Střídavé série Vícesekce řádků
Číselné řady ( operace s číselnými řadami )	harmonická řada série Leibniz Řada inverzních čtverců Série recipročních prvočísel Řada Dirichlet série Mercator Řada Grandi 1 - 2 + 3 - 4 + ... 1 + 2 + 3 + 4 + ...
funkční řádky	Taylorova řada série Laurent Fourierova řada Trigonometrické Fourierovy řady trigonometrická řada série Wiener
Jiné typy řádků	Neumannovy řady Řada Puiseux