Thước Golomb

Bách khoa toàn thư mở Wikipedia
Buớc tưới chuyển hướng Bước tới tìm kiếm
Thước Golomb có 4 vạch và chiều dài bằng 6. Thước này tối ưuhoàn hảo.

Trong toán học, thước Golomb là một tập hợp các vạch ở vị trí nguyên trên một thước thẳng sao cho không có hai cặp vạch nào đo cùng một khoảng cách. Số vạch của thước gọi là bậc, và khoảng cách giữa hai vạch xa nhau nhất gọi là chiều dài. Tịnh tiến và lấy đối xứng thước Golomb được coi là những biến đổi tầm thường, nên ta thường quy ước vạch nhỏ nhất nằm ở 0 và vạch thứ hai nằm ở vị trí nhỏ hơn trong số hai vị trí có thể (tùy vào việc có lấy đối xứng hay không).

Thước Golomb được đặt theo tên của Solomon W. Golomb và được phát hiện một cách độc lập bởi Sidon[1] và Babcock.[2]

Thước Golomb không nhất thiết phải đo được tất cả các khoảng cách nhỏ hơn hoặc bằng chiều dài của nó, nhưng khi nó có tính chất đó, nó được gọi là thước Golomb hoàn hảo. Người ta đã chứng minh được rằng không tồn tại thước Golomb hoàn hảo với ít nhất năm vạch.[3] Một thước Golomb là tối ưu nếu không tồn tại thước Golomb nào ngắn hơn có cùng bậc. Tạo một thước Golomb không khó, nhưng tìm thước Golomb tối ưu là một việc đòi hỏi nhiều công sức tính toán. Distributed.net đã hoàn thành quá trình tìm kiếm song song để tìm ra thước tối ưu bậc 24,[4] bậc 25[5] và bậc 26[6][7], công nhận những dự đoán trước đó về thước tối ưu.[8][9] Distributed.net cũng có kế hoạch tìm ra thước Golomb tối ưu bậc 27 và bậc 28. Tuy nhiên vì đã có một thuật toán cải tiến nên ước lượng thời gian thực hiện dự án này sẽ không lâu như những dự án trước.[10] Distributed.net đang tìm kiếm thước tối ưu bậc 27; vào tháng 5 năm 2009, ước lượng thời gian đến khi tìm ra nó là 7 năm.[11] Tính đến tháng 1 năm 2012, 47% công việc tính toán đã được hoàn thành sau 1063 ngày (2.9 năm) làm việc.[12]

Hiện nay vẫn chưa rõ độ phức tạp tính toán của việc tìm ra thước tối ưu bậc n (trong đó n được cho dưới dạng nhất phân). Đã từng có những dự đoán nó là một bài toán NP-khó.[3] Có những bài toán có liên hệ đến việc xây dựng thước Golomb được chứng minh là NP-khó, nhưng người ta cũng nhấn mạnh rằng không có bài toán NP-đầy đủ đã biết nào có dạng tương tự như việc tìm thước Golomb tối ưu.[13]

Định nghĩa[sửa | sửa mã nguồn]

Thước Golomb dưới dạng tập hợp[sửa | sửa mã nguồn]

Một tập hợp số nguyên

là một thước Golomb khi và chỉ khi

[14]

Bậc của thước Golomb là chiều dài của thước là . Dạng chính tắc và nếu , . Có thể thu được dạng đó bằng cách thực hiện phép tịnh tiến và lấy đối xứng.

Thước Golomb dưới dạng hàm số[sửa | sửa mã nguồn]

Một đơn ánh

với là một thước Golomb khi và chỉ khi

[15]:236

Bậc của thước là chiều dài của thước là . Dạng chính tắc có

nếu .

Tối ưu[sửa | sửa mã nguồn]

Thước Golomb bậc và chiều dài n có thể là tối ưu theo một trong hai tiêu chuẩn sau:[15]:237

  • trù mật tối ưu, nếu có m lớn nhất cho một giá trị n cố định
  • ngắn tối ưu, nếu có n nhỏ nhất cho một giá trị m cố định

Thuật ngữ thước Golomb tối ưu thường được dùng để chỉ loại thứ hai.

Ứng dụng thực tiễn[sửa | sửa mã nguồn]

Ví dụ một phòng họp với các ngăn với kích thước phỏng theo thước Golomb [0, 2, 7, 8, 11], nên có thể được cấu hình ở 10 kích thước khác nhau.[16]

Lý thuyết thông tin/Sửa lỗi[sửa | sửa mã nguồn]

Thước Golomb được dùng trong lý thuyết thông tin, cụ thể là trong mã sửa lỗi.[17]

Lựa chọn tần số radio[sửa | sửa mã nguồn]

Thước Golomb được dùng cho việc lựa chọn tần số radio để giảm ảnh hưởng của nhiễu biến điệu tương hỗ trong cả trường hợp gần mặt đất[18] và trong không gian[19].

Vị trí đặt ăngten radio[sửa | sửa mã nguồn]

