De Bruijn sequence (original) (raw)
Eine De-Bruijn-Folge ist ein Wort eines Alphabets mit Symbolen mit folgender Eigenschaft: Jedes mögliche Wort der Länge gebildet aus den Symbolen in taucht als zusammenhängendes Teilwort von auf, und ist das kürzeste Wort mit dieser Eigenschaft. wird die Ordnung von genannt. Dabei werden verschiedene , die durch zyklische Vertauschung der Symbole auseinander hervorgehen, nicht unterschieden. Eine De-Bruijn-Folge enthält also alle Wörter der Länge aus Symbolen (in zusammenhängender Form) genau einmal, wobei das Wort zyklisch betrachtet wird, das heißt die Symbole am Ende dürfen mit denen am Anfang fortgesetzt werden, um ein Teilwort zu bilden.
Property | Value |
---|---|
dbo:abstract | De Bruijnova posloupnost je pojem z kombinatoriky, podoboru matematiky. Pro zadaný řád n a zadanou abecedu o k prvcích se jedná o takovou 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 Počet různých de Bruijnových posloupností B(k,n) je . 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, a karetním kouzelnictví. Příkladem bezpečnostního využití je útok na 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. (cs) Eine De-Bruijn-Folge ist ein Wort eines Alphabets mit Symbolen mit folgender Eigenschaft: Jedes mögliche Wort der Länge gebildet aus den Symbolen in taucht als zusammenhängendes Teilwort von auf, und ist das kürzeste Wort mit dieser Eigenschaft. wird die Ordnung von genannt. Dabei werden verschiedene , die durch zyklische Vertauschung der Symbole auseinander hervorgehen, nicht unterschieden. Eine De-Bruijn-Folge enthält also alle Wörter der Länge aus Symbolen (in zusammenhängender Form) genau einmal, wobei das Wort zyklisch betrachtet wird, das heißt die Symbole am Ende dürfen mit denen am Anfang fortgesetzt werden, um ein Teilwort zu bilden. (de) In combinatorial mathematics, a de Bruijn sequence of order n on a size-k alphabet A is a cyclic sequence in which every possible length-n string on A occurs exactly once as a substring (i.e., as a contiguous subsequence). Such a sequence is denoted by B(k, n) and has length kn, which is also the number of distinct strings of length n on A. Each of these distinct strings, when taken as a substring of B(k, n), must start at a different position, because substrings starting at the same position are not distinct. Therefore, B(k, n) must have at least kn symbols. And since B(k, n) has exactly kn symbols, De Bruijn sequences are optimally short with respect to the property of containing every string of length n at least once. The number of distinct de Bruijn sequences B(k, n) is The sequences are named after the Dutch mathematician Nicolaas Govert de Bruijn, who wrote about them in 1946. As he later wrote, the existence of de Bruijn sequences for each order together with the above properties were first proved, for the case of alphabets with two elements, by Camille Flye Sainte-Marie. The generalization to larger alphabets is due to Tatyana van Aardenne-Ehrenfest and de Bruijn. Automata for recognizing these sequences are denoted as de Bruijn automata. In most applications, A = {0,1}. (en) En mathématiques, et notamment en combinatoire et en informatique théorique, une suite de de Bruijn ou un mot de de Bruijn est un mot circulaire ou collier particulier qui a la propriété de contenir toutes les sous-suites consécutives (ou facteurs) d'une longueur donnée une et une seule fois. Les suites sont nommées d'après le mathématicien néerlandais Nicolaas Govert de Bruijn qui a contribué à leur étude. (fr) Een debruijnrij is een begrip uit de combinatoriek. De debruijnrij is een cyclisch gelezen rij (de beginelementen van de rij komen na het laatste element terug) waarin, gegeven een groep van objecten, alle mogelijke rijtjes van lengte van deze objecten precies één keer als deelrij voorkomen. De rij heeft de lengte Er zijn verschillende debruijnrijen Debruijnrijen zijn vernoemd naar de Nederlandse wiskundige Nicolaas Govert de Bruijn. Hij onderzocht ze in een artikel dat in 1946 verscheen in de proceedings van de Koninklijke Nederlandse Akademie van Wetenschappen. (nl) Cykl de Bruijna rzędu n to cykliczny ciąg 0 i 1 długości w którym każdy podciąg kolejnych n elementów występuje dokładnie 1 raz. (pl) Inom kombinatoriken är en k-när de Bruijn-sekvens B(k, n) av ordningen n en cyklisk sekvens till ett givet alfabet A med storleken k i vilken varje möjlig delsekvens av längden n uppträder en och endast en gång som på varandra följande tecken. Sekvensen är uppkallad efter den holländske matematikern Nicolaas Govert de Bruijn. Varje B(k, n) har längden kn. Det finns skilda de Bruijn-sekvenser B(k, n). Enligt de Bruijn själv bevisades existensen av de Bruijn-sekvenser för alla ordningar med ovanstående egenskaper först för alfabet med två bokstäver av Camille Flye Sainte-Marie 1894, medan utvidgningen till större alfabeten är ett verk av Tanja van Aardenne-Ehrenfest och honom själv. (sv) Послідовність де Брейна — циклічний порядок , елементи якого належать заданій скінченній множині (зазвичай розглядають множину ), такий, що всі його підпослідовності заданої довжини різні. Часто розглядаються періодичні послідовності з періодом , що містять різних підпослідовностей , — тобто такі періодичні послідовності, в яких будь-який відрізок довжини є послідовністю де Брейна з тими самими параметрами і . Цикли названо так на честь нідерландського математика Ніколаса де Брейна, який вивчав їх , хоча вони вивчалися й раніше. (uk) Последовательность де Брёйна — циклический порядок , элементы которого принадлежат заданному конечному множеству (обычно рассматривают множество ), такой, что все его подпоследовательности заданной длины различны. Часто рассматриваются периодические последовательности с периодом , содержащие различных подпоследовательностей , — то есть такие периодические последовательности, в которых любой отрезок длины является последовательностью де Брёйна с теми же параметрами и . Циклы названы по имени голландского математика Николаса де Брёйна, изучившего их в 1946 году, хотя они изучались и ранее. (ru) |
dbo:thumbnail | wiki-commons:Special:FilePath/De_Bruijn_sequence.svg?width=300 |
dbo:wikiPageExternalLink | http://7ooo.mooo.com/text/ComputingTrailingZerosHOWTO.html http://viewstl.com/classic/%3Fembedded&url=http:/upload.wikimedia.org/wikipedia/commons/1/1e/De_bruijn_torus_3x3.stl&bgcolor=black%7C http://www.hakank.org/comb/deBruijnApplet.html https://cfn.upenn.edu/aguirre/wiki/public:de_bruijn https://jgeisler0303.github.io/deBruijnDecode/ http://mathworld.wolfram.com/PermutationCycle.html https://books.google.com/books%3Fid=0a5bLBbe_dMC&pg=PA295 https://books.google.com/books%3Fid=56LNfE2QGtYC&pg=PA50 https://books.google.com/books%3Fid=5l5ps2JkyT0C&pg=PA71 https://books.google.com/books%3Fid=GYpEAAAAQBAJ&pg=PA59 https://books.google.com/books%3Fid=sd9AqHeeHh4C&pg=PA174 http://www.dwc.knaw.nl/DL/publications/PU00018235.pdf http://alexandria.tue.nl/repository/books/252901.pdf http://alexandria.tue.nl/repository/freearticles/597493.pdf http://graphics.stanford.edu/~seander/bithacks.html http://www-igm.univ-mlv.fr/~berstel/Articles/2007Origins.pdf http://www.sju.edu/~rhall/mathforpoets.pdf http://www.hakank.org/comb/debruijn.cgi https://archive.org/stream/sanskritprosody00browgoog%23page/n44/mode/2up https://web.archive.org/web/20051202021442/http:/www.stefangeens.com/000435.html https://web.archive.org/web/20120212145748/http:/www.sju.edu/~rhall/mathforpoets.pdf https://web.archive.org/web/20140527202958/http:/lcni.uoregon.edu/~dow/Geek_art/Minimal_combinatorics/Minimal_arrays_containing_all_combinations.html https://web.archive.org/web/20141029120230/http:/202.41.82.144/rawdataupload/upload/insa/INSA_2/200059d2_123.pdf https://www.ams.org/journals/bull/1934-40-12/S0002-9904-1934-05988-3/S0002-9904-1934-05988-3.pdf http://chessprogramming.wikispaces.com/De+Bruijn+sequence http://www.macs.hw.ac.uk/~markl/Higgins.pdf http://202.41.82.144/rawdataupload/upload/insa/INSA_2/200059d2_123.pdf |
dbo:wikiPageID | 1565267 (xsd:integer) |
dbo:wikiPageLength | 31590 (xsd:nonNegativeInteger) |
dbo:wikiPageRevisionID | 1115875941 (xsd:integer) |
dbo:wikiPageWikiLink | dbr:Cambridge_University_Press dbr:Princeton_University_Press dbr:Python_(programming_language) dbr:Pāṇini dbr:Robot dbr:Sanskrit_prosody dbr:Eulerian_cycle dbr:Bitwise_operation dbr:De_Bruijn_graph dbr:De_Bruijn_torus dbc:Enumerative_combinatorics dbr:Permutation dbr:Personal_Identification_Number dbr:Indagationes_Mathematicae dbr:Integer_sequence dbr:Analysis_of_algorithms dbr:Mathematics dbr:Shift_register dbr:Functional_magnetic_resonance_imaging dbr:Gray_code dbr:Conjecture dbr:Equivalence_class dbr:Angle dbr:Alphabet_(computer_science) dbr:Stanford_University dbr:Subsequence dbr:Combinatorics dbr:Frank_Ruskey dbr:String_(computer_science) dbr:Linear-feedback_shift_register dbr:Finite_field dbc:Binary_sequences dbr:Nicolaas_Govert_de_Bruijn dbr:Normal_number dbr:Number_theory dbr:Discrete_Mathematics_(journal) dbr:Journal_of_Combinatorial_Theory dbr:Journal_of_Statistical_Physics dbr:Kees_Posthumus dbr:Rotary_encoder dbr:Mathematical_proof dbr:Hamiltonian_path dbr:Hash_table dbr:Addison–Wesley dbc:Articles_with_example_Python_(programming_language)_code dbr:Charles_Philip_Brown dbr:Karl_Popper dbr:L'Intermédiaire_des_Mathématiciens dbr:Automata_theory dbr:BEST_theorem dbr:Bulletin_of_the_American_Mathematical_Society dbr:Burrows–Wheeler_transform dbr:Pingala dbr:Mathematics_Magazine dbr:European_Journal_of_Combinatorics dbr:Lyndon_word dbr:Moser–de_Bruijn_sequence dbr:Simon_Stevin_(journal) dbr:Substring dbr:Superpermutation dbr:The_Logic_of_Scientific_Discovery dbr:Word_(data_type) dbr:N-sequence dbr:Cyclic_sequence dbr:Digital_door_lock dbr:File:BurrowsWheeler-_standard_permutation.svg dbr:File:De_Bruijn_binary_graph.svg dbr:File:De_Bruijn_sequence.svg dbr:File:De_Bruijn_sequence_10_4.svg dbr:File:De_bruijn_graph-for_binary_sequence_of_order_4.svg dbr:File:De_bruijn_torus_3x3.stl |
dbp:author1Link | Tatyana Pavlovna Ehrenfest (en) |
dbp:first | Tatyana (en) |
dbp:formalname | Lexicographically earliest binary de Bruijn sequences, B (en) |
dbp:last | de Bruijn (en) van Aardenne-Ehrenfest (en) |
dbp:name | Lexicographically smallest binary de Bruijn sequences (en) |
dbp:sequencenumber | A166315 (en) |
dbp:title | de Bruijn Sequence (en) |
dbp:urlname | deBruijnSequence (en) |
dbp:wikiPageUsesTemplate | dbt:= dbt:Cite_book dbt:Cite_journal dbt:Cite_web dbt:Distinguish dbt:Harvtxt dbt:Main_article dbt:MathWorld dbt:OEIS_el dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Tmath dbt:Val dbt:Anoto_paper_principle.svg dbt:Harvs dbt:Lowercase |
dbp:year | 1951 (xsd:integer) |
dct:subject | dbc:Enumerative_combinatorics dbc:Binary_sequences dbc:Articles_with_example_Python_(programming_language)_code |
rdf:type | owl:Thing yago:WikicatBinarySequences yago:WikicatSequencesAndSeries yago:Abstraction100002137 yago:Arrangement107938773 yago:Group100031264 yago:Ordering108456993 yago:Sequence108459252 yago:Series108457976 |
rdfs:comment | Eine De-Bruijn-Folge ist ein Wort eines Alphabets mit Symbolen mit folgender Eigenschaft: Jedes mögliche Wort der Länge gebildet aus den Symbolen in taucht als zusammenhängendes Teilwort von auf, und ist das kürzeste Wort mit dieser Eigenschaft. wird die Ordnung von genannt. Dabei werden verschiedene , die durch zyklische Vertauschung der Symbole auseinander hervorgehen, nicht unterschieden. Eine De-Bruijn-Folge enthält also alle Wörter der Länge aus Symbolen (in zusammenhängender Form) genau einmal, wobei das Wort zyklisch betrachtet wird, das heißt die Symbole am Ende dürfen mit denen am Anfang fortgesetzt werden, um ein Teilwort zu bilden. (de) En mathématiques, et notamment en combinatoire et en informatique théorique, une suite de de Bruijn ou un mot de de Bruijn est un mot circulaire ou collier particulier qui a la propriété de contenir toutes les sous-suites consécutives (ou facteurs) d'une longueur donnée une et une seule fois. Les suites sont nommées d'après le mathématicien néerlandais Nicolaas Govert de Bruijn qui a contribué à leur étude. (fr) Een debruijnrij is een begrip uit de combinatoriek. De debruijnrij is een cyclisch gelezen rij (de beginelementen van de rij komen na het laatste element terug) waarin, gegeven een groep van objecten, alle mogelijke rijtjes van lengte van deze objecten precies één keer als deelrij voorkomen. De rij heeft de lengte Er zijn verschillende debruijnrijen Debruijnrijen zijn vernoemd naar de Nederlandse wiskundige Nicolaas Govert de Bruijn. Hij onderzocht ze in een artikel dat in 1946 verscheen in de proceedings van de Koninklijke Nederlandse Akademie van Wetenschappen. (nl) Cykl de Bruijna rzędu n to cykliczny ciąg 0 i 1 długości w którym każdy podciąg kolejnych n elementów występuje dokładnie 1 raz. (pl) Послідовність де Брейна — циклічний порядок , елементи якого належать заданій скінченній множині (зазвичай розглядають множину ), такий, що всі його підпослідовності заданої довжини різні. Часто розглядаються періодичні послідовності з періодом , що містять різних підпослідовностей , — тобто такі періодичні послідовності, в яких будь-який відрізок довжини є послідовністю де Брейна з тими самими параметрами і . Цикли названо так на честь нідерландського математика Ніколаса де Брейна, який вивчав їх , хоча вони вивчалися й раніше. (uk) Последовательность де Брёйна — циклический порядок , элементы которого принадлежат заданному конечному множеству (обычно рассматривают множество ), такой, что все его подпоследовательности заданной длины различны. Часто рассматриваются периодические последовательности с периодом , содержащие различных подпоследовательностей , — то есть такие периодические последовательности, в которых любой отрезок длины является последовательностью де Брёйна с теми же параметрами и . Циклы названы по имени голландского математика Николаса де Брёйна, изучившего их в 1946 году, хотя они изучались и ранее. (ru) De Bruijnova posloupnost je pojem z kombinatoriky, podoboru matematiky. Pro zadaný řád n a zadanou abecedu o k prvcích se jedná o takovou 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 Počet různých de Bruijnových posloupností B(k,n) je . 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, a karetním kouzelnictví. (cs) In combinatorial mathematics, a de Bruijn sequence of order n on a size-k alphabet A is a cyclic sequence in which every possible length-n string on A occurs exactly once as a substring (i.e., as a contiguous subsequence). Such a sequence is denoted by B(k, n) and has length kn, which is also the number of distinct strings of length n on A. Each of these distinct strings, when taken as a substring of B(k, n), must start at a different position, because substrings starting at the same position are not distinct. Therefore, B(k, n) must have at least kn symbols. And since B(k, n) has exactly kn symbols, De Bruijn sequences are optimally short with respect to the property of containing every string of length n at least once. (en) Inom kombinatoriken är en k-när de Bruijn-sekvens B(k, n) av ordningen n en cyklisk sekvens till ett givet alfabet A med storleken k i vilken varje möjlig delsekvens av längden n uppträder en och endast en gång som på varandra följande tecken. Sekvensen är uppkallad efter den holländske matematikern Nicolaas Govert de Bruijn. Varje B(k, n) har längden kn. Det finns skilda de Bruijn-sekvenser B(k, n). (sv) |
rdfs:label | De Bruijnova posloupnost (cs) De-Bruijn-Folge (de) De Bruijn sequence (en) Suite de de Bruijn (fr) Debruijnrij (nl) Cykl de Bruijna (pl) Последовательность де Брёйна (ru) De Bruijn-sekvens (sv) Послідовність де Брейна (uk) |
owl:sameAs | freebase:De Bruijn sequence yago-res:De Bruijn sequence wikidata:De Bruijn sequence dbpedia-cs:De Bruijn sequence dbpedia-de:De Bruijn sequence dbpedia-fa:De Bruijn sequence dbpedia-fr:De Bruijn sequence dbpedia-he:De Bruijn sequence dbpedia-hu:De Bruijn sequence dbpedia-nl:De Bruijn sequence dbpedia-pl:De Bruijn sequence dbpedia-ru:De Bruijn sequence dbpedia-sv:De Bruijn sequence dbpedia-uk:De Bruijn sequence https://global.dbpedia.org/id/smey |
prov:wasDerivedFrom | wikipedia-en:De_Bruijn_sequence?oldid=1115875941&ns=0 |
foaf:depiction | wiki-commons:Special:FilePath/BurrowsWheeler-_standard_permutation.svg wiki-commons:Special:FilePath/De_Bruijn_binary_graph.svg wiki-commons:Special:FilePath/De_Bruijn_sequence.svg wiki-commons:Special:FilePath/De_Bruijn_sequence_10_4.svg wiki-commons:Special:FilePath/De_bruijn_graph-for_binary_sequence_of_order_4.svg |
foaf:isPrimaryTopicOf | wikipedia-en:De_Bruijn_sequence |
is dbo:knownFor of | dbr:Nicolaas_Govert_de_Bruijn dbr:Michael_Waterman |
is dbo:wikiPageDisambiguates of | dbr:De_Bruijn |
is dbo:wikiPageRedirects of | dbr:De_bruijn_sequence dbr:Shortest_random-like_sequence dbr:De_Bruijn_cycle dbr:De_Bruijn_sequences dbr:Ouroborean_ring |
is dbo:wikiPageWikiLink of | dbr:Rosetta_Code dbr:Sanskrit_prosody dbr:De_Bruijn_graph dbr:De_Bruijn_torus dbr:De_bruijn_sequence dbr:De_Bruijn dbr:Desert_Fireball_Network dbr:Index_of_combinatorics_articles dbr:Gray_code dbr:Sequence_assembly dbr:Torus dbr:Eulerian_path dbr:Find_first_set dbr:Nicolaas_Govert_de_Bruijn dbr:Normal_number dbr:Tatyana_Pavlovna_Ehrenfest dbr:Ehrenfeucht–Mycielski_sequence dbr:BEST_theorem dbr:Koorde dbr:Michael_Waterman dbr:Lyndon_word dbr:Scientific_phenomena_named_after_people dbr:Moser–de_Bruijn_sequence dbr:Nonlinear-feedback_shift_register dbr:Superpermutation dbr:Shortest_random-like_sequence dbr:De_Bruijn_cycle dbr:De_Bruijn_sequences dbr:Ouroborean_ring |
is dbp:knownFor of | dbr:Nicolaas_Govert_de_Bruijn |
is foaf:primaryTopic of | wikipedia-en:De_Bruijn_sequence |