Tìm tâm điểm tối ưu cho hệ thống mạng có dây

[Ada]

Đề bài. Giữa hai điểm, có thể vẽ được vô số đường truyền, với độ dài không nhất thiết bằng nhau. Một đường truyền là một đường gấp khúc mà mỗi đoạn của nó đều song song với một trục tọa độ. Trong mặt phẳng tọa độ, hãy tìm điểm X làm cực tiểu tổng độ dài N đường truyền ngắn nhất khả dĩ nối điểm X với N điểm đã cho trước.

Bối cảnh. Khi thiết kế một mạng có dây có N điểm để cắm thiết bị (máy vi tính, điện thoại), cần tìm chỗ đặt thiết bị trung tâm (switch, tổng đài) tối ưu về vật liệu (dây cáp truyền dẫn tín hiệu).

Đây là một trong các bài tập mình nghĩ ra để giúp một bạn tuyển dụng nhân viên quản trị hệ thống và mạng máy tính. Khi giải bằng giấy bút thì đề ra bằng bản vẽ, với N nhỏ (không quá 10). Mình đã đưa vài đồng nghiệp của mình làm thử ai cũng giải được dễ dàng. Họ đều là kỹ sư ngoài ngành CNTT, thậm chí ngoài mọi ngành có thể liên quan như điện, nước,.. Dễ hiểu thôi: bài toán này dành cho học sinh cấp II bình thường.

Nhưng đáng tiếc, khi dùng trong đề thi tuyển dụng, không có ứng viên nào giải được.

[khoaph]

Đề bài. Giữa hai điểm, có thể vẽ được vô số đường truyền, với độ dài không nhất thiết bằng nhau. Một đường truyền là một đường gấp khúc mà mỗi đoạn của nó đều song song với một trục tọa độ. Trong mặt phẳng tọa độ, hãy tìm điểm X làm cực tiểu tổng độ dài N đường truyền ngắn nhất khả dĩ nối điểm X với N điểm đã cho trước.

Bối cảnh. Khi thiết kế một mạng có dây có N điểm để cắm thiết bị (máy vi tính, điện thoại), cần tìm chỗ đặt thiết bị trung tâm (switch, tổng đài) tối ưu về vật liệu (dây cáp truyền dẫn tín hiệu).

Đây là một trong các bài tập mình nghĩ ra để giúp một bạn tuyển dụng nhân viên quản trị hệ thống và mạng máy tính. Khi giải bằng giấy bút thì đề ra bằng bản vẽ, với N nhỏ (không quá 10). Mình đã đưa vài đồng nghiệp của mình làm thử ai cũng giải được dễ dàng. Họ đều là kỹ sư ngoài ngành CNTT, thậm chí ngoài mọi ngành có thể liên quan như điện, nước,.. Dễ hiểu thôi: bài toán này dành cho học sinh cấp II bình thường.

Nhưng đáng tiếc, khi dùng trong đề thi tuyển dụng, không có ứng viên nào giải được.

Giữa 2 điểm A, B bất kì thì đường truyền dù gấp khúc thế nào(các đoạn song song trục tọa độ) thì min độ dài luôn = |xA - xB| + |yA - yB|
Gọi tọa độ điểm cần tìm là x, y và tọa độ các trạm là (x1, y1), (x2, y2), ...(xk, yk)... (xn, yn) thì tổng độ dài các đường truyền là tổng(|x - xk|) + tổng(|y - yk|), k chạy từ 1 tới N, gọi tổng đầu là X và tổng sau là Y, tổng độ dài đường truyền min khi X min và Y min
Tiếp theo ta sắp xếp dãy xk và dãy yk tăng dần
Tại đây ta xét 2 trường hợp
+nếu N lẻ , điểm cần tìm có tọa độ x((N + 1) / 2), y((N + 1) / 2)
+nếu N chẵn, điểm cần tìm có tọa độ x, y sao cho x(N / 2) <= x <= x(N / 2 + 1), y(N / 2) <= y <= y(N / 2 + 1).
Xong! Tốn khoảng nửa tiếng Đúng không?

