Thuật toán nâng cao
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (804.28 KB, 120 trang )
Mục ñích
Các khái niệm liên quan ñến bài toán và
giải quyết bài toán
Phân tích và ñánh giá thuật toán
Các kỹ thuật thiết kế thuật toán
Vận dụng giải quyết các bài toán cụ thể
Thuật toán nâng cao
Nguyễn Thanh Bình
Khoa Công nghệ Thông tin
Trường ñại học Bách khoa
ðại học ðà Nẵng
2
Nội dung
Giới thiệu
Chứng minh sự ñúng ñắn
ðộ phức tạp (complexity)
ðệ quy (recursion)
Chia ñể trị (divide and conquer)
Quy hoạch ñộng (dynamic programming)
Thuật toán tham lam (greedy algorithms)
Quay lui (backtracking)
Thuật toán xác xuất (probabiliste algorithms)
Lớp các bài toán NP ñầy ñủ (NP-complete)
Thuật toán xấp xĩ (approximation algorithms)
ðánh giá
7
41
70
122
152
191
290
355
399
442
461
3
Bài tập lớn 1
Tóm tắt bài báo khoa học
Bài tập lớn 2
Tìm hiểu và trình bày một chủ ñề về thuật
toán
Thi kết thúc môn học
4
1
Tài liệu tham khảo
1.
2.
3.
4.
5.
6.
7.
Bài tập lớn
Introduction to algorithms, T.H. Cormen, C.E. Leiserson,
R.R. Rivest, Mit Press 1990.
Type de Données et Algorithmes, M-C Gaudel, M. Soria, C.
Froidevaux, Ediscienne international, 1993.
Cours Complexité, M. Daniel, ESIL, 2006.
Data structures and algorithms, Alfred V. Aho, John E.
Hopcroft, Addison-Wesley, 1983.
Algorithm Analysis and Computational Comlexity, Ian
Parberry, Lecture Notes, University of North Texas, 2001.
The Art of Computer Programming, Volume 2, D. Knuth,
Addison-Wesley, 1981.
Các tài liệu khác trên Internet.
Mỗi học viên chọn trình bày một trong các chủ
ñề sau
Kỹ thuật nhánh và cận (branch and bound)
Kỹ thuật biến ñổi Fourier (Fourier transform)
Thuật toán di truyền (genetic algorithm)
Yêu cầu
Tìm hiểu và trình bày về chủ ñề
Minh hoạ và giải thích phương pháp bởi ít nhất 2 ví dụ
cụ thể
ðánh giá và phân tích giải pháp các ví dụ
Học viên tự tìm kiếm các tài liệu liên quan ñến chủ ñề
Kết quả
Báo cáo từ 10 ñến 20 trang
Báo cáo phải trích dẫn rỏ ràng các tài liệu tham khảo
5
6
Giới thiệu
Khái niệm giải thuật/thuật toán (algorithm)
Giới thiệu (1)
Thuật toán là một dãy xác ñịnh các thao tác cơ bản áp
dụng trên dữ liệu vào nhằm ñạt ñược giải pháp cho một
vấn ñề
Hai vấn ñề
Tìm một phương pháp giải quyết vấn ñề
Nguyễn Thanh Bình
Khoa Công nghệ Thông tin
Trường ñại học Bách khoa
ðại học ðà Nẵng
Giải pháp cho ax2 + bx + c = 0 : rỏ ràng và xác ñịnh
Giải pháp cho ax5 + bx4 + cx3 + dx2 + ex + f = 0 : không có
giải pháp tổng quát
Tìm một giải pháp hiệu quả
Phân biệt giải thuật và chương trình
Chương trình là cài ñặt thuật toán bằng một ngôn ngữ lập
trình
8
2
Giới thiệu
Giới thiệu
Thuật toán
Thuật toán hằng ngày trong cuộc sống
Nấu cơm
…
Thủ tục tính toán nhận tập các dữ liệu vào
(input) và tạo các dữ liệu ra (output)
Gọi ñiện thoại
Thuật toán ñược gọi là ñúng ñắn (correct),
nếu thuật toán dừng cho kết quả ñúng với
mọi dữ liệu vào
Thuật toán trong toán học/tin học
Nhân hai ma trận
Tính tích phân
Giải hệ phương trình bậc nhất
…
9
Giới thiệu
10
Giới thiệu
Các tính chất của thuật toán
Tính tổng quát (1)
Thuật toán phải áp dụng cho tất cả các mẫu dữ
liệu vào chứ không chỉ là một mẫu dữ liệu vào
cụ thể
Tính tổng quát
Tính hữu hạn
Ví dụ
Sắp xếp tăng dần một dãy các giá trị
Tính không nhập nhằng
Dữ liệu vào :
Kết quả
:
Tính hiệu quả
11
2
1
1
2
4
3
3
4
5
5
12
3
Giới thiệu
Giới thiệu
Tính tổng quát (2)
Tính hữu hạn
Phương pháp
Thuật toán phải dừng sau một số bước xác
ñịnh
So sánh hai phần tử liên tiếp nhau từ trái qua phải,
nếu không ñúng thứ tự thì hoán ñổi vị trí chúng
Bước
Bước
Bước
Bước
1:
2:
3:
4:
2↔1
2
1
1
2
1
2
4
3
4
3
4 ↔3
3
4
5
5
5
5
Ví dụ
nhập n
while (n ≠ 0)
n=n–2
endwhile
Dãy ñã ñược sắp xếp
Thuật toán có tổng quát không ?
Không
Thuật toán có dừng không ?
Ví dụ dữ liệu vào: 2 1 5 4 3
13
Giới thiệu
14
Giới thiệu
Tính hiệu quả
Tính không nhập nhằng
Các thao tác trong thuật toán phải ñược ñặc tả chặt chẽ
Ở mỗi bước thực thi, bước tiếp theo sẽ ñược thực thi phải
ñược xác ñịnh rõ ràng
Thuật toán phải sử dụng hiệu quả nguồn tài nguyên máy
tính
Thời gian
Bộ nhớ
Ví dụ
gt1 (n)
begin
p=1
for i from 1 to n do
p = p * i;
endfor
end
Ví dụ
Bước 1: x = 0
Bước 2: tăng x lên 1 hoặc giảm x xuống 1
Bước 3: if (x ∈[-2,2]) then
goto Bước 2
Thuật toán có nhập nhằng ?
gt2 (n)
begin
if (n = 0) return (1)
else
return (n*gt(n-1))
endif
end
Thuật toán nào hiệu quả hơn ?
15
16
4
Giới thiệu
Giới thiệu
ðặc tả thuật toán (1)
ðặc tả thuật toán (2)
Có nhiều cách ñặc tả thuật toán
Chọn phương pháp ñặc tả nữa hình thức
Không hình thức
Ngôn ngữ giả tựa C/Pascal kết hợp ngôn ngữ tự nhiên
Ngôn ngữ tự nhiên
if (ñiều kiện) then
…
else
…
endif
Nữa hình thức
Kêt hợp ngôn ngữ tự nhiên và các kí hiệu toán học
Sơ ñồ khối, ngôn ngữ giả, …
Hình thức
Các kí hiệu toán học
Ngôn ngữ Z, ngôn ngữ B, …
while () do
…
endwhile
for … from … to … do
…
endfor
17
Giới thiệu
18
Giới thiệu
Ví dụ 1
Ví dụ 1
Giải pháp thô
Có 15 hộp ñinh có chiều dài khác nhau. Cần
ñặt chúng vào trong 15 ngăn kéo. Chúng ta
cần phải thực hiện thế nào ñể có thể lấy ñược
loại ñinh chúng ta cần một cách nhanh nhất?
Chúng ta xếp các hộp ñinh vào các ngăn kéo theo thứ tự
bất kỳ. Sau ñó, mỗi khi cần lấy ñinh chúng ta mở các
ngăn kéo theo thứ tự từ trái qua phải.
Trường hợp xấu nhất: phải mở 15 ngăn kéo
Trường hợp trung bình: giả sử xác xuất lấy các loại ñinh
ngang nhau, phải mở 8 ngăn kéo
1 15
1 15 *16
∑ i = 15 * 2 = 8
15 1
Nếu những loại ñinh trong các ngăn kéo cuối cùng luôn
ñược sử dụng, cần nhiều lần mở các ngăn kéo
19
20
5
Giới thiệu
Giới thiệu
Ví dụ 1
Ví dụ 1
Giải pháp tiền xử lý
Giải pháp Las Vegas
Chúng ta sắp xếp các hộp ñinh theo thứ tự chiều dài của
chúng
Xếp vào các ngăn kéo theo thứ tự trên
Nếu lại mở các ngăn kéo từ trái sang phải thì sẽ không
thu ñược lợi ích gì
Mở các ngăn kéo theo phương pháp tìm kiếm nhị phân
Trường hợp xấu nhất: 4 lần mở ngăn kéo
Trường hợp trung bình: 3.26
Chúng ta chọn ngăn kéo ñể mở một cách ngẫu nhiên
Nếu may mắn, chúng ta có loại ñinh cần lấy
Nếu không, chúng ta loại bỏ ngăn kéo vừa mở, thực
hiện mở ngăn kéo khác một cách ngẫu nhiên
1
14 1
14 13 1
1 15
*1 + * * 2 + * * * 3 + ... = ∑1 i = 8
15
15 14
15 14 13
15
1
2
4
8
*1 + * 2 + * 3 + * 4 = 3.26
15
15
15
15
Giải pháp chỉ có ý nghĩa khi chúng ta thường xuyên mở
các ngăn kéo lấy ñinh
21
Giới thiệu
22
Giới thiệu
Ví dụ 2
Ví dụ 2
Thuật toán nhân hai số nguyên
Thuật toán nhân Anh
567
1234
567
1134
1701
2268
699678
Thuật toán nhân Bắc Mỹ
567
1234
2268
1701
1134
567
699678
23
24
6
Giới thiệu
Giới thiệu
Ví dụ 2
Ví dụ 2
Thuật toán nhân Ả-rập
ðếm số phép toán nhân và cộng ñược thực hiện
5
0
6
9
9
6
0
0
5
1
0
6
1
0
1
2
5
6
4
2
8
2
0
7
1
1
2
7
1
2
4
7
8
Thuật toán nhân Bắc Mỹ và thuận toán nhân Anh ñều sử
dụng 12 phép nhân và 15 phép cộng
Thuật toán Ả-rập sử dụng 12 phép nhân và 20 phép cộng
Số phép toán phụ thuộc vào số chữ số của mỗi số nguyên
1
2
Số phép nhân bằng m*n với m và n lần lượt là số chữ số của
mỗi số nguyên
3
4
8
So sánh ñộ hiệu quả các thuật toán ?
25
Giới thiệu
26
Giới thiệu
Ví dụ 2
Ví dụ 2
Thuật toán nhân Nga
567
1234
283
2468
141
4936
70
9872
35
19744
17
39488
8
78976
4
157952
2
315904
1
631808
699678
Thuật toán nhân « chia ñể trị »
Số chữ số của hai số nguyên phải bằng nhau và phải bằng
luỹ thừa 2
Nếu số chữ số của hai số nguyên khác nhau thì thêm vào các
số 0 ở bên trái
Ưu ñiểm: không cần
ghi nhớ các kết quả
nhân trung gian, chỉ
cần thực hiện phép
cộng và chia cho 2
Ý tưởng: chúng ta thay phép nhân của hai số nguyên có n
chữ số bởi 4 phép nhân của hai số nguyên có n/2 chữ số.
Tiếp tục, thay phép nhân của hai số nguyên có n/2 chữ số
bởi 4 phép nhân của hai số nguyên có n/4 chữ số, …
Cần nhân hai số nguyên: a và b. Gọi aL và aR là hai nữa
trái và phải của số a, tương tự bL và bR là hai nữa trái và
phải của b
27
28
7
Giới thiệu
Giới thiệu
Ví dụ 2
Ví dụ 2
Thuật toán nhân « chia ñể trị »
Thuật toán nhân « chia ñể trị »
a*b
Giảm số phép nhân a và b bởi các nữa của a và b từ 4
xuống còn 3
= (aL*10n/2+ aR)*(bL*10n/2+ bR)
= aL*bL*10n + aL*bR*10n/2 + aR*bL*10n/2 + aR*bR
= aL*bL*10n + (aL*bR + aR*bL)10n/2 + aR*bR
*
+ aLbL
aL
bL
aR
bR
aLbR
aRbL
aRbR
ðặt:
p = aL*bL
q = aR*bR
r = (aL + aR)*(bL + bR)
Khi ñó:
a*b
= aL*bL*10n + (aL*bR + aR*bL)*10n/2 + aR*bR
= p*10n + (r – p - q)*10n/2 + q
aLbL+ (aLbR +aRbL) + aRbR
ðể nhân a và b bởi các nữa của a và b, cần sử dụng 4 phép nhân
Số phép nhân sử dụng bởi thuật toán này ñược ñánh giá
là n*m0.59 với n ≥ m
Khi nhân hai số nguyên khá lớn, thuật toán này ñược
ñánh giá nhanh hơn các thuật toán trước
29
Giới thiệu
Giới thiệu
Ví dụ 2
Ví dụ 3: tính xn
Thuật toán nhân « chia ñể trị »
0567 * 1234
nhân
số bước dịch
05 12
4
05 34
2
67 12
2
67 34
0
30
kết quả
60
170
804
2278
699678
05 * 34
nhân
số bước dịch
0 3
2
0 4
1
5 3
1
5 4
0
Vào: một số nguyên x và một số nguyên
không âm n
Ra: y = xn
Thuật toán ñơn giản
kết quả
0
0
15
20
170
31
if n = 0 then
y=1
else
y=x
endif
for i from 1 to n do
y=y*x
endfor
32
8
Giới thiệu
Giới thiệu
Ví dụ 3: tính xn
Ví dụ 3: tính xn
Thuật toán nhị phân
Thuật toán nhị phân
Giảm số phép toán
Ý tưởng: sử dụng các kết quả trung gian
Nguyên tắc: nếu n/2 = 0 thì xn = xn/2 * xn/2 nếu không thì
xn = xn-1 * x
Chẳng hạn
1.
2.
Biểu diễn n bởi dãy nhị phân
Thay mỗi bít nhị phân
« 1 » bởi các kí hiệu SX
« 0 » bởi các kí hiệu S
x35 = x34 * x
x34 = x17 * x17
x17 = x16 * x
x16 = x8 * x8
x8 = x4 * x4
x4 = x2 * x2
x2 = x * x
3.
4.
Xoá cặp kí hiệu SX bên trái nhất
Kết quả: cách tính xn trong ñó
S nghĩa là bình phương
X nghĩa là nhân với x
Bắt ñầu từ x
33
Giới thiệu
34
Giới thiệu
Ví dụ 3: tính xn
Ví dụ 3: tính xn
Thuật toán nhị phân
Thuật toán nhị phân
Ví dụ: n = 35 = 100011(2)
Biểu diễn n bởi dãy nhị phân: ek-1ek-2…e0
if ek-1 = 0 then
y = 1 // khi n = 0
else
y=x
endif
for i from k-2 to 0 do
y=y*y
if ei = 1 then
y=y*x
endif
endfor
35
ei
y
số phép nhân
1
x
0
0
x2
1
0
x4
2
0
x8
3
1
x17
5
1
x35
7
36
9
Giới thiệu
Giới thiệu
Ví dụ 3: tính xn
Ví dụ 3: tính xn
Thuật toán nhị phân: giải thích
Thuật toán nhị phân: có giải pháp tốt hơn ?
Biểu diễn nhị phân của n: n = ∑i =0 Ai 2i
Giả sử chúng ta ñang trong quá trình tính xn. Gọi j là vị trí
bít bên cuối cùng (trái nhất) biểu diễn n, yj là kết quả cuối
cùng có ñược. Ban ñầu: j = p, yp = x = xAp
Có hai khả năng của Aj-1
p
Chẳng hạn tính x15
1. n = 15 = 1111
2. SX
SX
SX
3.
SX
SX
4. Bắt ñầu bởi x, chúng ta có:
Vậy, chúng ta sử dụng 6 phép
Aj-1 = 1. Thay thế Aj-1 bởi SX. Vậy yj-1 = yj2 * x
Aj-1 = 0. Thay thế Aj-1 bởi S. Vậy yj-1 = yj2
Cả hai trường hợp: yj-1 = yj2 * xAj-1
Tuy nhiên, chúng ta có thể tính x15 bởi:
x2, x3, x6, x12, x15 = x12 * x3
Nghĩa là chỉ cần sử dụng 5 phép nhân
Vậy: yp-1 = yp2 * xAp-1 = (xAp)2 * xAp-1 = x2Ap + Ap-1
Bằng truy hồi:
y1 = x
∑ip=0 Ai 2
i
SX
SX
x2, x3, x6, x7, x14, x15
nhân
= xn
37
Giới thiệu
38
Giới thiệu
Ví dụ 3: tính xn
Phân tích và ñánh giá các thuật toán
Phương pháp ước số
xn = x nếu n = 1
xn = xn-1 * x nếu n là số nguyên tố
xn = (xr)s nếu n = r * s với r là ước số nguyên tố nhỏ nhất
của n và s > 1
Dựa vào các tính chất của thuật toán
Ví dụ: n = 15
15 = 3 * 5, khi ñó x15 = (x3)5. Áp dụng thuật toán ñể tính
x3 và c5 với c = x3.
x3 = x2 * x, áp dụng thuật toán tính x2
x2 = x * x
c5 = c4 * c, áp dụng thuật toán tính c4
c4 = (c2)2
2 phép nhân tính c4, 3 phép nhân tính c5, 2 phép nhân tính
x3. Vậy 5 phép nhân tính x15
39
Chứng minh sự ñúng ñắn
ðánh giá ñộ phức tạp
40
10
Phân tích thuật toán
Chứng minh sự ñúng ñắn
(2)
Kiểm tra sự ñúng ñắn
Chỉ ra rằng thuật toán cho kết quả như mong
ñợi sau một số bước thực hiện
ðánh giá hiệu quả
ðánh giá nguồn tài nguyên thuật toán sử dụng
của máy tính
Nguyễn Thanh Bình
Khoa Công nghệ Thông tin
Trường ñại học Bách khoa
ðại học ðà Nẵng
Thời gian
Bộ nhớ
42
Ưu nhược ñiểm
Kiểm tra tính ñúng ñắn
Thực nghiệm
Kiểm thử (testing)
Thực nghiệm
Thực thi thuật toán trên tập các dữ liệu vào và quan
sát kết quả
Ưu ñiểm
Lý thuyết
Nhược ñiểm
Chứng minh sự ñúng ñắn (correctness proof)
Chứng minh rằng thuật toán cho kết quả ñúng với
mọi dữ liệu vào
43
giản hơn
thực hiện
Lý thuyết
-ðơn
-Bảo
-Dễ
ñắn
-Không
bảo ñảm
hoàn toàn tính ñúng
ñắn
ñảm tính ñúng
-Khó
thực hiện
thể áp dụng
cho các thuật toán
phức tạp
-Không
44
11
Chứng minh sự ñúng ñắn
Tiền ñiều kiện và hậu ñiều kiện
Tiền ñiều kiện (preconditions)
Một vài khái niệm
Các tính chất mà dữ liệu vào phải thoả mãn
Tiền ñiều kiện và hậu ñiều kiện
Hậu ñiều kiện (postconditions)
Các tính chất mà kết quả của thuật toán phải thoả mãn
Trạng thái của thuật toán
Ví dụ
Các xác nhận
Tìm giá trị m nhỏ nhất trong mảng không rỗng x[1..n]
preconditions: n ≥ 1
postconditions: m = min(x[i] | 1 ≤ i ≤ n)
Chú thích thuật toán
45
Trạng thái của thuật toán
46
Các xác nhận
Xác nhận (assertion)
Trạng thái của thuật toán
là một câu lệnh mô tả các ràng buộc trên trạng thái của
thuật toán
là tập các giá trị tương ứng với tất cả các biến ñược sử
dụng trong thuật toán
Ví dụ
Trong quá trình thực thi trạng thái thuật toán
thay ñổi
{x > 0}
x=x+y
{x > y}
Thuật toán là ñúng nếu cuối cùng trạng thái của
nó thoả mãn hậu ñiều kiện
Các xác nhận ñược sử dụng
Chứng minh sự ñúng ñắn
Chú thích thuật toán
Viết tài liệu
47
48
12
Chú thích thuật toán
Chứng minh sự ñứng ñắn
Sử dụng các xác nhận ñể chú thích thuật toán
Chứng minh ñúng ñắn một phần (partial correctness)
Chứng minh rằng khi dữ liệu vào thoả mãn tiền ñiều kiện thì
kết quả thuật toán sẽ thoả mãn hậu ñiều kiện
Ví dụ
min (x[1..n])
begin
{n ≥ 1}
m = x[1]
{m = x[1]}
for i from 2 to n do
{2 ≤ i ≤ n}
if (m > x[i]) then
m = x[i]
endif
{m = min(x[1], x[2], …, x[i])}
endfor
return (m)
end
Chứng minh ñúng ñắn toàn phần (total correctness)
Chứng minh rằng thuật toán ñúng ñắn một phần và thuật toán
dừng
Các bước trung gian trong chứng minh sự ñúng ñắn
Phân tích trạng thái của thuật toán
Phân tích sự ảnh hưởng của mỗi bước xử lý ñến trạng thái của
thuật toán
49
Chứng minh sự ñứng ñắn
50
Chứng minh sự ñứng ñắn
Ký hiệu
Các bước cơ bản
P - tiền ñiều kiện
Q - hậu ñiều kiện
A - thuật toán
Xác ñịnh các tiền ñiều kiện và hậu ñiều kiện
A ñúng ñắn nếu với dữ liệu vào thoả mãn P thì
A sẽ
cho kết quả thoả mãn Q
dừng sau một số bước xử lý hữu hạn
Chú thích thuật toán bằng cánh chèn thêm các xác nhận
liên quan ñến trạng thái của thuật toán sao cho
tiền ñiều kiện ñược thoả mãn
xác nhận cuối cùng phải bao hàm hậu ñiều kiện
Chứng minh rằng mỗi bước xử lý, thuật toán ñi từ xác
nhận trước xử lý ñến xác nhận sau xử lý
Ký hiệu
{P} A {Q}
51
52
13
Quy tắc lệnh tuần tự
Các quy tắc chứng minh sự ñúng ñắn
Một số quy tắc cho các cấu trúc lệnh cơ
bản
Dãy lệnh tuần tự A
{P0}
I1
{P1}
…
Lệnh tuần tự
{Pi-1}
Ik
{Pi}
Lệnh ñiều kiện/rẽ nhánh
Quy tắc
Nghĩa là:
Nếu
Nếu
-tiền ñiều kiện P
bao hàm xác nhận
ñầu tiên
-mỗi câu lệnh bao
hàm xác nhận tiếp
theo
-xác nhận cuối cùng
bao hàm hậu ñiều
kiện
P ⇒ P0
{Pk-1} Ik {Pk}, k=2..n
Pn ⇒ Q
Thì
…
Lệnh lặp
{P} A {Q}
Thì
-dãy lệnh tuần tự A
ñúng
{Pn-1}
In
{Pn}
53
Quy tắc lệnh tuần tự
54
Quy tắc lệnh ñiều kiện
Ví dụ
Hai biến x và y nhận hai giá trị tương ứng a và b. Hoán
ñổi giá trị hai biến x và y.
P = {x=a, y=b}
Q = {x=b, y=a}
{x=a, y=b,
tmp = x
{x=a, y=b,
x=y
{x=b, y=b,
y = tmp
{x=b, y=a,
Lệnh ñiều kiện A
{P0}
if (c) then
{c, P0}
I1
{c, P1}
else
{NOT c, P0}
I2
{NOT c, P2}
endif
tmp chưa có giá trị}
tmp=a}
tmp=a}
tmp=a}
Quy tắc
Nghĩa là:
Nếu
Nếu
-tiền ñiều kiện P
bao hàm xác nhận
ñầu tiên
-C có thể ñược ñịnh
giá
-cả hai nhánh ñều
bao hàm hậu ñiều
kiện
P ⇒ P0
c có giá trị
c AND P1 ⇒ Q
NOT c AND P2 ⇒ Q
Thì
{P} A {Q}
Thì
-lệnh ñiều kiện A
ñúng
55
56
14
Quy tắc lệnh ñiều kiện
Quy tắc lệnh lặp
Ví dụ
Một lệnh vòng lặp là ñúng khi
Tìm giá trị nhỏ nhất của a và b với a ≠ b
preconditions: a ≠ b
postconditions: m = min(a,b)
1.
2.
Lệnh A
{a ≠ b}
if (a < b) then
{a < b}
m=a
{a < b, m = a}
else
{a > b}
m=b
{a > b, m = b}
endif
{a < b, m = a} bao hàm m = min(a,b)
và
{a > b, m = b} bao hàm m = min(a,b)
Vậy {preconditions} A {postconditions}
ðúng ñắn một phần ñược chứng minh bởi quy
nạp toán học hoặc bất biến vòng lặp
ðúng ñắn toàn phần cần chứng minh thêm
thuật toán dừng
58
Bất biến vòng lặp
Ví dụ
ðịnh nghĩa
Một bất biến vòng lặp I là
một xác nhận thoả mãn:
1.
P ⇒ {I}
while (c) do
{c, I}
m=a
{I}
endwhile
{NOT c, I} ⇒ Q
Nếu chỉ tính chất 1 ñúng thì chỉ là ñúng ñắn một
phần
57
Bất biến vòng lặp
Lệnh lặp A
Nếu nó dừng, nó thoả mãn hậu ñiều kiện
Nó dừng sau một số bước hữu hạn
2.
3.
Tìm giá trị m nhỏ nhất trong mảng không rỗng x[1..n]
preconditions: n ≥ 1
postconditions: m = min(x[i] | 1 ≤ i ≤ n)
Bất biến vòng lặp ñúng
khi bắt ñầu vòng lặp
Trong quá trình lặp (tức
là ñiều kiện c ñúng) thì
bất biến vòng lặp I luôn
ñúng
Khi thoát khỏi vòng lặp
(tức là ñiều kiện c sai)
thì bất biến vòng lặp I
phải bao hàm hậu ñiều
kiện
min (x[1..n])
begin
m = x[1]
for i from 2 to n do
if (m > x[i]) then
m = x[i]
endif
endfor
return (m)
end
Khi xác ñịnh ñược bất biến vòng lặp, nghĩa là ñã
chứng minh ñược thuật toán ñúng ñắn một phần
59
min (x[1..n])
begin
i = 1, m = x[i]
while (i < n) do
i=i+1
if (m > x[i]) then
m = x[i]
endif
endwhile
return (m)
end
60
15
Bất biến vòng lặp
Hàm dừng
Ví dụ
ðể chứng minh vòng lặp dừng sau một số bước lặp hữu
hạn, chỉ cần xác ñịnh hàm dừng (termination function)
P: n ≥ 1
Q: m = min(x[i] | 1 ≤ i ≤ n)
min (x[1..n])
Bất biến vòng lặp:
begin
I = {m = min(x[j], j=1..i)}
i = 1, m = x[i]
{m = min(x[j], j=1..i)}
Bởi vì:
while (i < n) do
- nếu i=1, m=x[1] thì I ñúng
{i
- nếu i
thân vòng lặp, I vẫn ñúng
m = x[i]
endif
- nếu i=n, m=min(x[j], j=1..n)
{m = min(x[j], j=1..i)}
chính là hậu ñiều kiện
endwhile
{i=n, m = min(x[j], j=1..i)}
61
return (m)
end
Hàm dừng
Hàm T: N→N ñựoc gọi là hàm dừng nếu nó thoả mãn:
1. T luôn giảm
2. Nếu ñiều kiện c ñúng thì T(p)>0, nếu T(p)=0 thì ñiều kiện c
sai
Nhận xét
T phụ thuộc biến ñếm của vòng lặp p
Sau lần lặp thư nhất p = 1, sau lần lặp thứ hai p = 2, …
T sẽ bằng 0 vì nó luôn giảm
Khi T bằng 0 thì ñiều kiện c sai nên vòng lặp dừng
62
Ví dụ
Tìm chỉ số của phần tử (1)
Ví dụ
min (x[1..n])
begin
i = 1, m = x[i]
while (i < n) do
i=i+1
{ip = ip-1 + 1}
if (m > x[i]) then
m = x[i]
endif
endwhile
return (m)
end
ðịnh nghĩa
Cho mảng a[1..n] có chứa phần tử x. Tìm chỉ số i nhỏ
nhất sao cho a[i] = x.
Hàm dừng: T(p) = n - ip
Bởi vì:
preconditions: n≥1, ∃i∈[1..n]: a[i]=x
postconditions: ∃i∈[1..n]: a[i]=x, ∀k∈[1..i-1]:a[k]≠x
T(p) = n - ip = n - ip-1 – 1
= T(p-1) – 1
Vậy T(p) < T(p-1)
Nghĩa là hàm T luôn giảm
Chứng minh thuật toán sau là ñúng
Nếu ñiều kiện vòng lặp ñúng,
thì ip < n, vậy T(p) > 0
Nếu T(p) = 0, thì n – ip = 0
Khi ñó ñiều kiện vòng lặp sai
63
timphantu (a[1..n], x)
begin
i=1
while (a[i] ≠ x) do
i=i+1
endwhile
return (i)
end
64
16
Ví dụ
Ví dụ
Tìm chỉ số của phần tử (2)
Tìm chỉ số của phần tử (3)
Xác ñịnh bất biến vòng lặp
Xác ñịnh hàm dừng
Gọi k là chỉ số nhỏ nhất mà a[k]=x
timphantu (a[1..n], x)
begin
i=1
{a[k] ≠ x, k=1..i-1}
while (a[i] ≠ x) do
{a[i] ≠ x, a[k] ≠ x, k=1..i-1}
i=i+1
{a[k] ≠ x, k=1..i-1}
endwhile
{a[i] = x, a[k] ≠ x, k=1..i-1}
return (i)
end
Bất biến vòng lặp:
I = {a[k] ≠ x, k=1..i-1}
timphantu (a[1..n], x)
begin
i=1
while (a[i] ≠ x) do
i=i+1
{ip=ip-1+1}
endwhile
return (i)
end
Chứng minh quy nạp:
-i=1, thì k=1..0 nên I ñúng
-Giả sử I ñúng sau bước lặp i,
nghĩa là a[k] ≠ x, k=1..i-1
-Ở bước lặp i+1:
-nếu a[i+1]≠x thì a[k] ≠ x,
k=1..i, nghĩa là I ñúng
-nếu a[i+1]=x thì ta có hậu
ñiều kiện Q
65
Nhận xét
Hàm dừng:
T = k - ip
Thật vậy:
T(p) = k – ip = k – ip-1 – 1
= T(p-1) – 1
Vậy T(p) < T(p-1)
Nghĩa là hàm T luôn giảm
Nếu ñiều kiện a[ip]≠x ñúng, thì
k>ip, vậy T(p) >0
Nếu T(p) = 0, thì k=ip, khi ñó ñiều
66
kiện a[ip]≠x sai
Bài tập
Dễ dàng ñối với các lệnh tuần tự và lệnh ñiều
kiện
Khó khăn ñối với lệnh lặp
Xác ñịnh bất biến vòng lặp nói chung là rất phức
tạp
Chứng minh sự ñúng ñắn ñòi hỏi nhiều thời gian
và công sức
Không thể áp dụng ñối với các thuật toán phức
tạp
67
1.
Viết thuật toán tính n! và chứng minh nó ñúng ñắn.
2.
Thuật toán sau làm gì ? Chứng minh câu trả lời.
begin
m=n
k=0
b[0] = m MOD 2
m = m DIV 2
while (m ≠ 0) do
k=k+1
b[k] = m MOD 2
m = m DIV 2
endwhile
end
68
17
Bài tập
3.
Thuật toán sau làm gì ? Chứng minh câu trả lời.
ðộ phức tạp (3)
// cho b[1..n], ∀i: b[i] = 0 hoặc b[i] = 1
begin
i=n
m = b[i]
while (i > 0) do
i=i–1
m = 2*m + b[i]
endwhile
end
4.
Nguyễn Thanh Bình
Khoa Công nghệ Thông tin
Trường ñại học Bách khoa
ðại học ðà Nẵng
Viết thuật toán tính giá trị trung bình các phần tử của
mảng a[1..n]. Chứng minh thuật toán ñúng ñắn.
69
Nôi dung
ðộ phức tạp
ðộ phức tạp
Khái niệm ñộ phức tạp
ðộ phức tạp: lý thuyết và thực tế
ðánh giá ñộ phức tạp: ba trường hợp
Các hàm tiệm cận
ðộ phức tạp thực tế
ðộ phức tạp của một thuật toán là ño lường số các thao tác cơ
bản mà thuật toán thực hiện trên một bộ dữ liệu vào
Phụ thuộc vào dữ liệu vào
ðộ phức tạp là một hàm phụ thuộc vào kích thước n của bộ dữ
liệu vào
ðộ phức tạp có ý nghĩa khi n lớn
ðánh giá ñộ phức tạp thuật toán nhằm
Nghiên cứu hoạt ñộng của thuật toán
Tối ưu hay không
Phát hiện những phần phức tạp, làm chậm thuật toán
So sánh các giải pháp khác nhau trong cùng ngữ cảnh
vấn ñề
ngôn ngữ
máy tính
71
72
18
thời gian và bộ nhớ
lý thuyết và thực tế
ðánh giá ñộ phức tạp
Hai phương pháp ñánh giá ñộ phức tạp về
mặt thời gian
thời gian thực thi
bộ nhớ sử dụng
thường mâu thuẩn nhau
Phương pháp lý thuyết
Phương pháp thực tế
Chúng ta thường tìm cách giảm ñộ phức tạp về mặt thời
gian
bỏ qua ñộ phức tạp về mặt bộ nhớ
Phương pháp lý thuyết
Dẫn ñến
ñánh giá hoạt ñộng của thuật toán khi kích
thước dữ liệu n rất lớn
hoạt ñộng của thuật toán ñược ñánh giá bởi
các hàm của n
không tính ñến các chi tiết của thuật toán
thường làm tăng ñộ phức tạp về mặt bộ nhớ
làm tăng « ñộ phức tạp trí tuệ » của thuật toán
Thời gian phát triển
Rủi ro xảy ra lỗi
Chi phí bảo trì
73
lý thuyết và thực tế
74
lý thuyết và thực tế
Phương pháp thực tế
Quan hệ giữa phương pháp lý thuyết và phương pháp thực
tế
ðánh giá một cách chi tiết thuật toán
Tất cả các câu lệnh ñều ñược xem xét
ðánh giá riêng rẽ các hoạt ñộng khác nhau
Thường chỉ ñánh giá tập các thao tác cơ bản
thời gian thực thi thuật toán tỷ lệ thuận với số các thao tác này
Ví dụ
phép cộng/trừ số nguyên
phép nhân số nguyên
phép so sánh
thao tác ñọc/ghi
truy cập bộ nhớ
…
Số phép so sánh và trao ñổi dữ liệu ñối với thuật toán sắp xếp
Số các phép cộng và phép nhân ñối với thuật toán nhân hai ma trận
Số các truy cập ñĩa ñối với thuật toán thao tác trên CSDL
Các thao tác cơ bản ñược ñánh giá riêng rẽ
Sự lựa chọn tập các thao tác cơ bản phụ thuộc
Mang lại các kết quả rất chi tiết
kích thước dữ liệu
chi tiết cần ñánh giá
khả năng phân tích
…
nhưng thường phức tạp
thường khó ñể so sánh (do ñánh giá riêng rẽ)
Phát hiện các vùng phức tạp
Hỗ trợ tối ưu chương trình
75
76
19
Tính ñộ phức tạp
Tính ñộ phức tạp
Dựa vào ngữ pháp của thuật toán, chúng ta có
các nguyên tắc tính ñộ phức tạp như sau:
ðối với lời gọi hàm:
Nếu không có hàm ñệ quy, chúng ta luôn có thể tổ
chức sao cho mỗi một hàm gọi hàm khác mà số thao
tác cơ bản của hàm ñó ñã xác ñịnh
Nếu là hàm ñệ quy, tính số các thao tác cơ bản
thường dẫn ñến hệ thức truy hồi
ðối với các thao tác cơ bản là các lệnh tuần tự thì cộng
dồn số các thao tác
ðối với lệnh ñiều kiện, giả sử P(X) là số thao tác cơ bản
của cấu trúc lệnh X, thì:
Ví dụ
function factorial(n)
Thao tác cơ bản: số phép nhân
Begin
If (n = 1) then
C(0) = 0
factorial = 1
C(n) = C(n-1) + 1
Else
factorial = n * factorial (n-1)
Vậy: C(n) = n
EndIf
End
P(if C then I1 else I2) ≤ P(C) + max(P(I1), P(I2))
ðối với các lệnh lặp, số các thao tác cơ bản trong vòng
lặp là ∑P(i), trong ñó i biến ñiều khiển lặp, P(i) số thao
tác cơ bản ở lần lặp thứ i
77
Tính ñộ phức tạp: ba trường hợp
78
Tính ñộ phức tạp: ba trường hợp
ðộ phức tạp phụ thuộc vào dữ liệu sử dụng bởi thuật toán
Dn
: tập dữ liệu kích thước n
CA(d) : ñộ phức tạp của thuật toán A ñối với dữ liệu d của
tập Dn
p(d) : xác xuất xuất hiện của d
Trường hợp tốt nhất
Dữ liệu ñược tổ chức sao cho thuật toán hoạt ñộng hiệu quả
nhất
Giá trị nhỏ nhất của ñộ phức tạp thực tế
Trường hợp xấu nhất
ðộ phức tạp trong trường hợp tốt nhất: CminA(n)
Dữ liệu ñược tổ chức sao cho thuật toán hoạt ñộng kém hiệu
quả nhất
Giá trị lớn nhất của ñộ phức tạp thực tế
CminA(n) = min{CA(d), d∈ Dn}
ðộ phức tạp trong trường hợp xấu nhất: CmaxA(n)
Trường hợp trung bình
CmaxA(n) = max{CA(d), d∈ Dn}
Dữ liệu tương ứng với sự tổ chức ñược xem là trung bình
Không ñơn giản ñể xác ñịnh
Thường có ý nghĩa nhất
Không là trung bình của ñộ phức tạp tốt nhất và dộ phức xấu
nhất
ðộ phức tạp trung bình: CmoyA(n)
CmoyA(n) = ∑ p(d).CA(d)
79
80
20
Tính ñộ phức tạp: ba trường hợp
Tính ñộ phức tạp: ba trường hợp
Nếu xác xuất xuất hiện các dữ liệu là như
nhau, thì
Ví dụ 1: nhân hai ma trận
matrix_product (A, B, C, n)
Begin
For i from 1 to n
For j from 1 to n
C(i,j) = 0
For k from 1 to n
C(i,j) = C(i,j) + A(i,k) * B(k,j)
EndFor
EndFor
EndFor
End
card(Dn) = |Dn|
CmoyA(n) = (1/|Dn|) ∑ CA(d)
ðộ phức tạp trung bình nói chung là
không thể xác ñịnh chính xác
ðiều chắc chắn
CminA(n) ≤ CmoyA(n) ≤ CmaxA(n)
Quan hệ: CminA(n) ? CmoyA(n) ? CmaxA(n)
81
Tính ñộ phức tạp: ba trường hợp
Tính ñộ phức tạp: ba trường hợp
Ví dụ 2: tìm kiếm tuần tự trong một danh sách
function lookup (L, X, n)
Begin
i=1
While ((i ≤ n) and (L(i) ≠ X))
i=i+1
EndWhile
If (i > n) then
i=0
EndIf
lookup = i
End
82
Ví dụ 2: ñộ phức tạp trung bình
q: xác xuất X ở trong danh sách L
X trong L: khả năng xuất hiện tại các vị trí như nhau
Dn,i: tập dữ liệu với X ở vị trí i,
p(Dn,i) = q/n
Dn,0: tập dữ liệu với X không thuộc L, p(Dn,0) = 1-q
CA(Dn,i) = i và CA(Dn,0) = n
Thao tác cơ bản: số các
phép so sánh
n
CmoyA(n)
n
= ∑ p(Dn,i)CA(Dn,i) = (1-q) n + q/n ∑ i
i=0
i=1
= (1-q) n + q(n+1)/2
Trường hợp tốt nhất: L(1) = X, CminA(n) = 1
Trường hợp xấu nhất: X không có trong L hoặc L(n) = X,
CmaxA(n) = n
83
84
21
Tính ñộ phức tạp: ba trường hợp
Các hàm tiệm cận
Ví dụ 2: ñộ phức tạp trung bình
Nếu q = 1 (X thuộc L), thì CmoyA(n) = (n+1)/2
Nếu q = ½ (), thì CmoyA(n) = (3n+1)/4
Trường hợp trung bình
X nằm ở giữa danh sách L, tại vị trí n/2 hoặc (n+1)/2
ñộ phức tạp là n/2 hoặc (n+1)/2
Trong trường hợp tổng quát, chúng ta thường
không tính ñộ phức tạp chính xác, mà tính ñộ
phức tạp tiệm cận (khi n rất lớn)
Chúng ta xem xét các hàm (asymptotic
notations) theo n và thay ñổi của hàm khi mà n
rất lớn
Các hàm tiệm cận cho phép
ñánh giá ñộ hiệu quả của thuật toán
so sánh hiệu quả của các thuật toán
85
Các hàm tiệm cận
86
Các hàm tiệm cận
Kí hiệu O lớn
Kí hiệu o nhỏ
f = O(g) khi n → ∞ nếu:
f = o(g) khi n → ∞ nếu:
∃c > 0, ∃n0 > 0, 0 ≤ f (n) ≤ cg(n),∀n ≥ n0
∀c > 0, ∃n0 > 0,∀n ≥ n0,0 ≤ f (n) < cg(n)
g(n) là tiệm cận trên của f(n) với một số hằng số c
g(n) là tiệm cận trên của f(n) với mọi hằng số c
f(n) tăng chậm hơn g(n):
Ví dụ
Nếu f = o(g) thì f = O(g)
f (n)
lim
=0
n→ ∞ g ( n)
f(n) không tăng nhanh hơn g(n)
Ví dụ
2n = o(n2)
n2 = o(n4)
2n = O(n2)
2n2 = O(n2), nhưng 2n2 ≠ o(n2)
87
88
22
Các hàm tiệm cận
Các hàm tiệm cận
Kí hiệu Θ
Kí hiệu Θ
ñịnh nghĩa tiệm cận trên và tiện cận dưới của f(n)
f = Θ(g) khi n → ∞ nếu:
c2 g
∃c1 > 0, ∃c2 > 0,∃n0 > 0,0 ≤ c1g(n) ≤ f (n) ≤ c2g(n),∀n ≥ n0
f
c1 g
f(n) và g(n) tăng cùng tốc ñộ (so sánh trong nghĩa ñộ
phức tạp)
Ví dụ
f(n) = n2/2 - 3n = n2(1/2 – 3/n), g(n) = n2
xác ñịnh c1 và c2 sao cho: c1<= 1/2 – 3/n <=c2
Với c2= 1/2, n0 = 12, c1 = 1/2 – 3/12 = 1/4
Vậy n2/2 - 3n =Θ(n2)
Nếu f = Θ(g) thì:
f = O(g)
g = O(f)
89
Các hàm tiệm cận
90
Các hàm tiệm cận
Kí hiệu Ω
Các tính chất
f = Ω(g) khi n → ∞ nếu:
Nếu f = Θ(g) thì f = O(g) và f = Ω(g)
∃c > 0, ∃n0 > 0, 0 ≤ cg(n) ≤ f (n),∀n ≥ n0
Suy ra từ ñịnh nghĩa
Nếu f = Θ(g) thì g = Θ(f)
g(n) là tiệm cận dưới của f(n) với một số hằng số c
Chứng minh
f(n) tăng ít nhất cũng nhanh bằng g(n)
∃( c1 , c2 , n0 ), c1 > 0, c2 > 0, ∀n > n 0 , 0 ≤ c1 g ( n ) ≤ f ( n ) ≤ c2 g ( n )
1
f (n) ≤ g(n)
c2
1
∃(c1 ,n 0 ), c1 > 0, ∀n > n 0 , 0 ≤ g(n) ≤
f (n)
c1
Ví dụ
∃(c 2 ,n 0 ), c 2 > 0, ∀n > n 0 , 0 ≤
n2 = Ω(n)
91
92
23
Các hàm tiệm cận
Các hàm tiệm cận
ðộ phức tạp lý thuyết khi n → ∞
Hàm tương ñương
f ∼ g khi n → ∞ nếu:
lim
f (n )
=1
g (n)
f = o(g)
ñộ phức tạp của f < ñộ phức tạp của g
f(n) và g(n) tăng cùng tốc ñộ (một cách chính xác)
f = O(g)
ñộ phức tạp của f ≤ ñộ phức tạp của g
(theo các hằng số xác ñịnh)
f(n) và g(n) có cùng các giới hạn
f = Θ(g)
ñộ phức tạp của f cùng cở ñộ phức tạp
của g (theo các hằng số xác ñịnh)
Ví dụ
f = Ω (g)
ñộ phức tạp của f ≥ ñộ phức tạp của g
(theo các hằng số xác ñịnh)
f = ∼(g)
ñộ phức tạp của f = ñộ phức tạp của g
n→ ∞
f(n) = n2 - n và g(n) = n2
f(n) ∼ g(n)
93
Các hàm tiệm cận
94
Các hàm tiệm cận
Ví dụ 1
Ví dụ 2
Giả sử CminA(n) = 8n2 + 2n + 1 và CminB(n) = 1000n2 + 10n
+ 2 là các hàm biểu diễn thoài gian thực thi của hai phương
pháp cài ñặt cùng một thuật toán trong trường hợp xấu nhất.
Xác ñịnh O của hai hàm trên.
CminA(n) = 8n2 + 2n + 1
≤ 8n2 + 2n2 + n2 với n ≥ 1
= 11n2
chọn c = 11, n0 = 1, thì CminA(n) = O(n2)
CminB(n) = 1000n2 + 10n + 2
≤ 1000n2 + 10n2 + 2n2 với n ≥ 1
= 1012n2
chọn c = 1012, n0 = 1, thì CminB(n) = O(n2)
Thuật toán: O(n2)
95
Chứng minh rằng ∀k∈N:
Ta có:
∑
Vậy:
∑
Ta có:
∑
Vậy:
∑
i k = θ ( n k +1 )
i k ≤ ∑ n k = n.n k =n k +1
n
i =1
n
n
i =1
n
n
i =1
i =1
∑
i =1
i k = O (n k +1 ) với c =1
n
n
n
n n
n k +1
i k ≥ ∑i = n i k ≥ ∑i = n ( ) k ≥ ( ) k = k +1
2
2 2
2 2
2
n
i =1
i k = Ω(n k +1 ) với c = 1/2k+1
96
24
Các hàm tiệm cận
Hệ thức truy hồi
Như ñã trình bày, tính ñộ phức tạp hàm ñệ quy thường
dẫn ñến hệ thức truy hồi
Các họ hệ thức truy hồi thường gặp
Bài tập
Giả sử hàm f(n) = log (2n + α) ñược ñịnh nghĩa,
chứng minh rằng: f(n) = Θ(log(n))
Truy hồi bậc nhất
tuyến tính:
an
= n an-1 + g(n)
không tuyến tính:
an
= 1/(n+ an-1) + g(n)
hạng ñầu tiên phải có giá trị
Truy hồi bậc hai
tuyến tính:
an
= b an-1 + c an-2 + g(n)
không tuyến tính:
an
= 1/(an-1 + an-2) + g(n)
hai hạng ñầu tiên phải có giá trị
Truy hồi bậc k
tuyến tính:
an = b1 an-1 + b2 an-2 + … + bk an-k + g(n)
tuyến tính thuần nhất hệ số hằng số:
an = b1 an-1 + b2 an-2 + … + bk an-k
không tuyến tính: …
k hạng ñầu tiên phải có giá trị
97
Hệ thức truy hồi
98
Hệ thức truy hồi
Các họ hệ thức truy hồi thường gặp (tiếp)
Truy hồi tuyến tính bậc nhất (1)
Truy hồi hoàn toàn
Dạng hệ số hằng số: an = b an-1 + gn, biết trước a0
tuyến tính:
an = b1 an-1 + b2 an-2 + … + bk an-k + … + + bn-1 a1 + g(n)
không tuyến tính: …
n-1 hạng ñầu tiên phải có giá trị
an
= b an-1 + gn
an-1
= b an-2 + gn-1
an-2
= b an-3 + gn-2
…
a1
= b a0 + g1
______________________
Truy hồi phân hoạch
an = b an/2 + c an/2 + g(n)
hoặc dưới dạng: an = c an/b + g(n), với ñiều kiện n/b
là số nguyên
Nhiều trường hợp, rất phức tạp ñể giải hệ thức truy hồi
ðề cập ñến giải hệ thức
truy hồi tuyến tính bậc nhất
Truy hồi tuyến tính thuần nhất bậc 2 hệ số hằng số
truy hồi phân hoạch
an
= bn a0
+
* với hệ số = b
* với hệ số = b2
* với hệ số = bn-1
n
∑g
i
b n -i
i=1
99
100
25
