Тор Де Брейна
В комбинаторной математике тор Де Брейна , названный в честь голландского математика Николааса Говерта де Брейна , представляет собой массив символов алфавита (часто только 0 и 1), который содержит каждую возможную матрицу заданных размеров m × n ровно один раз. Это тор, потому что при поиске матриц его ребра считаются закругленными. Его название происходит от последовательности Де Брейна , которую можно считать частным случаем, когда n = 1 (одно измерение).
Один из основных открытых вопросов, касающихся торов Де Брейна, заключается в том, можно ли построить тор Де Брейна для определенного размера алфавита для заданных m и n . Известно, что они всегда существуют при n = 1 , поскольку тогда мы просто получаем последовательности Де Брейна, которые существуют всегда. Также известно, что «квадратные» торы существуют всегда, когда m = n и четно (в нечетном случае полученные торы не могут быть квадратными). [1] [2] [3]
Наименьший возможный двоичный «квадрат» тора де Брёйна, изображенный вверху справа, обозначенный как (4,4;2,2) 2 тор де Брёйна (или просто B 2 ), содержит все 2×2 двоичные матрицы .
BБ2
[ редактировать ]
Кроме «переноса», «инверсии» (замены нулей и единиц) и «поворота» (на 90 градусов), никакие другие (4,4;2,2) 2 тора де Брейна невозможны – это можно показать при полном осмотре. из всех 2 16 двоичные матрицы (или подмножество, удовлетворяющее ограничениям, таким как равное количество нулей и единиц). [4]
Тор можно развернуть, повторив n −1 строк и столбцов. Все подматрицы n × n без переноса, например, заштрихованная желтым цветом, затем образуют полный набор:
1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1 1
Более крупный пример: B 4
[ редактировать ]
В сетке выделены некоторые матрицы размером 4×4, в том числе матрицы с нулями и единицами в верхнем поле.
Пример следующего возможного двоичного «квадрата» тора де Брейна (256,256;4,4) 2 (сокращенно B 4 ) был явно построен. [5]
На изображении справа показан пример тора/массива (256,256;4,4) 2 де Брёйна, где нули закодированы как белые пиксели, а единицы – как красные пиксели соответственно.
Двоичные торы де Брёйна большего размера
[ редактировать ]Статья, в которой был построен пример тора (256,256;4,4) 2 де Брейна, содержала более 10 страниц двоичного кода, несмотря на уменьшенный размер шрифта, требующий трех строк на строку массива.
Последующий возможный двоичный тор де Брейна, содержащий все двоичные матрицы 6×6 , будет иметь 2 36 = 68 719 476 736 записей, что дает квадратный массив размером 262 144×262 144 , обозначаемый (262144,262144;6,6) 2 тором де Брейна или просто B 6 . Ее можно легко сохранить на компьютере — при печати с пикселями со стороной 0,1 мм такая матрица потребует площади примерно 26×26 квадратных метров .
Объект B 8 , содержащий все двоичные 8×8 матрицы и обозначенный (4294967296,4294967296;8,8) 2 , имеет в общей сложности 2 64 ≈ 18.447×10 18 записи: для хранения такой матрицы потребуется 18,5 экзабайт или 2,3 эксабайта памяти. В приведенном выше масштабе его площадь составит 429×429 квадратных километров .
Следующая таблица иллюстрирует суперэкспоненциальный рост.
| н | Клетки в подматрица = п 2 | Количество подматрицы = 2 н 2 | Б н сторона длина = 2 ( н 2 /2) |
|---|---|---|---|
| 2 | 4 | 16 | 4 |
| 4 | 16 | 65 536 | 256 |
| 6 | 36 | 68 719 476 736 | 262 144 |
| 8 | 64 | ~1.84 × 10 19 | ~4.29 × 10 9 |
| 10 | 100 | ~1.27 × 10 30 | ~1.13 × 10 15 |
| 12 | 144 | ~2.23 × 10 43 | ~4.72 × 10 21 |
| 14 | 196 | ~1.00 × 10 59 | ~3.17 × 10 29 |
| 16 | 256 | ~1.16 × 10 77 | ~3.40 × 10 38 |
| 18 | 324 | ~3.42 × 10 97 | ~5.85 × 10 48 |
| 20 | 400 | ~2.60 × 10 120 | ~1.61 × 10 60 |
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Фан, Коннектикут; Фан, С.М.; Ма, СЛ; Сиу, МК (1985). «О массивах де Брейна». Арс Комбинатория А. 19 : 205–213.
- ^ Чанг, Ф.; Диаконис, П.; Грэм, Р. (1992). «Универсальные циклы для комбинаторных структур» . Дискретная математика . 110 (1): 43–59. дои : 10.1016/0012-365x(92)90699-g .
- ^ Джексон, Брэд; Стивенс, Бретт; Херлберт, Гленн (сентябрь 2009 г.). «Проблемы исследования кодов Грея и универсальных циклов» . Дискретная математика . 309 (17): 5341–5348. дои : 10.1016/j.disc.2009.04.002 .
- ^ Эгген, Бернд Р. (1990). «Бинаторикс Б2». Частное общение .
- ^ Шиу, Вай-Чи (1997). «Декодирование массивов де Брейна, построенных методом ФФМС». Арс Комбинатория . 47 (17): 33–48.