De Bruijnova posloupnost

Příklad de Bruijnovy posloupnosti řádu 2 pro dvouprvkovou abecedu

De Bruijnova posloupnost je pojem z kombinatoriky, podoboru matematiky. Pro zadaný řád n a zadanou abecedu o k prvcích se jedná o takovou cyklickou posloupnost, která každé n-znakové slovo obsahuje právě jednou jako své podslovo. Bývá značena B(k,n). Délka takové posloupnosti je $k^{n}$ Počet různých de Bruijnových posloupností B(k,n) je

${\frac {(k!)^{k^{n-1}}}{k^{n}}}$.

De Bruijnovy posloupnosti jsou pojmenovány po nizozemském matematikovi Nicolaasovi Govertovi de Bruijnovi, který je začal studovat v roce 1946.

Teorie De Bruijnových posloupností nachází využití v samoopravných kódech, kryptografii, genetice, strojovém vidění a karetním kouzelnictví.

Příkladem bezpečnostního využití je útok na elektronický zámek chráněný čtyřmístným číselným PINem, přičemž zámek funguje tak, že po zadání každé jednotlivé číslice vždy zkontroluje, zda jsou poslední čtyři zadané číslice platným PINem, a pokud ano, odemkne se. Útok hrubou silou v takovém případě vyžaduje zdánlivě až 40 000 zadání číslice. Při využití znalosti de Bruijnových posloupností stačí k otevření zadat nanejvýš 10 003 číslic.

Odkazy

Reference

V tomto článku byly použity překlady textů z článků De-Bruijn-Folge na německé Wikipedii a De Bruijn sequence na anglické Wikipedii.

Externí odkazy

• Obrázky, zvuky či videa k tématu de Bruijnova posloupnost na Wikimedia Commons