www.wikidata.uk-ua.nina.az

Послідовність де Брейна циклічний порядок a 1 a t displaystyle a 1 ldots a t елементи якого належать заданій скінченній

Послідовність де Брейна

Послідовність де Брейна — циклічний порядок , елементи якого належать заданій скінченній множині (зазвичай розглядають множину ), такий, що всі його підпослідовності заданої довжини різні.

Часто розглядаються періодичні послідовності з періодом , що містять різних підпослідовностей , — тобто такі періодичні послідовності, в яких будь-який відрізок довжини є послідовністю де Брейна з тими самими параметрами і .

Цикли названо так на честь нідерландського математика Ніколаса де Брейна, який вивчав їх 1946 році, хоча вони вивчалися й раніше.

Властивості ред.

Очевидно, що довжина (період) такого циклу не може перевищувати  — числа всіх різних векторів довжини з елементами з ; нескладно довести, що ця оцінка досягається. Цикли цієї максимально можливої довжини зазвичай називають циклами де Брейна (втім, іноді цей термін застосовують і до циклів меншої довжини).

При існують такі цикли де Брейна з довжиною, на одиницю меншою максимуму, які виражаються лінійними рекурентними співвідношеннями порядку  : так, при співвідношення породжує послідовності з періодом 7, наприклад 0010111001011100 … (цикл де Брейна 0010111). На основі таких послідовностей побудовано, зокрема, циклічний надлишковий код CRC32 (EDB88320).

Приклади ред.

Приклади циклів де Брейна для з періодом 2, 4, 8, 16:

  • 01 (містить підпослідовності 0 і 1)
  • 0011 (містить підпослідовності 00, 01, 11, 10)
  • 00010111 (000, 001, 010, 101, 011, 111, 110, 100)
  • 0000100110101111

Кількість циклів де Брейна ред.

Кількість циклів де Брейна з параметрами і є (окремий випадок теореми де Брейна — BEST-теорема[en], названа за прізвищами де Брейна, Тетяни Еренфест, Седріка Сміта і Вільяма Татта).

Граф де Брейна ред.

Існує зручна інтерпретація послідовностей і циклів де Брейна, заснована на так званому графі де Брейна — орієнтованому графі з вершинами, що відповідають різним наборам довжини з елементами з , у якому з вершини у вершину ребро веде в тому і тільки тому випадку, коли (); при цьому самому ребру можна зіставити набір довжини  : . Для такого графу ейлерові шляхи (ейлерові цикли), що не проходять двічі через одне й те саме ребро, відповідають послідовності (циклу) де Брейна з параметрами і , а гамільтонові шляхи (гамільтонові цикли), що не проходять двічі через одну і ту ж вершину, — послідовності (циклу) де Брейна з параметрами і .

Граф де Брейна широко застосовується в біоінформатиці в задачах складання геному.

