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. . | Chương 4 Chiến lược biến thể-để-trị (transform-and-conquer) Nộ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 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). 2. 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). a11x1 + a12x2 + + a1nxn = b1 a’11x1 + a’12x2 + + a’1nxn = b’1 a21x1 + a22x2 + + a2nxn = b2 a’22x2 + + a’2nxn = b’2 ; ; an1x1 + an2x2 + + annxn = bn a’nnxn = b’n Là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 . | Chương 4 Chiến lược biến thể-để-trị (transform-and-conquer) Nộ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 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). 2. 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 + .
