Règle de Golomb

Dans les mathématiques , une règle de Golomb de , appelée pour le Solomon W. Golomb et découverte indépendamment par Sidon et Babcock, est un ensemble de marques aux positions de nombre entier le long d'une règle imaginaire tels qu'aucune deux paires de marques ne sont la même distance à part. Le nombre de marques sur la règle est son ordre , et la plus grande distance entre deux de ses marques est sa longueur . La traduction et la réflexion d'une règle de Golomb sont considérées insignifiante, ainsi la plus petite marque est d'habitude mise à 0 et à la prochaine marque au plus petit de ses deux valeurs possibles.

Il n'y a aucune condition qu'une règle de Golomb peut mesurer le toutes les distances de jusqu'à sa longueur, mais s'il fait, ce s'appelle une règle parfaite du Golomb. On l'a montré qu'aucune règle parfaite de Golomb n'existe pour cinq ou plus fait tic tac. Une règle de Golomb est le optimal si aucune règle plus courte de Golomb du même ordre n'existe. La création des règles de Golomb est facile, mais la conclusion des règles optimales de Golomb pour un ordre spécifique est informatique très provocante.net a accompli massivement distribuée une recherche parallèle des règles optimales d'order-24 Golomb, confirmant le candidat suspecté, et une recherche des règles order-25 optimales est actuellement en cours.

Une utilisation pratique des règles de Golomb est dans la conception des antennes par radio à réseaux de dipoles du telles que des antennes des radiotélescopes dans une règle de Golomb que la configuration peut souvent être vue aux emplacements de cellules de

Actuellement, la complexité de trouver les règles optimales de Golomb de la longueur arbitraire n est inconnue, mais on pense qu'est un problème NP-dur du .

Règles optimales connues de Golomb

La table suivante contient toutes les règles optimales connues de Golomb (à l'exclusion des règles qui sont équivalentes à un de ces derniers avec des marques à l'envers l'ordre). La table est complète jusques et y compris l'ordre 24. width=" bgcolor=" de style=" de style=" de style=" de style=" de align=" de align=" de align=" de style=" de style=" de style=" de align=" de style=" de style=" de style=" de style=" de style=" de style=" de style=" de style=" de style=" de style=" de style=" de style=" de style=" de

order bgcolor=" de	length bgcolor=" de	marks
1 style=" de	0 style=" de	0
2 style=" de	1 style=" de	0 1
3 style=" de	3 style=" de	0 1 3
4 style=" de	6 style=" de	0 1 4 6
5 align=" de	11 style=" de	0 1 4 9 11 0 2 7 8 11
6 align=" de	17 style=" de	0 1 4 10 12 17 0 1 4 10 15 17 0 1 8 11 13 17 0 1 8 12 14 17
7 align=" de	25 style=" de	0 1 4 10 18 23 25 0 1 7 11 20 23 25 0 1 11 16 19 23 25 0 2 3 10 16 21 25 0 2 7 13 21 22 25
8 style=" de	34 style=" de	0 1 4 9 15 22 32 34
9 style=" de	44 style=" de	0 1 5 12 25 27 35 41 44
10 style=" de	55 style=" de	0 1 6 10 23 26 34 41 53 55
11 align=" de	72 style=" de	0 1 4 13 28 33 47 54 64 70 72 0 1 9 19 24 31 52 56 58 69 72
12 style=" de	85 style=" de	0 2 6 24 29 40 43 55 68 75 76 85
13 style=" de	106 style=" de	0 2 5 25 37 43 59 70 85 89 98 99 106
14 style=" de	127 style=" de	0 4 6 20 35 52 59 77 78 86 89 99 122 127
15 style=" de	151 style=" de	0 4 20 30 57 59 62 76 100 111 123 136 144 145 151
16 style=" de	177 style=" de	0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177
17 style=" de	199 style=" de	0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199
18 style=" de	216 style=" de	0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216
19 style=" de	246 style=" de	0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246
20 style=" de	283 style=" de	0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283
21 style=" de	333 style=" de	0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333
22 style=" de	356 style=" de	0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356
23 style=" de	372 style=" de	0 3 7 17 61 66 91 99 114 159 171 199 200 226 235 246 277 316 329 348 350 366 372
24 style=" de	425 style=" de	0 9 33 37 38 97 122 129 140 142 152 191 205 208 252 278 286 326 332 353 368 384 403 425

La recherche des règles optimales de Golomb de l'ordre 25 actuellement en cours par le Distributed.net ( en date de 2007 ) est prévue pour confirmer la règle suivante, qui a été découverte en 1984 par M. width="

bgcolor=" de style=" de

order bgcolor=" de	length bgcolor=" de	marks
25 style=" de	480 style=" de	0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480

Voir également

Rangée de Costas de
Règle clairsemée
Règle parfaite

Random links: