Luận văn: Song Song Hóa Các Thuật Toán Trên Mạng Đồ Thị

Song song hóa các thuật toán trên mạng đồ thị

Nghiên cứu này tập trung vào việc giải quyết các bài toán trên mạng đồ thị, đặc biệt là bài toán tìm đường đi và bài toán luồng cực đại, bằng phương pháp xử lý song song. Lý thuyết đồ thị, với nguồn gốc từ thế kỷ 18 bởi Leonhard Euler, cung cấp một công cụ hữu hiệu để mô hình hóa và giải quyết các vấn đề trong nhiều lĩnh vực.

Trong bối cảnh dữ liệu ngày càng lớn và yêu cầu về tốc độ xử lý ngày càng cao, việc khai thác khả năng xử lý song song của các hệ thống máy tính trở nên cấp thiết. Nghiên cứu này đề xuất các thuật toán song song mới để tối ưu hóa việc tìm kiếm đường đi ngắn nhất và tính toán luồng cực đại trên các mạng đồ thị mở rộng.

Các phương pháp nghiên cứu bao gồm phân tích lý thuyết, thiết kế thuật toán song song, thực nghiệm và đánh giá hiệu quả thông qua các chỉ số như độ phức tạp thời gian và tốc độ tăng tốc (speedup). Mục tiêu là cải thiện hiệu năng tính toán, giảm thời gian xử lý so với các thuật toán tuần tự truyền thống.