Thiết kế và đánh giá thủ thuật Toán
Chia sẻ bởi Lê Thị Thanh Nghị |
Ngày 18/03/2024 |
11
Chia sẻ tài liệu: Thiết kế và đánh giá thủ thuật Toán thuộc Giáo dục tiểu học
Nội dung tài liệu:
1
Thiết kế và đánh giá thuật toán
Cao học, khoa công nghệ thông tin
Đại học quốc gia Hà nội.
Phan Thị Hà Dương
Viện Toán học. [email protected]
2
Chương trình
Chương 1: Giới thiệu về thuật toán
Chương 2: Phân tích tính hiệu quả của thuật toán
Chương 3: Phương pháp “tham lam”
Chương 4: Phương pháp “chia để trị”
Chương 5: Phương pháp qui hoạch động
Chương 6: Thuật toán trên đồ thị
Chương 7: Phương pháp xác suất
Chương 8: Về độ phức tạp tính toán
3
Ví dụ: Chương 3: Phương pháp “tham lam”
Giới thiệu chung
Thuật toán trên đồ thị
Cây bao trùm nhỏ nhất
Đường đi ngắn nhất
Thuật toán sắp xếp lịch làm việc
Thuật toán “heurisitic”
Tô màu đồ thị
Người đưa hàng
4
Sách tham khảo
5
Sách tham khảo
2. Algorithmique - conception et analyse
G. Brassard and P.Bratley, Masson, Paris , 1987
3. Data structure and algorithms
A. Aho, J. Hopcroft and J. Ullman, Addison Wesley Publishing Company
4. Lý thuyết độ phức tạp tính toán.
Phan Đình Diệu.
6
Chương 1: Giới thiệu về thuật toán
Khái niệm thuật toán
Một số ví dụ
Đánh giá thuật toán trong trường hợp xấu nhất và theo trung bình
Về thuật toán hiệu quả
Một số bài toán cụ thể
Cấu trúc dữ liệu
7
Khái niệm về thuật toán
Thuật toán:
Dữ kiện vào
Kết quả ra
Quá trình tính toán
Một dãy các bước tính toán
Một dãy số
Dãy số được
sắp xếp
Thuật toán sắp xếp
8
Một số từ khóa
if (điều kiện) then {…} else
for (điều kiện) do {…}
while (điều kiện) do {…}
procedure (T, a, b) {…}
function(A) {… return r; }
9
Sắp xếp chèn vào
2 4 6 1 3
5 4 6 1 3
2 4 5 6 1 3
4 5 6 1 3
2 4 5 6 3
1 2 3 4 5 6
10
Thuật toán xếp chèn vào
Insertion-Sort (A) {
for j = 2 to length (A) do {
k = A[j]; // chèn A[j] vào dãy đã sắp A[1..j-1]
j = j-1;
while i > 0 and A[i] > k do {
A[i+1] = A[i];
I = i-1; }
A{i+1} = k; }
}
11
Thuật toán xen kẽ (merge sort)
12
Sắp xếp xen kẽ
Merge-Sort(A,p,r){
if p < r then {
q = [(p+r-1)/2];
Merge-Sort(A,p,q);
Merge-Sort(A,q+1,r);
Merge(A,p,q,r);
}
}
13
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
14
Đánh giá thuật toán
Giải quyết một bài toán.
Vấn đề:
Có nhiều thuật toán. Chọn thuật toán nào ?
Mô hình hóa
Lập chương trình
Viết thuật toán
15
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.
16
Đá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;
}
}
17
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]
18
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.
19
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.
20
Thuật toán thứ nhất và thứ hai
fontion fib1(n){
if n < 2 then return n;
else return f(n-1) + f(n-2);
}
fonction fib2(n){
a= 0; b = 1;
for k = 1 to n do {c=b; b = a+b; a=c;}
return b;
}
21
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 = jh;
j = ih + jk +t;
i = ik +t;}
t = h^2;
h = 2kh+t;
k = k^2+t;
n = n div 2;
}
return j;
}
22
Ví dụ về thời gian chạy
(Pascal, CDC Cyber 835)
23
Cấu trúc dữ liệu
Dãy (list)
type tablist = structure{
value[1..lengthmax]: information elements;
counter: 0.. lengthmax;}
type elem = structure{
value: information element;
next: * elem;}
6
7
3
1
4
24
Đồ thị
type adjgraph = structure {
value[1..n]: information elements;
adjacent[1..n, 1..n]: booleans;}
type listgraph = array[1..n] of structure {
value: information element;
neighbours: list; }
1
2
4
3
25
Cây
type treenode = structure{
value: information element;
children: array[ ] of * treenodes;
}
type treenode = structure{
value: information element;
first child: * treenode;
next brother: * treenode;
}
type binarytreenode = structure{
value: information element;
left child, right child: * binarytreenode;
}
a
b
c
d
e
f
26
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
27
Chương 2: Phân tích tính hiệu quả của thuật toán
Các ký hiệu đánh giá tiệm cận
Phân tích thuật toán
Giải các phương trình đệ qui
Một số ví dụ
28
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.
29
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.
30
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.
31
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.
32
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) Є ω(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
33
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
f(n) = ω (g(n)) ≈ a > b
34
Sắp xếp các hàm sau theo quan hệ 0 và θ
35
Một số hàm cơ bản
n^b = o(a^n), với mọi a>1 và b
e^x = 1 + x + θ(x^2), với |x| ≤ 1
lg^b n = o(n^a), với mọi a > 0
n! = o(n^n)
n! = ω(2^n)
lg(n!)= θ(n lg n)
36
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)
37
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).
38
Đổ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)
39
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 + …
40
Ví dụ: Sắp xếp xen kẽ
Merge-Sort(A,p,r){
if p < r then {
q = [(p+r-1)/2];
Merge-Sort(A,p,q);
Merge-Sort(A,q+1,r);
Merge(A,p,q,r);
}
}
41
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
42
43
The Master Theorem
Cho a≥1 và b>1 hằng số, hàm số f(n) và T(n) được định nghĩa:
T(n) = aT(n/b) + f(n),
Khi đó định lý sẽ cho biết giới hạn tiệm cận của T(n)
44
Chương 3: Phương pháp “tham lam”
Giới thiệu chung
Thuật toán trên đồ thị
Cây bao trùm nhỏ nhất
Đường đi ngắn nhất
Thuật toán sắp xếp lịch làm việc
Thuật toán “heurisitique”
Tô màu đồ thị
Người đưa hàng
45
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
- Một hàm đích cho giá trị của một giải pháp (để tối ưu hóa)
46
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
47
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.
48
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”;
}
49
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”
50
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 xích
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
51
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.
52
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.
53
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
54
Tính đúng đắn
Vấn đề: chứng minh tính đúng đắn của thuật toán Kruskal
55
Ví dụ
1
2
3
4
5
6
7
1
2
4
6
4
5
6
3
8
4
7
3
56
Thuật toán Kruskal
MST-Kruskal(G,l){
Xếp E theo l tăng; n = # V; T = Ø;
Đặt n tplt, mỗi tplt chứa 1 phần tử của V;
do{
(u,v) cạnh độ dài min chưa xét đến;
if set(u)<> set(v) then{
T = T U (u,v); union(set(u),set(v));
}
} while(#T = n-1)
return T;
}
57
Phân tích
Đánh giá độ phức tạp tính toán của thuật toán Kruskal
Nếu đồ thị không liên thông, kết quả sẽ thế nào ?
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 ?
58
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 Є VB 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.
59
Bài tập
Chạy ví dụ t.t. Prim trong hình vẽ đã cho
Viết thuật toán Prim
Đánh giá độ phức tạp tính toán của t.t.
Chứng minh tính đúng đắn của t.t.
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 ?
Nếu đồ thị không liên thông, kết quả sẽ thế nào ?
60
Đườ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.
61
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
62
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
63
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
64
Thuật toán Dijkstra
Dijkstra(G,l,s){
S= {s}; C = V {s}; n= #V; d[s]=0;
for u Є C do {d[u] = l[s,u]; p[u] = Null;}
while (C≠Ø) do {
chọn v Є C để d[v] min;
C = C {v}; S = S U {v};
for w Є Adj[v] do {
if d[w] > d[u]+l[u,v] then { p[w]= v;
d[w]= d[v]+l[v,w];}}
}
65
Ví dụ
1
5
2
4
3
10
50
100
30
10
50
20
5
66
Tính đúng đắn
Chứng minh quy nạp rằng:
Nếu u Є S: d[u] là khoảng cách min từ s đến u
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
Cuối cùng S = V, d[u] là khoảng cách cần tìm
67
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)
68
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 tính cần phục vụ khách hàng.
Thời gian phục vụ khách hàng i la 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.
69
Thuật toán
Ý tưởng: Sắp xếp theo trình tự t[i] tăng.
Vấn đề:
Chứng minh tính đúng đắn của thuật toán
Độ phức tạp của thuật toán
Nếu có s máy tính, thuật toán thay đổi thế nào ?
70
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
71
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
72
Ý 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.
73
Chạy thuật toán trên ví dụ
Chọn việc 1. Tập {1} là tiềm năng
Chọn việc 4. Tập {1, 4} là tiềm năng
Chọn việc 3. Tập {1, 4, 3} không là tiềm năng. Bỏ việc 3 đi
Chọn việc 2. Tập {1, 4, 2} không là tiềm năng. Bỏ việc 2 đi
Kết quả tập {1, 4} được chọn. Thực hiện theo thứ tự 4, 1
74
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.
75
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.
76
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
77
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;
}
78
Phân tích thuật toán
Kiểm tra thuật toán
Tính độ phức tạp của thuật toán
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)
79
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)
80
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 oá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ỉ.
81
Thuật toán xấp xỉ
Thuật toán:
chọn 1 màu và 1 đỉnh bất kì, tô màu đỉnh đó.
xét các đỉnh còn lại, đỉnh nào tô được màu vừa chọn thì tô
nếu còn lại một số đỉnh, quay lại bước 1
82
Đá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ó
Tồn tại một hoán vị p để c(p)=c
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 ý.
83
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
84
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.
85
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)
86
Chương 4: Phương pháp “chia để trị”
Giới thiệu chung
Xác định ngưỡng
Phương pháp “phân đôi”
Sắp xếp “xen kẽ”. Sắp xếp nhanh
Số học các số nguyên lớn
Nhân ma trận
Giới thiệu về mật mã
87
Giới thiệu chung
(divide and conquer algorithms)
Ý tưởng: để giải quyết một bài toán,
chia ra làm nhiều phần nhỏ hơn,
giải quyết từng phần độc lập,
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.
88
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;
}
89
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)
90
Phương pháp “phân đôi”
funtion 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 : ?
91
Sắp xếp xen kẽ (Merge sort)
Ý tưởng:
Để xếp bảng T:
Chia T thành 2 bảng độ dài bằng nhau
Sắp xếp mỗi bảng con này
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
92
Thuật toán Merge-sort
Merge-Sort(A,p,r){
if p < r then {
q = [(p+r-1)/2];
Merge-Sort(A,p,q);
Merge-Sort(A,q+1,r);
Merge(A,p,q,r);
}
}
93
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
94
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.
95
Thuật toán quicksort
Quicksort(A,p,r){
if (p q=Partition(A,p,r);
Quicksort(A,p,q);
Quicksort(A,q+1,r);
}
}
96
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 6 5 7
97
Partition
Partition(A,p,r){
x = A[p];
i = p-1; j = r+1;
while (i repeat j = j-1 until A[j] ≤ x;
repeat i = i+1 until A[i] ≥ x;
if (i else return j;
}
}
98
Phân tích thuật toán
Partition(A,p,r): O(r-p)
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)
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.
99
Độ phức tạp trung bình
100
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ả.
101
Phân tích vấn đề
a
b
c
d
n
n
u
v
u v = 10^{2s} ac + 10 ^s (ad+bc) + bd (s = n/2)
102
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
103
Thuật toán nhân
Mult(u,v){
n= min(size(u), size(v));
if (n bé) then return uv;
else { s = n/2;
a= u div (10^s), b= u mod 10^s;
c= v div (10^s), d= v mod 10^s;
r= Mult(a+b,c+d);
p=Mult(a,c); q= Mult(b,d);
t = r-p-q;
return(p*10^{2s} + t*10^s+q);
}
}
104
Độ phức tạp thuật toán
T(n) = 3 T(n/2)+ θ(n)
T(n) = θ(n ^{lg 3}) ≈ θ(n^{1,59})
Bài tập: Thay đổi thuật toán để làm việc với các biểu diễn nhị phân và các phép toán trong biểu diễn nhị phân
105
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)
106
Thuật toán Strassen
Ý tưởng:
A =
a1
a2
a3
a4
b1
b2
b3
b4
B =
m2+m3
m1+m2+m4+m5
m1+m2+m4-m7
m1+m2+m5+m6
A*B =
107
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)
108
Độ phức tạp tính toán
T(n) = 7 T(n/2) + θ(n^2)
≈ θ(n^{2,81})
109
Giới thiệu về mật mã
Vấn đề: A và B muốn trao đổi thông tin sao cho C đọc được nhưng không hiểu được.
Giải quyết:
A, B chọn số nguyên tố lớn p và số g, 2 ≤ g ≤ p-1.
A chọn số A, B chọn số B ≤ p. A gửi số a, B gửi số b.
C biết đươc p,g,a,b. Nhưng không biết x.
A: a= g^A mod p
B: g^b mod p
A: x= b^A mod p
B: y = a^B mod p
a
b
=
110
Thuật toán logarithm rời rạc
Muốn tìm x, C phải tìm A (hoặc B).
Muốn tìm A, biết a, C phải tính logarithm
logD(g,a,p){
A=0; x=1;
do { A=A+1; x = xg;}
while ((a= x mod p) or (A=p))
return A;
}
111
Phân tích thuật toán
Trung bình: logD có p/2 vòng lặp while.
Nếu p rất lớn (vài chục chữ số) thì t.t. chạy rất lâu.
Chưa biết t.t. nào cải thiện hàm logD
112
Thuật toán Mũ (exponentiation)
A phải tính g^A mod p
Thuật toán đơn giản:
expD(g,A,p){
a=1;
for (i=1 to A) do a = a*g mod p;
return a;
}
113
Bài tập: Viết thuật toán “chia để trị” để tính hàm mũ theo thời gian O(lg p)
114
Chương 5: Phương pháp qui hoạch động
Giới thiệu chung
Nhân một dãy các ma trận
Các đường đi ngắn nhất
Người đưa hàng
115
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
116
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.
117
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 ou 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
118
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
1 3 3 1
1 4 6 4 1
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. đó.
119
Nhân một dãy các ma trận
Vấn đề: Ta muốn nhân một dãy các ma trận
M= M1xM2x…xMn
Có nhiều cách đặt các dấu ngoặc để nhân dần 2 ma trận. Chúng ảnh hưởng nhiều đến thời gian tính toán.
Ví dụ: M=ABCD, A=(10,2); B=(2,100);
C=(100,3); D=(3,20)
M=((AB)C)D: 10x2x100+2x100x3+10x3x20=3200 phép x
M=(AB)(CD): 10x2x100+100x3x20+10x100x20 = 28000
M=(A(BC))D: 2x100x3 +10x2x3 +10x3x20 = 1260
M=A((BC)D): 2x100x3 +2x3x20 +10x2x20 = 1120
M=A(B(CD)): 100x3x20+2x100x20 +10x2x20 = 10400
120
Ý tưởng tìm cách tính
Số các cách tính M (số Catalan):
C(n) = 1/n x C(2n-2,n-1) = Ω (4^n/n^2)
Không thể xét tất cả các trường hợp
Ý tưởng:
Nếu để tính M, cắt khúc ở i là tối ưu
Thì để tính M1x…xMi và M(i+1)x…xMn, ta cũng tính cách tối ưu.
=> Lập bảng a[i,j] để lưu trữ số phép x tối ưu khi tính Mix…xMj
121
Ý tưởng tìm cách tính (tiếp)
Chiều các ma trận: d[0..n], Mi=(d[i-1],d[i])
Xây dựng a[i,j] theo từng đường chéo.
Đường chéo s: a[i,j]: j-i=s.
s=0: a[i,i]=0, i= 1,2..,n
s=1: a[i,i+1]=d[i-1]d[i]d[i+1], i=1,2,..,n-1
1a[i,i+s]=min (a[i,k]+a[k+1,i+s]+d[i-1]d[i]d[i+1])
i≤k≤i+s-1
122
Ý tưởng tìm cách tính: ví dụ
M=ABCD, A=(10,2); B=(2,100);
C=(100,3); D=(3,20).
s=1:a[12]=2000,a[23]=600,a[34]=18000 …
j = 1 2 3 4
i=1 0 2000 ? ?
2 0 600 ?
3 0 18000
4 0
123
Bài tập
Viết thuật toán tính bảng a
Tính độ phức tạp tính toán
Thay đổi thuật toán thế nào để nhận được không chỉ a[1,n] mà còn cả cách tính tích M tối ưu nhất.
124
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) .
125
Ý tưởng thuật toán
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.
Xây dựng D[i,j] độ dài min từ i đến j:
Lúc đầu: D=L
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)
Sau n bước, D[i,j] là độ dài min từ i đến j.
126
Ví dụ
0 5 ∞ ∞
D0=L= 50 0 15 5
30 ∞ 0 15
15 ∞ 5 0
0 5 ∞ ∞
D1= 50 0 15 5
30 35 0 15
15 20 5 0
0 5 20 10 0 5 20 10 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
1
2
3
4
15
5
50
5
30
15
5
15
127
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;
}
128
Bài tập
Tìm độ phức tạp của thuật toán Floyd
Chứng minh tính đúng đắn của thuật toán
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 ?
Viết thuật toán xác định xem có đường đi giữa các cặp đỉnh của G.
129
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.
130
Ý tưởng thuật toán
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)
Cho S tập con của V{1}, i Є VS:
g(i,S)=min (đường từ i đến 1 qua S đúng 1 lần)
Min chu trình = g(1, V{1})
= min(L[1,j]+g(j,V{1,j}))
2≤j≤n
g(i,S)= min (L[i,j] + g(j,S{j}))
jЄS
g(i,Ø)=L[i,1], i=2,3,..,n
131
Ví dụ
0 10 15 20
5 0 9 10
L = 6 13 0 12
8 8 9 0
Tính g(j,Ø); j= 2,3,4
Tính g(j,S) với |S|=1;j=2,3,4
Tính g(j,S) với |S|=2;j=2,3,4
Tính g(1,{2,3,4})
4
3
1
2
10
5
20
8
9
13
12
9
8
10
6
15
132
Bài tập
Viết thuật toán tính chu trình ngắn nhất theo ý tưởng đã trình bày.
Tính toán độ phức tạp và bộ nhớ cần cho t.t.
Tính xem thực chất có bao nhiêu giá trị g(i,S) cần phải tính ?
Có thể cải thiện t.t. trên để tiết kiệm số lần tính g(i,S) không (mỗi giá trị tính đúng 1 lần) ?
133
Hàm nhớ
Thuật toán đơn giản tính g(i,S)
function g(i,S){
if (S=Ø) then return L[i,1];
min = ∞;
for (jЄS) do { d=L[i,j]+g(j,S{j});
if (d return min;
}
Số lần gọi các hàm g là Ω((n-1)!), nhiều giá trị được tính lại nhiều lần
134
Hàm nhớ (tiếp)
Lập một bảng gtab[.,.] để nhớ những giá trị g[i,S] đã được tính.
Khi gọi hàm g(i,S), sẽ kiểm tra xem g(i,S) đã được tính chưa
Lúc đầu gtab[i,S] = -1 với mọi i, S.
function g(i,S){
if (S=Ø) then return L[i,1];
if (gtab[i,S]≥0) then return gtab[i,S];
min = ∞;
for (jЄS) do { d=L[i,j]+g(j,S{j});
if (d gtab[i,S]= min; return min;
}
135
So sánh
Thời gian t.t. đơn giản: n!
Thời gian t.t. cải tiến: n^2 2^n
Bộ nhớ t.t. cải tiến: n 2^n
n n! n^2 2^n n 2^n
120 800 160
3628800 102400 10240
1,3 x 10^12 7372800 491520
2,4 x 10^18 419430400 2971520
136
Chương 6: Thuật toán trên đồ thị
Giới thiệu chung
Khám phá cây
Khám phá theo chiều rộng
Khám phá theo chiều sâu
“Branch and bound”
137
Giới thiệu chung
Đồ thị biểu diễn nhiều vấn đề:
Mạng, trò chơi, sơ đồ,…
Cấu trúc dữ liệu: đỉnh là một số bit bộ nhớ, cạnh là các con trỏ,…
Biểu diễn đồ thị, có nhiều cách:
Ma trận: a[i,j]=1 nếu có cạnh (i,j), =0 nếu không
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ị.
138
Khám phá cây
Xét các cây nhị phân, có 3 cách khám phá:
Thứ tự trước (prefix)
Thứ tự giữa (infix)
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.left);
if (r.right<>Null) then visit_prefix(r.right);
}
Chứng minh độ phức tạp tính toán của t.t. là O(n)
139
Khám phá theo chiều rộng
(Breadth-first search)
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
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
Xây dựng cây có gốc s.
Tô màu các đỉnh:
Lúc đầu tất cả màu trắng
Bắt đầu thăm u, tô u màu vàng
Nếu đã thăm mọi lân cận của u, tô u màu đỏ
Một xâu nhớ (FIFO) Q lưu trữ các đỉnh vàng
140
Ví dụ
141
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]=Đ;}
}
142
Phân tích
Đị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.
Tính độ phức tạp và bộ nhớ cho t.t. BFS
143
Khám phá theo chiều sâu
(Deep-first search)
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, …
Hàm thăm này được gọi đệ qui.
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,…
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.
Xây dựng được một rừng.
144
Ký hiệu
d[u]: thời điểm bắt đầu thăm u
f[u]: t.đ. Kết thúc thăm u
p[u]: cha của u
color[u] =T trước d[u],
= V đang thăm u
= Đ sau f[u]
145
Ví dụ
146
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);
}
147
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;
}
148
Phân tích
Tính độ phức tạp và bộ nhớ cần cho DFS
Định lý: Các ngoặc (d[u],f[u]) lập thành một bộ ngoặc đơn tốt (hai ngoặc hoặc là trong nhau hoặc là rời nhau)
149
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ự.
Biểu diễn tập có thứ tự bộ phận
150
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.
151
Ví dụ
152
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.
153
Thuật toán tính các t.p.l.t.m
Tpltm (G){
DFS(G) để tính f[u];
Tính G’
DFG(G’), các đỉnh của G’ được xếp theo f giảm
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ó.
154
Ví dụ
155
Branch and bound
So sánh các cách tìm kiếm trong đồ thị:
Theo chiều rộng: thăm hết các lân cận + một FIFO chứa các đỉnh đang thăm
Theo chiều sâu: thăm hết các con đường + một FILO chứa các đỉnh đang thăm
B.A.B.: thăm các đỉnh hứa hẹn nhất + một dãy chứa các đỉnh đang thăm
156
B.A.B: 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.
157
Ví dụ: ý tưởng
0 14 4 10 20
14 0 7 8 7
L= 4 5 0 7 16
11 7 9 0 2
18 7 17 4 0
Tìm chu trình đơn ngắn nhất từ đỉnh 1 đến đỉnh 1
Xây dựng cây gốc (1).
Mỗi nốt là một đường từ 1: (1,3), (1,3,4),…
Các con của mỗi nốt là các đường thêm vào một đỉnh
Với mỗi nốt, tính cận dưới của chu trình đi qua đường tương ứng
158
Ví dụ (tiếp): cách tính cận dưới
Tính cận dưới (inf):
Khoảng cách L[i,j] chia 2: một nửa đường từ i, một nửa đường đến j
inf từ i = min của các đường từ i
inf qua i = min (từ i) + min (đến i)
inf của nốt = tổng các inf để tạo ra chu trình qua nốt
159
Ví dụ (tiếp): tính cụ thể
inf(1)=inf(từ 1) + inf(đến 1) +
inf(qua 2)+inf(qua 3)+inf(qua 4)+inf(qua 5) = 2+2+6+4+3+3=20
160
Ví dụ (tiếp): xây dựng cây
1
inf 20
1,2
inf 31
1,3
inf 24
1,4
inf 29
1,5
inf 41
1,3,2
inf 24
1,3,4
inf 30,5
1,3,5
inf 40,5
1,3,2,4
=1,3,2,4,5,1
value=37
1,4,2
inf 40
1,4,3
inf 41,5
1,4,5
inf 29
1,3,2,5
=1,3,2,5,4,1
value=31
1,4,5,2
=1,4,5,2,3,1
value=30
1,4,5,3
=1,4,5,3,2,1
value=48
161
Chương 7: Giới thiệu về
phương pháp xác suất
Giới thiệu chung
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 Sherwood
Thuật toán Las Vegas
Thuật toán Monte Carlo
162
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”
163
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.
164
Phân loại các thuật toán xác suất
Thuật toán xác suất số:
Dùng trong việc tính toán xấp xỉ các bài toán số.
Độ chính xác trung bình tỷ lệ với thời gian chạy
- Dùng trong các ví dụ: tính toán thời gian chay TB của một hệ phức tạp, cách tính chính xác là rất phức tạp (hoặc không thể)
165
Phân loại các thuật toán xác suất (tiếp)
Thuật toán Monte Carlo:
- Có thể dùng trong các bài toán quyết định: đúng/sai, phân tích thừa số ng. tố,…
Luôn cho câu trả lời rõ ràng nhưng
Kết quả có thể không đúng
Xác xuất thành công tỷ lệ với thời gian chạy
166
Phân loại các thuật toán xác suất (tiếp)
Thuật toán Las Vegas:
Không bao giờ cho câu trả lời sai
Có thể không cho câu trả lời
Xác xuất thành công tỷ lệ với thời gian chạy
Dù vấn đề nào, xác xuất hỏng cũng có thể nhỏ tùy ý
* Cho trả lời chính xác với độ phức tạp trung bình có giới hạn
167
Phân loại các thuật toán xác suất (tiếp)
Thuật toán Sherwood:
- Luôn cho câu trả lời, trả lời luôn đúng
- Dùng trong các bài toán đã có thuật toán, với ĐPTTB nhỏ và ĐPT xấu nhất lớn
- Biễn ngẫu nhiên là để giảm sự khác nhau giữa hai trường hợp này
168
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.
169
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.
170
Phép thử Miller Rabin
Nguyên tắc:
a) n nguyên tố, a < n
=> a^{n-1} = 1 (mod n)
b) n nguyên tố, a a^2 = 1 (mod n) =>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 = ?
171
Thuật toán Miller-Rabin
M-R(n) {
i=1; chọn a ngẫu nhiên < n;
while (i 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
172
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 xac suất này nhỏ tùy ý.
173
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.
174
Thuật toán
Mỗi người chọn một số ngẫu nhiên từ 1 đến m (số người chọn)
Nếu không có ai chọn số 1, quay về bước 2.
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.
Nếu chỉ có 1 người chọn số 1 thì người này là chủ.
175
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.
176
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
177
Chương 8: Về độ phức tạp tính toán
Cây quyết định
Qui dẫn
Giới thiệu về NP- �
Thiết kế và đánh giá thuật toán
Cao học, khoa công nghệ thông tin
Đại học quốc gia Hà nội.
Phan Thị Hà Dương
Viện Toán học. [email protected]
2
Chương trình
Chương 1: Giới thiệu về thuật toán
Chương 2: Phân tích tính hiệu quả của thuật toán
Chương 3: Phương pháp “tham lam”
Chương 4: Phương pháp “chia để trị”
Chương 5: Phương pháp qui hoạch động
Chương 6: Thuật toán trên đồ thị
Chương 7: Phương pháp xác suất
Chương 8: Về độ phức tạp tính toán
3
Ví dụ: Chương 3: Phương pháp “tham lam”
Giới thiệu chung
Thuật toán trên đồ thị
Cây bao trùm nhỏ nhất
Đường đi ngắn nhất
Thuật toán sắp xếp lịch làm việc
Thuật toán “heurisitic”
Tô màu đồ thị
Người đưa hàng
4
Sách tham khảo
5
Sách tham khảo
2. Algorithmique - conception et analyse
G. Brassard and P.Bratley, Masson, Paris , 1987
3. Data structure and algorithms
A. Aho, J. Hopcroft and J. Ullman, Addison Wesley Publishing Company
4. Lý thuyết độ phức tạp tính toán.
Phan Đình Diệu.
6
Chương 1: Giới thiệu về thuật toán
Khái niệm thuật toán
Một số ví dụ
Đánh giá thuật toán trong trường hợp xấu nhất và theo trung bình
Về thuật toán hiệu quả
Một số bài toán cụ thể
Cấu trúc dữ liệu
7
Khái niệm về thuật toán
Thuật toán:
Dữ kiện vào
Kết quả ra
Quá trình tính toán
Một dãy các bước tính toán
Một dãy số
Dãy số được
sắp xếp
Thuật toán sắp xếp
8
Một số từ khóa
if (điều kiện) then {…} else
for (điều kiện) do {…}
while (điều kiện) do {…}
procedure (T, a, b) {…}
function(A) {… return r; }
9
Sắp xếp chèn vào
2 4 6 1 3
5 4 6 1 3
2 4 5 6 1 3
4 5 6 1 3
2 4 5 6 3
1 2 3 4 5 6
10
Thuật toán xếp chèn vào
Insertion-Sort (A) {
for j = 2 to length (A) do {
k = A[j]; // chèn A[j] vào dãy đã sắp A[1..j-1]
j = j-1;
while i > 0 and A[i] > k do {
A[i+1] = A[i];
I = i-1; }
A{i+1} = k; }
}
11
Thuật toán xen kẽ (merge sort)
12
Sắp xếp xen kẽ
Merge-Sort(A,p,r){
if p < r then {
q = [(p+r-1)/2];
Merge-Sort(A,p,q);
Merge-Sort(A,q+1,r);
Merge(A,p,q,r);
}
}
13
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
14
Đánh giá thuật toán
Giải quyết một bài toán.
Vấn đề:
Có nhiều thuật toán. Chọn thuật toán nào ?
Mô hình hóa
Lập chương trình
Viết thuật toán
15
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.
16
Đá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;
}
}
17
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]
18
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.
19
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.
20
Thuật toán thứ nhất và thứ hai
fontion fib1(n){
if n < 2 then return n;
else return f(n-1) + f(n-2);
}
fonction fib2(n){
a= 0; b = 1;
for k = 1 to n do {c=b; b = a+b; a=c;}
return b;
}
21
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 = jh;
j = ih + jk +t;
i = ik +t;}
t = h^2;
h = 2kh+t;
k = k^2+t;
n = n div 2;
}
return j;
}
22
Ví dụ về thời gian chạy
(Pascal, CDC Cyber 835)
23
Cấu trúc dữ liệu
Dãy (list)
type tablist = structure{
value[1..lengthmax]: information elements;
counter: 0.. lengthmax;}
type elem = structure{
value: information element;
next: * elem;}
6
7
3
1
4
24
Đồ thị
type adjgraph = structure {
value[1..n]: information elements;
adjacent[1..n, 1..n]: booleans;}
type listgraph = array[1..n] of structure {
value: information element;
neighbours: list; }
1
2
4
3
25
Cây
type treenode = structure{
value: information element;
children: array[ ] of * treenodes;
}
type treenode = structure{
value: information element;
first child: * treenode;
next brother: * treenode;
}
type binarytreenode = structure{
value: information element;
left child, right child: * binarytreenode;
}
a
b
c
d
e
f
26
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
27
Chương 2: Phân tích tính hiệu quả của thuật toán
Các ký hiệu đánh giá tiệm cận
Phân tích thuật toán
Giải các phương trình đệ qui
Một số ví dụ
28
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.
29
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.
30
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.
31
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.
32
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) Є ω(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
33
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
f(n) = ω (g(n)) ≈ a > b
34
Sắp xếp các hàm sau theo quan hệ 0 và θ
35
Một số hàm cơ bản
n^b = o(a^n), với mọi a>1 và b
e^x = 1 + x + θ(x^2), với |x| ≤ 1
lg^b n = o(n^a), với mọi a > 0
n! = o(n^n)
n! = ω(2^n)
lg(n!)= θ(n lg n)
36
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)
37
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).
38
Đổ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)
39
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 + …
40
Ví dụ: Sắp xếp xen kẽ
Merge-Sort(A,p,r){
if p < r then {
q = [(p+r-1)/2];
Merge-Sort(A,p,q);
Merge-Sort(A,q+1,r);
Merge(A,p,q,r);
}
}
41
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
42
43
The Master Theorem
Cho a≥1 và b>1 hằng số, hàm số f(n) và T(n) được định nghĩa:
T(n) = aT(n/b) + f(n),
Khi đó định lý sẽ cho biết giới hạn tiệm cận của T(n)
44
Chương 3: Phương pháp “tham lam”
Giới thiệu chung
Thuật toán trên đồ thị
Cây bao trùm nhỏ nhất
Đường đi ngắn nhất
Thuật toán sắp xếp lịch làm việc
Thuật toán “heurisitique”
Tô màu đồ thị
Người đưa hàng
45
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
- Một hàm đích cho giá trị của một giải pháp (để tối ưu hóa)
46
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
47
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.
48
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”;
}
49
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”
50
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 xích
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
51
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.
52
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.
53
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
54
Tính đúng đắn
Vấn đề: chứng minh tính đúng đắn của thuật toán Kruskal
55
Ví dụ
1
2
3
4
5
6
7
1
2
4
6
4
5
6
3
8
4
7
3
56
Thuật toán Kruskal
MST-Kruskal(G,l){
Xếp E theo l tăng; n = # V; T = Ø;
Đặt n tplt, mỗi tplt chứa 1 phần tử của V;
do{
(u,v) cạnh độ dài min chưa xét đến;
if set(u)<> set(v) then{
T = T U (u,v); union(set(u),set(v));
}
} while(#T = n-1)
return T;
}
57
Phân tích
Đánh giá độ phức tạp tính toán của thuật toán Kruskal
Nếu đồ thị không liên thông, kết quả sẽ thế nào ?
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 ?
58
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 Є VB 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.
59
Bài tập
Chạy ví dụ t.t. Prim trong hình vẽ đã cho
Viết thuật toán Prim
Đánh giá độ phức tạp tính toán của t.t.
Chứng minh tính đúng đắn của t.t.
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 ?
Nếu đồ thị không liên thông, kết quả sẽ thế nào ?
60
Đườ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.
61
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
62
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
63
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
64
Thuật toán Dijkstra
Dijkstra(G,l,s){
S= {s}; C = V {s}; n= #V; d[s]=0;
for u Є C do {d[u] = l[s,u]; p[u] = Null;}
while (C≠Ø) do {
chọn v Є C để d[v] min;
C = C {v}; S = S U {v};
for w Є Adj[v] do {
if d[w] > d[u]+l[u,v] then { p[w]= v;
d[w]= d[v]+l[v,w];}}
}
65
Ví dụ
1
5
2
4
3
10
50
100
30
10
50
20
5
66
Tính đúng đắn
Chứng minh quy nạp rằng:
Nếu u Є S: d[u] là khoảng cách min từ s đến u
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
Cuối cùng S = V, d[u] là khoảng cách cần tìm
67
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)
68
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 tính cần phục vụ khách hàng.
Thời gian phục vụ khách hàng i la 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.
69
Thuật toán
Ý tưởng: Sắp xếp theo trình tự t[i] tăng.
Vấn đề:
Chứng minh tính đúng đắn của thuật toán
Độ phức tạp của thuật toán
Nếu có s máy tính, thuật toán thay đổi thế nào ?
70
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
71
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
72
Ý 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.
73
Chạy thuật toán trên ví dụ
Chọn việc 1. Tập {1} là tiềm năng
Chọn việc 4. Tập {1, 4} là tiềm năng
Chọn việc 3. Tập {1, 4, 3} không là tiềm năng. Bỏ việc 3 đi
Chọn việc 2. Tập {1, 4, 2} không là tiềm năng. Bỏ việc 2 đi
Kết quả tập {1, 4} được chọn. Thực hiện theo thứ tự 4, 1
74
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.
75
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.
76
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
77
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;
}
78
Phân tích thuật toán
Kiểm tra thuật toán
Tính độ phức tạp của thuật toán
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)
79
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)
80
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 oá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ỉ.
81
Thuật toán xấp xỉ
Thuật toán:
chọn 1 màu và 1 đỉnh bất kì, tô màu đỉnh đó.
xét các đỉnh còn lại, đỉnh nào tô được màu vừa chọn thì tô
nếu còn lại một số đỉnh, quay lại bước 1
82
Đá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ó
Tồn tại một hoán vị p để c(p)=c
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 ý.
83
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
84
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.
85
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)
86
Chương 4: Phương pháp “chia để trị”
Giới thiệu chung
Xác định ngưỡng
Phương pháp “phân đôi”
Sắp xếp “xen kẽ”. Sắp xếp nhanh
Số học các số nguyên lớn
Nhân ma trận
Giới thiệu về mật mã
87
Giới thiệu chung
(divide and conquer algorithms)
Ý tưởng: để giải quyết một bài toán,
chia ra làm nhiều phần nhỏ hơn,
giải quyết từng phần độc lập,
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.
88
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;
}
89
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)
90
Phương pháp “phân đôi”
funtion 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 : ?
91
Sắp xếp xen kẽ (Merge sort)
Ý tưởng:
Để xếp bảng T:
Chia T thành 2 bảng độ dài bằng nhau
Sắp xếp mỗi bảng con này
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
92
Thuật toán Merge-sort
Merge-Sort(A,p,r){
if p < r then {
q = [(p+r-1)/2];
Merge-Sort(A,p,q);
Merge-Sort(A,q+1,r);
Merge(A,p,q,r);
}
}
93
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
94
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.
95
Thuật toán quicksort
Quicksort(A,p,r){
if (p
Quicksort(A,p,q);
Quicksort(A,q+1,r);
}
}
96
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 6 5 7
97
Partition
Partition(A,p,r){
x = A[p];
i = p-1; j = r+1;
while (i
repeat i = i+1 until A[i] ≥ x;
if (i
}
}
98
Phân tích thuật toán
Partition(A,p,r): O(r-p)
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)
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.
99
Độ phức tạp trung bình
100
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ả.
101
Phân tích vấn đề
a
b
c
d
n
n
u
v
u v = 10^{2s} ac + 10 ^s (ad+bc) + bd (s = n/2)
102
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
103
Thuật toán nhân
Mult(u,v){
n= min(size(u), size(v));
if (n bé) then return uv;
else { s = n/2;
a= u div (10^s), b= u mod 10^s;
c= v div (10^s), d= v mod 10^s;
r= Mult(a+b,c+d);
p=Mult(a,c); q= Mult(b,d);
t = r-p-q;
return(p*10^{2s} + t*10^s+q);
}
}
104
Độ phức tạp thuật toán
T(n) = 3 T(n/2)+ θ(n)
T(n) = θ(n ^{lg 3}) ≈ θ(n^{1,59})
Bài tập: Thay đổi thuật toán để làm việc với các biểu diễn nhị phân và các phép toán trong biểu diễn nhị phân
105
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)
106
Thuật toán Strassen
Ý tưởng:
A =
a1
a2
a3
a4
b1
b2
b3
b4
B =
m2+m3
m1+m2+m4+m5
m1+m2+m4-m7
m1+m2+m5+m6
A*B =
107
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)
108
Độ phức tạp tính toán
T(n) = 7 T(n/2) + θ(n^2)
≈ θ(n^{2,81})
109
Giới thiệu về mật mã
Vấn đề: A và B muốn trao đổi thông tin sao cho C đọc được nhưng không hiểu được.
Giải quyết:
A, B chọn số nguyên tố lớn p và số g, 2 ≤ g ≤ p-1.
A chọn số A, B chọn số B ≤ p. A gửi số a, B gửi số b.
C biết đươc p,g,a,b. Nhưng không biết x.
A: a= g^A mod p
B: g^b mod p
A: x= b^A mod p
B: y = a^B mod p
a
b
=
110
Thuật toán logarithm rời rạc
Muốn tìm x, C phải tìm A (hoặc B).
Muốn tìm A, biết a, C phải tính logarithm
logD(g,a,p){
A=0; x=1;
do { A=A+1; x = xg;}
while ((a= x mod p) or (A=p))
return A;
}
111
Phân tích thuật toán
Trung bình: logD có p/2 vòng lặp while.
Nếu p rất lớn (vài chục chữ số) thì t.t. chạy rất lâu.
Chưa biết t.t. nào cải thiện hàm logD
112
Thuật toán Mũ (exponentiation)
A phải tính g^A mod p
Thuật toán đơn giản:
expD(g,A,p){
a=1;
for (i=1 to A) do a = a*g mod p;
return a;
}
113
Bài tập: Viết thuật toán “chia để trị” để tính hàm mũ theo thời gian O(lg p)
114
Chương 5: Phương pháp qui hoạch động
Giới thiệu chung
Nhân một dãy các ma trận
Các đường đi ngắn nhất
Người đưa hàng
115
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
116
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.
117
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 ou 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
118
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
1 3 3 1
1 4 6 4 1
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. đó.
119
Nhân một dãy các ma trận
Vấn đề: Ta muốn nhân một dãy các ma trận
M= M1xM2x…xMn
Có nhiều cách đặt các dấu ngoặc để nhân dần 2 ma trận. Chúng ảnh hưởng nhiều đến thời gian tính toán.
Ví dụ: M=ABCD, A=(10,2); B=(2,100);
C=(100,3); D=(3,20)
M=((AB)C)D: 10x2x100+2x100x3+10x3x20=3200 phép x
M=(AB)(CD): 10x2x100+100x3x20+10x100x20 = 28000
M=(A(BC))D: 2x100x3 +10x2x3 +10x3x20 = 1260
M=A((BC)D): 2x100x3 +2x3x20 +10x2x20 = 1120
M=A(B(CD)): 100x3x20+2x100x20 +10x2x20 = 10400
120
Ý tưởng tìm cách tính
Số các cách tính M (số Catalan):
C(n) = 1/n x C(2n-2,n-1) = Ω (4^n/n^2)
Không thể xét tất cả các trường hợp
Ý tưởng:
Nếu để tính M, cắt khúc ở i là tối ưu
Thì để tính M1x…xMi và M(i+1)x…xMn, ta cũng tính cách tối ưu.
=> Lập bảng a[i,j] để lưu trữ số phép x tối ưu khi tính Mix…xMj
121
Ý tưởng tìm cách tính (tiếp)
Chiều các ma trận: d[0..n], Mi=(d[i-1],d[i])
Xây dựng a[i,j] theo từng đường chéo.
Đường chéo s: a[i,j]: j-i=s.
s=0: a[i,i]=0, i= 1,2..,n
s=1: a[i,i+1]=d[i-1]d[i]d[i+1], i=1,2,..,n-1
1
i≤k≤i+s-1
122
Ý tưởng tìm cách tính: ví dụ
M=ABCD, A=(10,2); B=(2,100);
C=(100,3); D=(3,20).
s=1:a[12]=2000,a[23]=600,a[34]=18000 …
j = 1 2 3 4
i=1 0 2000 ? ?
2 0 600 ?
3 0 18000
4 0
123
Bài tập
Viết thuật toán tính bảng a
Tính độ phức tạp tính toán
Thay đổi thuật toán thế nào để nhận được không chỉ a[1,n] mà còn cả cách tính tích M tối ưu nhất.
124
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) .
125
Ý tưởng thuật toán
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.
Xây dựng D[i,j] độ dài min từ i đến j:
Lúc đầu: D=L
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)
Sau n bước, D[i,j] là độ dài min từ i đến j.
126
Ví dụ
0 5 ∞ ∞
D0=L= 50 0 15 5
30 ∞ 0 15
15 ∞ 5 0
0 5 ∞ ∞
D1= 50 0 15 5
30 35 0 15
15 20 5 0
0 5 20 10 0 5 20 10 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
1
2
3
4
15
5
50
5
30
15
5
15
127
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;
}
128
Bài tập
Tìm độ phức tạp của thuật toán Floyd
Chứng minh tính đúng đắn của thuật toán
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 ?
Viết thuật toán xác định xem có đường đi giữa các cặp đỉnh của G.
129
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.
130
Ý tưởng thuật toán
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)
Cho S tập con của V{1}, i Є VS:
g(i,S)=min (đường từ i đến 1 qua S đúng 1 lần)
Min chu trình = g(1, V{1})
= min(L[1,j]+g(j,V{1,j}))
2≤j≤n
g(i,S)= min (L[i,j] + g(j,S{j}))
jЄS
g(i,Ø)=L[i,1], i=2,3,..,n
131
Ví dụ
0 10 15 20
5 0 9 10
L = 6 13 0 12
8 8 9 0
Tính g(j,Ø); j= 2,3,4
Tính g(j,S) với |S|=1;j=2,3,4
Tính g(j,S) với |S|=2;j=2,3,4
Tính g(1,{2,3,4})
4
3
1
2
10
5
20
8
9
13
12
9
8
10
6
15
132
Bài tập
Viết thuật toán tính chu trình ngắn nhất theo ý tưởng đã trình bày.
Tính toán độ phức tạp và bộ nhớ cần cho t.t.
Tính xem thực chất có bao nhiêu giá trị g(i,S) cần phải tính ?
Có thể cải thiện t.t. trên để tiết kiệm số lần tính g(i,S) không (mỗi giá trị tính đúng 1 lần) ?
133
Hàm nhớ
Thuật toán đơn giản tính g(i,S)
function g(i,S){
if (S=Ø) then return L[i,1];
min = ∞;
for (jЄS) do { d=L[i,j]+g(j,S{j});
if (d
}
Số lần gọi các hàm g là Ω((n-1)!), nhiều giá trị được tính lại nhiều lần
134
Hàm nhớ (tiếp)
Lập một bảng gtab[.,.] để nhớ những giá trị g[i,S] đã được tính.
Khi gọi hàm g(i,S), sẽ kiểm tra xem g(i,S) đã được tính chưa
Lúc đầu gtab[i,S] = -1 với mọi i, S.
function g(i,S){
if (S=Ø) then return L[i,1];
if (gtab[i,S]≥0) then return gtab[i,S];
min = ∞;
for (jЄS) do { d=L[i,j]+g(j,S{j});
if (d
}
135
So sánh
Thời gian t.t. đơn giản: n!
Thời gian t.t. cải tiến: n^2 2^n
Bộ nhớ t.t. cải tiến: n 2^n
n n! n^2 2^n n 2^n
120 800 160
3628800 102400 10240
1,3 x 10^12 7372800 491520
2,4 x 10^18 419430400 2971520
136
Chương 6: Thuật toán trên đồ thị
Giới thiệu chung
Khám phá cây
Khám phá theo chiều rộng
Khám phá theo chiều sâu
“Branch and bound”
137
Giới thiệu chung
Đồ thị biểu diễn nhiều vấn đề:
Mạng, trò chơi, sơ đồ,…
Cấu trúc dữ liệu: đỉnh là một số bit bộ nhớ, cạnh là các con trỏ,…
Biểu diễn đồ thị, có nhiều cách:
Ma trận: a[i,j]=1 nếu có cạnh (i,j), =0 nếu không
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ị.
138
Khám phá cây
Xét các cây nhị phân, có 3 cách khám phá:
Thứ tự trước (prefix)
Thứ tự giữa (infix)
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.left);
if (r.right<>Null) then visit_prefix(r.right);
}
Chứng minh độ phức tạp tính toán của t.t. là O(n)
139
Khám phá theo chiều rộng
(Breadth-first search)
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
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
Xây dựng cây có gốc s.
Tô màu các đỉnh:
Lúc đầu tất cả màu trắng
Bắt đầu thăm u, tô u màu vàng
Nếu đã thăm mọi lân cận của u, tô u màu đỏ
Một xâu nhớ (FIFO) Q lưu trữ các đỉnh vàng
140
Ví dụ
141
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]=Đ;}
}
142
Phân tích
Đị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.
Tính độ phức tạp và bộ nhớ cho t.t. BFS
143
Khám phá theo chiều sâu
(Deep-first search)
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, …
Hàm thăm này được gọi đệ qui.
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,…
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.
Xây dựng được một rừng.
144
Ký hiệu
d[u]: thời điểm bắt đầu thăm u
f[u]: t.đ. Kết thúc thăm u
p[u]: cha của u
color[u] =T trước d[u],
= V đang thăm u
= Đ sau f[u]
145
Ví dụ
146
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);
}
147
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;
}
148
Phân tích
Tính độ phức tạp và bộ nhớ cần cho DFS
Định lý: Các ngoặc (d[u],f[u]) lập thành một bộ ngoặc đơn tốt (hai ngoặc hoặc là trong nhau hoặc là rời nhau)
149
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ự.
Biểu diễn tập có thứ tự bộ phận
150
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.
151
Ví dụ
152
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.
153
Thuật toán tính các t.p.l.t.m
Tpltm (G){
DFS(G) để tính f[u];
Tính G’
DFG(G’), các đỉnh của G’ được xếp theo f giảm
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ó.
154
Ví dụ
155
Branch and bound
So sánh các cách tìm kiếm trong đồ thị:
Theo chiều rộng: thăm hết các lân cận + một FIFO chứa các đỉnh đang thăm
Theo chiều sâu: thăm hết các con đường + một FILO chứa các đỉnh đang thăm
B.A.B.: thăm các đỉnh hứa hẹn nhất + một dãy chứa các đỉnh đang thăm
156
B.A.B: 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.
157
Ví dụ: ý tưởng
0 14 4 10 20
14 0 7 8 7
L= 4 5 0 7 16
11 7 9 0 2
18 7 17 4 0
Tìm chu trình đơn ngắn nhất từ đỉnh 1 đến đỉnh 1
Xây dựng cây gốc (1).
Mỗi nốt là một đường từ 1: (1,3), (1,3,4),…
Các con của mỗi nốt là các đường thêm vào một đỉnh
Với mỗi nốt, tính cận dưới của chu trình đi qua đường tương ứng
158
Ví dụ (tiếp): cách tính cận dưới
Tính cận dưới (inf):
Khoảng cách L[i,j] chia 2: một nửa đường từ i, một nửa đường đến j
inf từ i = min của các đường từ i
inf qua i = min (từ i) + min (đến i)
inf của nốt = tổng các inf để tạo ra chu trình qua nốt
159
Ví dụ (tiếp): tính cụ thể
inf(1)=inf(từ 1) + inf(đến 1) +
inf(qua 2)+inf(qua 3)+inf(qua 4)+inf(qua 5) = 2+2+6+4+3+3=20
160
Ví dụ (tiếp): xây dựng cây
1
inf 20
1,2
inf 31
1,3
inf 24
1,4
inf 29
1,5
inf 41
1,3,2
inf 24
1,3,4
inf 30,5
1,3,5
inf 40,5
1,3,2,4
=1,3,2,4,5,1
value=37
1,4,2
inf 40
1,4,3
inf 41,5
1,4,5
inf 29
1,3,2,5
=1,3,2,5,4,1
value=31
1,4,5,2
=1,4,5,2,3,1
value=30
1,4,5,3
=1,4,5,3,2,1
value=48
161
Chương 7: Giới thiệu về
phương pháp xác suất
Giới thiệu chung
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 Sherwood
Thuật toán Las Vegas
Thuật toán Monte Carlo
162
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”
163
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.
164
Phân loại các thuật toán xác suất
Thuật toán xác suất số:
Dùng trong việc tính toán xấp xỉ các bài toán số.
Độ chính xác trung bình tỷ lệ với thời gian chạy
- Dùng trong các ví dụ: tính toán thời gian chay TB của một hệ phức tạp, cách tính chính xác là rất phức tạp (hoặc không thể)
165
Phân loại các thuật toán xác suất (tiếp)
Thuật toán Monte Carlo:
- Có thể dùng trong các bài toán quyết định: đúng/sai, phân tích thừa số ng. tố,…
Luôn cho câu trả lời rõ ràng nhưng
Kết quả có thể không đúng
Xác xuất thành công tỷ lệ với thời gian chạy
166
Phân loại các thuật toán xác suất (tiếp)
Thuật toán Las Vegas:
Không bao giờ cho câu trả lời sai
Có thể không cho câu trả lời
Xác xuất thành công tỷ lệ với thời gian chạy
Dù vấn đề nào, xác xuất hỏng cũng có thể nhỏ tùy ý
* Cho trả lời chính xác với độ phức tạp trung bình có giới hạn
167
Phân loại các thuật toán xác suất (tiếp)
Thuật toán Sherwood:
- Luôn cho câu trả lời, trả lời luôn đúng
- Dùng trong các bài toán đã có thuật toán, với ĐPTTB nhỏ và ĐPT xấu nhất lớn
- Biễn ngẫu nhiên là để giảm sự khác nhau giữa hai trường hợp này
168
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.
169
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.
170
Phép thử Miller Rabin
Nguyên tắc:
a) n nguyên tố, a < n
=> a^{n-1} = 1 (mod n)
b) n nguyên tố, a
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 = ?
171
Thuật toán Miller-Rabin
M-R(n) {
i=1; chọn a ngẫu nhiên < n;
while (i
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
172
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 xac suất này nhỏ tùy ý.
173
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.
174
Thuật toán
Mỗi người chọn một số ngẫu nhiên từ 1 đến m (số người chọn)
Nếu không có ai chọn số 1, quay về bước 2.
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.
Nếu chỉ có 1 người chọn số 1 thì người này là chủ.
175
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.
176
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
177
Chương 8: Về độ phức tạp tính toán
Cây quyết định
Qui dẫn
Giới thiệu về NP- �
* Một số tài liệu cũ có thể bị lỗi font khi hiển thị do dùng bộ mã không phải Unikey ...
Người chia sẻ: Lê Thị Thanh Nghị
Dung lượng: |
Lượt tài: 0
Loại file:
Nguồn : Chưa rõ
(Tài liệu chưa được thẩm định)