Cấu trúc dữ liệu và giải thuật (phần 10)

Chia sẻ: Nguyen Kien | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

107
lượt xem 28
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thuật toán nhân ma trận trước đây bạn được làm quen thì có vẻ thiên về lập trình cơ bản, nhưng trong bài này các bạn sẽ được làm quen với thuật toán nhân ma trận rất nổi tiếng, kinh điển, hãy tìm hiểu

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cấu trúc dữ liệu và giải thuật (phần 10)

NHÂN MA TR N NHÂN
Phép toán trên ma tr n Ph C ng, tr ma tr n: - 2 ma tr n ch có th c ng ho c tr cho nhau n u chúng có cùng kích thư c. Nhân ma tr n: - Có th nhân 2 ma tr n v i nhau n u s c t c a ma tr n 1 = s hàng c a ma tr n 2 K t qu s là ma tr n có s hàng c a ma tr n 1 và c t ma tr n 2 - Ví d : Nhân 2 ma tr n có kích thư c 3x4 và 4x7 ư c ma tr n có kích thư c 3x7
Nhân ma tr n Nhân Tính ch t c a nhân ma tr n: - Nhân ma tr n không có tính giao hoán - Ví d : Cho 2 ma tr n vuông A và B K t qu A*B # B*A Ví d : Cho 2 ma tr n 2x3 * 3x4 K t qu ma tr n (2x4)
Nhân ma tr n Nhân Thu t toán: Nhân 2 ma tr n G(n x n) và H(n x n) K t qu R(n x n) for (int i =1;i
Thu t toán Strassen Thu to - Thu t toán Strassen ng d ng v i ma tr n vuông - Thu t toán Strassen áp d ng gi i thu t chia tr A B = R × A0×B0+A1×B2 A0×B1+A1×B3 A0 A1 B0 B1 = × A2×B0+A3×B2 A2×B1+A3×B3 A2 A3 B2 B3 - Chia nh ma tr n A, B thành nh ng ma tr n con A0,A1,…
Thu t toán Strassen Thu to P1 = (A11+ A22)(B11+B22) C11 = P1 + P4 - P5 + P7 P2 = (A21 + A22) * B11 C12 = P3 + P5 P3 = A11 * (B12 - B22) C21 = P2 + P4 P4 = A22 * (B21 - B11) C22 = P1 + P3 - P2 + P6 P5 = (A11 + A12) * B22 P6 = (A21 - A11) * (B11 + B12) P7 = (A12 - A22) * (B21 + B22)
Thu t toán Strassen Thu to Cài t: void matmul(int *A, int *B, int *R, int n) { if (n == 1) { (*R) += (*A) * (*B); } else { matmul(A, B, R, n/4); matmul(A, B+(n/4), R+(n/4), n/4); matmul(A+2*(n/4), B, R+2*(n/4), n/4); matmul(A+2*(n/4), B+(n/4), R+3*(n/4), n/4); matmul(A+(n/4), B+2*(n/4), R, n/4); matmul(A+(n/4), B+3*(n/4), R+(n/4), n/4); matmul(A+3*(n/4), B+2*(n/4), R+2*(n/4), n/4); matmul(A+3*(n/4), B+3*(n/4), R+3*(n/4), n/4); } }
Thu t toán Strassen Thu to ánh giá gi i thu t: - Thu t toán Strassen có ph c t p O(nlog7) = O(n2,81)
PHƯƠNG TRÌNH TUY N TÍNH TUY
Phương trình tuy n tính Ph Tìm giá tr (x1,…,xn) Ví d :