Mở đầu Định nghĩa 1.1:Ma trận là một bảng số hình chữ nhật gồm mxn số thực được viết thành m hàng và n cột có dạng như sau : 15 A mn: cấp của ma trận i: chỉ thứ tự hàng (i=) aij: phần tử nằm ở hàng i cột j j: chỉ thứ tự cột (j=) Ký hiệu: A=[aij]mn Ví dụ 1.1: Ma trận là ma trận cấp 3x4 1. Số học ma trận : a. Phép cộng hai ma trận : Định nghĩa1. Tổng của hai ma trận A,B là ma trận C=[cij]mn sao cho cij = aij + bij i,j: i= ; j= Ký hiệu: C=A+B Ví dụ 1.2: + = Tổng của hai ma trận có cùng kích thước nhận được bằng cách cộng các phần tử ở những vị trí tương ứng.Các ma trận có kích thuớc khác nhau không thể cộng được với nhau, vì tổng của hai ma trận chỉ được xác định khi cả hai ma trận có cùng số hàng và cùng số cột.
Tính chất :Giả sử A, B là hai ma trận cùng cấp, khi đó : A+B=B+A (giao hoán) A+(B+C)=(A+B)+C (kết hợp) b. Phép nhân hai ma trận Định nghĩa1. Tích của ma trận A với ma trận B là ma trận C=[cij]mn với i,j: i=, j= Ký hiệu: A.B hay AB Chú ý : Tích của hai ma trận chỉ được xác định khi số cột của ma trận thứ nhất bằng số hàng của ma trận thứ hai.1: Tích A=[aik]mq và B=[bkj]qn Ví dụ 1. Giải : Vì A là ma trận 4x3 và B là ma trận 3x2 nên tích của AB là xác định và là ma trận 4x2.
Để tìm các phần tử của AB, các phần tử tương ứng của các hàng của A và các cột của B ban đầu được nhân với nhau rồi sau đó các tích đó sẽ đuợc cộng lại. Ví dụ, phần tử ở vị trí (3,1) của AB là tổng các tích của các phần tử ở hàng thứ ba của A và cột thứ nhất của B, cụ thể là 3. Khi tất cả các phần tử của AB đã được : Phép nhân ma trận không có tính chất giao hoán. Tức là nếu A và B là hai ma trận, thì không nhất thiết AB phải bằng BA.
Thực tế có thể chỉ một trong hai tích đó là xác định. 16 Ví dụ, nếu A là ma trận 2x3 và B là ma trậ 3x4, khi đó AB là xác định và là ma trận 2x4, tuy nhiên ma trận BA là không xác định vì không thể nhân ma trận 3x4 với ma trận 2x3. Giả sử A là ma trận m x n và B là ma trận r x s. Khi đó AB là xác định chỉ khi n = r và BA là xác định chỉ khi s = m.
Hơn nữa, khi AB và BA đều xác định, thì chúng cũng sẽ không cùng kích thước trừ trường hợp m = n = r = s. Do đó, nếu cả hai AB và BA xác định và có cùng kích thước thì cả A và B đều phải là các ma trận vuông và có cùng kích thước. Thậm chí nếu cả A và B dều là các ma trận n x n, thì AB và BA cũng không nhất thiết phải bằng nhau, như ví dụ dưới đây cho thấy: Ví dụ 1.4: Cho A = Hỏi AB có bằng BA không ? Giải : Ta tìm được Vậy : AB BA Tính chất: A cấp mxn, B cấp nxp, C cấp pxq A.C (kết hợp) A cấp mxn, B và cấp nxp A. Thuật toán cộng hai ma trận : Giả sử rằng C=[cij]mn, là tổng của ma trận A=[aij]mnvà ma trận B=[bij]mn.
Thuật toán dựa trên định nghĩa cộng ma trận được biểu diễn dưới dạng giả mã như sau : Thuật toán 1: Cộng ma trận Procedure cong_ma_tran (A, B: ma tran) Begin for i : =1 to m for j :=1 to n cij := aij + bij; End; d. Thuật toán nhân ma trận : Định nghĩa của tích hai ma trận dẫn tới thuật toán tính tích của hai ma trận. Giả sử rằng C=[cij]mn, là tích của ma trận A=[aiq]mkvà ma trận B=[bqj]kn. Thuật toán dựa trên định nghĩa nhân ma trận được biểu diễn dưới dạng giả mã như sau : Thuật toán2: Nhân ma trận Procedure nhan_ma_tran (A, B: ma tran) Begin for i : =1 to m forj :=1 to n begin cij = 0; 17 fork := 1 to q do cij := cij + aikbkj; end; End; {C = [cij] là tích của A và B} 1.
Chuyển vị và luỹ thừa các ma trận Định nghĩa1.4: Ma trận đồng nhất (hay còn gọi là ma trận đơn vị) bậc n là ma trận In=[ ij]nn với ij = 1 nếu i = jvà ij = 0 nế u i j. Do đó: Nhân một ma trận với ma trận đơn vị kích thước thích hợp không làm thay đổi ma trận đó. Nói cách khác, khi A là ma trận m x n, ta có: Ain = ImA = A Người ta cũng có thể định nghĩa luỹ thừa của các ma trận vuông khi A là một ma trận n x n, ta có: Phép toán chuyển hàng thành cột và cột thành hàng của một ma trận vuông cũng được sử dụng trong nhiều thuận toán.5: Cho A = [aij] là ma trận cấp m x n. Chuyển vị của A được ký hiệu là A , là ma trận n x m nhận được bẳng cách trao đổi các hàng và cột của ma trận A cho t nhau.
Nói cách khác, nếu At = [bij] thì bij = aji với i = 1, 2, .6: Chuyển vị của ma trận Các ma trận không đổi khi trao đổi các hàng và cột của nó cho nhau thường đóng vai trò quan trọng.6: Một ma trận vuông A được gọi là đối xứng nếu A =At. Như vậy A = [aij] là đối xứng nếu aij = aji với mọi i và j ; 0 i n và 0 j n. Chú ý rằng một ma trận là đối xứng nếu và chỉ nếu nó là ma trận vuông và đối xứng qua đường chéo chính của nó.Phép đối xứng này được minh hoạ trên hình 2.2 : Ma trận đối xứng Ví dụ 7 : Ma trận đối xứng 1. Các ma trận 0 1 (không một) Các ma trận có các phần tử là 0 hoặc 1 được gọi là các ma trận không một.
Các ma trận không một thường được dùng để biểu diễn các cấu trúc rời rạc. Các thuật toán dùng các cấu trúc này dựa trên số học Boole cho các ma trận không một. Số học này lại dựa trên các phép toán Boole và thực hiện trên các cặp bit và được định nghĩa bởi: 18 Định nghĩa 1.7:Cho A = [aij] là các ma trận không một m x n. Khi đó hợp của A và B, được ký hiệu là A B là ma trận không một với phần tử ở vị trí (i, j) là a ij bij.
Giao của A và B được ký hiệu là A B, là ma trận không, một với phần tử ở vị trí (i, j) là aij bij.7:Tìm hợp giao của các ma trận không – một sau : A= B= Giải : Hợp của A và B là : Giao của A và B là : Định nghĩa 1.8: Cho A = [aij] là ma trận không một m x k và B = [b ij] là ma trận không một k x n. Khi đó tích Boole của A và B được ký hiệu là A B là ma trận m x n với phần tử ở vị trí (i, j) [cij] là: cij = (ai1 Chú ý rằng tích Boole của A và B nhận được bằng cách tương tự với tích thông thường của hai ma trận đó, nhưng với phép cộng được thay bằng phép và với phép nhân được thay bằng phép. Dưới đây là ví dụ về tích Boole của các ma trận.9 : Tìm tích Boole của A với B, với: Giải : Tích Boole A B được cho bởi: A B= == Thuật toán3 dưới dạng giả mã sau đây mô tả thuật toán tính tích Boole của hai ma trận. Thuật toán 3: Tích Boole Procedure tich_Boole(A,B: các ma trận không một) Begin for i : = 1 to m for j :=1 to n begin cij := 0; for q :=1 to k cij := cij (aiq bqj); end; End; {C=[cij] là tích Boole của A và B} Chúng ta cũng có thể định nghĩa luỹ thừa Boole của các ma trận không một vuông.Các luỹ thừa này sẽ được dùng trong các nghiên cứu sau này về các đường trong đồ 19 thị, các đường này được dùng, chẳng hạn để mô hình các đường liên lạc trong các mạng máy tính.9: Cho A là ma tận không một vuông và r là một số nguyên dương.
Luỹ thừa Boole bậc r của A được ký hiệu là A[r] với: (A[r] là hoàn toàn xác định vì tích Boole có tính chất kết hợp) Chúng ta cũng có thể định nghĩa A[r] là In. Cho Tìm A[r] với mọi n nguyên dương. Giải : Ta thấy ngay rằng : A[2] = AA = Ta cũng tìm được : A[3] = A[2]A = và A[4] = A[3]A = Tính thêm 1 lần nữa, ta được : A[5] = A[4]A = Có thể thấy rằng A[n] = A[5] với mọi n nguyên dương không nhỏ hơn 5. Số các phép toán bit được dùng để tích Boole của hai ma trận n x n cũng dễ dàng xác định được.11: Có bao nhiêu phép toán bit được dùng để tính A B với A, B là các ma trận không một n x n.
Giải: Có n2phép toán bit trong A B. Thuật toán Mục tiêu: Tính toán chính xác độ phức tạp của thuật toán; Trả lời chính xác các bảng test về độ phức tạp của thuật toán; Ứng dụng đánh giá độ phức tạp thuật toán trong thực tế. Khái niệm thuật toán Định nghĩa 2.1:Thuật toán (algorithm) là một dãy các quy tắc nhằm xác định một dãy các thao tác trên các đối tượng sao cho sau một số hữu hạnbước thực hiện sẽ đạt được mục tiêu đặt ra. Các đặc trưng của thuật toán Đầu vào (Input): Một thuật toán có các giá trị đầu vào từ một tập đã được chỉ rõ.
Đầu ra (Output): Từ mỗi tập các giá trị đầu vào, thuật toán sẽ tạo ra các giá trị đầu ra. Các giá trị đầu ra chính là nghiệm của bài toán. Tính dừng: Sau một số hữu hạn bước thuật toán phải dừng. Tính xác định: Ở mỗi bước, các bước thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng.
Nói rõ hơn, trong cùng một điều kiện hai bộ xử lý cùng thực hiện một bước của thuật toán phải cho những kết quả như nhau. Tính hiệu quả: Trước hết thuật toán cần đúng đắn, nghĩa là sau khi đưa dữ liệu vào thuật toán hoạt động và đưa ra kết quả như ý muốn. 20 Tính phổ dụng: Thuật toán có thể giải bất kỳ một bài toán nào trong lớp các bài toán.