Professional Documents
Culture Documents
VÀ THUẬT TOÁN
Data Structures and Algorithms
NỘI DUNG
1.1. Ví dụ mở đầu
• Ví dụ: Nếu dãy đã cho là -2, 11, -4, 13, -5, 2 thì cần đưa ra
câu trả lời là 20 (là trọng lượng của dãy con 11, -4, 13)
• Thuật toán đơn giản đầu tiên có thể nghĩ để giải bài toán đặt ra
là: Duyệt tất cả các dãy con có thể
và tính tổng của mỗi dãy con để tìm ra trọng lượng lớn nhất.
• Trước hết nhận thấy rằng, tổng số các dãy con có thể của dãy đã
cho là
• Thuật toán này có thể cài đặt trong đoạn chương trình sau:
int maxSum = 0;
for (int i=0; i<n; i++) {
for (int j=i; j<n; j++) {
int sum = 0;
for (int k=i; k<=j; k++)
sum += a[k];
if sum > maxSum
maxSum = sum;
}
}
a[k ] a[ j ] a[k ]
k i k i
• Nhận xét này cho phép rút bớt vòng lặp for trong cùng.
• Phân tích thuật toán. Ta lại tính số lần thực hiện phép cộng
và thu được kết quả sau:
n 1
n2 n
i 0
(n i) n (n 1) ... 1
2 2
• Để ý rằng số này là đúng bằng số lượng dãy con. Dường như
thuật toán thu được là rất tốt, vì ta phải xét mỗi dãy con đúng 1
lần.
• Để tổ hợp lời giải, nhận thấy rằng chỉ có thể xảy ra một
trong 3 trường hợp:
– Dãy con lớn nhất nằm ở dãy con bên trái (nửa trái)
– Dãy con lớn nhất nằm ở dãy con bên phải (nửa phải)
– Dãy con lớn nhất bắt đầu ở nửa trái và kết thúc ở nửa phải (giữa).
• Do đó, nếu ký hiệu trọng lượng của dãy con lớn nhất ở
nửa trái là wL, ở nửa phải là wR và ở giữa là wM thì
trọng lượng cần tìm sẽ là
max(wL, wR, wM).
• Việc tìm trọng lượng của dãy con lớn nhất ở nửa trái
(wL) và nửa phải (wR) có thể thực hiện một cách đệ qui
• Để tìm trọng lượng wM của dãy con lớn nhất bắt đầu ở
nửa trái và kết thúc ở nửa phải ta thực hiện như sau:
– Tính trọng lượng của dãy con lớn nhất trong nửa trái kết
thúc ở điểm chia (wML) và
– Tính trọng lượng của dãy con lớn nhất trong nửa phải bắt
đầu ở điểm chia (wMR).
– Khi đó wM = wML + wMR.
• m – điểm chia của dãy trái, m+1 là điểm chia của dãy phải
Tính WML của dãy con Tính WMR của dãy con
lớn nhất trong nửa trái lớn nhất trong nửa phải
kết thúc tại am bắt đầu từ am+1
• Để tính trọng lượng của dãy con lớn nhất ở nửa trái (từ
a[i] đến a[j]) kết thúc ở a[j] ta dùng thuật toán sau:
MaxLeft(a, i, j);
{
maxSum = -; sum = 0;
for (int k=j; k>=i; k--) {
sum = sum+a[k];
maxSum = max(sum, maxSum);
}
return maxSum;
}
• Để tính trọng lượng của dãy con lớn nhất ở nửa phải (từ
a[i] đến a[j]) bắt đầu từ a[i] ta dùng thuật toán sau:
MaxRight(a, i, j);
{
maxSum = -; sum = 0;
for (int k=i; k<=j; k++){
sum = sum+a[k];
maxSum = max(sum, maxSum);
}
return maxSum;
}
• Ta khẳng định rằng T(2k) = k.2k. Ta chứng minh bằng qui nạp
• Cơ sở qui nạp: Nếu k=0 thì T(20) = T(1) = 0 = 0.20.
• Chuyển qui nạp: Nếu k>0, giả sử rằng T(2k-1) = (k-1)2k-1 là
đúng. Khi đó
T(2k) = 2T(2k-1)+2k = 2(k-1).2k-1 + 2k = k.2k.
• Quay lại với ký hiệu n, ta có
T(n) = n log n .
• Kết quả thu được là tốt hơn thuật toán thứ hai !
• Các bảng trình bày dưới đây cho thấy thời gian tính với
giả thiết máy tính có thể thực hiện 108 phép cộng trong 1
giây
Việc phát triển thuật toán dựa trên DP bao gồm 3 giai đoạn:
1. Phân rã: Chia bài toán cần giải thành những bài toán con nhỏ
hơn có cùng dạng với bài toán ban đầu.
2. Ghi nhận lời giải: Lưu trữ lời giải của các bài toán con vào
một bảng.
3. Tổng hợp lời giải: Lần lượt từ lời giải của các bài toán con
kích thước nhỏ hơn tìm cách xây dựng lời giải của bài toán
kích thước lớn hơn, cho đến khi thu được lời giải của bài toán
xuất phát (là bài toán con có kích thước lớn nhất).
• Ph©n r·. Gäi si lµ trọng lượng cña d·y con lín nhÊt
trong d·y a1, a2, ..., ai , i = 1, 2, ..., n.
Râ rµng sn lµ gi¸ trÞ cÇn t×m.
• Tæng hîp lêi gi¶i.
– Tríc hÕt, ta cã
s1 = a1.
– Gi¶ sö i > 1 vµ sk lµ ®· biÕt víi k = 1, 2, ..., i-1. Ta cÇn tÝnh si lµ
trọng lượng của d·y con lín nhÊt cña d·y
• Do dãy con lớn nhất của dãy này hoặc là có chứa phần tử ai hoặc là không
chứa phần tử ai, nên nó chỉ có thể là một trong hai dãy:
– Dãy con lớn nhất của dãy a1, a2, ..., ai-1
– Dãy con lớn nhất của dãy a1, a2, ..., ai kết thúc tại ai.
• Từ đó suy ra
si = max {si-1, ei}, i = 2, …, n.
trong đó ei là trọng lượng của dãy con lớn nhất của dãy a1, a2, ..., ai kết
thúc tại ai.
• Để tính ei, ta cũng có thể sử dụng công thức đệ qui sau:
– e1 = a1;
– ei = max {ai, ei-1 + ai}, i = 2, ..., n.
NỘI DUNG
1.1. Ví dụ mở đầu
• §Þnh nghÜa. Bµi to¸n tÝnh to¸n F lµ ¸nh x¹ tõ tËp c¸c x©u nhÞ ph©n ®é dµi
h÷u h¹n vµo tËp c¸c x©u nhÞ ph©n ®é dµi h÷u h¹n:
F : {0, 1}* {0, 1}*.
• VÝ dô:
– Mçi sè nguyªn x ®Òu cã thÓ biÓu diÔn díi d¹ng x©u nhÞ ph©n lµ c¸ch
viÕt trong hÖ ®Õm nhÞ ph©n cña nã.
– HÖ ph¬ng tr×nh tuyÕn tÝnh Ax = b cã thÓ biÓu diÔn díi d¹ng x©u lµ
ghÐp nèi cña c¸c x©u biÓu diÔn nhÞ ph©n cña c¸c thµnh phÇn cña ma
trËn A vµ vect¬ b.
– §a thøc mét biÕn P(x) = a0 + a1 x + ... + an xn hoµn toµn x¸c ®Þnh bëi
d·y sè n, a0, a1, ..., an, mµ ®Ó biÓu diÔn d·y sè nµy chóng ta cã thÓ sö
dông x©u nhÞ ph©n.
Cấu trúc dữ liệu và thuật toán - N.Đ. Nghĩa. Bộ môn KHMT
• Problem solving
– Là quá trình đặt bài toán và phát triển chương trình máy tính để giải bài
toán đặt ra
– Đòi hỏi để phát triển một phần mềm có chất lượng tốt
– Lập trình viên có thể di chuyển từ một pha trong vòng đời
sang bất kỳ pha nào còn lại
Vòng đời của phần mềm như là một bánh lái có thể quay từ một pha đến một pha
khác bất kỳ
Nguyễn Đức Nghĩa - Bộ 1-35
Cấu trúc dữ liệu và thuật toán - N.Đ. Nghĩa. Bộ môn KHMT
môn KHMT ĐHBKHN
9 pha:
• Phase 1: Chỉ rõ đặc điểm kỹ thuật (Specification) (đặc tả)
• Phase 2: Thiết kế (Design)
• Phase 3: Phân tích rủi ro (Risk Analysis)
• Phase 4: Kiểm thử (Verification)
• Phase 5: Lập trình (Coding)
• Phase 6: Test thử (Testing)
• Phase 7: Tinh chế lời giải (Refining the Solution)
• Phase 8: Sản xuất (Production)
• Phase 9: Bảo trì (Maintenance)
• Đánh giá độ phức tạp tính toán của thuật toán là đánh giá lượng
tài nguyên các loại mà thuật toán đòi hỏi sử dụng. Có hai loại tài
nguyên quan trọng đó là thời gian và bộ nhớ. Trong giáo trình
này ta đặc biệt quan tâm đến đánh giá thời gian cần thiết để thực
hiện thuật toán mà ta sẽ gọi là thời gian tính của thuật toán.
• Thời gian tính phụ thuộc vào dữ liệu vào.
• §Þnh nghÜa. Ta gäi kÝch thíc d÷ liÖu ®Çu vµo (hay độ dài dữ
liệu vào) lµ sè bÝt cÇn thiÕt ®Ó biÓu diÔn nã.
• Ta sẽ tìm cách đánh giá thời gian tính của thuật toán bởi một hàm
của độ dài dữ liệu vào.
Cấu trúc dữ liệu và thuật toán - N.Đ. Nghĩa. Bộ môn KHMT
– Thêi gian nhiÒu nhÊt cÇn thiÕt ®Ó thùc hiÖn thuËt to¸n víi mäi bé d÷ liÖu
®Çu vµo kÝch thíc n. Thêi gian nh vËy sÏ ®îc gäi lµ thêi gian tÝnh tåi
nhÊt cña thuËt to¸n víi ®Çu vµo kÝch thíc n.
– Thêi gian trung b×nh cÇn thiÕt ®Ó thùc hiÖn thuËt to¸n trªn tËp h÷u h¹n c¸c
®Çu vµo kÝch thíc n. Thêi gian nh vËy sÏ ®îc gäi lµ thêi gian tÝnh trung
b×nh cña thuËt to¸n.
Cấu trúc dữ liệu và thuật toán - N.Đ. Nghĩa. Bộ môn KHMT
NỘI DUNG
1.1. Ví dụ mở đầu
Q, W, O
Ký hiệu Q
10n2 - 3n = (n2) ?
• Với giá trị nào của các hằng số n0, c1, và c2 thì bất đẳng
thức trong định nghĩa là đúng?
Đối với hàm g(n) cho trước, ta ký hiệu O(g(n)) là tập các hàm
O(g(n)) = {f(n): tồn tại các hằng số dương c và n0 sao cho:
f(n) cg(n) với mọi n n0 }
Đối với hàm g(n) cho trước, ta ký hiệu W(g(n)) là tập các hàm
W(g(n)) = {f(n): tồn tại các hằng số dương c và n0 sao cho:
cg(n) f(n) với mọi n n0 }
Liên hệ giữa , W, O
• Nói “Thời gian tính là O(f(n))” hiểu là: Đánh giá trong tình huống tồi
nhất (worst case) là O(f(n)). Thường nói: “Đánh giá thời gian tính
trong tình huống tồi nhất là O(f(n))”
• Nghĩa là thời gian tính trong tình huống tồi nhất được xác định
bởi một hàm nào đó g(n) O(f(n))
• “Thời gian tính là W(f(n))” hiểu là: Đánh giá trong tình huống tốt nhất
(best case) là W(f(n)). Thường nói: “Đánh giá thời gian tính trong
tình huống tốt nhất là W(f(n))”
– Nghĩa là thời gian tính trong tình huống tốt nhất được xác định
bởi một hàm nào đó g(n) W(f(n))
Ví dụ
• Mọi thuật toán sắp xếp đều đòi hỏi duyệt qua tất
cả các phần tử, vì thế bài toán sắp xếp có thời gian
W(n) trong tình huống tốt nhất.
n logn n nlogn n2 n3 2n
4 2 4 8 16 64 16
8 3 8 24 64 512 256
Sự tương tự giữa
so sánh các hàm số và so sánh các số
fg ab
f (n) = O(g(n)) a b
f (n) = W(g(n)) a b
f (n) = (g(n)) a = b
A B
• 5n2 + 100n 3n2 + 2
• log3(n2) log2(n3)
Ví dụ
A B
• 5n2 + 100n 3n2 + 2 A (B)
A (n2), n2 (B) A (B)
• log3(n2) log2(n3)
A B
• 5n2 + 100n 3n2 + 2 A (B)
A (n2), n2 (B) A (B)
Ví dụ
A B
• 5n2 + 100n 3n2 + 2 A (B)
A (n2), n2 (B) A (B)
• Với mỗi cặp hàm sau đây, hoặc f(n) = O(g(n)), f(n) = Ω(g(n)),
hoặc f(n) = Θ(g(n)). Hãy xác định quan hệ nào là đúng.
– f(n) = log n2; g(n) = log n + 5 f(n) = (g(n))
– f(n) = n; g(n) = log n2 f(n) = W(g(n))
– f(n) = log log n; g(n) = log n f(n) = O(g(n))
– f(n) = n; g(n) = log2 n f(n) = W(g(n))
– f(n) = n log n + n; g(n) = log n f(n) = W(g(n))
– f(n) = 10; g(n) = log 10 f(n) = (g(n))
– f(n) = 2n; g(n) = 10n2 f(n) = W(g(n))
– f(n) = 2n; g(n) = 3n f(n) = O(g(n))
Ví dụ
– 1000n2+1000n = O(n2):
– 5n2 = W(n)
c, n0 sao cho: 0 cn 5n2 cn 5n2 c = 1 và n0 = 1
– 100n + 5 ≠ W(n2)
Giả sử: c, n0 sao cho: 0 cn2 100n + 5.
Ta có: 100n + 5 100n + 5n ( n 1) = 105n
Suy ra: cn2 105n n(cn – 105) 0
Do n dương cn – 105 0 n 105/c
vô lý: n không thể nhỏ hơn hằng số
Ví dụ
• ½ n2 - ½ n ≤ ½ n2 n ≥ 0 c2= ½
• ½ n2 - ½ n ≥ ½ n2 - ½ n * ½ n ( n ≥ 2 ) = ¼ n2
c1= ¼
n ≠ (n2): c1 n2 ≤ n ≤ c2 n2
Chú ý
• Giá trị của n0 và c không phải là duy nhất trong chứng minh công thức tiệm
cận
• Chỉ cần tìm các hằng c và n0 nào đó thoả mãn bất đẳng thức trong định nghĩa
công thức tiệm cận
• Định nghĩa (Upper Bound). Cho bài toán P, ta nói cận trên
cho thời gian tính của P là O(g(n)) nếu để giải P tồn tại thuật
toán giải với thời gian tính là O(g(n)) .
• Định nghĩa (Lower Bound). Cho bài toán P, ta nói cận dưới
cho thời gian tính của P là (g(n)) nếu mọi thuật toán giải P
đều có thời gian tính là W(g(n)) .
• Định nghĩa. Cho bài toán P, ta nói thời gian tính của P là
Q(g(n)) nếu P có cận trên là O(g(n)) và cận dưới là W(g(n)) .
1.1. Ví dụ mở đầu
• Để mô tả thuật toán có thể sử dụng một ngôn ngữ lập trình nào
đó. Tuy nhiên điều đó có thể làm cho việc mô tả thuật toán trở
nên phức tạp đồng thời rất khó nắm bắt.
• Vì thế, để mô tả thuật toán người ta thường sử dụng giả ngôn
ngữ (pseudo language), trong đó cho phép vừa mô tả thuật
toán bằng ngôn ngữ đời thường vừa sử dụng những cấu trúc
lệnh tương tự như của ngôn ngữ lập trình.
• Dưới đây ta liệt kê một số câu lệnh chính được sử dụng trong
giáo trình để mô tả thuật toán.
while condition do
dãy câu lệnh
endwhile;
repeat
Câu lệnh case:
dãy câu lệnh;
until condition; Case
cond1: stat1;
for i=n1 to n2 [step d] cond2: stat2;
dãy câu lệnh; .
.
endfor; .
condn: stat n;
• Vào-Ra endcase;
read(X); /* X là biến đơn hoặc mảng */
print(data) hoặc print(thông báo)
• Ví dụ: Thuật toán tìm phần tử lớn nhất trong mảng A(1:n)
Function max(A(1:n))
begin
datatype x; /* để giữ giá trị lớn nhất tìm được */
integer i;
x=A[1];
for i=2 to n do
if x < A[i] then
x=A[i];
endif
endfor ;
return (x);
end max;
Cấu trúc dữ liệu và thuật toán - N.Đ. Nghĩa. Bộ môn KHMT
Procedure swap(x, y)
begin
temp=x;
x = y;
y = temp;
end swap;
1.1. Ví dụ mở đầu
• Cấu trúc tuần tự. Gi¶ sö P vµ Q lµ hai ®o¹n cña thuËt to¸n, cã
thÓ lµ mét c©u lÖnh nhng còng cã thÓ lµ mét thuËt to¸n con.
Gäi Time(P), Time(Q) lµ thêi gian tÝnh cña P vµ Q t¬ng øng.
Khi ®ã ta cã
Quy t¾c tuÇn tù: Thêi gian tÝnh ®ßi hái bëi “P; Q”, nghÜa lµ P
thùc hiÖn tríc, tiÕp ®Õn lµ Q, sÏ lµ
Time(P; Q) = Time(P) + Time(Q) ,
hoÆc trong ký hiÖu Theta:
Time(P; Q) = (max(Time(P), Time(Q)).
for i =1 to m do P(i);
t(i)
i 1
• Cần xác định một hàm của các biến trong vòng lặp sao
cho hàm này có giá trị giảm dần trong quá trình lặp. Khi
đó
– Để chứng minh tính kết thúc của vòng lặp ta chỉ cần chỉ ra
giá trị của hàm là số nguyên dương.
– Còn để xác định số lần lặp ta cần phải khảo sát xem giá trị
của hàm giảm như thế nào.
• Việc phân tích vòng lặp Repeat được tiến hành tương tự
như phân tích vòng lặp While.
• Gọi d= j-i+1. d – số phần tử của mảng cần tiếp tục khảo sát
• Ký hiệu i, j, i*, j* theo thứ tự là giá trị của i, j trước và sau khi
thực hiện lần lặp. Khi đó
– Nếu x < T[k], thì i*=i, j*=(i+j) div 2 - 1, vì thế d*=j*- i*+1
= (i+j) div 2 - 1- i + 1 (i+j)/2 - i < (j - i + 1)/2 = d/2.
– Nếu x > T[k], thì j*=j, i*=(i+j) div 2 + 1, vì thế d*=j*-
i*+1 = j - (i+j) div 2 j -(i+j-1)/2 - i = (j - i + 1)/2 = d/2.
– Nếu x = T[k], thì d* = 1 còn d 2
Binary-Search (tiếp)
Hàm trên C
Ví dụ: FibIter
function Fibiter(n)
begin
i:=0; j:=1; Câu lệnh đặc
for k:=1 to n do trưng
begin • Số lần thực hiện câu lệnh
j:= j+i; đặc trưng là n.
i:= j-i;
• Vậy thời gian tính của thuật
end;
toán là O(n)
Fibiter:= j;
end;
• Nhận xét: Khi thuật toán đòi hỏi thực hiện nhiều vòng lặp lồng nhau, thì có
thể lấy câu lệnh nằm trong vòng lặp trong cùng làm câu lệnh đặc trưng.
• Tuy vậy, cũng cần hết sức thận trọng khi sử dụng cách lựa chọn này.
• Ví dụ. Sắp xếp kiểu nhốt chim vào chuồng (Pigeonhole Sorting).
Sắp xếp n số nguyên dương có giá trị nằm trong khoảng 1..s.
Đầu vào: T[1..n]: mảng chứa dãy cần sắp xếp.
Đầu ra: T[1..n]: mảng chứa dãy được sắp xếp không giảm.
Thuật toán bao gồm 2 thao tác:
– Đếm chim: Xây dựng mảng U[1..s], trong đó phần tử U[k] đếm số
lượng số có giá trị là k trong mảng T.
– Nhốt chim: Lần lượt nhốt U[1] con chim loại 1 vào U[1] lồng đầu tiên,
U[2] con chim loại 2 vào U[2] lồng tiếp theo, ...
procedure Pigeonhole-Sorting;
begin
(* đếm chim *)
for i:=1 to n do inc(U[T[i]]);
(* Nhốt chim *)
i:=0;
for k:=1 to s do
while U[k]<>0 do
begin
i:=i+1;
T[i]:=k;
U[k]:=U[k]-1;
end;
end;
• Nếu chọn câu lệnh bất kỳ trong vòng lặp while làm câu lệnh
đặc trưng, thì rõ ràng với mỗi k, câu lệnh này phải thực hiện
U[k] lần. Do đó số lần thực hiện câu lệnh đặc trưng là
s
U [k ] n
k 1
Khi đó s = n2. Rõ ràng thời gian tính của thuật toán không phải là
O(n), mà phải là O(n2).
• Lỗi ở đây là do ta xác định câu lệnh đặc trưng chưa đúng, các
câu lệnh trong thân vòng lặp while không thể dùng làm câu lệnh
đặc trưng trong trường hợp này, do có rất nhiều vòng lặp rỗng
(khi U[k] = 0).
• Nếu ta chọn câu lệnh kiểm tra U[k] <> 0 làm câu lệnh đặc
trưng thì rõ ràng số lần thực hiện nó sẽ là n + s. Vậy thuật toán có
thời gian tính O(n+s) = O(n2).
Cấu trúc dữ liệu và thuật toán - N.Đ. Nghĩa. Bộ môn KHMT
Questions?