Bài giảng Phân tích và thiết kế giải thuật - Chương 1: Các khái niệm căn bản

Môn học:

Phân tích và Thiết kế Giải thuật

Số tín chỉ: 3

BÀI GIẢNG ĐIỆN TỬ

Biên soạn bởi: PGS.TS. Dương Tuấn Anh

Khoa Khoa Học và Kỹ Thuật Máy Tính

Trường Đ.H. Bách Khoa

Đại học Quốc Gia Tp Hồ Chí Minh

1

Tài liệu tham khảo

[1] Cormen, T. H., Leiserson, C. E, and Rivest, R. L.,

Introduction to Algorithms, The MIT Press, 1997.

[2] Levitin, A., Introduction to the Design and Analysis

of Algorithms, Addison Wesley, 2003

[3] Sedgewick, R., Algorithms in C++, Addison-

Wesley, 1998

[4] Weiss, M.A., Data Structures and Algorithm

Analysis in C, TheBenjamin/Cummings Publishing,

1993

2

Đề cương Môn học

1. Các khái niệm căn bản

2. Chiến lược chia-để-trị

3. Chiến lược giảm-để-trị

4. Chiến lược biến thể-để-trị

5. Qui hoạch động và giải thuật tham lam

6. Giải thuật quay lui

7. Vấn đề NP-đầy đủ

8. Giải thuật xấp xỉ

3

Môn học: Phân tích và thiết kế giải thuật

Chương 1

CÁC KHÁI NIỆM CĂN BẢN

4

Nội dung

1. Đệ quy và hệ thức truy hồi

2. Phân tích độ phức tạp giải thuật

3. Phân tích giải thuật lặp

4. Phân tích giải thuật đệ quy

5. Chiến lược thiết kế giải thuật

6. Thiết kế giải thuật kiểu “trực tiếp” (bruce-force)

5

1. Đệ quy

Hệ thức truy hồi

Thí dụ 1: Hàm tính giai thừa

N! = N.(N-1)!

với N ≥ 1

0! = 1

Những định nghĩa hàm đệ quy mà chứa những đối số nguyên

được gọi là những hệ thức truy hồi (recurrence relation).

function factorial (N: integer): integer;

begin

if N = 0

then factorial: = 1

else factorial: = N*factorial (N-1);

end;

6

Hệ thức truy hồi

Thí dụ 2: Số Fibonacci

Hệ thức truy hồi:

F_N= F_N-1+ F_N-2

for N ≥ 2

F₀= F₁= 1

1, 1, 2, 3, 5, 8, 13, 21, …

function fibonacci (N: integer): integer;

begin

if N <= 1

then fibonacci: = 1

else fibonacci: = fibonacci(N-1) +

fibonacci(N-2);

end;

7

Số Fibonacci – Cây đệ quy

computed

Có nhiều tính toán dư thừa

khi tính số Fibonacci bằng

hàm đệ quy.

8

Một cách khác: Ta có thể dùng một mảng để chứa những trị số

đi trước trong khi tính hàm fibonacci. Ta có một giải thuật

không đệ quy.

procedure fibonacci;

const max = 25;

var i: integer;

F: array [0..max] of integer;

begin

Giải thuật không đệ quy

thường làm việc hữu hiệu

và dễ kiểm soát hơn 1 giải

thuật đệ quy.

Nhờ vào sử dụng stack, ta

có thể chuyển đổi một giải

thuật đệ quy thành một giải

thuật lặp tương đương.

F[0]: = 1; F[1]: = 1;

for i: = 2 to max do

F[i]: = F[i-1] + F[i-2]

end;

9

2. Phân tích độ phức tạp giải thuật

Với phần lớn các bài toán, thường có nhiều giải thuật khác

nhau để giải một bài toán.

Làm cách nào để chọn giải thuật tốt nhất để giải một bài

toán?

Làm cách nào để so sánh các giải thuật cùng giải được một

bài toán?

Phân tích độ phức tạp của một giải thuật: dự đoán các tài

nguyên mà giải thuật đó cần.

Tài nguyên: Chỗ bộ nhớ

Thời gian tính toán

Thời gian tính toán là tài nguyên quan trọng nhất.

10

Hai cách phân tích

Thời gian tính toán của một giải thuật thường là

một hàm của kích thước dữ liệu nhập.

Chúng ta quan tâm đến:

•

Trường hợp trung bình (average case): thời gian

tính toán mà một giải thuật cần đối với một “dữ

liệu nhâp thông thường” (typical input data).

Trường hợp xấu nhất (worst case): thời gian tính

toán mà một giải thuật cần đối với một “dữ liệu

nhâp xấu nhất”

11

Khung thức của sự phân tích

♦ Bước 1: Đặc trưng hóa dữ liệu nhập và quyết định kiểu

phân tích thích hợp.

