Линейка Голомба
-
Определение линейки Голомба
- Линейка Голомба — это набор меток, расположенных на целых позициях вдоль линейки.
- Никакие две пары меток не находятся на одинаковом расстоянии друг от друга.
- Количество меток — это порядок линейки, а наибольшее расстояние между метками — её длина.
-
История и свойства
- Линейка Голомба названа в честь Соломона У. Голомба и независимо открыта Сайдоном и Бэбкоком.
- Софи Пикар сформулировала теорему о конгруэнтности двух линейок Голомба с одинаковым заданным расстоянием.
- Идеальной линейки Голомба для пяти и более отметок не существует.
- Линейка Голомба является оптимальной, если не существует более короткой линейки того же порядка.
-
Сложность поиска
- Создание линейок Голомба несложно, но поиск оптимальных линейок очень сложен.
- Распределенный.net завершила поиск оптимальных линейок с 24-го по 28-й порядок.
- Сложность поиска оптимальных линейок произвольного порядка неизвестна, но задачи, связанные с построением линейки Голомба, NP-сложны.
-
Практическое применение
- Линейки Голомба используются в теории информации и исправлении ошибок.
- Применяются при выборе радиочастот и размещении радиоантенн.
- Используются в многодиапазонных трансформаторах тока.
-
Методы построения
- Разработаны методы построения асимптотически оптимальных линейок Голомба.
- Конструкция Эрдеш–Турана дает линейку Голомба для каждого нечетного простого числа.
-
Известные оптимальные линейки
- Приведены все известные оптимальные линейки Голомба, кроме тех, у которых отметки расположены в обратном порядке.
- Первые четыре линейки идеальны.
- Оптимальные линейки были известны до определенной даты, когда было доказано, что все остальные линейки не были меньше.