✨Thước Golomb

Thước Golomb

frame|Thước Golomb có 4 vạch và chiều dài bằng 6. Thước này tối ưu và hoà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 và Babcock.

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. bậc 25 và bậc 26, công nhận những dự đoán trước đó về thước tối ưu. 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. 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. , 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.

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ó. 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.

Định nghĩa

Thước Golomb dưới dạng tập hợp

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

A = \left\{a_1,a_2,...,a_m\right\} \quad a_1 < a_2 <... < a_m

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

\forall i,j,k,l \in \left\{1,2,...,m\right\}, a_i-a_j=a_k-a_l \iff i=k \land j=l.

Bậc của thước Golomb là $m$ và chiều dài của thước là $a_m - a_1$ . Dạng chính tắc có $a_1 = 0$ và nếu $m > 2$ , $a_2 - a_1 < a$ m - a{m-1}. 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ố

Một đơn ánh

f:\left\{1,2,...,m\right\}\to\left\{0,1,...,n\right\}

với $f(1)=0$ và $f(m)=n$ là một thước Golomb khi và chỉ khi

\forall i,j,k,l \in \left\{1,2,...,m\right\}, f(i)-f(j)=f(k)-f(l) \iff i=k \land j=l.

Bậc của thước là $m$ và chiều dài của thước là $n$ . Dạng chính tắc có : $f(2)<f(m)-f(m-1)$ nếu $m>2$ .

Tối ưu

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

Lý thuyết thông tin/Sửa lỗi

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

Lựa chọn tần số radio

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 và trong không gian.

Vị trí đặt ăngten radio

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].

Phương pháp xây dựng

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

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

2pk+(k^2\,\bmod\,p),k\in[0,p-1]

Các thước Golomb tối ưu đã biết

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.

👁️ 1 | 🔗 | 💖 | ✨ | 🌍 | ⌚

💫 Thước Golomb

frame|Thước Golomb có 4 vạch và chiều dài bằng 6. Thước này _tối ưu_ và _hoà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

💫 Dãy Sidon

Trong lý thuyết số, một **dãy Sidon** (hay **tập hợp Sidon**), đặt theo tên của nhà toán học Hungary Simon Sidon, là một dãy các số tự nhiên _A_ = {_a_₀, _a_₁, _a_₂, ...} sao cho các tổng của hai

💫 Danh sách nhà toán học Do Thái

Đây là **danh sách các nhà toán học người Do Thái**, bao gồm các nhà toán học và các nhà thống kê học, những người đang hoặc đã từng là người Do Thái hoặc có