Siêu đồ thị tiết lộ giải pháp cho một vấn đề 50 tuổi

Cài win online từ xa

Cài Win online

Mục tiêu ở đây là tìm ra các tam giác nằm trên các đường thẳng này sao cho các tam giác đó thỏa mãn hai yêu cầu: Thứ nhất, không có hai tam giác nào có chung một cạnh. (Các hệ thống đáp ứng yêu cầu này được gọi là hệ thống ba Steiner.) Và thứ hai, đảm bảo rằng mọi tập hợp con tam giác nhỏ đều sử dụng một số lượng nút đủ lớn.

Cách các nhà nghiên cứu đã làm điều này có lẽ được hiểu rõ nhất với một phép loại suy.

Nói rằng thay vì tạo hình tam giác từ các cạnh, bạn đang xây nhà từ những viên gạch Lego. Một số tòa nhà đầu tiên bạn làm rất xa hoa, với kết cấu gia cố và trang trí phức tạp. Khi bạn đã hoàn thành những việc này, hãy đặt chúng sang một bên. Chúng sẽ đóng vai trò như một “chất hấp thụ” —một loại kho dự trữ có cấu trúc.

Bây giờ hãy bắt đầu tạo các tòa nhà từ những viên gạch còn lại của bạn, tiếp tục mà không cần lên kế hoạch nhiều. Khi nguồn cung cấp Legos của bạn cạn kiệt, bạn có thể thấy mình với một số viên gạch lạc chỗ, hoặc những ngôi nhà không chắc chắn về mặt cấu trúc. Nhưng vì các tòa nhà hấp thụ quá cũ và được gia cố, bạn có thể nhổ một số viên gạch ở đây và ở đó và sử dụng chúng mà không gặp phải thảm họa.

Trong trường hợp của hệ thống ba Steiner, bạn đang cố gắng tạo ra các hình tam giác. Trong trường hợp này, bộ hấp thụ của bạn là một bộ sưu tập các cạnh được lựa chọn cẩn thận. Nếu bạn thấy mình không thể sắp xếp phần còn lại của hệ thống thành hình tam giác, bạn có thể sử dụng một số cạnh dẫn vào bộ hấp thụ. Sau đó, khi bạn làm xong việc đó, bạn chia nhỏ bộ hấp thụ thành các hình tam giác.

Sự hấp thụ không phải lúc nào cũng hoạt động. Nhưng các nhà toán học đã mày mò quá trình này, tìm ra những cách mới để xoay quanh các chướng ngại vật. Ví dụ, một biến thể mạnh mẽ được gọi là hấp thụ lặp lại chia các cạnh thành một chuỗi các tập hợp lồng nhau, để mỗi cạnh hoạt động như một bộ hấp thụ cho phần lớn nhất tiếp theo.

Conlon nói: “Trong hơn một thập kỷ qua, đã có những cải tiến lớn. “Đó là một thứ gì đó của một loại hình nghệ thuật, nhưng họ đã thực sự nâng nó lên tầm nghệ thuật cao vào thời điểm này.”

Vấn đề của Erdős rất phức tạp ngay cả với sự hấp thụ lặp đi lặp lại. Mehtaab Sawhney, một trong bốn nhà nghiên cứu đã giải quyết nó, cùng với Ashwin Sah, người cũng giống như Sawhney, là nghiên cứu sinh tại Học viện Công nghệ Massachusetts, cho biết: “Rất nhanh chóng trở nên rõ ràng tại sao vấn đề này vẫn chưa được giải quyết; Michael Simkin, nghiên cứu sinh sau tiến sĩ tại Trung tâm Khoa học và Ứng dụng Toán học tại Đại học Harvard; và Matthew Kwan, một nhà toán học tại Viện Khoa học và Công nghệ Áo. “Có những nhiệm vụ kỹ thuật khá thú vị, khá khó khăn.”

Ví dụ, trong các ứng dụng khác của hấp thụ lặp đi lặp lại, khi bạn hoàn thành việc bao phủ một tập hợp — hoặc với các hình tam giác cho hệ ba Steiner hoặc với các cấu trúc khác cho các vấn đề khác — bạn có thể xem xét nó đã được xử lý và quên nó đi. Tuy nhiên, các điều kiện của Erdős đã ngăn cản bốn nhà toán học làm điều đó. Một cụm tam giác có vấn đề có thể dễ dàng liên quan đến các nút từ nhiều bộ hấp thụ.

Sawhney nói: “Một hình tam giác bạn đã chọn cách đây 500 bước, bạn cần phải nhớ cách nghĩ về nó như thế nào.

Điều mà cả bốn cuối cùng đã tìm ra là nếu họ chọn các hình tam giác của mình một cách cẩn thận, họ có thể tránh được việc phải theo dõi từng thứ nhỏ nhặt. Sawhney nói: “Điều tốt hơn nên làm là nghĩ về bất kỳ tập hợp nhỏ nào gồm 100 hình tam giác và đảm bảo rằng tập hợp các hình tam giác đó được chọn với xác suất chính xác”.

Các tác giả của bài báo mới lạc quan rằng kỹ thuật của họ có thể được mở rộng ra ngoài vấn đề này. Họ đã áp dụng chiến lược của mình cho một bài toán về các ô vuông Latinh, giống như một sự đơn giản hóa một câu đố sudoku.

Ngoài ra, có một số câu hỏi cuối cùng có thể đặt ra cho các phương pháp hấp thụ, Kwan nói. “Có rất nhiều vấn đề trong tổ hợp, đặc biệt là trong lý thuyết thiết kế, nơi các quy trình ngẫu nhiên là một công cụ thực sự mạnh mẽ.” Một trong những vấn đề như vậy, phỏng đoán của Ryser-Brualdi-Stein, cũng là về các ô vuông Latinh và đã chờ đợi một giải pháp từ những năm 1960.

Maya Stein, Phó giám đốc Trung tâm Mô hình Toán học tại Đại học Chile, cho biết: Mặc dù sự hấp thụ có thể cần phát triển thêm trước khi giải quyết được vấn đề đó, nhưng nó đã trải qua một chặng đường dài kể từ khi ra đời. “Đó là điều thực sự tuyệt vời khi thấy những phương pháp này phát triển như thế nào.”

Câu chuyện gốc tái bản với sự cho phép của Tạp chí Quanta, một ấn phẩm độc lập về mặt biên tập của Tổ chức Simons có nhiệm vụ nâng cao hiểu biết của công chúng về khoa học bằng cách bao gồm các phát triển và xu hướng nghiên cứu trong toán học cũng như khoa học vật lý và đời sống.

Dịch vụ cài đặt phần mềm máy tính từ xa

Dịch vụ sửa cài đặt phần mềm và Win online qua mạng

cài đặt phần mềm và Win online qua mạng Hà Nội

Nguồn: https://trungtamsuamaytinh.com
Danh mục: TIN HỌC

Vui lòng đánh giá về dịch vụ tại nhà