Bài giảng Phân tích thiết kế thuật toán: Chương 3 - Nguyễn Văn Linh

Bài giảng "Phân tích thiết kế thuật toán - Chương 3: Kỹ thuật thiết kế giải thuật" cung cấp các kiến thức giúp người học có thể: Biết các kỹ thuật thiết kế giải thuật: từ ý tưởng cho đến giải thuật chi tiết, hiểu rõ nguyên lý của các kỹ thuật phân tích thiết kế giải thuật, vận dụng kỹ thuật phân tích thiết kế để giải các bài toán thực tế. Mời các bạn tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế thuật toán: Chương 3 - Nguyễn Văn Linh CHƯƠNG 3:  KỸ THUẬT THIẾT KẾ GIẢI THUẬT Nguyễn Văn Linh Khoa Công nghệ thông tin và Truyền  thông Đại học Cần Thơ nvlinh@cit.ctu.edu.vn Nguyễn Văn Linh Mục tiêu • Biết các kỹ thuật thiết kế giải thuật: từ ý tưởng  cho đến giải thuật chi tiết. • Hiểu rõ nguyên lý của các kỹ thuật phân tích thiết  kế giải thuật. • Vận dụng kỹ thuật phân tích thiết kế để giải các  bài toán thực tế: các bài toán dạng nào thì có thể  áp dụng được kỹ thuật này.  Nguyễn Văn Linh Mô hình từ bài toán đến chương trình Thiết kế Đánh giá Lập trình #include Bài  … toán  thực tế Giải thuật Giải thuật tốt Chương trình Kỹ  thuật  thiết  kế  giải  Kỹ thuật phân tích  Ngôn ngữ lập trình: thuật: đánh giá giải thuật: •PASCAL, C/C++,  Chia  để  trị,  quy  hoạch  •Độ phức tạp của  JAVA, … động, … giải thuật •Cải tiến GT Nguyễn Văn Linh Kỹ thuật chia để trị • Cần phải giải bài toán có kích thước n. • Ta chia bài toán ban đầu thành một số bài toán con  đồng dạng với bài toán ban đầu có kích thước nhỏ  hơn n. • Giải các bài toán con và tổng hợp lời giải của  chúng, ta có được lời giải của bài toán ban đầu. • Đối với từng bài toán con, ta cũng sẽ áp dụng kỹ  thuật này để chia chúng thành các bài toán con nhỏ  hơn nữa.  • Quá trình phân chia này sẽ cho chúng ta các bài toán  cơ sở. Nguyễn Văn Linh Nhìn lại giải thuật MergeSort và QuickSort • MergeSort:  – Phân chia: chia danh sách có n phần tử thành 2 danh sách có n/2 phần tử.  – Quá trình phân chia sẽ dẫn đến các danh sách chỉ có 1 phần tử, là bài toán  cơ sở. – Tổng hợp: trộn (merge) 2 danh sách có thứ tự thành một danh sách có thứ  t ự. • QuickSort:  – Phân hoạch danh sách ban đầu thành 2 danh sách “bên trái” và “bên phải”.  – Sắp xếp 2 danh sách “bên trái” và “bên phải” ta thu được danh sách có thứ  tự. – Bài toán cơ sở: Sắp xếp danh sách có 1 phần tử hoặc nhiều phần tử có giá  trị giống nhau. – Tổng hợp: đã bao hàm trong giai đoạn phân chia.  Nguyễn Văn Linh Bài toán nhân số nguyên lớn • Các NNLT đều có kiểu dữ liệu số nguyên (integer  trong Pascal, Int trong C…), nhưng các kiểu này đều có  miền giá trị hạn chế.  • Người lập trình phải tìm một cấu trúc dữ liệu thích  hợp để biểu diễn cho một số nguyên.  • Để thao tác được trên các số nguyên được biểu diễn  bởi một cấu trúc mới, người lập trình phải xây dựng  các phép toán cho số nguyên như phép cộng, phép trừ,  phép nhân… • Sau đây ta sẽ đề cập đến bài toán nhân hai số nguyên  lớn..  Nguyễn Văn Linh Giải thuật nhân 2 số nguyên lớn • Xét bài toán nhân 2 số nguyên lớn X và Y, mỗi số có n chữ số. • Theo cách nhân thông thường: 1426   x      3219 ­­­­­­­­­­­ 12834 1426       2852       4278     ­­­­­­­­­­­­­      4590294 • Việc nhân từng chữ số của X và Y tốn n2 phép nhân.  • Nếu phép nhân 2 chữ số  tốn O(1) thời gian thì độ phức tạp của  giải thuật này là O(n2).  Nguyễn Văn Linh Giải thuật chia để trị cho bài toán nhân số  nguyên lớn • Để đơn giản cho việc phân tích giải thuật ta giả sử n là lũy  thừa của 2.  • Còn về phương diện lập trình, giải thuật cũng đúng trong  trường hợp n bất kỳ. • Biểu diễn X = A10n/2 + B và Y = C10n/2 + D • Trong đó A, B, C, D là các số có n/2 chữ số.  • Ví dụ X = 1234 thì A = 12 và B = 34 vì 12*102 + 34 = 1234 = X • Với cách biểu diễn này thì XY = AC10n + (AD + BC)10n/2 + BD Nguyễn Văn Linh Giải thuật chia để trị cho bài toán nhân số  nguyên lớn (tt) • Ta phân tích bài toán ban đầu thành một số bài toán  nhân 2 số có n/2 chữ số.  • Sau đó, ta kết hợp các kết quả trung gian theo công  thức XY = AC10n + (AD + BC)10n/2 + BD.  • Việc phân chia này sẽ dẫn đến các bài toán nhân 2 số  có 1 chữ số. Đây là bài toán cơ sở.  Nguyễn Văn Linh Đánh giá giải thuật • Theo công thức XY = AC10n + (AD + BC)10n/2 + BD • Ta thực hiện 4 phép nhân các số nguyên có n/2 chữ số, 3 phép  cộng các số lớn hơn n  chữ số và 2 phép nhân với 10n và 10n/2.  • Phép cộng các số có lớn hơn n chữ số cần O(n).  • Phép nhân với 10n tốn O(n) (dịch trái n lần).  • Gọi T(n) là thời gian nhân 2 số có n chữ số ta có phương trình  đệ quy sau: • T(1) = 1 • T(n) = 4T(n/2) + n • Giải hệ này ta được T(n) = O(n2). Ta không cải tiến được so  với giải thuật nhân thông thường. Nguyễn Văn Linh Cải tiến giải thuật • Ta biến đổi công thức XY = AC10n + (AD + BC)10n/2 +  BD • XY = AC10n + [(A ­B)(D­C) + AC + BD]10n/2 + BD (**) • Theo công thức này, ta chỉ cần 3 phép nhân các số nguyên  có n/2 chữ số, 6 phép cộng trừ và 2 phép nhân với 10n,  10n/2. Ta có phương trình đệ quy sau: • T(1) = 1 • T(n) = 3T(n/2) + n • Giải phương trình ta được T(n) = O(nlog3) = O(n1.59). Rõ  ràng cải tiến hơn giải thuật cũ rất nhiều.  Nguyễn Văn Linh Giải thuật thô để nhân 2 số nguyên có n chữ  số Big_Integer mult(Big_Integer X, Big_Integer Y, int n) {   Big_Integer m1, m2, m3, A, B, C, D; int s; /* lưu dấu của tích XY */ s = sign(X)*sign(Y); /* sign(X) trả về 1 n ếu X d ương; ­1 n ếu X âm; 0 nếu X =  0*/ X = ABS(X); ...