Примітки ред.

  1. Якщо , то в циклічному порядку вибирається елемент з індексом
  2. de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764.
  3. Flye Sainte-Marie C. Question 48 // L'intermédiaire math. — 1894. — v. 1. — pp. 107—110.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Poslidovnist de Brejna ciklichnij poryadok a 1 a t displaystyle a 1 ldots a t elementi yakogo nalezhat zadanij skinchennij mnozhini zazvichaj rozglyadayut mnozhinu 0 1 k 1 displaystyle 0 1 ldots k 1 takij sho vsi jogo pidposlidovnosti a i 1 a i n displaystyle a i 1 ldots a i n 1 zadanoyi dovzhini n displaystyle n rizni Chasto rozglyadayutsya periodichni poslidovnosti z periodom T displaystyle T sho mistyat T displaystyle T riznih pidposlidovnostej a i 1 a i n displaystyle a i 1 ldots a i n tobto taki periodichni poslidovnosti v yakih bud yakij vidrizok dovzhini T n 1 displaystyle T n 1 ye poslidovnistyu de Brejna z timi samimi parametrami n displaystyle n i k displaystyle k Cikli nazvano tak na chest niderlandskogo matematika Nikolasa de Brejna yakij vivchav yih 1946 roci 2 hocha voni vivchalisya j ranishe 3 Zmist 1 Vlastivosti 2 Prikladi 3 Kilkist cikliv de Brejna 4 Graf de Brejna 5 PrimitkiVlastivosti red Ochevidno sho dovzhina period takogo ciklu ne mozhe perevishuvati k n displaystyle k n nbsp chisla vsih riznih vektoriv dovzhini n displaystyle n nbsp z elementami z 0 1 k 1 displaystyle 0 1 ldots k 1 nbsp neskladno dovesti sho cya ocinka dosyagayetsya Cikli ciyeyi maksimalno mozhlivoyi dovzhini zazvichaj nazivayut ciklami de Brejna vtim inodi cej termin zastosovuyut i do cikliv menshoyi dovzhini Pri k 2 displaystyle k 2 nbsp isnuyut taki cikli de Brejna z dovzhinoyu na odinicyu menshoyu maksimumu yaki virazhayutsya linijnimi rekurentnimi spivvidnoshennyami poryadku n displaystyle n nbsp tak pri n 3 displaystyle n 3 nbsp spivvidnoshennya x n x n 2 x n 3 mod 2 displaystyle x n x n 2 x n 3 pmod 2 nbsp porodzhuye poslidovnosti z periodom 7 napriklad 0010111001011100 cikl de Brejna 0010111 Na osnovi takih poslidovnostej pobudovano zokrema ciklichnij nadlishkovij kod CRC32 EDB88320 Prikladi red Prikladi cikliv de Brejna dlya k 2 displaystyle k 2 nbsp z periodom 2 4 8 16 01 mistit pidposlidovnosti 0 i 1 0011 mistit pidposlidovnosti 00 01 11 10 00010111 000 001 010 101 011 111 110 100 0000100110101111Kilkist cikliv de Brejna red Kilkist cikliv de Brejna z parametrami n displaystyle n nbsp i k displaystyle k nbsp ye k k n 1 k n displaystyle k k n 1 k n nbsp okremij vipadok teoremi de Brejna BEST teorema en nazvana za prizvishami de Brejna Tetyani Erenfest Sedrika Smita i Vilyama Tatta Graf de Brejna red Isnuye zruchna interpretaciya poslidovnostej i cikliv de Brejna zasnovana na tak zvanomu grafi de Brejna oriyentovanomu grafi z k n displaystyle k n nbsp vershinami sho vidpovidayut k n displaystyle k n nbsp riznim naboram dovzhini n displaystyle n nbsp z elementami z 0 1 k 1 displaystyle 0 1 ldots k 1 nbsp u yakomu z vershini x 1 x n displaystyle x 1 ldots x n nbsp u vershinu y 1 y n displaystyle y 1 ldots y n nbsp rebro vede v tomu i tilki tomu vipadku koli x i y i 1 displaystyle x i y i 1 nbsp i 2 n displaystyle i 2 ldots n nbsp pri comu samomu rebru mozhna zistaviti nabir dovzhini n 1 displaystyle n 1 nbsp x 1 x n y n x 1 y 1 y n displaystyle x 1 ldots x n y n x 1 y 1 ldots y n nbsp Dlya takogo grafu ejlerovi shlyahi ejlerovi cikli sho ne prohodyat dvichi cherez odne j te same rebro vidpovidayut poslidovnosti ciklu de Brejna z parametrami n 1 displaystyle n 1 nbsp i k displaystyle k nbsp a gamiltonovi shlyahi gamiltonovi cikli sho ne prohodyat dvichi cherez odnu i tu zh vershinu poslidovnosti ciklu de Brejna z parametrami n displaystyle n nbsp i k displaystyle k nbsp Graf de Brejna shiroko zastosovuyetsya v bioinformatici v zadachah skladannya genomu Primitki red Yaksho j gt t displaystyle j gt t nbsp to v ciklichnomu poryadku vibirayetsya element z indeksom j mod t displaystyle j bmod t nbsp de Bruijn N G A combinatorial problem Koninklijke Nederlandse Akademie v Wetenschappen 1946 v 49 pp 758 764 Flye Sainte Marie C Question 48 L intermediaire math 1894 v 1 pp 107 110 Otrimano z https uk wikipedia org w index php title Poslidovnist de Brejna amp oldid 38320716