Bão Katrina và KHMT

Tình hình bão, các nguy hại, phương thức cứu trợ, ... đã được các nhà khoa học dự báo từ lâu. Đây là một ví dụ dự báo năm 2004. Có thể liên hệ gì từ một cơn bão như Katrina và khoa học máy tính?

• Việc dùng máy tính thực thi các mô hình dự báo thời tiết , dự đoán bão, gió xoáy, núi lửa, và các tai họa thiên nhiên khác đã khá phổ thông. Hệ thống thông tin địa lý (geographic information system, hay GIS) là một ngành nghiên cứu thú vị và hữu dụng, nhất là trong nghiên cứu thời tiết, địa chất.

• Mấy hôm đầu tiên sau khi New Orleans bị ngập, các hệ thống thông tin liên lạc đều không làm việc, có điện thoại cầm tay cũng không dùng được vì nghẽn mạch. Các nhà lãnh đạo ở New Orleans rất cần phương tiện để điều phối nhân lực đi các nơi cứu người. May nhờ có sự giúp đỡ của quân đội với các kênh truyền thông trên các băng tần riêng, việc này mới từ từ vào đúng đường ray. Một trong các ngành nghiên cứu trong mạng máy tính hiện nay là mobile ad hoc networks (MANETs). Đây là các mạng không dây nối kết các thiết bị cầm tay (điện thoại, máy tính, PDAs, ...) mà không cần một cơ sở hạ tầng mạng có sẵn, rất tiện dụng và cần thiết cho việc liên lạc khi có thảm họa hoặc trong chiến trận.

Khi nhiều tổ chức riêng rẽ và nhiều cá nhân muốn đi khắp nơi cứu hộ, có hai cách làm: (1) có một ban chỉ huy giữ bản đồ phân bổ nhân lực đi khắp nơi, và (2) các nhóm khác nhau đi một cách tự giác.

Cách (1) có cái bất lợi là cần một khoảng thời gian nhất định để thu thập thông tin (có những nhóm nào, đang ở đâu, phương tiện, khí tài gồm những gì, vân vân), để tổ chức ban chỉ huy điều phối, tổ chức cách liên lạc hiệu quả, ... Trong tình trạng cứu nhân như cứu hỏa, mỗi phút mỗi giây chậm trễ đều có thể phải trả giá bằng nhân mạng.

Cách (2) lại có cái bất lợi khác là rất không hiệu quả, và không chắc rằng các nhóm nhỏ sẽ bao trùm hết được toàn bộ các nơi, cho dù tất cả bọn họ đều có bản đồ và có liên lạc với nhau khi gặp (ở các ngã tư đường chẳng hạn).

Có thể phải dùng một tổ hợp của hai cách để cho giải pháp hiệu quả nhất.

Ta có thể mô hình một phiên bản đơn giản hóa của bài toán này bằng một đồ thị. Vài con kiến bò độc lập với nhau ở từ đỉnh này sang đỉnh khác của đồ thị. Câu hỏi là: hãy thiết kế một thuật toán phân bố cho từng con kiến sao cho thời gian bao quát toàn bộ đồ thị là ngắn nhất. (Một đồ thị được bao quát nếu mỗi đỉnh đều có ít nhất một con kiến ghé thăm.) Biến thể của các giả thiết sau đây là các phiên bản khác nhau của bài toán:

• Các con kiến trao đổi/không trao đổi thông tin lẫn nhau nếu gặp ở một đỉnh nào đó.
• Các con kiến có bản đồ/không có bản đồ.
• Các con kiến chỉ cần bao quát x phần trăm của bản đồ trong khoảng thời gian y ngày.

Trong mạng máy tính thì bạn có thể tưởng tượng ta gửi một vài agents (con kiến) đi thu thập thông tin về các routers trên mạng. Trong P2P networks thì các con kiến tượng trưng cho các query packets. Cũng có thể hỏi: cấu hình mạng (topology) thế nào thì các con kiến sẽ hoạt động hiệu quả nhất. Những thứ này sẽ liên quan chặt chẽ đến random walks on graphs và expanders, một công cụ toán học cực kỳ hữu dụng trong KHMT hiện đại.

Trả lời phần nào các câu hỏi trên, và bạn sẽ có một luận án tiến sĩ ra trò!