tCác bài báo kinh điển của KHMT (7)

Một mạng sắp xếp ( sorting network) là một dạng cấu hình mạch xử lý song song với n cổng vào và n cổng ra như hình sau đây:



Các hình vuông là các bộ so sánh (comparator) có hai đầu vào và hai đầu ra. Bộ so sánh sẽ đưa số nhập nhỏ hơn lên đầu ra trên và số lớn hơn xuống dưới. (Trên hay dưới chỉ mang tính tương đối, đại loại là một ngõ xuất sẽ chứa số nhỏ, ngõ còn lại chứa số lớn.) Bất kể thứ tự n số nhập ra sao, thứ tự của n số xuất phải tăng dần từ trên xuống dưới ở mặt ra của mạng.

Số lớn nhất các bộ so sánh mà một tín hiệu nhập có thể đi qua gọi là độ sâu của mạng. Trong hình trên thì mạng có chiều sâu là 5. Tổng số các bộ so sánh là kích thước của mạng sắp xếp. Một bài toán kinh điển trong KHMT là: cho trước n, thiết kế mạng sắp xếp n x n với kích thước nhỏ nhất, và độ sâu càng nhỏ càng tốt. (Độ sâu đánh giá thời gian mà mạch này xếp thứ tự, kích thước cho biết độ phức tạp của mạng.)

Ta có thể dùng ý tưởng của các giải thuật sắp xếp kinh điển như merge sort hay bubble sort để thiết kế một mạng sắp xếp một cách dễ dàng. Ví dụ, ta dùng đệ qui thiết kế mạng cho n/2 trước, sau đó nối kết hai mạng nhỏ hơn này với một bộ trộn (merger) để tại mạng n x n. (Cách này còn gọi là chia để trị - divide and conquer.)

Bài tập 1 : dùng ý tưởng của bubble sort để thiết kế một mạng sắp xếp n x n.

Bài tập 2: chứng minh rằng một mạng sắp xếp n x n cần ít nhất n lg(n) bộ so sánh.

Bài tập 3: chứng minh rằng một mạng sắp xếp n x n có độ sâu ít nhất là lg(n).

Các cận dưới này thách thức các nhà khoa học máy tính trong một thời gian dài, cho đến bài báo kinh điển sau đây:

M. Ajtai, J. Komlós, and E. Szemerédi. An O(n log n) sorting network. Combinatorica 3(1), 1-19, 1983.

Trong bài báo này, Miklos Ajtai, János Komlós, và Enre Szemeredi chứng minh sự tồn tại của các mạng sắp xếp n x n với O(n lg n) bộ so sánh và độ sâu O(lg n). Mạng thiết kế kiểu này gọi là mạng AKS, và nó tối ưu (đến một hệ số nhân). Kết quả này hồi đó là một trong những kết quả rất lớn, không chỉ trong nhánh nghiên cứu về các mạng sắp xếp mà về lý thuyết tính toán nói chung.

Tiếc rằng kết quả của họ dùng phương pháp xác suất (probabilistic method ), chỉ chứng minh được sự tồn tại nhưng không xây dựng được một mạng cụ thể (với mỗi n). Việc xây dựng một mạng cụ thể với kích thước và độ sâu như mạng AKS vẫn là một bài toán mở quan trọng trong KHMT (đã hơn 20 năm). Bài báo của họ dùng expander graphs, một thành phần không thể thiếu của lý thuyết máy tính hiện đại.