Thông thường, ta tập trung vào việc

- chứng minh rằng thời gian tính toán luôn nhỏ hơn một “cận

trên” (upper bound), hay

- dẫn xuất ra thời gian chạy trung bình đối với một dữ liệu

nhập ngẫu nhiên.

♦ Bước 2: nhận dạng thao tác trừu tượng (abstract operation)

mà giải thuật dựa vào đó làm việc.

Thí dụ: thao tác so sánh trong giải thuật sắp thứ tự.

Tổng số thao tác trừu tượng thường tùy thuộc vào một vài đại

lượng.

♦ Bước 3: thực hiện phân tích toán học để tìm ra các giá trị

trung bình và giá trị xấu nhất của các đại lượng quan trọng.

12

Hai trường hợp phân tích

•

Thường thì không khó để tìm ra cận trên của thời

gian tính toán của một giải thuật.

Nhưng phân tích trường hợp trung bình thường đòi

hỏi một sự phân tích toán học cầu kỳ, phức tạp.

Về nguyên tắc, một giải thuật có thể được phân tích

đến một mức độ chính xác rất chi li. Nhưng trong

thực tế, chúng ta thường chỉ tính ước lượng

(estimating) mà thôi

•

Tóm lại, chúng ta tìm kiếm một ước lượng thô về thời

gian tính toán của một giải thuật (nhằm mục đích

phân lớp độ phức tạp).

13

Phân lớp độ phức tạp

Hầu hết các giải thuật thường có một thông số chính, N, số

mẩu dữ liệu nhập mà được xử lý.

Thí dụ:

Kích thước của mảng (array) được sắp thứ tự hoặc tìm kiếm.

Số nút của một đồ thị.

Giải thuật có thể có thời gian tính toán tỉ lệ với

1. Nếu tác vụ chính được thực thi một vài lần.

thời gian tính toán là hằng số.

2. lgN (logarithmic)

log₂N ≡ lgN

Giải thuật tăng chậm hơn sự tăng của N.

14

3. N (linear)

4. NlgN

5. N²(quadratic) khi giải thuật là vòng lặp lồng hai

6. N³(cubic)

7. 2^N

khi giải thuật là vòng lặp lồng ba

một số giải thuật có thời gian chạy luỹ thừa.

Một vài giải thuật khác có thể có thời gian chạy

N^3/2, N^1/2, (lgN)²…

15

16

Độ phức tạp tính toán

Chúng ta tập trung vào phân tích trường hợp xấu nhất. Khi

phân tích, bỏ qua những thừa số hằng số để xác định sự phụ

thuộc hàm của thời gian tính toán đối với kích thước dữ liệu

nhập.

Thí dụ: Thời gian tính toán của sắp thứ tự bằng phương pháp

trộn (mergesort ) là tỉ lệ với NlgN.

Khái niệm “tỉ lệ với” (proportional to)

Công cụ toán học để làm chính xác khái niệm này là

ký hiệu – O (O-notation).

Định nghĩa: Một hàm g(N) được gọi là O(f(N)) nếu tồn tại hai

hằng số c₀và N₀sao cho g(N) nhỏ hơn c₀f(N) với mọi

N > N₀.

17

Ký hiệu O

Ký hiệu O là một cách hữu ích để phát biểu cận trên về thời

gian tính toán mà độc lập đối với đặc tính dữ liệu nhập và

chi tiết hiện thực hóa.

Chúng ta cố gắng tìm cả “cận trên” lẫn “cận dưới” của thời

gian tính toán trong phân tích trường hợp xấu nhất.

Nhưng cận dưới (lower-bound ) thì thường khó xác định.

18

Phân tích trường hợp trung bình

Với kiểu phân tích này, ta phải

- đặc trưng hóa dữ liệu nhập của giải thuật

- tính giá trị trung bình của số lần một phát biểu được

thực thi.

- tính thời gian tính toán trung bình của toàn giải

thuật.

Nhưng thường thì khó

- xác định thời gian chạy của mỗi phát biểu.

- đặc trưng hóa chính xác dữ liệu nhập trong thực tế.

19

Các kết quả tiệm cận và xấp xỉ

Kết quả của một sự phân tích toán học thường mang tính xấp

xỉ (approximate): nó có thể là một biểu thức gồm một chuỗi

những số hạng giảm dần tầm quan trọng.

Ta thường để ý đến các số hạng dẫn đầu trong biểu thức toán

học.

Thí dụ: Thời gian tính toán trung bình của một chương trình

là:

a₀NlgN + a₁N + a₂

Ta có thể viết lại là:

a₀NlgN + O(N)

Với N lớn, ta không cần tìm giá trị của a₁hay a₂.

20

Bài giảng Phân tích và thiết kế giải thuật - Chương 1: Các khái niệm căn bản - Dương Tuấn Anh