Приветствую Вас, уважаемые Читатели! Сегодня мы поговорим об очередном случае, когда абстрактная математика находит своё применение в большом количестве практических ситуаций.
Типичная линейка имеет множество равномерно расположенных отметок. Однако она крайне неэффективна. Например, расстояние длиной 1 см можно измерить несколькими способами на этой линейке. Расстояние между соседними большими метками на линейке равно 1, поэтому его можно измерить двенадцатью избыточными способами.
Аналогично, существует несколько способов измерения расстояния в 2 см и 3 см … ... Возможно ли создать более эффективную линейку? Давайте разберемся!
Линейка Голомба
Итак, линейка Голомба названа в честь Соломона Голомба - американского математика, который внёс весомый вклад в теорию кодирования, а еще вдохновил российского программиста Алексея Пажитнова на создание "Тетриса".
Сама "линейка", конечно, виртуальная и представляет собой набор неотрицательных чисел, наделенных одним замечательным свойством: разница между любыми двумя числами, отложенным на линейке уникальна.
Количество отметок на линейке - это ее порядок, а наибольшее расстояние между двумя отметками - это ее длина. Таким образом, на рисунке выше мы видим линейку 4-го порядка и длиной 6.
Эта же линейка имеет еще два замечательных свойства: оптимальности и идеальности.
Идеальность заключается в том, что линейка может измерить все расстояния вплоть до ёё собственной длины (1,2,3,4,5,6).
Оптимальность заключается в том, что не существует более короткой линейки этого же порядка.
Как построить линейку Голомба ?
Существует несколько методов, которые позволяют это сделать, да и данная проблема алгоритмически исследована вдоль и поперек. Есть и частные методики, например, Пол Эрдеш предложил такую формулу, которая создает линейку Голомба для простых чисел:
Изобразив эти числа на прямой получим попарно разные расстояния между числами:
Конечно, до оптимальности и уж тем более до идеальности ( [0,1,4,6] - наибольшая идеальная линейка) этому представителю очень далеко. Вообще оптимальная линейка пятого порядка имеет вид [0,1,4,9,11] или [0,2,7,8,11].
Ах да, если из линейки [0,1,4,6] получить линейку [1,2,5,7] путем сдвига на одну единицу, мы получаем т.н. эквивалентную линейку, которая ничего нового не несёт.
И здесь скрывается главная сложность связанная с линейками Голомба - это доказательство их оптимальности, связанно с поистине колоссальными вычислениями. Например, нижу приведена оптимальная линейка 6-го порядка длины 17:
С увеличением порядка сложность, понятное дело, возрастает. Ведь недостаточно доказать, что все попарные расстояния различны (их не так много n*(n-1)/2, где n - количество делений), но надо показать, что данная линейка самая короткая.
На данный момент известны линейки Голомба до 150-го порядка, однако оптимальность доказана только для линеек порядка, не превышающего 28. Для этого понадобилось 8,5 лет, а также усилия 65000 добровольцев из 80 стран мира! Всё это для того, чтобы получить ряд чисел:
0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553 585
С оптимальностью понятно, но линейки Голомба также характеризуются количество расстояний, которые они не могут измерить:
Видно, например, что оптимальной линейкой Голомба с 26 метками можно измерить числа примерно до 300, при этом почти 150 первых чисел можно измерить все, без пропусков.
Применение и источники
Линейки больших порядков представляют, скорее, теоретический интерес, в то время как практическое применение находят линейки 4-10 порядков.
- Очень интересный материал, в котором автор описал "на пальцах" применение линейки Голомба для радиолокации атмосферных неоднородностей.
- Линейки используются в теории оптимального приёма для уменьшения интермодуляционных помех - оригинал статьи.
- Здесь - краткое описание и исторические моменты поиска линеек Голомба.
- Здесь - находится препринт статьи на английском языке по применению линеек в радарах SuperDarn, предназначенных для изучения ионосферы.
- Еще есть материалы о примении в теории кодирования (все платные буржуйские ресурсы) и неподтвержденная информация о построении на основе линеек понижающих трансформаторов.