1236214
Thước Golomb
https://vi.wikipedia.org/wiki?curid=1236214
Title: Thước Golomb
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. 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, 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.