Thước Golomb được dùng trong thiết kế của mảng pha của ăngten vô tuyến, chẳng hạn như trong kính thiên văn vô tuyến. Ở các điểm thu phát sóng, các ăngten thường nằm ở vị trí như trong thước Golomb [0,1,4,6].[Còn mơ hồ ]

Phương pháp xây dựng[sửa | sửa mã nguồn]

Có nhiều phương thức xây dựng thước Golomb tiệm cận tối ưu.

Phương thức xây dựng của Erdős–Turan[sửa | sửa mã nguồn]

Cách xây dựng dưới đây của Paul ErdősPál Turán xây dựng được thước Golomb với mọi số nguyên tố lẻ p.[20]

Các thước Golomb tối ưu đã biết[sửa | sửa mã nguồn]

Bảng dưới đây chứa tất cả các thước Golomb tối ưu đã biết, ngoại trừ ảnh đối xứng của chúng. Bốn thước đầu tiên là hoàn hảo.

Bậc Chiều dài Các vạch
1 0 0
2 1 0 1
3 3 0 1 3
4 6 0 1 4 6
5 11 0 1 4 9 11
0 2 7 8 11
6 17 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 25 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 34 0 1 4 9 15 22 32 34
9 44 0 1 5 12 25 27 35 41 44
10 55 0 1 6 10 23 26 34 41 53 55
11 72 0 1 4 13 28 33 47 54 64 70 72
0 1 9 19 24 31 52 56 58 69 72
12 85 0 2 6 24 29 40 43 55 68 75 76 85
13 106 0 2 5 25 37 43 59 70 85 89 98 99 106
14 127 0 4 6 20 35 52 59 77 78 86 89 99 122 127
15 151 0 4 20 30 57 59 62 76 100 111 123 136 144 145 151
16 177 0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177
17 199 0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199
18 216 0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216
19 246 0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246
20 283 0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283
21 333 0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333
22 356 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356
23 372 0 3 7 17 61 66 91 99 114 159 171 199 200 226 235 246 277 316 329 348 350 366 372
24 425 0 9 33 37 38 97 122 129 140 142 152 191 205 208 252 278 286 326 332 353 368 384 403 425
25 480 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
26 492 0 1 33 83 104 110 124 163 185 200 203 249 251 258 314 318 343 356 386 430 440 456 464 475 487 492

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Sidon, S. (1932), “Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen”, Mathematische Annalen 106: 536–539 
  2. ^ Babcock, Wallace C. (1953), “Intermodulation Interference in Radio Systems/Frequency of Occurrence and Control by Channel Selection”, Bell System Technical Journal 31: 63–73 
  3. ^ a ă “Modular and Regular Golomb Rulers”. 
  4. ^ “stats.distributed.net - OGR-24 Overall Project Stats”. Truy cập ngày 27 tháng 3 năm 2008. 
  5. ^ “stats.distributed.net - OGR-25 Overall Project Stats”. Truy cập ngày 22 tháng 9 năm 2008. 
  6. ^ “distributed.net: staff blogs – bovine”. Truy cập 7 tháng 10 năm 2015. 
  7. ^ “distributed.net: Projects”. Truy cập 7 tháng 10 năm 2015. 
  8. ^ “distributed.net -.plan archives”. Truy cập ngày 27 tháng 3 năm 2008. 
  9. ^ “distributed.net -.plan archives 2”. Truy cập ngày 26 tháng 10 năm 2008. 
  10. ^ “distributed.net: staff blogs – 2008 – October – 26”. Truy cập 7 tháng 10 năm 2015. 
  11. ^ bovine's plan, 24-Feb-2009 17:26
  12. ^ OGR-27 / Overall Project Stats
  13. ^ C. Meyer, P.A. Papakonstantinou, “On the Complexity of Constructing Golomb Rulers”. , Discrete Applied Mathematics
  14. ^ Dimitromanolakis, Apostolos. “Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers” (PDF). Truy cập ngày 20 tháng 12 năm 2009. 
  15. ^ a ă Drakakis, Konstantinos (2009). “A Review Of The Available Construction Methods For Golomb Rulers”. Advances in Mathematics of Communications 3 (3): 235–250. doi:10.3934/amc.2009.3.235. 
  16. ^ Paul Erdos and P. Turan. "On a problem of Sidon in additive number theory, and on some related problems," J. London Math. Soc, 16:212--215, 1941
  17. ^ “A class of binary recurrent codes with limited error propagation” (tóm tắt). Truy cập ngày 14 tháng 3 năm 2011. 
  18. ^ “Intermodulation Interference in Radio Systems” (trích dẫn). Truy cập ngày 14 tháng 3 năm 2011. 
  19. ^ “Carrier frequency assignment for nonlinear repeaters” (tóm tắt). Bibcode:1977COMTR...7..227F. 
  20. ^ Erdős, Paul; Turán, Pál (1941). “On a problem of Sidon in additive number theory and some related problems”. Journal of the London Mathematical Society 16 (4): 212–215. doi:10.1112/jlms/s1-16.4.212. 

Liên kết ngoài[sửa | sửa mã nguồn]