Thuật toán trực tuyến

Trong khoa học máy tính, một thuật toán là trực tuyến nếu nó không nhận được toàn bộ dữ liệu ngay từ đầu mà chỉ nhận được từng phần của dữ liệu và phải đưa ra kết quả ngay sau mỗi lần nhận thêm dữ liệu mới. Một thuật toán là ngoại tuyến nếu nó nhận được toàn bộ dữ liệu trước khi phải đưa ra kết quả.

Do không được biết trước toàn bộ dữ liệu, thuật toán trực tuyến có thể phải đưa ra những lựa chọn mà sau đó hóa ra là không tối ưu. Việc phân tích thuật toán trực tuyến tập trung vào tìm hiểu chất lượng kết quả thu được tốt đến đâu. Phân tích cạnh tranh cụ thể hóa ý tưởng này bằng cách so sánh kết quả của thuật toán trực tuyến với kết quả tối ưu của thuật toán ngoại tuyến cho cùng một dữ liệu vào.

Ngoài mô hình thuật toán trực tuyến còn có nhiều mô hình khác trong đó dữ liệu vào cũng được cung cấp từng phần một cho thuật toán, chẳng hạn như thuật toán dòng dữ liệu (tập trung vào lượng bộ nhớ cần dùng để lưu trữ thông tin về phần dữ liệu đã xử lý), thuật toán động (tập trung vào thời gian cần thiết để cập nhật kết quả sau mỗi lần dữ liệu thay đổi) và thuật toán học trực tuyến.

Danh sách một số bài toán trực tuyến

Có rất nhiều bài toán đã được nghiên cứu trong mô hình thuật toán trực tuyến. Sau đây là một vài ví dụ.

• Bài toán cập nhật danh sách
• Bài toán thay thế trang
• Bài toán thư ký
• Bài toán thuê ván trượt tuyết
• Bài toán tên cướp

Tham khảo

• Borodin, A. (1998). Online Computation and Competitive Analysis. El-Yaniv, R. Cambridge University Press. ISBN 0-521-56392-5.

Tham khảo