Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13 MỤC LỤC MỤC LỤC I PHƯƠNG PHÁP QUY HOẠCH ĐỘNG .3 1.1 Phương pháp quy hoạch động 1.2 Các bước thực quy hoạch động 1.3 Hạn chế quy hoạch động .4 II BÀI TOÁN XÂU CON CHUNG DÀI NHẤT CỦA XÂU KÝ TỰ .5 2.1 Phát biểu toán .5 2.2 Phân tích giải toán 2.3.Phương pháp quy hoạch động cho LCS (Longest Common Subsequence) .5 III BÀI TOÁN XÂU CON CHUNG DÀI NHẤT CỦA K XÂU KÝ TỰ 10 3.1 Phát biểu toán tổng quát .10 3.2 Phân tích, giải toán 10 Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13 MỞ ĐẦU Trong ngành hệ thống thông tin, quy hoạch động phương pháp giảm thời gian chạy thuật toán thể tính chất toán gối (overlapping subproblem) cấu trúc tối ưu (optimal substructure) Nhà toán học Richard Bellman phát minh phương pháp quy hoạch động vào năm 1953 Ngành thành lập chủ đề kỹ nghệ phân tích hệ thống tổ chức IEEE thừa nhận Cấu trúc tối ưu có nghĩa lời giải tối ưu cho toán sử dụng để tìm lời giải tối ưu cho toán toàn cục Ví dụ, đường ngắn tới đỉnh đồ thị tìm thấy cách: trước hết tính đường ngắn tới đích từ tất đỉnh kề nó, dùng kết để chọn đường toàn cục tốt Nói chung, ta giải toán với cấu trúc tối ưu quy trình ba bước: Chia toán thành toán nhỏ Giải toán cách tối ưu cách sử dụng đệ quy quy trình ba bước Sử dụng kết tối ưu để xây dựng lời giải tối ưu cho toán ban đầu Các toán giải cách chia chúng thành toán nhỏ hơn, tiếp tục thế, ta đến trường hợp đơn giản dễ tìm lời giải Trong tập tìm xâu chung nhỏ (liên tiếp) k chuỗi nhóm vận dụng nguyên lý quy hoạch động để giải toán Qua nhóm bày tỏ lòng cảm ơn tới PGS.TS Đào Thanh Tĩnh giảng dạy môn Phân tích đánh giá thuật toán hướng dẫn nhóm hoàn thành tập Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13 I PHƯƠNG PHÁP QUY HOẠCH ĐỘNG 1.1 Phương pháp quy hoạch động Bellman (Richard Bellman Ernes)[1] phát biểu nguyên lý tối ưu (cũng gọi nguyên lý Bellman) mà ý tưởng sau: “Với trình điều khiển tối ưu, trạng thái bắt đầu A 0, với trạng thái A trình đó, phần trình kể từ trạng thái A xem trạng thái bắt đầu tối ưu” Chú ý nguyên lý thừa nhận mà không chứng minh Phương pháp tìm điều khiển tối ưu theo nguyên lý Bellman thường gọi quy hoạch động Thuật ngữ nói lên thực chất trình điều khiển động: số bước lựa chọn điều khiển tối ưu dường không tốt tựu chung trình lại tốt Phương pháp quy hoạch động dùng để giải toán tối ưu có chất đệ quy, tức việc tìm phương án tối ưu cho toán đưa tìm phương án tối ưu số hữu hạn toán Đối với nhiều thuật toán đệ quy tìm hiểu, nguyên lý chia để trị (divide and conquer) thường đóng vai trò chủ đạo việc thiết kế thuật toán Để giải toán lớn, ta chia làm nhiều toán dạng với để giải độc lập Trong phương pháp quy hoạch động, nguyên lý thể rõ: Khi cần phải giải toán nào, ta giải tất toán lưu trữ lời giải hay đáp số chúng với mục đích sử dụng lại theo phối hợp để giải toán tổng quát Đó điểm khác Quy hoạch động phép giải đệ quy nội dung phương pháp quy hoạch động Phép phân giải đệ quy toán lớn phân rã thành nhiều toán giải toán Việc giải toán lại đưa phép phân rã tiếp thành nhiều toán nhỏ lại giải tiếp toán nhỏ giải hay chưa Quy hoạch động việc giải tất toán nhỏ (bài toán sở) để từ bước giải toán lớn hơn, giải toán lớn (bài toán ban đầu) 1.2 Các bước thực quy hoạch động Bước 1: Lập hệ thức Dựa vào nguyên lý tối ưu tìm cách chia trình giải toán thành giai đoạn, sau Njkop0 tìm hệ thức biểu diễn tương quan định bước xử lý với bước xử lý trước Hoặc tìm cách phân rã toán thành “bài toán con” tương tự có kích thước nhỏ hơn, tìm hệ thức nêu quan hệ kết toán kích thước cho với kết “bài toán con” kiểu có kích thước nhỏ nhằm xây dựng phương trình truy toán (dạng hàm thủ tục đệ quy) Về cách xây dựng phương trình truy toán: Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13 Ta chia việc giải toán thành n giai đoạn Mỗi giai đoạn i có trạng thái ban đầu t(i) chịu tác động điều khiển d(i) biến thành trạng thái t(i+1) giai đoạn i+1 (i=1,2,…,n-1) Theo nguyên lý tối ưu Bellman việc tối ưu giai đoạn cuối không làm ảnh hưởng đến kết toàn toán Với trạng thái ban đầu t(n) sau làm giai đoạn n tốt ta có trạng thái ban đầu giai đoạn n-1 t(n1) tác động điều khiển giai đoạn n-1 d(n-1), tiếp tục xét đến giai đoạn n-1 Sau tối ưu giai đoạn n-1 ta lại có t(n-2) d(n-2) lại tối ưu giai đoạn n-2 … giai đoạn từ n giảm đến tối ưu coi hoàn thành toán Gọi giá trị tối ưu toán tính đến giai đoạn k Fk giá trị tối ưu toán tính riêng giai đoạn k Gk Fk = Fk-1 + Gk ax {G k (t ( k ), d ( k )) + Fk −1 (t ( k − 1))} (*) Hay là: Fk (t (k )) = m ∀d ( k ) Bước 2: Tổ chức liệu chương trình - Tổ chức liệu cho đạt yêu cầu sau: - Dữ liệu tính toán dần theo bước - Dữ liệu lưu trữ để giảm lượng tính toán lặp lại - Kích thước miền nhớ dành cho lưu trữ liệu nhỏ tốt, kiểu liệu chọn phù hợp, nên chọn đơn giản dễ truy cập Cụ thể - Các giá trị Fk thường lưu trữ bảng (mảng chiều hai, ba, v.v… chiều) - Cần lưu ý khởi trị giá trị ban đầu bảng cho thích hợp, kết toán có kích cỡ nhỏ toán giải: F1 (t (1)) = m ax {G (t (1), d (1)) + F0 (t (0))} ∀d (1) - Dựa vào công thức, phương trình truy toán (*) giá trị có bảng để tìm dần giá trị lại bảng Ngoài cần mảng lưu trữ nghiệm tương ứng với giá trị tối ưu gian đoạn Dựa vào bảng lưu trữ nghiệm bảng giá trị tối ưu giai đoạn xây dựng, tìm kết toán Bước 3: Làm tốt hệ thức Làm tốt thuật toán cách thu gọn hệ thức (*) giảm kích thước miền nhớ Thường tìm cách dùng mảng chiều thay cho mảng hai chiều giá trị dòng (hoặc cột) mảng hai chiều phụ thuộc dòng (hoặc cột) kề trước Trong số trường hợp thay mảng hai chiều với giá trị phần tử nhận giá trị 0, mảng hai chiều cách dùng kỹ thuật quản lý bit 1.3 Hạn chế quy hoạch động Việc tìm công thức, phương trình truy toán tìm cách phân rã toán nhiều đòi hỏi phân tích tổng hợp công phu, dễ sai sót, khó nhận Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13 thích hợp, đòi hỏi nhiều thời gian suy nghĩ Đồng thời lúc kết hợp lời giải toán cho kết toán lớn Khi bảng lưu trữ đòi hỏi mảng hai, ba chiều … khó xử lý liệu với kích cỡ chiều lớn hàng trăm Có toán giải quy hoạch động II BÀI TOÁN XÂU CON CHUNG DÀI NHẤT CỦA XÂU KÝ TỰ 2.1 Phát biểu toán Xâu chung hai xâu A B xâu P ta nhận xâu P cách xóa số ký tự xâu A xâu B (giữ nguyên thứ tự trước/sau ký tự lại) Cho hai xâu ký tự A B, tìm xâu chung P dài A B Ví dụ: A:= "AABCDEFE", B:= "DEABCFGHN", P:="ABCF" xâu chung dài A B 2.2 Phân tích giải toán Cho hai xâu ký tự: A = (a1a2 am), B = (b1b2 bn) P = (p1p2…pk) xâu chung dài A B Một cách giải toán ta sử dụng thuật toán Brute-Force (vét cạn) [2] tìm xâu chung dài (LCS) tìm tất xâu A, tìm xem có phải xâu B hay không, từ ta tìm xâu chung dài A B Mỗi xâu A ứng với tập tập số (1,2,…,m) có nghĩa ta có 2m tập con, phương pháp đòi hỏi thời gian hàm mũ có độ phức tạp O(n2m) giải cho xâu lớn 2.3.Phương pháp quy hoạch động cho LCS (Longest Common Subsequence) Áp dụng nguyên lý quy hoạch động ta giải toán LCS Gọi T[i,j] độ dài xâu chung dài hai xâu A[1 i] i ≤ m B[1 j] j ≤ n, điều có nghĩa T[i,j] độ dài xâu chung dài i ký tự đầu xâu A j ký tự đầu xâu B Do T[m,n] độ dài xâu chung dài A B a) Định lý: Cho hai xâu ký tự: A = (a 1a2 am), B = (b1b2 bn) P = (p1p2…pk) xâu chung dài A B i) Nếu am = bn pk = am = bn Pk-1 LCS Am-1 Bn-1 ii) Nếu am≠ bn pk≠am P LCS Am-1 B iii) Nếu am≠ bn pk≠bn P LCS A Bn-1 Chứng minh: i) Nếu pk ≠ am thêm am = bn vào P chứa xâu chung A B có độ dài k+1, mâu thuẫn với giả thiết P LCS A B, vậy, phải có pk = am = bn Bây tiền tố Pk-1 có độ dài k-1 xâu chung Am-1 Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13 Bn-1 Chúng ta chứng minh LCS, giả sử có xâu chung W A m-1 Bn-1 có độ dài lớn k-1 Khi đó, ta thêm a m = bn vào W kết W có độ dài lớn k, mâu thuẫn ii) Nếu pk ≠ am , P xâu chung Am-1 B Nếu tồn xâu chung W Am-1 B với chiều dài lớn k, W xâu chung A m B, trái với giả thiết P LCS A B iii) Chứng minh tương tự ii) b) Công thức truy hồi cho LCS: Qua định lý ta rút số vấn đề: • Trường hợp i=0 j= độ dài xâu chung dài A B 0, nghĩa T[0,j] = T[i,0] = • Trường hợp xét = bj ta thêm pk = am = bn vào P độ dài xâu chung dài T[i,j] độ dài xâu chung dài A i-1 Bj-1 T[i-1,j-1] cộng thêm • Ngược lại ≠ bj ta phải tìm LCS Ai-1 B, tìm LCS A B j-1 T[i-1,j] T[i,j-1] Xâu lớn LCS A B 0  Ta có: T [ i, j ] = T [ i − 1, j − 1] +  max{T [ i − 1, j ], T [ i, j − 1]} nÕui = 0, j = nÕuai = b j nÕuai ≠ b j Giải thuật 2.1: 1) Input (A[1, ,m], B[1, ,n]) 2) For i = to m T[i,0] := 0; For j = to n T[0,j] := 0; 3) For i = to m For j = to n If A[i] = B[j] then T[i,j] := T[i-1,j-1] + Else T[i,j] := max { T[i-1,j], T[i,j-1]} 4) Output (T[m,n]) Đánh giá: Qua giải thuật có hai vòng lặp for lồng nhau, trường hợp xấu thuật toán có độ phức tạp O(mn), tốt thuật toán Brute-Force Ví dụ: Cho hai xâu A:= "AABCDEFE", B:= "DEABCFGHNBBE", tìm độ dài xâu chung dài Ta xây dựng bảng sau: Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13 B[j] 10 11 12 D E A B C F G H N B B E A[i] 0 0 0 0 0 0 0 A 1 2 2 2 2 2 A 1 2 2 2 2 2 B 1 3 3 3 3 4 C 1 4 4 4 4 D 1 4 4 4 4 E 2 4 4 4 F 2 5 5 5 E 2 5 5 5 Bảng 0-1 Bảng phương án tìm độ dài xâu chung dài c) Truy vết tìm xâu chung dài nhất: * Giải thuật đệ quy đưa xâu chung dài Giải thuật 2.2 Backtrackall(T[0 m,0 n], A[1 m], B[1 n], i, j) 1) If (i=0) or (j=0) then Return R; 2) Else if A[i] = B[j] then R = A[i] + R; Backtrackall(T,A,B,i-1,j-1)} Else If T[i,j-1] >= T[i-1,j] then Backtrackall(T,A,B,i,j-1) If T[i-1,j] >= T[i,j-1] then Backtrackall(T,A,B,i-1,j) Đánh giá: gọi B(m,n) độ phức tạp tính toán toán, ta có B(m,n)=B(m1,n)+B(m,n-1)+C với C số hữu hạn nhỏ phép so sánh gán, to coi C = Giả sử n = m ta có: B(n,n) = 2B(n-1,n) = 2.2B(n-1,n-1) = 2.2…2.B(0,0) = 2nn Vậy thuật toán trường hợp tồi O(2mn) * Một cải tiến thuật toán truy vết - Ý tưởng: Ta dựa vào bảng phương án để truy vết tìm xâu chung Xuất phát từ ô T[m,n], giả sử đứng ô T[i,j] ta xét ô trước ô T[i-1,j], T[i,j-1], hai ô có giá trị ô T[i,j] ta lùi ô hai ô trước có giá trị nhỏ ô đứng T[i’,j’], Khi A[i’] = B[j’] Kết nạp A[i’] vào chuỗi P Lùi ô T[i’-1,j’-1] tiếp tục lặp lại T[0,0] Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13 Giải thuật 2.3: 1) P := ‘’; m := length(A); n := length(B); 2) While (n>0) and (m>0) begin a) while (n>0)and(T[m,n]=T[m,n-1]) n:=n-1 b) while (m>0)and(T[m,n]=T[m-1,n]) m:=m-1 c) begin P := A[m] +P; m := m -1 ; n := n-1 ; end ; end ; 3) Output(P); Thuật toán có độ phức tạp O(m+n) - Nhận xét: Để tìm xâu liên tiếp dài chuỗi, ta thực tìm kiếm xâu liên tục bước truy vết để tìm xâu dài chuỗi đó; để thực tìm kiếm vậy, ta sử dụng thêm biến đếm số bước nhảy k, k>1 ta xét xâu liên tục vừa tìm (P1) với xâu liên tục tìm trước (P2); trình lặp lại tìm đến đầu mảng Giải thuật 2.4: 1) P1=’’; P2=’’; m := length(A); n := length(B); 2) While (n>0) and (m>0) Begin 2.1) k=m; 2.2) While (n>0)and(T[m,n]=T[m,n-1]) n:=n-1; 2.3) While (m>0)and(T[m,n]=T[m-1,n]) m:=m-1; 2.4) Begin If (k-m>1) then Begin if (Length(P1)>=Length(P2)) then P2:=P1; P1=’’; End; P1=A[m]+P1; m := m -1 ; n := n-1 ; end ; End ; Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13 3) Output(P); Thuật toán có độ phức tạp O(m+n) Ví dụ: Xét hai xâu A:= "AABCDEFE", B:= "DEABCFGHNBBE" Ta tìm xâu chung dài "ABCFE" B[j] A[i] A A B C D E F E 0 0 0 0 0 D 1 1 1 1 E 1 1 2 A 2 2 2 2 B 2 3 3 3 C 2 4 4 F 2 4 5 G 2 4 5 H 2 4 5 N 2 4 5 10 B 2 4 5 11 B 2 4 5 12 E 2 4 5 Bảng 0-2 Bảng truy vết tìm xâu chung dài 2.4 Cải tiến phương pháp quy hoạch động cho LCS hai xâu A, B Dựa vào công thức quy hoạch động bảng quy hoạch tóm tắt lại sau: Khởi tạo dòng bảng, sau dùng dòng tính dòng 1, dùng dòng tính dòng v.v tới tính hết dòng n Có thể nhận thấy tính xong dòng thứ k việc lưu trữ dòng từ dòng tới dòng k - không cần thiết việc tính dòng k + phụ thuộc giá trị lưu trữ dòng k Vậy để tiết kiệm không gian nhớ ta dùng hai mảng chiều: Mảng Current lưu dòng thời xét bảng mảng Next lưu dòng kế tiếp, mảng Current gán giá trị tương ứng dòng Sau dùng mảng Current tính mảng Next, mảng Next sau tính mang giá trị tương ứng dòng Rồi lại gán mảng Current := Next tiếp tục dùng mảng Current tính mảng Next, mảng Next gồm giá trị tương ứng dòng v.v Vậy ta có giải thuật cải tiến với độ phức tạp tính toán O(mn) không gian tuyến tính O(m+n) [3] sau: Giải thuật 2.5: (giả sử n ≥ m) 1) Input (A[1, ,m], B[1, ,n]) 2) For j = to n Current[j] := 0; Next[0]:= 0; 3) For i = to m a) For j = to n If A[i] = B[j] then Next[j] := Current[j-1] + Else Next[j] := max { Current[j], Next[j-1]} b) Current := Next; Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13 4) Output (Current[n]) Khi ta có giải thuật truy vết tìm xâu chung dài sau: Giải thuật 2.6: (giả sử n ≥ m) 1) P := ‘’; m := length(A); n := length(B); 2) While (n>0) begin a) while (n>0)and(Current[n]=Current[n-1]) n:=n-1 b) begin P := B[n] +P; n := n-1 ; end ; end ; 3) Output(P); III BÀI TOÁN XÂU CON CHUNG DÀI NHẤT CỦA K XÂU KÝ TỰ 3.1 Phát biểu toán tổng quát Cho xâu ký tự: ( ) ( ) A1 = a11 , a12 , , a1m1 , ( ) A2 = a21 , a22 , , a2m , ., An = an1 , an2 , , anmn Tìm xâu chung dài A1,A2, …,An Ký hiệu MLCS(A1,A2, …,An) 3.2 Phân tích, giải toán Để tìm hiểu toán tổng quát ta xét ví dụ trường hợp xâu A 1, A2, A3 sau: A1 = “T CCACA” , A2 = “ACCAAG” A3 = “AC” Bao có thuật toán vét cạn, độ phức tạp tính toán O(m2m32m1) m1, m2, m3 độ dài xâu Điều thực chiều dài xâu lớn có nhiều xâu Nếu ta áp dụng phương pháp quy hoạch động cho cặp xâu một, giả dụ tìm B = LCS(A1,A2), sau tìm LCS(B, A3), độ phức tạp tính toán O(m1m2m3l) với l độ dài xâu B Đồng thời ta không tìm MLCS A1= T C C A C A Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh 10 Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13 A2= A C C A A G A1= T C C A C A A2= A C C A A G A3= A C Hình 0-1 LCS(A1,A2) MLCS(A1,A2,A3) Ta tìm thấy B = LCS(A1,A2) = “CCAA”, sau ta tìm LCS(B, A 3) = “A” hoăc “C”, MLCS(A1,A2,A3) = “AC” Như ta dùng phương pháp quy hoạch động cho toán xâu sử dụng bảng phương án chiều sau: nÕui = or j = or k= 0  nÕuA 1[i] = A 2[ j ] = A 3[ k ] T[i,j,k] = T[i - 1,j - 1,k - 1]+ max{ T[i - 1,j, k],T[i,j - 1,k],T[i,j, k - 1]} choc¸ctrêng hîp kh¸c  Tổng quát cho trường hợp N xâu ký tự: 0 nÕu i1 = or or i n =  nÕu A1[i1 ] = A [i2 ] = = A n [in ] T[i1,i2,,in] = T[i1 - 1, i - 1, , i n - 1] + max{ T[i - 1, i , , i ], T[i , i - 1, , i ], T[i , i , , i - 1]} cho c¸c trêng hîp kh¸c n n n  Giải thuật 3.1: Cho trường hợp xâu 1) Input (A1[1, ,m1], A2[1, ,m2], A3[1, ,m3]) 2) For i = to m1 T[i,0,0] := 0; For j = to m2 T[0,j,0] := 0; For k = to m3 T[0,0,k] := 0; 3) For i = to m1 For j = to m2 For k = to m3 If A1[i] = A2[j]=A3[k] then T[i,j,k] := T[i-1,j-1,k-1] + Else T[i,j,k] := max { T[i-1,j,k]; T[i,j-1,k]; T[i,j,k-1]} 4) Output (T[m1,m2,m3]) Đánh giá : Thuật toán sử dụng vòng lặp for lồng nên thuật toán có độ phức tạp tính toán nhớ O(m1m2m3) Dưới đậy giải thuật truy vết tìm xâu chung dài xâu Giải thuật 3.2: 1) P := “”; m1 := length(A1); m2 := length(A2); m3 := length(A3) Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh 11 Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13 2) While (m1>0) and (m2>0) and (m3>0) begin a) while (m1>0)and(T[m1,m2,m3]=T[m1-1,m2,m3]) m1:=m1-1 b) while (m2>0)and(T[m1,m2,m3]=T[m1,m2-1,m3]) m2:=m2-1 c) while (m3>0)and(T[m1,m2,m3]=T[m1,m2,m3-1]) m3:=m3-1 d) begin P := A1[m1] +P; m1 := m1 -1 ; m2 := m2 -1 ; m3 := m3-1 ; end ; end ; 3) Output(P); - Số phép so sánh vòng lặp while = min(m1,m2,m3) - Số phép so sánh vòng lặp, gồm vòng lặp while: m1+m2+m3 => số phép tính cần thực hiện: (m1+m2+m3)*min(m1,m2,m3)=(m1+m2+m3)*kmin Thuật toán có độ phức tạp O((m1+m2+m3)*kmin)=O(m*n) KẾT LUẬN Trong báo cáo nhóm phân tích toán, sử dụng giải pháp để giải toán trường hợp k xâu ký tự Dưới bảng đánh giá số thuật toán Tên thuật toán Độ phức tạp tính toán m Vét cạn cho xâu O(n2 ) Quy hoạch động cho xâu O(mn) Cải tiến theo phương pháp O(mn) Hirschberg Quy hoạch động cho xâu O(mnp) Quy hoạch động cho k xâu Độ phức tạp không gian O(m+n) O(m) O((m+n+p)*k) TÀI LIỆU THAM KHẢO Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh 12 Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13 [1] http://en.wikipedia.org/wiki/Richard_E._Bellman [2] T.H Cormen, C.E Leiserson, R.L.Rivest, C.Stein, "Introduction to Algorithms", Second Edition, the MIT Press, McGraw-Hill, 2001 [3] DanielA.Hirschberg “ A linear space algorithm for computing maximal common subsequences”, Communications of the ACM,18(6):341-343,1975 [4] http://en.wikipedia.org/wiki/Longest_common_subsequence_problem [5] Hunt, J.W & Szymanski, T.G.: A Fast Algorithm for Computing Longest Common Subsequences, Comm of the ACM, Vol 20, NO 5, 1977, pp 350-353 [6] L.Bergroth,H.Hakonen, T.Raita, Asurvey of longest common Subsequence algorithms, in: String Processing and Information Retrieval(SPIRE), IEEE Computer Society,2000, pp.39–48 [7] C.S Iliopoulos,M.S Rahman, New effcient algorithms for LCS and constrained LCS problem, in: H Broersma, S.S Dantchev, M Johnson, S Szeider (Eds.), Algorithms and Complexity in Durham 2007—Proceedings of the Third ACiD Workshop, 17–19 September 2007, Durham, UK, ACiD, Texts in Algorithmics, vol 9, King’s College, London, ISBN 978-1-904987- 55-0, 2007, pp 83–94.] [8] J.Y Yang, Y Xu, and Y Shang, An Efficient Parallel Algorithm for Longest Common Subsequence Problem on GPUs Proceedings of the World Congress on Engineering 2010 Vol I WCE 2010, June 30 - July 2, 2010, London U.K Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh 13 ... k ch cỡ chiều lớn hàng trăm Có toán giải quy hoạch động II BÀI TOÁN XÂU CON CHUNG DÀI NHẤT CỦA XÂU K TỰ 2.1 Phát biểu toán Xâu chung hai xâu A B xâu P ta nhận xâu P cách xóa số k tự xâu A xâu. .. quy hoạch động ta giải toán LCS Gọi T[i,j] độ dài xâu chung dài hai xâu A[1 i] i ≤ m B[1 j] j ≤ n, điều có nghĩa T[i,j] độ dài xâu chung dài i k tự đầu xâu A j k tự đầu xâu B Do T[m,n] độ dài. .. nguyên thứ tự trước/sau k tự lại) Cho hai xâu k tự A B, tìm xâu chung P dài A B Ví dụ: A:= "AABCDEFE", B:= "DEABCFGHN", P:="ABCF" xâu chung dài A B 2.2 Phân tích giải toán Cho hai xâu k tự: A =