Голомбов лењир

Голомбов лењир реда 4 и дужине 6. Овај лењир је и оптималан и савршен.

Голомбов лењир, који је добио име по Соломону В. Голомбу, је скуп ознака на целобројним позицијама дуж имагинарног лењира, таквих да ниједна два пара ознака нису на подједнакој раздаљини. Број ознака на лењиру представља његов ред, а највећа раздаљина између две ознаке је његова дужина. Транслација и рефлексија Голомбовог лењира је тривијална, па се обично најмања ознака поставља на 0 а следећа на мању од њене две могуће позиције.

Није обавезно да Голомбов лењир буде у могућности да да мери све раздаљине од 0 до своје дужине, али ако је у стању, онда је то савршени Голомбов лењир. Доказано је да не постоји савршен Голомбов лењир реда већег од четири. Голомбов лењир је оптималан ако непостоји краћи Голомбов лењир истог реда. Прављење Голомбовог лењира је лако, али налажење оптималног лењира датог реда је рачунски веома захтеван процес. Пројекат Distributed.net је завршио дистрибуирану паралелну потрагу за оптималним Голомбовим лењирима реда 24, потврдивши претпостављеног кандидата, а тренутно траје потрага за оптималним лењиром реда 25.

Једна практична примена Голомбових лењира је у дизајну радио антена.

Тренутно није позната комплексност налажења оптималног Голомбовог лењира произвољне дужине, али се верује да спада у ред НП-тешких проблема.[1]

други језици
Deutsch: Golomb-Lineal
English: Golomb ruler
español: Regla de Golomb
français: Règle de Golomb
日本語: ゴロム定規
Nederlands: Golomb-liniaal
svenska: Golomblinjal
Tiếng Việt: Thước Golomb