[Ada]

Giữa 2 điểm A, B bất kì thì đường truyền dù gấp khúc thế nào(các đoạn song song trục tọa độ) thì min độ dài luôn = |xA - xB| + |yA - yB|
Gọi tọa độ điểm cần tìm là x, y và tọa độ các trạm là (x1, y1), (x2, y2), ...(xk, yk)... (xn, yn) thì tổng độ dài các đường truyền là tổng(|x - xk|) + tổng(|y - yk|), k chạy từ 1 tới N, gọi tổng đầu là X và tổng sau là Y, tổng độ dài đường truyền min khi X min và Y min
Tiếp theo ta sắp xếp dãy xk và dãy yk tăng dần
Tại đây ta xét 2 trường hợp
+nếu N lẻ , điểm cần tìm có tọa độ x((N + 1) / 2), y((N + 1) / 2)
+nếu N chẵn, điểm cần tìm có tọa độ x, y sao cho x(N / 2) <= x <= x(N / 2 + 1), y(N / 2) <= y <= y(N / 2 + 1).
Xong! Tốn khoảng nửa tiếng Đúng không?

Cách dựng đúng rồi. Mình không nhìn thấy phân tích và/hoặc chứng minh. Nhưng đây là bài tập lập trình chứ không phải bài tập thuật toán nên giải như vậy là được rồi.

Cảm ơn bạn.

[khoaph]

