Правитель Голомба

Линейка Голомба Определение линейки Голомба Линейка Голомба — это набор меток, расположенных на целых позициях вдоль линейки.   Никакие две пары […]

Линейка Голомба

  • Определение линейки Голомба

    • Линейка Голомба — это набор меток, расположенных на целых позициях вдоль линейки.  
    • Никакие две пары меток не находятся на одинаковом расстоянии друг от друга.  
    • Количество меток — это порядок линейки, а наибольшее расстояние между метками — её длина.  
  • История и свойства

    • Линейка Голомба названа в честь Соломона У. Голомба и независимо открыта Сайдоном и Бэбкоком.  
    • Софи Пикар сформулировала теорему о конгруэнтности двух линейок Голомба с одинаковым заданным расстоянием.  
    • Идеальной линейки Голомба для пяти и более отметок не существует.  
    • Линейка Голомба является оптимальной, если не существует более короткой линейки того же порядка.  
  • Сложность поиска

    • Создание линейок Голомба несложно, но поиск оптимальных линейок очень сложен.  
    • Распределенный.net завершила поиск оптимальных линейок с 24-го по 28-й порядок.  
    • Сложность поиска оптимальных линейок произвольного порядка неизвестна, но задачи, связанные с построением линейки Голомба, NP-сложны.  
  • Практическое применение

    • Линейки Голомба используются в теории информации и исправлении ошибок.  
    • Применяются при выборе радиочастот и размещении радиоантенн.  
    • Используются в многодиапазонных трансформаторах тока.  
  • Методы построения

    • Разработаны методы построения асимптотически оптимальных линейок Голомба.  
    • Конструкция Эрдеш–Турана дает линейку Голомба для каждого нечетного простого числа.  
  • Известные оптимальные линейки

    • Приведены все известные оптимальные линейки Голомба, кроме тех, у которых отметки расположены в обратном порядке.  
    • Первые четыре линейки идеальны.  
    • Оптимальные линейки были известны до определенной даты, когда было доказано, что все остальные линейки не были меньше.  

Полный текст статьи:

Правитель Голомба

Оставьте комментарий

Прокрутить вверх