Bài giảng Nâng cao năng lực dạy học Thuật toán - Nguyễn Thế Dũng

212 trang ngocly 3240

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Nâng cao năng lực dạy học Thuật toán - Nguyễn Thế Dũng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_nang_cao_nang_luc_day_hoc_thuat_toan_nguyen_the_du.ppt

Nội dung text: Bài giảng Nâng cao năng lực dạy học Thuật toán - Nguyễn Thế Dũng

Nâng cao năng lực dạy học Thuật toán Nguyễn Thế Dũng Khoa Tin học – ĐHSP Huế. 1
Nội dung Chủ đề 1: Giới thiệu về thuật toán Chủ đề 2: Phân tích tính hiệu quả của thuật toán Chủ đề 3: Phương pháp “tham lam” Chủ đề 4: Phương pháp “chia để trị” Chủ đề 5: Phương pháp qui hoạch động Chủ đề 6: Thuật toán trên đồ thị Chủ đề 7: Phương pháp xác suất Chủ đề 8: Về độ phức tạp tính toán 2
Tài liệu tham khảo 1. Nâng cao năng lực dạy học thuật toán – Nguyễn Đức Nhuận – Nguyễn Thế Dũng. 2. Giải thuật và lập trình – Lê Minh Hoàng. 3
Tài liệu tham khảo 3. Thuật Toán – Nguyễn Xuân Huy. 4. Một số vấn đề chọn lọc trong Tin học - Nguyễn Xuân My và một số tác giả. 5. Lý thuyết độ phức tạp tính toán - Phan Đình Diệu. 6. Trí tuệ nhân tạo – Hoàng Lan Giao – ĐHKH Huế. 7. Slide này có tham khảo slide Phân tích – thiết kế thuật toán – Phan Hà Hạnh Dương – ĐHQG Hà Nội 4
Một số khó khăn trong dạy học lập trình ◼ Học sinh khó hiểu. ◼ Chuyển sang lập trình rất khó khăn. • Sự khác nhau giữa lập trình và thuật toán. ◼ Cái nhìn về thuật toán chưa khái quát. • Phân lớp, đánh giá thuật toán • Nói chung dạy và học thuật toán là khó, đòi hỏi đam mê!!!. • Vì sao??? Làm sao???
◼ Kinh nghiệm giảng dạy bồi dưỡng. ◼ Quan điểm nhận xét về chương trình, nội dung liên quan đến thuật toán. ◼ Trao đổi 1 bài dạy về lập trình cụ thể.
Chủ đề 1: Giới thiệu về thuật toán I. Khái niệm thuật toán II. Một số ví dụ III. Đánh giá thuật toán trong trường hợp xấu nhất và theo trung bình IV. Về thuật toán hiệu quả V. Một số bài toán cụ thể VI. Cấu trúc dữ liệu 7
Khái niệm về thuật toán Thuật toán: Quá trình tính toán Dữ kiện vào Một dãy các bước tính toán Thuật toán sắp xếp Một dãy số 8
◼ Một định nghĩa bài bản về thuật toán xin xem thêm trong các giáo trình “Automat và ngôn ngữ hình thức”. ◼ Có liên quan đến Máy tính điện tử logic – máy Turing, tính giải được của bài toán và lý thuyết hàm đệ qui.
Đánh giá thuật toán Giải quyết một bài toán. Mô hình hóa Viết thuật toán Lập chương trình Vấn đề: Có nhiều thuật toán. Chọn thuật toán nào ? 10
Phương pháp đánh giá Phương pháp thực nghiệm: Lập trình, và thử trên các ví dụ xem thuật toán nào nhanh. Phương pháp lý thuyết: Tính toán thời gian, bộ nhớ, cần thiết của mỗi thuât toán dựa theo độ lớn của dữ liệu vào. Ưu điểm: - không phụ thuộc ngôn ngữ lập trình, loại máy tính - Biết được tính hiệu quả của thuật toán đối với các dữ liệu có kích thước lớn. 11
Đánh giá thuật toán trong trường hợp xấu nhất và theo trung bình Ví dụ: Sắp xếp lựa chọn Select-Sort (A){ for i=1 to n-1 do { index = i; x = T[i]; for j= i+1 to n do { if T[j] < x then { index = j; x = T[j];} } T{index = T{i}; T{i} = x; } } 12
Ví dụ Hãy chạy thuật toán Insertion-Sort Merge-Sort Đối với các bảng sau : A = [3,1,4,1,5,9,2,6,5,3] B = [1,2,3,4,5,6] C = [6,5,4,3,2,1] 13
Thời gian chạy trong trường hợp xấu nhất: là cận trên đối với mọi dữ liệu vào. Thời gian chạy trung bình: thường khó phân tích và đánh giá hơn. 14
Ví dụ: dãy Fibonacci Dãy Fibonacci được định nghĩa: F(0) = 0, F(1) = 1, và F(n) = F(n-1) + F(n-2) với n > 1. Tìm thuật toán tính số Fibonacci thứ n. 15
Thuật toán thứ nhất và thứ hai function fib1(n){ if n < 2 then return n; else return fib1(n-1) + fib2(n-2); } function fib2(n){ a= 0; b = 1; for k = 1 to n do {c=b; b = a+b; a=c;} return b; } 16
Thuật toán thứ ba fonction fib3(n){ i = 1; j = 0; k = 0; h = 1; while n>0 do { if (n lẻ) then { t = j*h; j = i*h + j*k +t; i = i*k +t;} t = h^2; h = 2*k*h+t; k = k^2+t; n = n div 2; } return j; } 17
Ví dụ về thời gian chạy (Pascal, CDC Cyber 835) n 10 20 30 50 100 1000 1 1000 0 000 0000 000 0 fib1 8 ms 1 s 2 min 21 days fib2 1/6 1/3 ½ ms ¾ ms 3/2 150 15 s 25 ms ms ms ms min fib3 1/3 2/5 ½ ms ½ ms ½ ms 1 ms 3/2 2 ms ms ms ms 18
Cấu trúc dữ liệu Dãy (list) 6 7 1 3 type tablist = structure{ value[1 lengthmax]: information elements; counter: 0 lengthmax;} type elem = structure{ value: information element; next: * elem;} 19
Đồ thị 2 1 type adjgraph = structure { 3 value[1 n]: information elements; 4 adjacent[1 n, 1 n]: booleans;} type listgraph = array[1 n] of structure { value: information element; neighbours: list; } 20
Cây type treenode = structure{ value: information element; a children: array[ ] of * treenodes; } type treenode = structure{ value: information element; b c first child: * treenode; next brother: * treenode; } type binarytreenode = structure{ d e f value: information element; left child, right child: * binarytreenode; } 21
Tập hợp set[1 N]: integer; fonction find(x){ } // tìm phần tử có giá trị x procedure merge(a,b) // tìm hợp của hai tập được sắp Đề tài tiểu luận: Xây dựng các thuật toán mô tả các thao tác cơ bản trên: dãy, cây nhị phân. 22
Chủ đề 2: Phân tích tính hiệu quả của thuật toán I. Các ký hiệu đánh giá tiệm cận II. Phân tích thuật toán III. Giải các phương trình đệ qui IV. Một số ví dụ 23
Ký hiệu O: O(g(n)) = {f(n): tồn tại hằng số c và N để: 0 ≤ f(n)< c g(n) với mọi n ≥ N} Đây là một quan hệ thứ tự: phản xứng, “phi đối xứng” và bắc cầu. 24
Ký hiệu Ω Ω(g(n)) = {f(n): tồn tại hằng số c và N để: f(n)≥ c g(n) với mọi n ≥ N} f(n) Є Ω (g(n)) ≈ g(n) Є O(f(n)) Đây là một quan hệ thứ tự: phản xứng, “phi đối xứng” và bắc cầu. 25
Ký hiệu θ θ(g(n))={f(n): tồn tại 2 hằng c, d và N để: c g(n) ≤ f(n) ≤ d g(n) với mọi n ≥ N} f(n) = θ(g(n)) ≈ f(n) = O(g(n)) và f(n) = Ω(g(n)) Đây là một quan hệ tương đương: phản xứng, đối xứng và bắc cầu. 26
Ký hiệu o o(g(n)) = {f(n): với mọi hằng c >0, tồn tại N để: 0 ≤ f(n)< c g(n) với mọi n ≥ N} Đây là một quan hệ thứ tự: phản xứng, “phi đối xứng” và bắc cầu. 27
Ký hiệu ω ω(g(n)) = {f(n): với mọi hằng c >0, tồn tại N để: 0 ≤ c g(n) <f(n) với mọi n ≥ N} f(n) Є ω(g(n)) ≈ g(n) Є o(f(n)) Đây là một quan hệ thứ tự: phản xứng, “phi đối xứng” và bắc cầu 28
Nhận xét f(n) = O (g(n)) ≈ a ≤ b f(n) = Ω (g(n)) ≈ a ≥ b f(n) = θ (g(n)) ≈ a = b f(n) = o (g(n)) ≈ a b Tiểu luận: Độ phức tạp thuật toán. Lớp các bài toán với các độ phức tạp. Đánh giá độ phức tạp của các thuật toán đệ qui. Đánh giá các thuật toán cơ bản ở sách Tin học lớp 11. 29
Sắp xếp các hàm sau theo quan hệ 0 và θ 30
Một số hàm cơ bản 1. n^b = o(a^n), với mọi a>1 và b 2. e^x = 1 + x + θ(x^2), với |x| ≤ 1 3. lg^b n = o(n^a), với mọi a > 0 4. n! = o(n^n) 5. n! = ω(2^n) 6. lg(n!)= θ(n lg n) 31
Giải các phương trình đệ qui Ví dụ: T(n) = θ(1) nếu n= 1 2 T(n/2) + θ(n) nếu n >1 T(n) = θ(n lg n) 32
Phương pháp truy hồi - Dự đoán kết quả - Chứng minh bằng truy hồi (quy nạp) Ví dụ: Cho T(n) = 2 T(n/2) + n. Ta chứng minh truy hồi rằng T(n) = O(n lg n). 33
Đổi biến Ví dụ: T(n) = 2 T([√n]) + lg n Đặt m = lg n, ta có: T(2^m) = 2 T(2^{m/2}) + m Đặt S(m) = T(2^m), ta có: S(m)= 2 S(m/2) + m T(n) = S(m) = O(m lg m) = O(lg n lg lg n) 34
Phương pháp tính dần từng bước Ví dụ T(n) = 3T(n/4)+n T(n) = n+ 3 T(n/4) = n + 3(n/4 + 3T(n/16)) = n + 3 n/4 + 3 (n/16 + 3T(n/64)) ≤ n + 3n/4 + 9n/16 + 35
Ví dụ: Sắp xếp xen kẽ Merge-Sort(A,p,r){ 1. if p < r then { 2. q = [(p+r-1)/2]; 3. Merge-Sort(A,p,q); 4. Merge-Sort(A,q+1,r); 5. Merge(A,p,q,r); } } 36
Phân tích thuật toán Merge-Sort Đây là một thuật toán chia để trị. Chia: bước 2: θ(1) Trị: bước 3 và 4: 2T(n/2) Hợp lại:bước 5: θ(n) Tổng kết: T(n) = θ(1) nếu n=1 2T(n/2) + θ(n) nếu n >1 37
hồi trong sách Toán rời rạc. Toán rời rạc – Nguyễn Gia Định – ĐHKH Huế Tiểu luận: Các phương pháp sắp xếp trên mảng, đánh giá độ phức tạp. Giả sử mảng đó được lưu trữ trên bộ nhớ ngoài thì cách sắp xếp thế nào? 38
Chủ đề 3: Phương pháp “tham lam” I. Giới thiệu chung II. Thuật toán trên đồ thị 1) Cây bao trùm nhỏ nhất 2) Đường đi ngắn nhất III. Thuật toán sắp xếp lịch làm việc IV. Thuật toán “heurisitique” 1) Tô màu đồ thị 2) Người đưa hàng 39
Giới thiệu chung (greedy algorithms) Các thuật toán tham lam chủ yếu để giải quyết các bài toán tối ưu. Ta có: - Một tập các đối tượng - Một dãy các đối tượng đã lựa chọn - Một hàm để xem một tập các đối tượng có lập thành một giải pháp hay không (không nhất thiết tối ưu) - Một hàm để xem một tập đối tượng có là tiềm năng hay không - Một hàm để lựa chọn ứng viên có triển vọng nhất 40 - Một hàm đích cho giá trị của một giải pháp (để tối ưu hóa)
Cách giải quyết Tìm một tập các đối tượng lập thành một giải pháp và tối ưu hóa hàm đích. Từng bước một: - Đầu tiên tập đối tượng là rỗng - Tại mỗi bước, ta cố thêm vào một đối tượng tốt nhất còn lại (nhờ hàm chọn) + Nếu tập mới không là tiềm năng, bỏ đối tượng này đi, chọn đối tượng khác + Ngược lại, đối tượng mới này xếp vào cuối tập + Kiểm tra xem tập mới có là một giải pháp 41
Tính đúng đắn Một thuật toán “tham lam” chạy đúng nếu giải pháp được lựa chọn là tối ưu. Tiểu luận: Trình bày phương pháp tham lam và xây dựng 1 lớp các bài toán giải bằng tham lam. Với các bài toán chỉ ra các yếu tố nói trên. Cài đặt bài toán tô màu đồ thị bằng phương pháp tham lam và chạy thử nghiệm cho các đồ thị khác nhau. 42
Thuật toán sinh Thuật_toán Tham_lam{ // vào: tập hợp C các đối tượng // ra: tập S (giải pháp tối ưu) S = Ø; while(! solution(S) and C <> Ø) do { x = phần tử của C sao cho select(x) max; C = C \ {x}; if realisable(S U {x}) then S = S U {x};} if solution(S) then return S; else return “không có nghiệm”; } Xác định các yếu tố trên cho các bài / trang 25 - 2743
Cây bao trùm nhỏ nhất Bài toán: Cho đồ thị vô hướng liên thông G=(V,E). Mỗi cạnh e Є E có độ dài l(e). Tìm tập con T của E sao cho (V,T) vẫn liên thông và tổng Σ l(e) (e Є E) là nhỏ nhất. Vấn đề: Chứng minh (V,T) là một cây. “Cây bao trùm nhỏ nhất” 44
Một số khái niệm Một tập cạnh là: - một giải pháp nếu nó tạo một cây bao trùm - một tiềm năng nếu nó không chứa chu trình - một tập tiềm năng là một triển vọng nếu có thể thêm cạnh vào nó để đạt một giải pháp tối ưu Một cạnh “nối” một tập đỉnh nếu đúng một đỉnh của nó nằm trong tập đỉnh này 45
Mệnh đề: Cho đồ thị vô hướng liên thông G=(V,E). Mỗi cạnh e Є E có độ dài l(e). Cho B là một tập con (thực) của V. Cho T là một tập cạnh triển vọng sao cho không cạnh nào của T nối B. Cho e là một cạnh có độ dài min của B. Ta có: T U {e} là một triển vọng. 46
Thuật toán Kruskal (ý tưởng) - Lúc đầu T rỗng - Tại mỗi thời điểm (V,T) là một hợp rời các thành phần liên thông (tplt): trong mỗi tplt, các cạnh của T lập thành một cây bao trùm nhỏ nhất. - Cuối cùng: chỉ còn một tplt, và T là cây bao trùm nhỏ nhất của đồ thị G. 47
- Xếp các cạnh của E theo thứ tự tăng dần - Nếu một cạnh nối hai tplt, thêm vào T - Nếu không, bỏ đi, xét cạnh tiếp theo 48
Tính đúng đắn Vấn đề: chứng minh tính đúng đắn của thuật toán Kruskal 49
Ví dụ 2 3 1 1 2 6 6 5 4 4 6 3 8 4 5 7 3 4 7 50
Thuật toán Kruskal MST-Kruskal(G,l){ 1. Xếp E theo l tăng; n = # V; T = Ø; 2. Đặt n tplt, mỗi tplt chứa 1 phần tử của V; 3. do{ 4. (u,v) cạnh độ dài min chưa xét đến; 5. if set(u)<> set(v) then{ 6. T = T U (u,v); union(set(u),set(v)); 7. } 8. } while(#T = n-1) 9. return T; 51 10. }
Phân tích 1. Đánh giá độ phức tạp tính toán của thuật toán Kruskal 2. Nếu đồ thị không liên thông, kết quả sẽ thế nào ? 3. Một đồ thị có thể có nhiều cây bao trùm nhỏ nhất. Cây nào được cho bởi thuật toán Kruskal ? 52
Thuật toán Prim (ý tưởng) - Lúc đầu T rỗng và cây B chứa một đỉnh bất kỳ - Tại mỗi thời điểm, T là một cây bao trùm nhỏ nhất của B. Chọn một cạnh (u,v) độ dài min sao cho u Є V\B và v Є B. Thêm u vào B và (u,v) vào T - Cuối cùng: B=V, và T là cây bao trùm nhỏ nhất của đồ thị G. 53
Bài tập 1. Viết thuật toán Prim 2. Đánh giá độ phức tạp tính toán của t.t. 3. Chứng minh tính đúng đắn của t.t. 4. Một đồ thị có thể có nhiều cây bao trùm nhỏ nhất. Cây nào được cho bởi thuật toán Prim ? 5. Nếu đồ thị không liên thông, kết quả sẽ thế nào ? 54
Bài tập ◼ Xác định các yếu tố liên quan đến thuật toán tham lam cho các bài toán ở trang 25 – 27.
Đường đi ngắn nhất Bài toán: Cho đồ thị có hướng G=(V,E). Mỗi cạnh e Є E có độ dài l(e). Một đỉnh nguồn s. Tìm đường đi ngắn nhất từ s đến các đỉnh khác của G. 56
Thuật toán Dijkstra (ý tưởng) - Tập S gồm các đỉnh đã xác định đường ngắn nhất từ s - Tập C gồm các đỉnh còn lại - Lúc đầu S = {s} - Tại mỗi thời điểm, chọn trong C đỉnh có khoảng cách từ s min, thêm vào S - Cuối cùng S = V 57
Bổ đề: (đường con của một đường ngắn nhất cũng là đường ngắn nhất) Hệ quả: Ta có thể xây dựng một cây gốc s để đường duy nhất từ s đến mỗi u là đường có khoảng cách min 58
Khai triển ý tưởng - Bảng d: d[u]: khoảng cách min (tạm thời) từ s đến u - Bảng Adj: Adj[u] : các đỉnh liên hệ với u - Bảng l: l[u,v]: độ dài cạnh (u,v) (nếu không có (u,v) thì l[u,v] = ∞ - Bảng p: p[u] là “cha” của u trên đường từ s đến u - Kết quả là một cây gốc s, đường duy nhất từ s đến mỗi u là đường có khoảng cách min 59
Thuật toán Dijkstra Dijkstra(G,l,s){ 1. S= {s}; C = V \ {s}; n= #V; d[s]=0; 2. for u Є C do {d[u] = l[s,u]; p[u] = Null;} 3. while (C≠Ø) do { 4. chọn v Є C để d[v] min; 5. C = C \ {v}; S = S U {v}; 6. for w Є Adj[v] do { 7. if d[w] > d[u]+l[u,v] then { p[w]= v; 8. d[w]= d[v]+l[v,w];}} 60 }
Ví dụ 1 50 10 30 2 5 100 5 20 10 4 3 50 61
Tính đúng đắn Chứng minh quy nạp rằng: 1. Nếu u Є S: d[u] là khoảng cách min từ s đến u 2. Nếu u Є C: d[u] là khoảng cách min từ s đến u của các đường chỉ đi qua các đỉnh của S 3. Cuối cùng S = V, d[u] là khoảng cách cần tìm 62
Phân tích thuật toán Độ phức tạp: O(V^2) Nếu đồ thị ít cạnh: O(E lg V) 63
Sắp xếp lịch làm việc Bài toán 1: tối thiểu hóa thời gian chờ đợi: Một máy cái trong công nghiệp cần phục vụ khách hàng. Thời gian phục vụ khách hàng i là t[i]. Tìm cách xếp khách hàng để tối thiểu hóa tổng thời gian chờ đợi của khách. 64
Thuật toán Ý tưởng: Sắp xếp theo trình tự t[i] tăng. Vấn đề: 1. Chứng minh tính đúng đắn của thuật toán 2. Độ phức tạp của thuật toán 65
Sắp xếp lịch làm việc có lợi nhuận Bài toán: Cho một tập n việc phải làm, mỗi việc trong thời gian đơn vị. Việc i sẽ đem lại lợi nhuận g[i] nếu được thực hiện trước hạn d[i]. Tìm cách thực hiện các công việc để có lợi nhuận cao nhất 66
Ví dụ Dữ kiện i 1 2 3 4 g[i] 50 10 15 30 d[i] 2 1 2 1 Các khả năng Công việc 1,3 2,1 2,3 3,1 4,1 4,3 Lợi nhuận 65 60 25 65 80 45 67
Ý tưởng thuật toán Một tập hợp công việc là tiềm năng nếu có một dãy (tiềm năng) thực hiện mọi công việc của tập này trước thời hạn. Thuật toán: Từng bước một, thêm vào tập công việc một công việc i chưa được xét có g[i] max và tập mới vẫn là tiềm năng. 68
Chạy thuật toán trên ví dụ 1. Chọn việc 1. Tập {1} là tiềm năng 2. Chọn việc 4. Tập {1, 4} là tiềm năng 3. Chọn việc 3. Tập {1, 4, 3} không là tiềm năng. Bỏ việc 3 đi 4. Chọn việc 2. Tập {1, 4, 2} không là tiềm năng. Bỏ việc 2 đi 5. Kết quả tập {1, 4} được chọn. Thực hiện theo thứ tự 4, 1 69
Xác định tập tiềm năng Bổ đề: Cho J là một tập công việc và cho p= {s1,s2, ,sk} là một hoán vị của các việc đó sao cho d[s1]≤d[s2] ≤ ≤d[sk]. Tập J là tiềm năng ≈ dãy p là tiềm năng. 70
Tính đúng đắn của thuật toán Cho I là tập nhận được từ thuật toán Cho J là một tập tối ưu. Chứng minh lợi nhuận của I và của J bằng nhau. 71
Quy ước Ký hiệu: n việc được xếp thứ tự 1,2, ,n để g giảm Tập việc là một bảng j n>0, d[i]>0 Biến chặn 0: d[0]=0; j[0]=0 72
Thuật toán Săp_xếp(d){ d[0]=0; j[0]=0; j[1]=1; k=1; for i=2 to n do{ r=k; while d[j[r]]>max(d[i],r) do r=r-1; if d[j[r]]≤d[i] and d[i]>r then { for (l=k,r+1,-1) do j[l+1]=j[l]; j[r+1]=i; k=k+1;}} return j; } 73
Phân tích thuật toán 1. Kiểm tra thuật toán 2. Tính độ phức tạp của thuật toán 3. Cải tiến cách kiểm tra tập tiềm năng. Viết thuật toán mới với độ phức tạp O(n lg n) 74
Thuật toán định hướng Với một số bài toán tối ưu, thuật toán tìm nghiệm chính xác có độ phức tạp rất lớn. Ta sử dụng các thuật toán đơn giản, tìm nghiệm xấp xỉ. (chú ý rằng trong 1 số trường hợp, t.t.x.x không cho kết quả tối ưu) 75
Tô màu đồ thị Bài toán: Cho một đồ thị vô hướng G=(V,E). Tô màu G là tô màu các đỉnh sao cho hai đỉnh liên thuộc không cùng màu. Tìm cách tô màu sử dụng ít màu nhất. Kết quả đã biết: các thuật toán tối ưu đã biết đều có độ phức tạp là hàm mũ. Mục đích: Tìm thuật toán xấp xỉ. 76
Thuật toán xấp xỉ Thuật toán: 1. chọn 1 màu và 1 đỉnh bất kì, tô màu đỉnh đó. 2. xét các đỉnh còn lại, đỉnh nào tô được màu vừa chọn thì tô 3. nếu còn lại một số đỉnh, quay lại bước 1 77
Đánh giá Cho đồ thị G, p là một hoán vị các đỉnh của G, c(p) là số màu nhận được bởi t.t.x.x, c là số màu tối ưu. Ta có 1. Tồn tại một hoán vị p để c(p)=c 2. Với mọi a>0, tồn tị G, p để c/c(p) < a Như vậy t.t.x.x có thể đạt tối ưu, và cũng có thể “xấu” tùy ý. 78
Người đưa hàng Bài toán: Cho một đồ thị có hướng, các cạnh có độ dài. Tìm một chu trình ngắn nhất bắt đầu và kết thúc tại một đỉnh, và đi qua mỗi đỉnh còn lại đúng một lần. G=(V,E), V={1,2, ,n}, L[i,j]: độ dài cạnh 79
Thuật toán xấp xỉ Ở mỗi bước, chọn một cạnh ngắn nhất chưa được xét thỏa mãn: • Không tạo nên một chu trình với các cạnh đã chọn (trừ trường hợp cạnh cuối cùng) • Không là cạnh thứ 3 liên hệ với cùng một đỉnh. 80
Ví dụ đến j= 2 3 4 5 6 Từ i= 1 3 10 11 7 25 2 6 12 8 26 3 9 4 20 4 5 15 5 18 Các cạnh được chọn là: 12, 35, 45, 23, 46, 16, tạo chu trình (1,2,3,5,4,6,1), độ dài 58. Kết quả này không tối ưu (56 là tối ưu) 81
Chủ đề 4: Phương pháp “chia để trị” I. Giới thiệu chung II. Xác định ngưỡng III. Phương pháp “phân đôi” IV. Sắp xếp “xen kẽ”. Sắp xếp nhanh V. Số học các số nguyên lớn VI. Nhân ma trận VII. Giới thiệu về mật mã 82
Giới thiệu chung (divide and conquer algorithms) Ý tưởng: để giải quyết một bài toán, 1. chia ra làm nhiều phần nhỏ hơn, 2. giải quyết từng phần độc lập, 3. sau đó từ các kết quả này, xây dựng kết quả của bài toán ban đầu. Viêc giải quyết các phần nhỏ hơn này có thể thực hiên một cách đệ qui. 83
Thuật toán sinh Thuật_toán DAC(x){ //t.t. này cho kết quả y ứng với đầu vào x if (x đủ nhỏ) then return base(x); chia x thành x_1, x_2, , x_k; for (i=1 to k) do y_i = DAC(x_i); hợp các y_i lại để tìm ra y; return y; } 84
Bài toán tìm kiếm Bài toán: Cho bảng T[1 n] các số được xếp tăng dần. Cho số x. Tìm phần tử trong T có giá trị x Thuật toán đơn giản: while (T[i]≤x) do if (T[i]=x) then return i; else i=i+1; Độ phức tạp: O(n) 85
Phương pháp “phân đôi” function dicto (T[i j],x){ if (i=j) then { if (T[i]=x) then return i; else return “không có”; else { k=(i+j+1)/2; if (x < T[k]) then return dicto(T[i k-1],x); else return dicto(T[k j],x); } } Độ phức tạp : ? 86
Sắp xếp xen kẽ (Merge sort) Ý tưởng: Để xếp bảng T: 1. Chia T thành 2 bảng độ dài bằng nhau 2. Sắp xếp mỗi bảng con này 3. Từ hai bảng con đã sắp, xếp xen kẽ lại để được bảng T sắp xếp Chú ý: bước 2 được thực hiện đệ qui 87
Thuật toán Merge-sort Merge-Sort(A,p,r){ 1. if p < r then { 2. q = [(p+r-1)/2]; 3. Merge-Sort(A,p,q); 4. Merge-Sort(A,q+1,r); 5. Merge(A,p,q,r); } } 88
Phân tích thuật toán Đây là một thuật toán chia để trị. Chia: bước 2: θ(1) Trị: bước 3 và 4: 2T(n/2) Hợp lại:bước 5: θ(n) Tổng kết: T(n) = θ(1) nếu n=1 2T(n/2) + θ(n) nếu n >1 89
Sắp xếp nhanh (quicksort) Chia: Bảng T[p r] được chia thành 2 phần T[p q] và T[q+1 r] sao cho mọi phần tử trong bảng 1 nhỏ hơn mọi phần tử bảng 2 Trị: Mỗi bảng con được sắp xếp đệ qui Hợp: Vì mỗi bảng đã đúng vị trí. Kết thúc. 90
Thuật toán quicksort Quicksort(A,p,r){ 1. if (p<r) then { 2. q=Partition(A,p,r); 3. Quicksort(A,p,q); 4. Quicksort(A,q+1,r); } } 91
Chia đôi bảng (Partition) Ví dụ: 5 3 2 6 4 1 3 7 5 3 2 6 4 1 3 7 3 3 2 6 4 1 5 7 3 3 2 6 4 1 5 7 3 3 2 1 4 5 6 7 92
Partition Partition(A,p,r){ 1. x = A[p]; 2. i = p-1; j = r+1; 3. while (i<j) do { 4. repeat j = j-1 until A[j] ≤ x; 5. repeat i = i+1 until A[i] ≥ x; 6. if (i<j) then exchange (A[i], A[j]); 7. else return j; 8. } } 93
Phân tích thuật toán 1. Partition(A,p,r): O(r-p) 2. Trường hợp xấu nhất: mỗi lần chia bảng ta được 1 bảng 1 phần tử, và một bảng tất cả phần tử còn lại: T(n) = T(n-1) + θ(n). Như vậy: T(n) = θ(n^2) 3. Trường hợp tốt nhất: bảng luôn phân đôi đều: T(n) = 2 T(n/2) + θ(n). Như vậy: T(n) = θ(n lg n) Câu hỏi: Cho ví dụ về trường hợp xấu nhất, tốt nhất. 94
Số học các số nguyên lớn Phép nhân hai số nguyên cực lớn: Bài toán: Cho u và v là hai số nguyên lớn, giả sử mỗi số biểu diễn bởi n chữ số. Tìm thuật toán nhân u và v hiệu quả. 95
Phân tích vấn đề n u a b v c d n u v = 10^{2s} ac + 10 ^s (ad+bc) + bd (s = n/2) 96
Phân tích vấn đề (tiếp) Nhận xét: r = (a+b)(c+d) = ac+(ad+bc)+bd Thay vì tính 4 phép nhân ac, bd, ad, bc, Ta tính ac, bd, và r 97
Thuật toán nhân Mult(u,v){ 1. n= min(size(u), size(v)); 2. if (n bé) then return uv; 3. else { s = n/2; 4. a= u div (10^s), b= u mod 10^s; 5. c= v div (10^s), d= v mod 10^s; 6. r= Mult(a+b,c+d); 7. p=Mult(a,c); q= Mult(b,d); 8. t = r-p-q; 9. return(p*10^{2s} + t*10^s+q); 10. } } 98
Độ phức tạp thuật toán T(n) = 3 T(n/2)+ θ(n) T(n) = θ(n ^{lg 3}) ≈ θ(n^{1,59}) 99
Nhân hai ma trận Bài toán: Cho 2 ma trận A, và B, kích cỡ n*n. Tìm ma trận tích C = A*B. Thuật toán đơn giản: T(n) = θ(n^3) 100
Thuật toán Strassen Ý tưởng: A = a1 a2 b1 b2 B = a3 a4 b3 b4 m2+m3 m1+m2+m5+m6 A*B = m1+m2+m4-m7 m1+m2+m4+m5 101
Tính m_i m1 = (a3+a4-a1)(b4-b2+b1) m2 = a1 *b1 m3 = a2* b3 m4= (a1-a3)(b4-b2) m5= (a3+a4)(b2-b1) m6 = (a2-a3+a1-a4)*b4 m7 = a4*(b1+b4-b2-b3) 102
Độ phức tạp tính toán T(n) = 7 T(n/2) + θ(n^2) ≈ θ(n^{2,81}) 103
Chủ đề 5: Phương pháp qui hoạch động I. Giới thiệu chung II. Bài toán hướng dẫn viên du lịch III. Các đường đi ngắn nhất IV. Người đưa hàng 104
Giới thiệu chung So sánh với phương pháp “chia để trị”: - Chia thành các phần nhỏ hơn - Thực hiện độc lập từng phần - Hợp các kết quả nhỏ lại. Vấn đề: - nếu có nhiều phần nhỏ giống nhau, liên quan đến nhau - => sử dụng kết quả đã tính: lập bảng lưu trữ dần các kết quả của các phần con 105
Chia để trị: từ trên xuống: nhìn ngay vào vấn đề lớn, chia nhỏ ra, trị phần con Quy hoạch động: từ dưới lên: bắt đầu từ các trường hợp đơn giản, nhỏ, xây dựng dần lên, đến bài toán tổng kết cuối cùng. 106
Ví dụ nhỏ: phép tính tổ hợp Tính C(n,k) = n!/(n-k)!k! Thuật toán đơn giản: function C(n,k){ if (k=0 or k=n) then return 1; else return C(n-1,k-1)+C(n,k-1); } Câu hỏi: tính độ phức tạp tính toán của thuật toán này 107
Ví dụ nhỏ: phép tính tổ hợp (tiếp) Cải thiện thuật toán: dùng tam giác Pascal 0. 1 1. 1 1 2. 1 2 1 3. 1 3 3 1 4. 1 4 6 4 1 5. 1 5 10 10 5 1 Câu hỏi: Viết thuật toán bằng cách dùng bảng lưu trữ kết quả, tính độ phức tạp tính toán của t.t. đó. 108
Hướng dẫn viên du lịch Giới thiệu bài toán: Đưa khách đi từ thành phố 1 đến thành phố 7 Khoảng cách giữa các thành phố cho trước. Chi phí đi 1 chặng là (x-100)^2, với x là độ dài chặng đi, Tiền nghỉ là 200. Tìm lộ trình để tối thiếu chi phí. 109
Phân tích bài toán Gọi chi phí đi từ thành phố i -> 7 là fi7. Chi phí từ 5 ->7 là f57 = ? Chi phí từ 4 ->7 là f47 = ? Chi phí từ 1 -> 7 là f17= ? Nhận xét: Quá trình qui hoạch động gồm các bước? Lưu vết 110
Các đường đi ngắn nhất Bài toán: Cho đồ thị có hướng G=(V,E). Mỗi cạnh e Є E có độ dài l(e). Tìm đường đi ngắn nhất giữa các cặp đỉnh của G. Ký hiệu: V={1,2, ,n} L[i,i] = 0, L[i,j] = l(e) nếu e=(i,j) L[i,j] = ∞ nếu không có cạnh (i,j) . 111
Ý tưởng thuật toán 1. Nếu k nằm trên 1 đường đi ngắn nhất từ i đến j thì đoạn từ i đến k và từ k đến j cũng là những đường đi ngắn nhất. 2. Xây dựng D[i,j] độ dài min từ i đến j: 1. Lúc đầu: D=L 2. Sau bước thứ k, D[i,j] là độ dài min từ i đến j (mà chỉ đi qua các đỉnh 1,2, ,k) 3. Sau n bước, D[i,j] là độ dài min từ i 112 đến j.
Ví dụ 0 5 ∞ ∞ D0=L= 50 0 15 5 15 30 ∞ 0 15 4 15 ∞ 5 0 1 5 0 5 ∞ ∞ D1= 50 0 15 5 5 50 15 5 30 35 0 15 30 15 20 5 0 2 3 0 5 20 10 0 5 20 10 15 0 5 15 10 D2= 50 0 15 5 D3= 50 0 15 5 D4= 20 0 10 5 30 35 0 15 30 35 0 15 30 35 0 15 15 20 5 0 15 20 5 0 15 20 5 0 113
Thuật toán Floyd Floyd(L){ array D = L; for (k=1 to n) do for (i=1 to n) do for (j=1 to n) do D[i,j]= min(D[i,j],D[i,k]+D[k,j]); return D; } 114
Bài tập 1. Tìm độ phức tạp của thuật toán Floyd 2. Chứng minh tính đúng đắn của thuật toán 3. Nếu muốn biết không chỉ độ dài mà cả đường đi ngắn nhất, phải thêm gì vào thuật toán ? 4. Viết thuật toán xác định xem có đường đi giữa các cặp đỉnh của G. 115
Người đưa hàng Bài toán: Cho một đồ thị có hướng, các cạnh có độ dài. Tìm một chu trình ngắn nhất bắt đầu và kết thúc tại một đỉnh, và đi qua mỗi đỉnh còn lại đúng một lần. G=(V,E), V={1,2, ,n}, L[i,j]: độ dài cạnh. 116
Ý tưởng thuật toán 1. Chu trình bắt đầu từ đỉnh 1. Min chu trình bắt đầu từ 1 = min (L[1,j]+ min đường từ j đến 1) 2. Cho S tập con của V\{1}, i Є V\S: g(i,S)=min (đường từ i đến 1 qua S đúng 1 lần) 3. Min chu trình = g(1, V\{1}) = min(L[1,j]+g(j,V\{1,j})) 2≤j≤n 4. g(i,S)= min (L[i,j] + g(j,S\{j})) jЄS 5. g(i,Ø)=L[i,1], i=2,3, ,n 117
Ví dụ 0 10 15 20 5 0 9 10 10 L = 6 13 0 12 1 5 2 8 8 9 0 10 8 20 8 13 9 15 1. Tính g(j,Ø); j= 2,3,4 6 2. Tính g(j,S) với |S|=1;j=2,3,44 12 3 3. Tính g(j,S) với |S|=2;j=2,3,4 4. Tính g(1,{2,3,4}) 9 118
Bài toán cái túi và bài toán dãy con tăng dài nhất Xem sách: Giải thuật và lập trình – Lê Minh Hoàng. Trang 153 - 158 119
Chủ đề 6: Thuật toán trên đồ thị I. Giới thiệu chung II. Khám phá cây III. Khám phá theo chiều rộng IV. Khám phá theo chiều sâu V. “Branch and bound” 120
Giới thiệu chung 1. Đồ thị biểu diễn nhiều vấn đề: 1. Mạng, trò chơi, sơ đồ, 2. Cấu trúc dữ liệu: đỉnh là một số bit bộ nhớ, cạnh là các con trỏ, 2. Biểu diễn đồ thị, có nhiều cách: 1. Ma trận: a[i,j]=1 nếu có cạnh (i,j), =0 nếu không 2. Dãy liên hệ: Adj[i] là một dãy các cạnh được nối với i, i là các đỉnh của đồ thị. 121
Khám phá cây Xét các cây nhị phân, có 3 cách khám phá: 1. Thứ tự trước (prefix) 2. Thứ tự giữa (infix) 3. Thứ tự sau (suffix) Visit_prefix (r){ //r là gốc của cây print (r.value); if (r.left Null) then visit_prefix(r.right); } Chứng minh độ phức tạp tính toán của t.t. là O(n) 122
Khám phá theo chiều rộng (Breadth-first search) 1. Chọn một đỉnh nguồn s, và thăm các đỉnh khác theo thứ tự từ gần đến xa s 2. Thăm u: thăm tất cả các lân cận của u, sau đó mới thăm lân cận của các đỉnh này 3. Xây dựng cây có gốc s. 4. Tô màu các đỉnh: 1. Lúc đầu tất cả màu trắng 2. Bắt đầu thăm u, tô u màu vàng 3. Nếu đã thăm mọi lân cận của u, tô u màu đỏ 5. Một xâu nhớ (FIFO) Q lưu trữ các đỉnh vàng 123
Thuật toán BFS (G,s){ for (u Є V\{s}) do { color[u]= T ; d[u]=∞; p[u]=Null;} color[s]= V ; d[s]=0; p[s]=Null; Q={s}; while (Q<>Ø) do { u=head(Q); for (v Є Adj[u]) do{ if (color[v]=T) then { color[v]=V; d[v]=d[u]+1; p[v]=u; add(Q,v);}} sup(Q); color[u]=Đ;} } 124
Phân tích 1 Định lý: Nếu đồ thị liên thông. Sau BFS, ta nhận được cây gốc s và đường đi từ s đến u là 1 đường đi ngắn nhất từ s đến u trong G. 2 Tính độ phức tạp và bộ nhớ cho t.t. BFS 125
Khám phá theo chiều sâu (Deep-first search) 1. Thăm u, rồi thăm 1 lân cận v của u, rồi thăm 1 lân cận của v, 2. Hàm thăm này được gọi đệ qui. 3. Sau mỗi lệnh thăm v lân cận của u, nếu u còn lân cận nào, thì lại thăm, 4. Nếu bắt đầu từ s, sau khi thăm s, còn các đỉnh, ta lại chọn một đỉnh mới để thăm. 126 5. Xây dựng được một rừng.
Ký hiệu 1. d[u]: thời điểm bắt đầu thăm u 2. f[u]: t.đ. Kết thúc thăm u 3. p[u]: cha của u 4. color[u] =T trước d[u], = V đang thăm u = Đ sau f[u] 127
Thuật toán DFS(G){ for (u Є V) do { color[u]=T; p[u]=Null;} time=0; for (u Є V) do if (color[u]=T) then DFS-visit(u); } 128
Thuật toán (tiếp) DFS-visit(u){ color[u]=V; d[u]=time=time+1; for (vЄAdj[u]) do { if (color[v]=T) then { p[v]=u; DFS-visit(v);} } color[u]=Đ; f[u]=time=time+1; } 129
Tìm kiếm sâu lặp procedure Depth_Limited_Search(d); begin 1. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu u0; depth(u0) 0; 2. loop do 2.1 if L rỗng then {thông báo thất bại; stop}; 2.2 Loại trạng thái u ở đầu danh sách L; 2.3 if u là trạng thái kết thúc then {thông báo thành công; stop}; 2.4 if depth(u) <= d then for mỗi trạng thái v kề u do {Đặt v vào đầu danh sách L; depth(v) depth(u) + 1};
procedure Depth_Deepening_Search; begin for d  0 to max do {Depth_Limited_Search(d); if thành công then exit} end;
Sắp xếp topology Bài toán: Cho G là đồ thị có hướng, không chu trình. Một sắp xếp topology của G là một cách xếp tuyến tính các đỉnh của G sao cho i trước j nếu (i,j) là cạnh. Ứng dụng: - Sắp xếp các công việc thỏa mãn một số thứ tự. 132 - Biểu diễn tập có thứ tự bộ phận
Thuật toán sắp xếp topology Topological-Sort(G){ DFS(G); Xếp vào theo thứ tự f[u] giảm } Vấn đề: chứng minh tính đúng đắn của t.t. và tính độ phức tạp. 133
Ví dụ 134
Thành phần liên thông mạnh Định nghĩa: Đồ thị có hướng là liên thông mạnh nếu giữa hai đỉnh luôn có đường đi. Một đồ thị có hướng bất kỳ được phân thành các t.p.l.t.m., mỗi t.p. là một đồ thị con lớn nhất liên thông mạnh. Bài toán: phân tích G thành các t.p.l.t.m. 135
Thuật toán tính các t.p.l.t.m Tpltm (G){ 1. DFS(G) để tính f[u]; 2. Tính G’ 3. DFG(G’), các đỉnh của G’ được xếp theo f giảm 4. Mỗi cây trong rừng từ bước 3 là một t.p.l.t.m } G’=(V,E’); E’={(u,v): (v,u) Є E} Vấn đề: chứng minh tính đúng đắn của t.t. và tính độ phức tạp của nó. 136
Ví dụ 137
Tìm kiếm có kinh nghiệm. ◼ Tìm kiếm tốt nhất - đầu tiên = Tìm kiếm rộng + Hàm đánh giá. ◼ Tìm kiếm leo đồi = Tìm kiếm sâu + Hàm đánh giá. ◼ Tìm kiếm beam
Tìm kiếm đường đi ngắn nhất ◼ Thuật toán tìm kiếm nhánh-và-cận = Tìm kiếm leo đồi + hàm cận. ◼ Xem các ví dụ trong [2]/26 – 29. ◼ Nhánh cận và bài toán cái túi. ◼ Nhánh là? ◼ Cận là? ◼ Mục đích của cận là?
Procedure BanchBound; Begin Lowcost := ; Cost* :=0; Tính S1; K :=1; While k>0 do Begin While (Sk <>) and (cost* <lowcost) do Begin Chọn ak Sk; Sk :=Sk-{ak}; Cost* :=cost*(a1, , ak); If (a1, , ak) là nghiệm then If cost (a1, , ak) < lowcost then Lowcost := cost((a1, , ak); k :=k+1; Tính Sk; End; k :=k-1; cost* := cost*(a1, , ak); End; End;
Tìm kiếm đối tượng tốt nhất Tìm kiếm leo đồi. Tìm kiếm gradient.
Tìm kiếm mô phỏng luyện kim procedure Simulated_Anneaning; begin t  0; u  trạng thái ban đầu nào đó; T  nhiệt độ ban đầu; repeat v  trạng thái được chọn nhẫu nhiên trong lân cận u; if cost(v) > cost(u) then u  v else u  v với xác suất e /T; T  g(T, t); t  t + 1; until T đủ nhỏ
Tìm kiếm mô phỏng sự tiến hóa. Thuật toán di truyền ◼ procedure Genetic_Algorithm; ◼ begin ◼ t  0; ◼ Khởi tạo thế hệ ban đầu P(t); ◼ Đánh giá P(t) (theo hàm thích nghi); ◼ repeat ◼ t  t + 1; ◼ Sinh ra thế hệ mới P(t) từ P(t-1) bởi ◼ Chọn lọc ◼ Lai ghép ◼ Đột biến; Đánh giá P(t);
Tìm kiếm có đối thủ ◼ Xem thêm trong Giáo trình Trí tuệ nhân tạo. ◼ Lý thuyết trò chơi và vận dụng nó trong dạy học Tin học.
Chủ đề 7: Giới thiệu về phương pháp xác suất I. Giới thiệu chung II. Phân loại các thuật toán xác suất III. Thuật toán xác suất số IV. Thuật toán Sherwood V. Thuật toán Las Vegas VI. Thuật toán Monte Carlo 145
Giới thiệu chung ◼ Khái niệm: Thuật toán xác xuất là thuật toán sử dụng đầu vào là các số ngẫu nhiên. ◼ Nhận xét: - Đầu vào này phải hữu ích - Các số này là “giả ngẫu nhiên” 146
Ví dụ Thuật toán sắp xếp Quicksort: - Phần tử so sánh được chọn ở đầu bảng: - Độ phức tạp xấu nhất là 0(n^2) - Độ phức tạp trung bình là 0(n lg n) Vấn đề: nếu bảng đã gần xếp đúng, không hiệu quả. Giải quyết: Chọn phần tử so sánh một cách ngẫu nhiên trong bảng. 147
Phân loại các thuật toán xác suất Thuật toán xác suất số Thuật toán Monte Carlo Thuật toán Las Vegas Thuật toán Sherwood 148
Thuật toán Monte Carlo Bài toán ví dụ: Thử xem một số có nguyên tố hay không. Ý nghĩa: trong mật mã cần tìm các số nguyên tố lớn. 149
Thuật toán đơn giản Tính nguyên tố (n) { while (i< n) do { if (n chia hết cho i) return sai; i = i+1; } return đúng; } Nhận xét: cho I chạy đến sqrt(n) - Để thử tính chia hết: thời gian nhiều. 150
Phép thử Miller Rabin Nguyên tắc: a) n nguyên tố, a a^{n-1} = 1 (mod n) b) n nguyên tố, a a = 1, -1 (mod n) Câu hỏi: viết thuật toán test (n,a) thử hai điều kiên trên. Độ p.t.t.t = ? 151
Thuật toán Miller-Rabin M-R(n) { i=1; chọn a ngẫu nhiên < n; while (i<k and test (n,a)=false) do { chọn a ngẫu nhiên < n; i = i+1;} return test(n,a); } - Số lần chọn các số ngẫu nhiên a là k lần. - Tính độ p.t.t.t 152
Xác xuất của thuật toán Tính chất: Nếu n lẻ, thì có ít nhất ¾ số a < n sẽ cho kết quả test(n,a)= true nếu n không nguyên tố. Như vậy sau k lần thì xác xuất không tìm thấy a cho test(n,a)=true là (1/4)^k. Và ta có thể cho xác suất này nhỏ tùy ý. 153
Thuật toán Las-Vegas Bài toán: Bầu một người chủ. Có n người, cần chọn ra một người. Đòi hỏi: các lần chạy t.t. khác nhau, chọn ra những người khác nhau. Ý nghĩa: Trong bài toán mạng, tránh tình trạng tắc nghẽn khi các máy cùng đến một lúc. 154
Thuật toán 1. Mỗi người chọn một số ngẫu nhiên từ 1 đến m (số người chọn) 2. Nếu không có ai chọn số 1, quay về bước 2. 3. Nếu có ít nhất 2 người chọn số 1, thì những người này tiếp tục, quay về bước 1. 4. Nếu chỉ có 1 người chọn số 1 thì người này là chủ. 155
Tính chất của thuật toán - Thuật toán không chắc chắn là sẽ dừng - Nhưng nếu dừng nó luôn cho kết quả đúng. 156
Phân tích thuật toán Xác xuất để có k người vào vòng 2 là: p(n,k) = C^k_n (1/n)^k (1-1/n)^(n- k) P(n,0) = (1-1/n)^n. Xác xuất để vòng 1 lặp l lần là (1- 1/n)^{nl} Xác xuất để t.t. không dừng là = 0 157
Chủ đề 8: Về độ phức tạp tính toán I. Cây quyết định II. Qui dẫn III. Giới thiệu về NP- đầy đủ 1) Lớp P và NP 2) Một số bài toán NP- đầy đủ 3) Định lý Cook 4) Một số qui dẫn 158
Cây quyết định Vấn đề: Có một bảng n phần tử cần được sắp xếp tăng dần. Cần tối thiểu bao nhiêu phép so sánh để thực hiện thuật toán ? Chú ý: chỉ tính so sánh các phần tử, không tính so sánh các chỉ số. 159
Định nghĩa cây quyết định Định nghĩa: một cây quyết định là một cây nhị phân có hướng và được dán nhãn, - mỗi đỉnh trong chứa một phép so sánh 2 phần tử cần được xếp - Mỗi lá chứa một hoán vị các phần tử Cho một thứ tự, một đường đi trong cây bắt đầu từ gốc, và đặt các câu hỏi mà nó gặp: nếu trả lới “đúng” thì rẽ trái, nếu “không” thì rẽ phải. Đường kết thúc ở một lá. Lá này chứa kết quả ứng với thứ tự vào. 160
Tính chất - Một cây quyết định là đúng để sắp xếp n phần tử nếu với mọi thứ tự vào đều cho ra kết quả đúng với thứ tự đó. - Một cây quyết định là gọn nếu không có đường nào mâu thuẫn, tức là mọi lá đều nhận được từ gốc qua một dãy các quyết định đúng. 161
Ví dụ cây quyết định sắp 3 số A<B B<C B<C A < B < C A<C A<C C ≤ B ≤ A A < C ≤ B C ≤ A< B B ≤ A <C B < C < A 162
Thuật toán Mọi cây quyết định đúng để sắp xếp n số sẽ cho một thuật toán tương ứng để sắp xếp n số đó. Bài tập: 1. Viết thuật toán tương ứng với cây quyết định đã cho. 2. Vẽ cây quyết định gọn tương ứng cho các t.t. sắp xếp chèn vào, lựa chọn, xen kẽ với 3 số. 163
Nhận xét - Vẽ cây quyết định cho thuật toán sắp xếp vun đống cho 3 số. - Nhận xét gì về cây này: có bao nhiêu lá ? Có các phép so sánh thừa hay không ? Cây có gọn không ? 164
- Nhận xét gì về độ cao của các cây quyết định ? - Độ dài lớn nhất từ đỉnh tới một lá nói lên điều gì ? 165
Thời gian tối đa Bổ đề 1: Mọi cây nhị phân k lá có độ cao ít nhất là bằng [lg k] Bổ đề 2: Mọi cây quyết định đúng để xếp n số có ít nhất k! lá Định lý: Mọi thuật toán để xếp n số bằng các phép so sánh sẽ mất thời gian là Ω(n lg n) trong trường hợp xấu nhất 166
Thời gian trung bình Định nghĩa: độ cao trung bình của cây nhị phân A là tổng độ sâu của các lá chia cho số lá Bổ đề 3: Mọi cây nhị phân k lá có độ cao trung bình ít nhất là bằng [lg k] Định lý: Mọi thuật toán để xếp n số bằng các phép so sánh sẽ mất thời gian trung bình là Ω(n lg n). 167
Bài tập 1. Tìm công thức chính xác cho số các phép so sánh trong trường hợp xấu nhất của t.t. xếp chèn vào và lựa chọn. 2. Tìm công thức chính xác cho số các phép so sánh tính trung bình của t.t. xếp chèn vào và lựa chọn. 3. So sánh hai kết quả này. 168
Một ví dụ nhỏ function sort(T[1 n]){ i = min (T); j = max(T); table C[i j]=0; for (k=1 to n) do C[T[k]]=C[T[k]]+1; k=1; for (p=i to j) do for (q=1 to C[p]) do {T[k]=p; k=k+1;} } 169
Câu hỏi 1. Chạy t.t. trên cho bảng T[1 10] = {3,1,4,1,5,9,2,6,5,3} 2. Tính xem để xếp n số, t.t. này thực hiện bao nhiêu phép so sánh giữa các số 170
Thời gian đa thức: Vấn đề trừu tượng Vấn đề trừu tượng Q: là một quan hệ hai ngôi trên tập các trạng thái I và tập các lời giải S. Bài toán quyết định: là có một lời giải Co’/Không Bài toán tối ưu: có một đại lượng cần cực tiểu (đại) hóa có thể đưa về bài toán quyết định: đặt một giá trị biên. 171
Mã hóa - Một mã hóa của một tập S các đối tượng trừu tượng là một ánh xạ e từ S vào các dãy nhị phân. - Một t.t. máy tính giải một vấn đề trừu tượng sẽ nhận một mã hóa của một trạng thái như là đầu vào. - Vấn đề cụ thể: là vấn đề mà các trạng thái là các dãy nhị phân. 172
Thuật toán thời gian đa thức Thuật toán giải một vấn đề cụ thể trong thời gian O(T(n)) nếu: mỗi đầu vào i có độ dài n, t.t. cho kết quả trong thời gian = O(T(n)). Một vấn đề cụ thể giải được trong thời gian đa thức nếu tồn tại t.t. giải nó trong t.g. O(n^k), k hằng số. Lớp P = {vấn đề cụ thể giải được trong t.g.đ.t.} 173
Mã hóa chuẩn - Một vấn đề trừu tượng có thể có nhiều cách mã hóa thành vấn đề cụ thể. - Mã hóa chuẩn: các số tự nhiên theo biểu diễn (tương đương đa thức với) nhị phân. - Một tập phần tử được mã theo dãy các mã của các phần tử. - Đồ thị, công thức, được mã tương tự * Ta có thể xét vấn đề trừu tượng như vấn đề cụ thể 174
Ngôn ngữ Bảng chữ cái A: tập hữu hạn các ký tự. Từ: 1 dãy các chữ cái của A. Một ngôn ngữ L trên A: 1 tập các từ trên A. Từ rỗng: ε Ngôn ngữ rỗng: Ø Ngôn ngữ gồm tất cả các từ trên A: A* 175
Các phép toán trên các ngôn ngữ - Hợp, giao, - phần bù Ḹ = A* \ L - dán (concatenation): L=L1.L2 = {xy: x Є L1, y Є L2} - Bao đóng Kleene: L*={ε} U L U L^2 U L^3 U 176
Bài toán - ngôn ngữ Σ = {0,1}. Bài toán quyết đinh Q  Ngôn ngữ L = {x Є Σ*: Q(x) = 1} Thuật toán A chấp nhận một từ x Є Σ*: nếu với đầu vào x, A cho kết quả A(x) = 1. A loại bỏ x nếu A(x) = 0 Ngôn ngữ L được chấp nhận bởi A:L={x Є Σ*:A(x)=1} L được chấp nhận bởi A trong t.g.đ.t. nếu có hằng k: mọi từ x độ dài n được A chấp nhận trong t.g O(n^k) - Chú ý: nếu x |Є L, A có thể không loai bỏ x, mà chạy không dừng. 177
Ngôn ngữ được quyết định Một ngôn ngữ L được quyết định bởi t.t. A: nếu x thuộc L  A chấp nhận x và x không thuộc L  A loại bỏ x. L được quyết định bởi A trong t.g.đ.t. nếu có hằng k: mọi từ x độ dài n được A quyết định trong t.g O(n^k) 178
Lớp P P = {L ngôn ngữ trên Σ: có t.t. A quyết đinh L trong t.g.đ.t.} Định lý: P = {L ngôn ngữ trên Σ: có t.t. A ch L chấp nhận L trong t.g.đ.t.} 179
Thuật toán kiểm chứng ◼ Thuật toán kiểm chứng: là một t.t. A hai biến, một biến bình thướng là một xâu nhị phân đàu vào x, và một biến là xâu nhị phân y (được gọi là xâu kiểm chứng). ◼ T.t A kiểm chứng x nếu tồn tại xâu kiểm chứng y để A(x,y) =1. ◼ Ngôn ngữ L được kiểm chứng bởi A là: L = {x Є Σ*: tồn tại y Є Σ*: A(x,y)=1 } 180
Lớp NP ◼ Lớp độ phức tạp tính toán NP là lớp các ngôn ngữ được kiểm chứng trong thời gian đa thức. ◼ L Є NP  tồn tại t.t. 2 biến t.g.đ.t. A và hằng số c sao cho: L= {x Є Σ*: tồn tại y Є Σ*, |y|=O(|x|^c): A(x,y)=1 } Ta nói: A kiểm chứng L trong t.g.đ.t. 181
Ví dụ Bài toán: chu trình Hamilton: HAM-CYCLE Є NP 182
Lớp co-NP - L Є co-NP  Σ*\L Є NP - 4 trường hợp có thể xảy ra: 183
Phép qui dẫn ◼ Ngôn ngữ L1 qui dẫn được về ngôn ngữ L2 trong t.g.đ.t. (L1 ≤_P L2) nếu tồn tại một hàm tính được trong t.g.đ.t. f: Σ* -> Σ* sao cho x Є L1  f(x) Є L2 f: hàm qui dẫn T.t. F t.g.đ.t. tính f: t.t. qui dẫn 184
Bài tập 1. Chứng minh rằng quan hệ qui dẫn là một quan hệ thứ tự. 2. Chứng minh bổ đề: Bổ đề: Cho 2 ngôn ngữ L1, L2, nếu L1 ≤ L2 thì L2 Є P kéo theo L1 Є P. 185
Lớp NP- đầy đủ Ngôn ngữ L là NP-đầy đủ (NPC) nếu: 1. L Є NP, và 2. Với mọi L’ Є NP thì L’ ≤_P L. Ngôn ngữ L là NP-khó nếu L thỏa mãn đk 2 (nhưng không nhất thiết đk 1). 186
P versus NP ◼ Định lý: Nếu có một bài toán NP-đầy đủ nào giải được trong t.g.đ.t. thì P = NP. Nếu có một bài toán trong NP nào mà không giải được trong t.g.đ.t. thì tất cả các bài toán NP-đầy đủ đều không giải được trong t.g.đ.t. 187
Chứng minh tính NP-đầy đủ 1. Bổ đề: Nếu L là một ngôn ngữ sao cho L’ ≤_P L với L’ Є NPC, thì L là NP-khó. Hơn nữa, nếu L Є NP thì L Є NPC. 2. Để chứng minh L Є NPC: - chứng minh L Є NP - chọn một ngôn ngữ L’ Є NPC - tìm một t.t. F tính hàm f chuyển mối trạng thái của L’ về một trạng thái của L - chứng minh f thỏa mãn: x Є L’  f(x) Є L với mọi x Є Σ* - chứng minh t.t. F chạy trong t.g.đ.t. 188
Circuit satisfiability Combinational element: một dãy các phần tử có môt số cố định các phần tử vào và ra và hoàn thành tính toán một hàm. Boolean combinational element: đầu vào và ra là thuộc {0,1} (0: sai, 1: đúng) Một boolean combinational element dùng để tính 1 hàm boolean đơn được gọi là một logic gate. 189
Boolean combinational circuit xây dựng từ các boolean combinational elements (được nối với nhau bằng các dây(wire)) 190
1. Circuit input (đầu vào): các dây không nối với một phần tử vào nào Circuit output (đàu ra): các dây không nối với một phần tử ra nào Ta xét các circuit chỉ có một đầu ra. 2. Một phép gán giá trị của một circuit là một tập các giá trị đầu vào. 3. Môt circuit là satisfiable (thỏa mãn) nếu có một phép gán giá trị đầu vào sao cho đàu ra của circuit là 1. 191
Ví dụ 192
Bài toán Circuit satisfiability “Cho một boolean combinational circuit gồm các cổng AND, OR, NOT; nó có thỏa mãn hay không ?” Độ dài của circuit: số các boolean combinational elements + số các wires Ngôn ngữ: CIRCUIT-SAT={ : C là một satisfiable boolean combinational circuit} 193
CIRCUIT-SAT Є NP-đầy đủ Bổ đề: CIRCUIT-SAT Є NP Bổ đề: CIRCUIT-SAT là NP-khó Định lý: CIRCUIT-SAT Є NP-đầy đủ 194
SAT Một trạng thái của bài toán SAT là một công thức boolean Φ gồm: 1. Các biến boolean: x1, x2, 2. Các liên kết boolean: các hàm boolean một hoặc hai biến: AND, OR, NOT, ->,  3. Các dấu ngoặc Một công thức Φ là satisfiable (thỏa mãn được )nếu có một phép gán giá trị để giá trị ra của Φ là 1. SAT = { : Φ là một công thức thỏa mãn được} 195
SAT Є NP-đầy đủ ◼ Đinh lý: SAT Є NP-đầy đủ ◼ Chứng minh: - SAT Є NP - Qui dẫn CIRCUIT-SAT về SAT. 196
3-CNF SAT ◼ 1 literal trong một công thức boolean là một biến x hoặc ¬x. ◼ 1 công thức boolean là có dạng hợp chuẩn (conjunctive normal form, CNF), nếu nó được biểu diễn như là một phép AND của các clause, mỗi clause là một phép OR của các literal. ◼ 1 công thức boolean là một dạng 3-CNF nếu mỗi clause của nó có đúng 3 literal khác nhau. ◼ 3-CNF-SAT={Ф Є 3-CNF và là công thức thoả mãn được} 197
3-CNF-SAT Є NP-đầy đủ Định lý: 3-CNF-SAT Є NP-đầy đủ Chứng minh: - 3-CNF-SAT Є NP - Qui dẫn SAT về 3-CNF-SAT 198
3-CNF-SAT là NP-khó Ý tưởng: chứng minh SAT ≤P 3-CNF-SAT: ◼ Với mỗi công thức boolean Φ, ta tìm tương ứng một công thức f(Φ) Є 3-CNF. ◼ Xây dựng f(Φ) theo 3 bước: 1. Φ’: là công thức gồm phép AND của các clause 2. Φ’’: có dạng chuẩn CNF 3. Φ’’’: có dạng chuẩn 3-CNF. f(Φ)= Φ’’’ ◼ Chứng minh: Φ thỏa mãn được  f(Φ) thỏa mãn được ◼ Chứng minh f(Φ) có độ dài đa thức và f có tgđt 199
Bước 1: Φ -> Φ’ 200
◼ Xây dựng cây nhị phân: • Các lá là các literal của Φ • Các nốt trong là các toán tử của Φ • Thêm một biến yi cho mỗi nốt trong ◼ Φ’: là phép AND của gốc và các clause tương ứng với các nốt trong (mỗi clause có ≤ 3 literal) 201
Φ’ -> Φ’’ ◼ Với mỗi clause C của Φ’: • Viết bảng giá trị của C theo các biến • Hợp các giá trị 0 lại, được dạng chuẩn DNF của ¬C • Theo luật De Morgan, AND -> OR, OR ->AND: được dạng chuẩn CNF của C (C là AND của các clause, mỗi clause là gồm các phép OR) ◼ Φ’’: là AND của các tất cả clause nhận được (mỗi clause có ≤ 3 literal) 202
Φ’’ -> Φ’’’ Ck ٨ ٨ C2 ٨ Φ’’ = C1 ◼ ◼ Nếu Ci có: • 3 literal: để nguyên y ٧ x) ٨ (p ٧ y ٧ y = (x ٧ literal Ci = x 2 • (p¬ ٧ ٧ p ٧ x) ٨ (q ٧ p ٧ literal Ci = x = (x 1 • (q¬ ٧ p¬ ٧ x) ٨ (q ٧ p¬ ٧ x) ٨ (q¬ ◼ Φ’’’: nhận được Є 3-CNF 203
Chứng minh tính đúng đắn ◼ Φ thỏa mẫn được  Φ’’’ thỏa mãn được ◼ Φ’’’: độ dài đa thức ◼ Tính Φ’’’: trong thời gian đa thức 204
Bài toán chu trình Hamilton ◼ Cho đồ thị G=(V,E) vô hướng ◼ Một chu trình Hamilton trong G là một chu trình đơn và đi qua tất cả các đỉnh của G (qua mỗi đỉnh đúng một lần, trừ đỉnh đầu trùng đỉnh cuối). ◼ Đồ thị G được gọi là đồ thị Hamilton nếu nó có chu trình Hamilton, nếu không nó được gọi là đồ thi không phải Hamilton. ◼ Bài toán chu trình Hamilton: đồ thị G có chu trình Hamilton hay không ? ◼ HAM-CYCLE = { : G là đồ thị Hamilton} 205
HAM-CYLCE Є NP-đầy đủ ◼ HAM-CYCLE Є NP ◼ 3-CNF-SAT ≤P HAM-CYCLE: Xây dựng hàm f: Φ Є 3-CNF -> đồ thị G=(V,E) Sao cho Φ thỏa mãn được  G là đồ thị Hamilton. 206
Ý tưởng Φ: các biến x1, , xn; các clause: C1, ,Ck Đồ thị G gồm hai phần: trái, phải: 1. Trái: mỗi Ci: xây dựng một widget dạng B. Nối bi4 với bi+1,1, i=1,2, ,k-1 2. Phải: mỗi xm: x’m và x’’m nối bằng em và ¬em: em Є h  xm = 1 3. Nối (b11 , x1’) và (bk4, xn’’) 4. Nối các clause với các biến có liên quan bằng các widget dạng A. 207
Chứng minh tính đúng đắn G Є HAM-CYCLE => Φ Є 3-CNF-SAT: Chu trình h trong G: 1. (b11 , x1’) và (bk4, xn’’) Є h 2. Bên trái: đi qua các widget B 3. Bên phải: qua hoặc em hoặc ¬em Gán giá trị cho Φ như sau: Nếu em Є h: xm= 1, nếu ¬em Є h: xm = 0 208
Φ Є 3-CNF-SAT => G Є HAM-CYCLE Xây dựng h như sau: 1. Nếu xm= 1: em Є h, nếu xm = 0: ¬em Є h 2. (bij, bịj+1) Є h  literal thứ j của Ci = 0 209
Thời gian đa thức ◼ Dễ thấy: 1. G độ dài đa thức 2. Tính G trong thời gian đa thức 210
Bài toán Người đưa hàng Bài toán: Cho đồ thị G đầy đủ và có trong số c(i,j) cho mỗi cạnh (i,j). Tìm chu trình Hamilton có trọng số nhỏ nhất. Đưa về bài toán quyết định: TSP={ : G=(V,E) đồ thị đầy đủ, c hàm số V*V -> Z, k Є Z và G có chu trình người đưa hàng có trọng số ≤ k} 211
TSP Є NP-đầy đủ 1. TSP Є NP: dễ chứng minh 2. Qui dẫn HAM-CYCLE về TSP: - Cho G=(V,E) Є HAM-CYCLE, xây dựng một trạng thái của TSP như sau: G’=(V,E’): E’=V*V; và c là: c(i,j) = 1 nếu (i,j) Є E, =0 nếu (i,j) ¬Є E Є TSP  Є HAM-CYCLE. - có độ dài đa thức và được tính trong tgđt. 212