Bài giảng Phân tích và thiết kế giải thuật: Chương 4 - PGS.TS. Dương Tuấn Anh

Trong chương 4 các bạn sẽ tìm hiểu về chiến lược biến thể để trị. Trong chương này sẽ có các nội dung cơ bản như sau: Chiến lược biến thể để trị, giải thuật Gauss để giải hệ phương trình tuyến tính, cấu trúc heap và heapsort, giải thuật Horner để định trị đa thức, so trùng dòng ký tự bằng giải thuật Rabin-Karp. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích và thiết kế giải thuật: Chương 4 - PGS.TS. Dương Tuấn AnhChương 4 Chiến lược biến thể-để-trị (transform-and-conquer) 1Nội dung Chiến lược Biến thể-để-trị Giải thuật Gauss để giải hệ phương trình tuyến tính Cấu trúc heap và heapsort Giải thuật Horner để định trị đa thức So trùng dòng ký tự bằng giải thuật Rabin- Karp 21.Biến thể để trị (transform-and-conquer) Kỹ thuật biến thể-để-trị thường làm việc theo hai bước.  Bước 1 là bước biến thể, thể hiện của bài toán được biến đổi để chuyển sang một dạng dễ dẫn đến lời giải.  Bước 2 là bước tìm ra lời giải cho bài toán. Có nhiều biến dạng của bước 1:  Biến thể để đưa đến một thể hiện đơn giản hơn của bài toán (đơn giản hóa thể hiện -instance simplification)  Biến thể để đưa đến một biểu diễn khác của cùng bài toán (biến đổi biểu diễn -representation change)  Biến thể để đưa đến một thể hiện của một bài toán khác mà đã có tồn tại giải thuật (thu giảm bài toán - problem reduction). 32. Giải thuật Gauss để giải hệphương trình tuyến tính Cho hệ phương trình gồm n phương trình với n ẩn số. a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2 ; ; an1x1 + an2x2 + … + annxn = bn Để giải hệ phương trình trên, ta dùng giải thuật loại trừ Gauss (Gauss elimination). Ý tưởng chính của giải thuật : biến đổi hệ thống n phương trình tuyến tính với n biến thành một hệ thống tương đương (tức là có cùng lời giải như hệ phương trình ban đầu) với một ma trận tam giác trên (một ma trận với các hệ số zero dưới đường chéo chính) Giải thuật Gauss thể hiện tinh thần của chiến lược biến thể- để-trị theo kiểu “đơn giản hóa thể hiện” (instance simplification). 4a11x1 + a12x2 + … + a1nxn = b1 a’11x1 + a’12x2 + … + a’1nxn = b’1a21x1 + a22x2 + … + a2nxn = b2 a’22x2 + … + a’2nxn = b’2 ; ;an1x1 + an2x2 + … + annxn = bn a’nnxn = b’nLàm cách nào để ta có thể chuyển một hệ thống với ma trận A bất kỳ thành một hệ thống tương đương với ma trận tam giác trên A’?Bằng một loạt các phép biến đổi cơ bản như sau: - Hoán vị hai phương trình trong hệ thống - Thay một phương trình bằng phương trình đó nhân với một hệ số. - Thay một phương trình với tổng hay hiệu phương trình đó với một phương trình khác được nhân một hệ số. 5Thí dụ2x1 – x2 + x3 =14x1 + x2 – x3 = 5x1 + x2 + x3 = 02 -1 1 14 1 -2 5 row 2 – (4/2) row 11 1 1 0 row 3 – (1/2) row 12 -1 1 10 3 -3 3 row 3 – (1/2) row 20 3/2 ½ -1/22 -1 1 10 3 -3 30 0 2 -2 x3 = (-2/2)=1; x2 = (3-(-3)x3/3 = 0; x1 = (1-x3 – (-1)x2)/2 = 1 6Giải thuật GaussGaussElimination(A[1..n,1..n],b[1..n])for i := 1 to n do A[i,n+1] := b[i];for i := 1 to n -1 do for j := i + 1 to n do for k:= i to n+1 do A[j,k] := A[j,k]-A[i,k]*A[j,i]/A[i,i];Lưu ý: Vector cột b cũng được gom vào thành cột thứ n+1 của ma trận A.Trở ngại: Khi A[i,i] = 0, giải thuật không làm việc được. Và khi |A[i,i]| quá nhỏ, giải thuật sẽ bị sai số làm tròn khi máy tính tính toán (round-off-error) gây ảnh hưởng xấu, làm cho sự tính toán trở nên không chính xác. 7Giải thuật Gauss cải tiến Để tránh trường hợp |A[i,i]| quá nhỏ nêu trên, ta áp dụng kỹ thuật tìm phần tử chốt bán phần (partial pivoting) được mô tả như sau: “Tại lượt lặp thứ i của vòng lặp ngoài, ta cần tìm hàng nào có hệ số ở cột thứ i mang giá trị tuyệt đối lớn nhất và hoán đổi hàng này với hàng i và dùng hệ số đó như là phần tử chốt của lượt lặp thứ i” 8Giải thuật Gauss cải tiếnBetterGaussElimination(A[1..n,1..n],b[1..n])for i := 1 to n do A[i,n+1] := b[i];for i := 1 to n -1 do pivotrow := i; for j := i+1 to n do if |A[j,i]| > |A[pivotrow,i]| then pivotrow:= j; for k:= i to n+1 do swap(A[i,k], A[pivotrow,k]); for j := i + 1 to n do temp:= A[j,i]/A[i,i]; for k:= i to n+1 do A[j,k] := A[j,k]-A[i,k]*temp; 9Độ phức tạp của giải thuật Gauss n-1 n n-1 nC(n) = i=1 j=i+1 (n+1-i+1) = i=1 j=i+1 (n+2-i) n-1 n-1 = i=1 (n+2-i)(n-(i+1)+1) = i=1 (n+2-i)(n-i) = (n+1)(n-1)+n(n-2)+..+3.1 n-1 n-1 ...