Bài giảng Ma trận và giải thuật

Nội dung text: Bài giảng Ma trận và giải thuật

1. 1.1. CÁC KHÁI NIỆM CƠ BẢN 1. Logic mệnh đề. 2. Logic vị từ. 3. Các phương pháp chứng minh. 4. Tập hợp và hàm. 5. Ma trận và giải thuật.
2. NỘI DUNG I. Ma trận. 1. Khái niệm. 2. Các phép tốn trên ma trận. II. Thuật tốn và biểu diễn thuật tốn. 1. Khái niệm. 2. Đặc tính cơ bản của thuật tốn. 3. Biểu diễn thuật tốn. III. Bài tập 2
3. 1. Ma trận – Khái niệm  Ma trận là một bảng số hình chữ nhật, cĩ kích thước mxn. Hàng thứ i của ma trận là ma trận 1x n (a , a , . . . .,a ) Cho ma trận i1 i2 in Cột thứ j của ma trận A là ma trận n x 1 a a . . . a a 11 12 1n 1 j a a . . . a a A 21 22 2n 2 j . . . . . . . . . . a a a . . . a nj n1 n2 nn Đơn giản, cĩ thể viết ma trận như sau A = [aij] 3
4. 2. Ma trận - Các phép tốn trên ma trận (1/3) a. Phép cộng  Cho A = [aij] và B = [bij] là các ma trận m x n.  Tổng của A và B được ký hiệu là A + B là ma trận m x n cĩ phần tử thứ (i,j) là aij + bij .  Nĩi cách khác A + B = [aij + bij ]. b. Phép nhân  Cho A = [aij] là ma trận m x k và B = [bij] là ma trận k x n.  Tích của A và B, được ký hiệu là AB , là ma trận m x n với phần tử (i, j) bằng tổng các tích của các phần tử tương ứng từ hàng thứ i của A và cột thứ j của B.  Nĩi cách khác, nếu AB = [cij] thì k c . . .  a b ij a b a b a b it tj i1 1 j i2 2 j ik kj t 1 4
5. 2. Ma trận - Các phép tốn trên ma trận (2/3) c. Chuyển vị và luỹ thừa các ma trận  Ma trận vuơng n x n In =[ij] cĩ các phần tử trên đường chéo chính ii =1 gọi là ma trận đơn vị.  Cho ma trận A = [aij] cĩ kích thước m x n, chuyển vị của A ký hiệu là AT 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 A cho nhau. T  Nĩi cách khác, nếu A = [bij], thì bij = aji. 5
6. 2. Ma trận - Các phép tốn trên ma trận (3/3) Một số ví dụ 1 a 1 2 3 T Ví dụ: Cho ma trận A chuyĨn vÞ cđa A lµ A 2 b a b c 3 c Ma trận vuơng A được gọi là đối xứng nếu AT = A. a b c d b 1 2 3 Ví dụ: Ma trận A là ma trận đối xứng c 2 2 e d 2 e 3 6
7. 3. Thuật tốn và biểu diễn thuật tốn (1/8) a. Khái niệm  Thuật tốn là một phương pháp giải quyết bài tốn, vấn đề bằng cách mơ tả từng bước thực hiện để sau một số hữu hạn bước sẽ đi đến kết quả.  Với thuật tốn, cĩ phương pháp chỉ dẫn cho người hoặc máy thực hiện việc giải quyết vấn đề cụ thể, theo đĩ khơng phải "tư duy" gì thêm vẫn đưa ra kết quả mong muốn. 7
8. 3. Thuật tốn và biểu diễn thuật tốn (2/8) b. Đặc tính cơ bản của thuật tốn  Tính đúng đắn.  Thuật tốn được xây dựng cho một bài tốn, một vấn đề nào đĩ phải bảo đảm sau một số hữu hạn bước thực hiện phải đi đến kết quả đúng.  Tính dừng  Sau một số bước hữu hạn thuật tốn sẽ cho kết quả  Tính tuần tự.  Thuật tốn được xây dựng trong đĩ phải mơ tả tuần tự thứ tự thực hiện các bước cụ thể, bảo đảm khi thực hiện khơng đi vào ngõ cụt, khơng gặp trở ngại nào.  Tính phổ biến.  Thuật tốn được xây dựng thường nhằm giải quyết một lớp bài tốn hoặc vấn đề nào đĩ.  Tính tối ưu.  Khi xây dựng thuật tốn cần phải lưu ý bảo đảm điều kiện tốt nhất cho việc thực hiện, điều này cĩ nghĩa là trong từng bước hoặc tổng thể cần lựa chọn trong các phương án tốt nhất cĩ thể được. 8
9. 3. Thuật tốn và biểu diễn thuật tốn (3/8) c. Biểu diễn thuật tốn.  Biểu diễn bằng ngơn ngữ tự nhiên.  Biểu diễn sơ đồ, lưu đồ khối.  Biểu diễn giả lệnh ngơn ngữ lập trình. 9
10. 3. Thuật tốn và biểu diễn thuật tốn (4/8) c.1. Biểu diễn bằng ngơn ngữ tự nhiên.  Phương pháp này dùng ngơn ngữ tự nhiên để diễn tả các bước cần thực hiện của thuật tốn.  Phương pháp biểu diễn ngơn ngữ cĩ ưu, nhược điểm:  gần gũi dễ hiểu đối người thực hiện,  trong nhiều trường hợp khơng chặt chẽ và đa nghĩa vì bản chất của ngơn ngữ tự nhiên là đa nghĩa.  khơng cĩ tính thống nhất giữa các ngơn ngữ khác nhau. 10
11. 3. Thuật tốn và biểu diễn thuật tốn (5/8) c.1. Biểu diễn bằng ngơn ngữ tự nhiên.  Ví dụ: Biểu diễn thuật tốn giải phương trình bậc 2: ax2 + bx + c = 0 với a, b, c là các số thực và a 0.  Bước 1. Đưa vào (Input) a, b, c  Bước 2. Tính biệt thức = b2 - 4ac  Bước 3. Xét dấu :  Nếu 0 chuyển sang bước 4  Ngược lại chuyển sang bước 4  Bước 4. Tính nghiệm - b - b x ; x 1 2a 2 2a đưa ra thơng báo nghiệm của phương trình là x1và x2. Sang bước 6.  Bước 5. (Output) Đưa ra thơng báo phương trình vơ nghiệm.  Bước 6. Kết thúc. 11
12. 3. Thuật tốn và biểu diễn thuật tốn (5/8) c.2. Biểu diễn sơ đồ, lưu đồ khối.  Thuật tốn cĩ thể biểu diễn bằng sơ đồ khối. Chỉ sự bắt đầu hoặc kết thúc của thuật tốn Mơ tả một phép tốn, thao tác cần thực hiện Mơ tả dữ liệu vào (Intput), ra (Output) Mơ tả điều kiện hoặc một biểu thức logic cần kiểm tra Mơ tả lựa chọn một trong các khả năng xảy ra Chỉ chiều đi của thuật tốn 12
13. 3. Thuật tốn và biểu diễn thuật tốn (6/8) c.2. Biểu diễn sơ đồ, lưu đồ Begin khối. Input các hệ số a, b, c  Ví dụ về sử dụng sơ đồ khối: b2 - 4ac  Một số ưu, nhược điểm:  Cĩ tính tổng quát cao, 0  thống nhất, Th«ng b¸o PT v« nghiƯm - b  khắc phục được tính đa nghĩa x 1,2 2a và hàng rào ngơn ngữ,  khĩ hiểu với đại đa số những Thơng báo PT cĩ nghiệm x1,x2 người khác chuyên ngành,  khĩ biểu diễn với giải thuật lớn. End 13
14. 3. Thuật tốn và biểu diễn thuật tốn (7/8) c.3. Biểu diễn giả lệnh ngơn ngữ lập trình.  Cĩ thể sử dụng giả mã lệnh để biểu diễn giải thuật.  Với giả mã lệnh, cĩ thể hiểu thuật tốn mà khơng phụ thuộc vào ngơn ngữ lập trình.  Phương pháp này rất thơng dụng và dễ dàng sử dụng.  Tuy nhiên, khĩ chuyển đổi đối với trường hợp quá tổng quát. 14
15. 3. Thuật tốn và biểu diễn thuật tốn (8/8) c.3. Biểu diễn giả lệnh ngơn ngữ lập trình. Ví dụ về biểu diễn bằng giả mã lệnh: Begin Input a, b, c; Delta = b2 - 4ac; if Delta 0 then Begin x1 = (-b + Sqrt(Delta)) / (2a); x2 = (-b - Sqrt(Delta)) / (2a); Output 'Phương trình cĩ 2 nghiệm x1 = ', x1,' và x2= ',x2; End; Else Output ‘Phương trình vơ nghiệm’; 15