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

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
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật (phần 10)NHÂN MA TR NNHÂ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 uchú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 ama 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 quA*B # B*AVí d : Cho 2 ma tr n 2x3 * 3x4 K t qu matr n (2x4) Nhân ma tr n NhânThu 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×B3A0 A1 B0 B1 = × A2×B0+A3×B2 A2×B1+A3×B3A2 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 toP1 = (A11+ A22)(B11+B22) C11 = P1 + P4 - P5 + P7P2 = (A21 + A22) * B11 C12 = P3 + P5P3 = A11 * (B12 - B22) C21 = P2 + P4P4 = A22 * (B21 - B11) C22 = P1 + P3 - P2 + P6P5 = (A11 + A12) * B22P6 = (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 PhTìm giá tr (x1,…,xn)Ví d :