Ktl-icon-tai-lieu

Tính toán song song và phân tán

Được đăng lên bởi Chi Linh Nguyen
Số trang: 28 trang   |   Lượt xem: 1794 lần   |   Lượt tải: 5 lần
TRƯỜNG ĐẠI HỌC LẠC HỒNG
KHOA CÔNG NGHỆ THÔNG TIN

--------

BÀI BÁO CÁO CUỐI KỲ
Môn học:

TÍNH TOÁN SONG SONG VÀ PHÂN TÁN

ĐỀ BÀI:
SONG SONG HÓA THUẬT TOÁN DIJKSTRA TÌM ĐƯỜNG ĐI
NGẮN NHẤT TỪ MỘT ĐỈNH ĐẾN TẤT CẢ CÁC ĐỈNH

Giảng viên: PGS.TS Trần Văn Lăng
Học viên thực hiện: Trịnh đình Thắng

Đồng Nai, 2013

MỤC LỤC
1. Giới thiệu...........................................................................................................................1

1.1 Đôi nét về lịch sử..........................................................................................................
1.2 Phát biểu bài toán.........................................................................................................
2. Nội dung thuật toán...........................................................................................................3

2.1 Xây dựng thuật toán tuần tự tìm đường đi ngắn nhất trên đồ thị................................
2.2 Song song hóa thuật toán tim đường đi ngắn nhất trên đồ th......................................
3. Chương trình PVM..............................................................................................................….3

3.1 Kiến trúc của máy ảo song song PVM( Parallel Virtual Machine) ............................
3.2 Cơ chế hoạt động..........................................................................................................
3.3 Sử dụng PV
3.4 Lập trình PVM
3.5 Thực nghiệm chạy một số ví dụ
4. Đánh giá thuật giải.............................................................................................................7
4.1 Chi phí thời gian

4.2 Tính Speedup và Efficiency........................................................................................
5. Kết luận..............................................................................................................................8
6. Tài liệu tham khảo……………………………………………………………...............9

1. GIỚI THIỆU
1.1 Đôi nét về lịch sử
Bài toán tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh là một trong số những
bài toán tối ưu trên đồ thị và được ứng dụng rộng rãi trong thực tế cũng như các ứng dụng thú
vị trong ngành toán học rời rạc. Bài toán được đề xuất và giải quyết bởi nhà khoa học máy tính
người Hà Lan Edsger Dijkstra và được gọi là thuật toán Dijkstra, thuật toán được xây dựng
năm 1956 và xuất bản năm 1959, là một thuật toán giải quyết tìm đường đi ngắn nhất nguồn
đơn trong một đồ thị có hướng không có cạnh mang trọng s...




 !"
#$$%&'
Đ BI:
SONG SONG HÓA THUẬT TOÁN DIJKSTRA TÌM ĐƯỜNG ĐI
NGẮN NHẤT TỪ MỘT ĐỈNH ĐẾN TẤT CẢ CÁC ĐỈNH
Giảng viên: &$($)*%++,
Học viên thực hiện: )-./0,
1,2345678
Tính toán song song và phân tán - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Tính toán song song và phân tán - Người đăng: Chi Linh Nguyen
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
28 Vietnamese
Tính toán song song và phân tán 9 10 148