Ứng dụng của phép nhân ma trận

L

lamdetien36

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Như tất cả chúng ta đều biết, một trong những yêu cầu không thể thiếu đối với việc giải quyết các bài tập tin học là độ phức tạp của thuật toán. Thông thường, để đạt được độ phức tạp thuật toán như mong muốn, cách làm thường là tìm ra một thuật toán ban đầu làm cơ sở, rồi từ đó dùng các kỹ năng để giảm độ phức tạp của thuật toán. Trong bài viết này, tôi xin giới thiệu với bạn đọc một phương pháp khá thông dụng: nhân ma trận.

Trước khi đọc bài viết này, nếu bạn chưa có khái niệm gì về ma trận, bạn có thể tham khảo định nghĩa về ma trận trong một tài liệu khác.

Trước hết, tôi xin nhắc lại tóm tắt khái niệm về phép nhân ma trận:
Cho 2 ma trận: A kích thước MxN và B kích thước NxP.
Kết quả phép nhân ma trận A và B là ma trận C kích thước MxP, với mỗi phần tử của ma trận C được tính theo công thức:
nhanmatran1.jpg

Để thực hiện phép nhân ma trận trên máy tính, ta có thể thực hiện thuật toán với độ phức tạp O(MNP) như sau:
Mã: 
[/COLOR][/FONT]
[FONT=tahoma][COLOR=#000000]for i:=1 to M do
for j:=1 to P do[/COLOR][/FONT]
[FONT=tahoma][COLOR=#000000]begin[/COLOR][/FONT]
     [FONT=tahoma][COLOR=#000000]C[i,j]:=0;[/COLOR][/FONT]
     [FONT=tahoma][COLOR=#000000]for k:=1 to N do[/COLOR][/FONT]
           [FONT=tahoma][COLOR=#000000]C[i,j]:=C[i,j]+A[i,k]*B[k,j];[/COLOR][/FONT]
[FONT=tahoma][COLOR=#000000]end;[/COLOR][/FONT]

(đối với phép nhân các ma trận vuông kích thước NxN, có thuật toán nhân ma trận Strassen với độ phức tạp O(Nlog7) theo tư tưởng chia nhỏ ma trận (giống với cách nhân nhanh 2 số lớn)) tuy nhiên cài đặt rất phức tạp và nói chung không cần thiết. Thông thường, với các bài toán chúng ta gặp, phép nhân ma trận có độ phức tạp O(N3) là đủ).

Cần chú ý thêm là phép nhân ma trận không có tính giao hoán (do có thể thực hiện nhân 2 ma trận A kích thước MxN và ma trận B kích thước NxP nhưng không thể thực hiện phép nhân B*A nếu P ≠ M) nhưng có tính kết hợp:
(A*B)*C = A*(B*C)

Ví dụ 1:

Trước hết, chúng ta hãy cùng xem xét một ví dụ kinh điển nhất trong ứng dụng của phép nhân ma trận, mà thông thường ai đã học qua phần này đều biết.
Dãy Fibonacci được định nghĩa như sau:
F0= 1
F1= 1
...
Fi= Fi-1 + Fi-1 (i ³ 2)

Yêu cầu: Cho N (N ≤ 109), tính FN
Phân tích:

Hiển nhiên cách làm thông thường là tính lần lượt các Fi. Tuy nhiên, cách làm này hoàn toàn không hiện quả với N lên đến 109, và ta cần một cách tiếp cận khác:
Ta xét các lớp số:
Lớp 1:F1, F2
Lớp 2: F2, F3
...
Lớp i: Fi, Fi+1

Ta hình dung mỗi lớp là một ma trận 1x2. Tiếp đó, ta sẽ biến đổi từ lớp i-1 đến lớp i. Sau mỗi lần biến đổi như vậy, ta tính thêm đượcFi+1. Để thực hiện phép biến đổi này, chú ý là các số ở lớp sau chỉ phụ thuộc vào lớp ngay trước nó theo các phép cộng, ta tìm được cách biến đổi bằng nhân ma trận:

nhanmatran2.jpg


(Chắc hẳn đọc đến đây bạn đọc sẽ thắc mắc, làm thế nào để tìm được ma trận
nhanmatran3.jpg

Để tìm được ma trận này, ta làm như sau:
Ta có:
Fi = 0* Fi-1 +1* Fi nên hàng đầu của ma trận là 0 1
Fi+1 = 1* Fi-1 +1* Fi nên hàng hai của ma trận là 1 1 )

Bây giờ ta sẽ cần tìm cách tăng tốc việc tính
nhanmatran4.jpg
. Việc tính nhanh
79.gif
cũng hoàn toàn tương tự việc ta tính aT với a là số nguyên. Sau đây là đoạn code minh hoạ. Trong đoạn code này, để bạn đọc dễ hiểu, tôi bỏ qua yếu tố về tính toán số lớn, và thực hiện các phép tính với kiểu số longint
Mã: 
type
    matrix = array[0..1, 0..1] of longint;
const
     a: matrix = ((0, 1), (1, 1));
//Định nghĩa phép nhân 2 ma trận
operator * (a, b:matrix) c: matrix;
 var
    i, j, k:longint;
 begin
      fillchar(c, sizeof(c), 0);
      for i := 0 to 1 do
      for j := 0 to 1 do
      for k := 0 to 1 do
          c[i, j] := c[i, j] + a[i, k] * b[k, j];
 end;
//Tính a^n
function power(n: longint): matrix;
 var
    temp:matrix;
 begin
      if n = 1 then exit(a);
      temp := cal(n div 2);
      temp := temp * temp;
      if n mod 2 = 1 then temp := temp * a;
      exit(temp);
 end;
Ví dụ 2:

Tiếp theo, chúng ta sẽ cùng xem xét một ví dụ tổng quát hơn của ví dụ 1.
Cho số nguyên N (N ≤ 100) và 2 dãy số a1, a2, ..., aN ;b1, b2, ..., bN. Dãy số c được định nghĩa như sau:
nhanmatran5.jpg

Yêu cầu: Tính ck với k ≤ 109.
(Nguồn bài: http://www.spoj.pl/problems/SEQ/ . Sau khi code các bạn có thể vào http://www.spoj.pl/register/để đăng ký thành viên và gửi bài để kiểm tra tính đúng đắn của bài làm của mình)

Nguồn: http://www.vnschool.net/modules.php?name=News&file=article&sid=3782

Một số bài tập áp dụng nhân ma trận cơ bản:
- LATGACH
- LATGACH4
- ONE4EVER (bài này em chưa biết làm :D ai làm được rồi thì chỉ em với :D)
 
T

thienvamai

bài ONE4EVER dễ mà, chẳng qua tìm cách để nhân 2 số <=10^15 sao cho không tràn số 64bit thôi
 
Last edited by a moderator:
T

thienvamai

bài này mình thấy khá đơn giản, nghĩ khoảng 3' sẽ ra được công thức này

[TEX]\begin{bmatrix} a & 1 \\ 0 & 1 \end{bmatrix} [/TEX] x [TEX]\begin{bmatrix} Fi \\ b\end{bmatrix}[/TEX] = [TEX]\begin{bmatrix} F(i+1) \\ b\end{bmatrix}[/TEX]
 
You must log in or register to reply here.
Top Bottom