Phân tích & Thiết kế Giải thuật nâng cao

*Phân tích & Thiết kế Giải thuật nâng caoAdvanced Algorithm Analysis and Design PGS. TS. TRẦN CAO ĐỆĐại Học Cần Thơ 2014Bài giảng cho Thạc sĩ Ngành HTTT*Phần 1: KT phân tích và thiết kế giải thuậtPGS. TS. TRẦN CAO ĐỆĐại Học Cần Thơ 2014*Chương 1: KỸ THUẬT PHÂN TÍCH GIẢI THUẬTPGS. TS. TRẦN CAO ĐỆĐại Học Cần Thơ 2014*Thuật toánGiải thuật / Thuật toán (algorithm)Xuất phát từ nhà toán học Arập Al-Khowarizmi (khoảng năm 825). Giải thuật là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán, hoặc hành động cần thực hiện ... để cho ta lời giải của bài toán. Ví dụ thuật toán Euclid . Input: m, n nguyên dương Output: g (ước chung lớn nhất của m và n)Thuật toán :Bước 1: Tìm r, phần dư của m cho nBước 2: Nếu r = 0, thì g:=n và dừng lại. Ngược lại (r0) ,thì m:=n; n:=r và quay lại bước 1.*Tính chất của thuật toánInput: Mỗi thuật toán đều có một tập các giá trị đầu vào (có thể rỗng) Output: Mỗi thuật toán có một tập dữ liệu ra đầu ra (output), tương ứng với input.Tính xác định: các bước của thuật toán phải xác định (các thao tác phải rõ ràng, không gây nên sự nhập nhằng).Tính chính xác: Thuật toán phải tạo ra các giá trị đầu ra chính xác tương ứng với giá trị đầu vào. Trong cùng một điều kiện hai bộ xử lý cùng thực hiện một thuật toán phải cho cùng một kết quả như nhau.Tính hữu hạn: Với mọi bộ dữ liệu vào (hợp lệ), thuật toán phải dừng lại sau một số hữu hạn bước thực hiện.Tính khả thi: Các phép toán có mặt trong thuật toán phải đủ đơn giản, có thể thực hiện được trong một lượng thời gian hữu hạn (có thể thực hiện bởi con người với giấy, bút trong một khoảng thời gian hữu hạn).  Tính tổng quát: phải áp dụng được cho một lớp bài toán.*Vấn đề giải được & không giải đượcMột bài toán:Có một hoặc nhiều thuật toán giải. Giải được  Lựa chọn thuật toán Không tồn tại thuật toán để giải gọi là vấn đề không giải được (bằng thuật toán).Vd: KHÔNG CÓ Thuật toán chắc thắng cho người thứ hai của cờ ca rô.KHÔNG CÓ Thuật toán xem một máy Turing có dừng lại sau n bước hay không.*Vấn đề chứng minh thuật toánTiếp cận khoa họcTính đúng đắn của thuật toánThuật toán đúng đắn, chính xácThuật toán dừngSo sánh thuật toán: phân tích độ phức tạp thời gian. Tiếp cận thực hànhThuật toán đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình)Thuật toán sử dụng tiết kiệm nhất các nguồn tài nguyên của máy tính, và đặc biệt chạy nhanh nhất có thể được.*Thời gian thực hiện chương trìnhTiếp cận 1: tính số giây, phút, giờ, ngày cần thiết để chạy chương trìnhKhông chính xác: Phụ thuộc tốc độ máyPhụ thuộc vào tập dữ liệu vào: có input chạy nhanh, có input chạy chậmKhông khả thiChỉ thực hiện được trên một số inputKhông chỉ ra được sự biến thiên của thời gian theo độ dài inputTiếp cận 2: theo số phép toán cơ bản mà chương trình phải thực hiệnPhép toán cơ bản Số phép +,-,*,/,=; Số chỉ thị cơ bản của máy tính)Độc lập tốc độ máyVẫn phụ thuộc vào đặc tính của inputTrường hợp xấu nhấtTrường hợp tốt nhấtTrường hợp ngẫu nhiên*Độ phức tạp thời gian của giải thuậtĐộ phức tạp thời gian của giải thuật là một hàm theo kích thước của input, T(n).So sánh độ phức tạp thời gian: so sánh theo tỷ suất tăng của hàm thời gian. Kí hiệu : tiệm cận xấp xỉ(g(n)) = {f(n)/ c1,c2,n0 >0 : n>n0 , 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) }Ta viết: f(n)= (g(n)) thay cho f(n)  (g(n))Kí hiệu O: tiệm cận trênO(g(n)) = {f(n)/ c,n0>0: n>n0, 0 ≤ f(n) ≤ cg(n) }Ta viết: f(n)= O(g(n)) thay cho f(n)  O(g(n))Kí hiệu : tiệm cận dưới (g(n)) = {f(n)/ c,n0>0: n>n0, 0 ≤ cg(n) ≤ f(n)}Ta viết: f(n)=  (g(n)) thay cho f(n)   (g(n))*Ví dụ f(n)= 3n3 + 2n2 f(n)= (n3) f(n)= (n3) f(n)= O(n3)*Tỷ suất tăng – độ phức tạp thời gian Định lý: f(n), g(n), f(n)= (g(n))  f(n)= O(g(n))  f(n)= (g(n)) Định lý f(n) ≥ 0, g(n): f(n)= (g(n))Định nghĩanếu f(n)= (g(n)) ta nói f(n) có tỷ suất tăng là g(n).nếu f(n) biễu diễn cho một hàm thời gian thực hiện chương trình và f(n)= (g(n)), ta nói f(n) có độ phức tạp (thời gian) là g(n). (1), (1), O(1) biểu diễn cho hằng số.*Một số hàm cổ điểnHàm đa thức P(n)=O(nd)Hàm giai thừa Xấp xỉ Stirling log(n!) =  (nlogn)*Tính chất của các tiệm cậnPhản xạ f(n) = (f(n)) f(n) = (f(n) f(n) = O(f(n)Đối xứng f(n)= (g(n))  g(n)= (f(n)Bắc cầu f(n) = (g(n))  g(n) = (h(n))  f(n)= (h(n)) f(n) = (g(n))  g(n) = (h(n))  f(n)= (h(n)) f(n) = O(g(n))  g(n) = O(h(n))  f(n)= O(h(n))*Ký hiệu O() của f(x) Độ phức thời gian O(1) O(logn) O(n) O(nlogn) O(n2) O(n3) O(2n) O(n!) Hằng Logarit Tuyến tính gần tuyến tính Bình phương Lập phương Mũ Giai thừaCác độ phức tạp thời gian *Cách tính độ phức tạp thời gian của giải thuậtGiải thuật không đệ quiQui tắc cộngQui tắc nhânVí dụFor i:=1 to n do a[i]:=random(1000);For i:=1 to n-1 do for j:=i+1 to n do if (a[i]>a[j]) then swap(a[i],a[j]);Giải thuật đệ quiThiết lập công thức truy hồi T(n) = aT(n/b) + c(n)Giải công thức truy hồi (phương trình đệ qui)Ví dụ: tính độ phức tạp của quicksortT(1)=1T(n)=2T(n/2)+nGiải ra T(n)=O(nlogn)Phương trình hồi quyT(1)=1T(n) = aT(n/b) + d(n), n>1Phương pháp giảiPhương pháp thay thế (n bởi n/b)Phương pháp tổng quát với hàm nhânPhương pháp tổng quát (Master theorem)*Phương pháp thay thếT(1)=1T(n) = 4T(n/2) + n, n>1Giả sử n=2k hay k=log2nThay n bởi n/2T(n)= 4T(n/2) + n = 4(4T(n/4)+n/2) + n = 42T(n/22)+4n/2+n = 4iT(n/2i) + 4i-1n/2i-1++4n/2+n (bước i) = 4kT(n/2k) + 4k-1n/2k-1++4n/2+n (bước k) = 4k + 4k-1n/2k-1++4n/2+n = 4k + n (2k-1+2+1)= n2 + n(2k-1) = n2 + n(n-1) Vậy T(n)=O(n2)*Phương pháp tổng quát với hàm nhânT(1)=1T(n)=aT(n/b) + d(n)Giả sử : n=bk k=logbnBằng thay thế k bước ta có:T(n)= ak + ∑j=0k-1ajd(bk-j)*Nghiệm thuần nhấtNghiệm riêngNếu d là hàm nhân, tức là d(m*n) = d(m)*d(n)Thì ta có thể giải được nghiệm riêng dễ dàng∑j=0k-1ajd(bk-j) = d(b)k ∑j=0k-1(a/d(b))j = (ak-d(b)k)/(a/d(b)-1) Lời giải với d(n) là hàm nhân Nếu a>d(b): T(n)=O(nlogba)Nếu a1d(n)=n là hàm nhân a=4, b=2, d(b) = 2 1 là các hằng số; f(n) là hàm tiệm cận không âm của n Lời giải Nếu f(n) = O(nlogba−) , với  là hằng số dương thì T(n) = Θ(nlogba). f(n) = Θ(nlogbalogkn), với k≥0 thì T(n) = Θ(nlogbalogk+1n).f(n) = Ω(nlogba+ ε), với ε> 0 và f(n) thỏa af(n/b) ≤cf(n) với c 0, nε > lgn !*Tài liệu tham khảoR. Sedgewick, Algorithms in Java, Addision-Wesley, 2004. Chapter 1.Aho, A. V. , J. E. Hopcroft, J. D. Ullman. Data Structure and Algorihtms, 1983.Kenneth H. Rosen, Discrete Mathematics and its applications, 4th edition, McGraw-Hill, 2000.R. Sedgewick, Algorithms , 1987.*Chương 2: KỸ THUẬT THIẾT KẾ GIẢI THUẬTTS. TRẦN CAO ĐỆĐại Học Cần Thơ 2012*Chia để trị Divide and conquerGiải một bài toán kích thước n, chia bài toán đã cho thành a số bài toán con có kích thưóc là b nhỏ hơn n. Giải các bài toán con (chia để trị)Tổng hợp kết quả lại để được lời giải của bài toán ban đầu. Ví dụ QuickSort: Sắp xếp một danh sách gồm n phần tửTìm một giá trị chốt và phân hoạch danh sách đã cho thành hai danh sách con “bên trái” và “bên phải “. Sắp xếp “bên trái” và “bên phải” thì ta được danh sách có thứ tự. Quá trình phân chia sẽ dẫn đến các bài toán sắp xếp một danh sách chỉ gồm một phần tử hoặc gồm nhiều phần tử có khoá bằng nhau, đó chính là các bài toán cơ sở, vì bản thân chúng đã có thứ tự rồi. Tổng hợp kết quả: hiển nhiên2 5 6 1 2 6 8 9 2 1 2 5 6 6 8 91 2 2 5 6 6 8 9*Ví dụ#define null -1int a[]int findPivot_ind(int i, int j){ for (int k=i+1; (kj) return null; // no pivot else if (a[k]>a[i]) return k; else return i;}int partition(int i, int j, int pivot){ int l=i; int r=j; while (l=pivot) r--; if (l 0 thì chọn X[k,V] đồ vật loại k. Tính lại V = V - X[k,V] * gk. Ví dụ: trong bảng trên, ta sẽ xét các đồ vật từ 5 đến 1. Khởi đầu V = W = 9. *013012010090706040311005313412210391726041300004012010090816050400000030122101908151504000000231228282814141400000019876543210 VkBan đầu V=W=9 k=5X[5, 9]=0 chọn 0 đồ vật 5k=4X[4, 9]=3 chọn 3 đồ vật 4V=V-gk*X[k, V]=9-2*3=3 *013012010090706040311005313412210391726041300004012010090816050400000030122101908151504000000231228282814141400000019876543210 VkVới V=3k=3X[3, 3]=0 chọn 0 đồ vật 3k=2X[2, 3]=0 chọn 0 đồ vật 2k=1X[1, 3]=1 chọn 1 đồ vật 1 *Cuối cùng: chọn 3 đồ vật 4 và 1 đồ vật 1 trọng lượng tổng cộng : 3*2 + 1*3 = 9 giá trị : 3*3 + 1*4 = 13013012010090706040311005313412210391726041300004012010090816050400000030122101908151504000000231228282814141400000019876543210 Vk *Sample code #include #define MAX 10typedef struct { char Name[20]; int Weight, Value; int Quantity;} Objet;typedef Objet List_Objets[MAX];typedef int Table[10][100]; void construction (List_Objets list, int n, int W, Table& F, Table& X){ int xk, yk, k; int FMax, XMax, v; for (v= 0; v FMax) { FMax=F[k-1][v-xk *list[k].Weight]+ xk*list[k].Value; XMax= xk; } F[k][v] = FMax; X[k][v] = XMax; } }} void search(List_Objets list, int n, int W, Table F, Table X) { int k, v; v = W; for (k = n; k >=1; k--) if (X[k][v] > 0) { list[k].Quantity = X[k][v]; cout= Vq) return Vq; //cắt } return Vq;} *Phân nhánh tính cậnBranch and boundGiải bài toán tối ưuVét cạn: lâuGreedy: không cho kết quả tối ưuPhân nhánh tính cậnPhân nhánhChia bài toán thành một số bài toán con Cây tìm kiếm hoặc cây quyết địnhGiải bài toán tối ưuVét cạn: lâuGreedy: không cho kết quả tối ưuPhân nhánh tính cậnPhân nhánhChia bài toán thành một số bài toán con Cây tìm kiếm hoặc cây quyết định*Ví dụXét bài toán TSP Phân nhánh Tính cậnBài toán tìm Min  tính cận dướiCận dưới: mỗi đỉnh: chọn hai cạnh có độ dài nhỏ nhất. Cận dưới = tổng độ dài tất cả các cạnh được chọn chia cho 2.Ví dụ:cận dưới của nút D (ab+ac+ba+be+ca+cb+de+dc+eb+ed)/2 = 41/2 = 20.5Lời giải tạm thờiLời giải tạm thờiLời giải tạm thờiBài toán cái ba lôbranch and boundBài toán tìm max. Xét theo thứ tự giảm của đơn giáNút gốc: trạng thái ban đầu của ba lôTổng giá trị được chọn TGT = 0. Cận trên của nút gốc CT = W * Ðơn giá lớn nhất. Nút con: khả năng chọn đồ vật TGT = TGT (của nút cha) + số đồ vật được chọn * giá trị mỗi vật. W = W (của nút cha) - số đồ vật được chọn * trọng lượng mỗi vật. CT = TGT + W * Ðơn giá của vật sẽ xét kế tiếp.*Kĩ thuật tìm kiếm địa phương Local searchGiải các bài toán tìm lời giải tối ưu:Xuất phát từ một phương án nào đó. biến đổi lên phương án hiện hành  phương án tốt hơn. Lặp lại cho đến khi không còn có thể cải thiện được phương án nữa. Bài toán cây phủ tối thiểu Cho G = (V,E) đồ thị vô hướng liên thôngTìm cây phủ của G mà tổng độ dài các cạnh nhỏ nhất. Kĩ thuật tìm kiếm địa phương Phương án ban đầu là một cây phủ nào đó. Xét tất cả các cạnh của G theo thứ tăng dần của độ dàiPhép biến đổi (địa phương): Chọn một cạnh có độ dài nhỏ nhất trong tập các cạnh chưa sử dụng để thêm vào cây. Loại khỏi chu trình cạnh có độ dài lớn nhất. Tập hợp các cạnh theo thứ tự từ nhỏ đến lớn: ad, ab, be, bc, ac, cd, bd, de, ae và ce.Cây xuất phát với giá là 20Thêm cạnh ad = 2, bỏ cạnh cd = 5 Cây mới có giá là 17Thêm cạnh ab = 3, bỏ cạnh bc = 4 Cây có giá là 16Thêm cạnh be = 3, bỏ cạnh ae = 7 Cây có giá là 12. Ví dụBài toán đường đi của người giao hàngXuất phát từ một chu trình nào đó. Bỏ đi hai cạnh có độ dài lớn nhất không kề nhau, nối các đỉnh lại với nhau sao cho vẫn tạo ra một chu trình đủ. Tiếp tục quá trình cho đến khi nào không còn cải thiện được phương án nữa. Phương án ban đầu, giá 25Bỏ ae và cd, nối a với d và e với c. chu trình mới ( a b c e d a) giá = 23 Bỏ ce và ab nối a với c và b với e. chu trình mới (a c b e d a) giá = 19. *Tài liệu tham khảoAho, A. V. , J. E. Hopcroft, J. D. Ullman. Data Structure and Algorihtms, 1983.R. Sedgewick, Algorithms in Java, Addision-Wesley, 2004. Chapter 1.R. Sedgewick, Algorithms , 1987.Goodrich, Tamassia, Algorithm Design, 2002.www.codeproject.comHết phần 1