| 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)
|
| 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)
|