Chứng minh:
Ta có |a| + |b| >= |a + b|, dấu = xảy ra khi a, b cùng dấu
Sắp xếp dãy xk và dãy yk tăng dần
Đặt Tx = (|x - x1| + |xN - x|) + (|x - x2| + |x(N - 1) - x|) +... = tổng(|x - xk| + |x(N + 1 - k) - x| với k >=1 và k <= N / 2(được làm tròn xuống)
Tổng độ dài đường truyền theo hoành độ là Tx nếu N chẵn và = Tx + |x - x((N + 1) / 2)| nếu N lẻ
Theo trên Tx >= |x - x1 + xN - x| + |x - x2 + x(N - 1) - x| +... =|xN - x1| + |x(N - 1) - x2| +... = tổng (|x(N + 1 - k) - xk| với k>= 1, k <= N / 2
Dấu = xảy ra khi x1 <= x <= xN, x2 <= x <= x(N - 1),..., xk <= x <= x(N - k + 1) với k <= N / 2
Giao lại với nhau thành x(i) <= x <= x(N + 1 - i) với i = N / 2 nếu N chẵn hay i = (N - 1) / 2 nếu N lẻ
trong tr hợp N lẻ thì có thêm Tx + |x - x((N+1) / 2)| >= Tx + 0 = Tx>=...
dấu = xảy ra khi x = x((N + 1) / 2)
tương tự với Ty

[Ada]

Chứng minh:
Ta có |a| + |b| >= |a + b|, dấu = xảy ra khi a, b cùng dấu
Sắp xếp dãy xk và dãy yk tăng dần
Đặt Tx = (|x - x1| + |xN - x|) + (|x - x2| + |x(N - 1) - x|) +... = tổng(|x - xk| + |x(N + 1 - k) - x| với k >=1 và k <= N / 2(được làm tròn xuống)
Tổng độ dài đường truyền theo hoành độ là Tx nếu N chẵn và = Tx + |x - x((N + 1) / 2)| nếu N lẻ
Theo trên Tx >= |x - x1 + xN - x| + |x - x2 + x(N - 1) - x| +... =|xN - x1| + |x(N - 1) - x2| +... = tổng (|x(N + 1 - k) - xk| với k>= 1, k <= N / 2
Dấu = xảy ra khi x1 <= x <= xN, x2 <= x <= x(N - 1),..., xk <= x <= x(N - k + 1) với k <= N / 2
Giao lại với nhau thành x(i) <= x <= x(N + 1 - i) với i = N / 2 nếu N chẵn hay i = (N - 1) / 2 nếu N lẻ
trong tr hợp N lẻ thì có thêm Tx + |x - x((N+1) / 2)| >= Tx + 0 = Tx>=...
dấu = xảy ra khi x = x((N + 1) / 2)
tương tự với Ty

Chính xác. Cảm ơn bạn.

[NguNhuheo]

Tuỳ theo tuyển dụng công việc gì.
Tôi làm quản lý đồ án nhiều năm. Nhưng nếu đi thi tuyển dụng gặp bài này thì tôi nói:
"Người giỏi toán chưa chắc (và rất ít khi) giỏi các kỹ năng giao tiếp. Công ty này mất hơn phân nửa thời gian để thử thách một bài toán thì chắc là không trọng các kỹ năng khác"
Tôi gấp bài ra về, vì có trúng tuyển cũng chẳng làm lâu được.

[khoaph]

Làm nghề lập trình thì chỉ cần giao tiếp được là đủ, cần gì phải giỏi, chỉ cần biết trình bày được ý tưởng của code kiết, viết hướng dẫn sử dụng, biết uml v.v... . Theo mình, kỹ năng phân tích logic là quan trọng, giao tiếp cũng quan trọng. Vấn đề là đào tạo kỹ năng giao tiếp cho người khá môn toán và đào tạo kỹ năng toán học cho người khá giao tiếp cái nào dễ hơn thôi, cái này tùy nhận định của từng công ty, đúng không nhỉ.
Ps: cảm ơn bạn quá khen, he he...

[Ada]

Không thử cách này, họ cũng phải thử cách khác. Công tác quản trị hệ thống và mạng máy tính không đòi hỏi tư duy phức tạp, nhưng đòi hỏi dũng khí và quyết tâm tìm ra chính xác nguyên nhân, thường là hết sức đơn giản, của một hiện tượng phức tạp. Giống như giải một bài toán mà thoạt nhìn tưởng là khó mà thực ra là dễ.

[NguNhuheo]

Không thử cách này, họ cũng phải thử cách khác. Công tác quản trị hệ thống và mạng máy tính không đòi hỏi tư duy phức tạp, nhưng đòi hỏi dũng khí và quyết tâm tìm ra chính xác nguyên nhân, thường là hết sức đơn giản, của một hiện tượng phức tạp. Giống như giải một bài toán mà thoạt nhìn tưởng là khó mà thực ra là dễ.

Theo tôi thì chính nhóm người tuyển dụng này không biết đánh giá kỹ năng giao tiếp. Đã không biết cách đánh giá thì lấy tư cách gì chấm điểm.

Chấm một bài toán thì cần biết toán. Chấm một bài luận cần phải biết luận.

[Ada]

Theo tôi thì chính nhóm người tuyển dụng này không biết đánh giá kỹ năng giao tiếp. Đã không biết cách đánh giá thì lấy tư cách gì chấm điểm.

Chấm một bài toán thì cần biết toán. Chấm một bài luận cần phải biết luận.

Mình không làm nghề nhân sự, nhưng mình giao tiếp cũng nhiều. Mình không thấy lý do gì để đánh giá họ như bạn cả.

Quản trị hệ thống máy tính và mạng không những cần có khả năng giải quyết các tình huống mà còn phải báo cáo được tình huống, cụ thể là chỉ rõ hiện tượng, lý giải được nguyên nhân và giải pháp, chỉ rõ kết quả. Nhiều tình huống đòi hỏi giải quyết trong nhóm, và báo cáo tập thể. Đó cũng là một kỹ năng giao tiếp. Nhưng do có nhiều chi tiết kỹ thuật, phương thức giao tiếp được ưu tiên là viết, hơn là nói. Cũng giống như làm một bài toán, ra được kết quả là tốt, nhưng trình bày được kết quả bằng giấy trắng mực đen thì càng tốt hơn.