1
PHÂN TÍCH VÀ
THIẾT KẾ GIẢI THUẬT
ANALYS AND DESIGN
ALGORITHMS
1
2
Mục tiêu môn học

Cung c p ki n th c và k năng trong ấ ế ứ ỹ
vi c phân tích đ ph c t p tính toán ệ ộ ứ ạ
c a gi i thu t.ủ ả ậ

Tìm hi u các chi n thu t thi t k gi i ể ế ậ ế ế ả
thu tậ
2
3
Nội dung môn học
3
TT Nội dung
Số
tiết
Phân bổ thời gian
Ghi
chú
Lý
thuyết
Bài
Tập
Tự
học

2. Kiểm tra cuối kỳ: Tự luận
3. Bài tập lớn: làm các bài tập
4. Điểm Đề tài < 4  không được thi kết thúc môn  học lại
5. Thi kết thúc môn: Tự luận
6. Kiểm tra thường kỳ
4
5
Tài liệu học tập

Giáo trình:

[1] Cormen, T. H., Leiserson, C. E, and Rivest,
Introduction to Algorithms, The MIT Press,
1997.

Tham khảo:

[2] Sedgewick, Algorithms in C++, Addison-
Wesley, 1998

[3] Weiss, M.A, Data Structures and Algorithm
Analysis in C , The Benjamin/Cummings
Publishing, 1993
5
6
Nhắc nhở một số quy định

Đi học đúng giờ

Đeo thẻ SV

Thuật ngữ và Khái Niệm

Các định nghĩa về độ phức tạp

Kỹ thuật chia-để-trị và giải thuật đệ quy

Phương trình truy hồi và cách giải phương
trình truy hồi

Vài thí dụ minh hoạ về phân tích độ phức tạp
giải thuật
9

10
Thuật ngữ và khái niệm

Cấu trúc dữ liệu

Thuật toán

Độ phức tạp của thuật toán
10

11
Cấu trúc dữ liệu

(1) Sự tổ chức hợp lý của các thành phần dữ liệu,

(2) Tập các thao tác để truy cập các thành phần dữ liệu.



Giải thuật hay thuật toán là dãy các thao tác xác
Giải thuật hay thuật toán là dãy các thao tác xác
định nhằm giải một bài toán nào đó.
định nhằm giải một bài toán nào đó.

Ví dụ: Tính tổng các số nguyên lẻ từ 1n
Input: Số nguyên n
Output: Tổng các số nguyên lẻ từ 1n

B1: S=0

B2: i=1

B3: Nếu i>n thì sang B7, ngược lại sang B4

B4: S=S+i

B5: i=i+2

B6: Quay lại B3

B7: Tổng cần tìm là S
13
14
Các đặc trưng của Thuật toán

INPUT: Có các bộ dữ liệu đầu vào thuộc một tập
hợp dữ liệu nào đó.


ngôn ngữ tựa PASCAL;

Ngôn ngữ lập trình cấp cao (High programming
languages) như Pascal, C/C++ vv
16
17
Các phương pháp biểu diễn giải thuật
Các phương pháp biểu diễn giải thuật
Ví dụ: Tìm x trong dãy a1, a2, , an

Đầu vào: Số x, dãy n số a1, a2, , an

Đầu ra: Một giá trị logic true hoặc false

Search(x, a, n)

1 for i ←1 to n

2 do if ai= x

then return true

4 return false
17
18

Cấu trúc dữ liệu

Thuật toán



Thời gian tối thiểu để thực hiện giải thuật với
mọi kích thước đầu vào n gọi là thời gian chạy
tốt nhất(best-case)của giải thuật

Thời gian nhiều nhất để thực hiện giải thuật với
mọi kích thước đầu vào n được gọi là thời gian
chạy xấu nhất (worst-case) của giải thuật

Thời gian trung bình để thực hiện giải thuật với
mọi kích thước đầu vào n được gọi là thời gian
chạy trung bình (average case) của giải thuật
21
Độ phức tạp thời gian của thuật toán
22

Ví dụ Đánh giá độ phức tạp về thời gian của
giải thuật

Search(x, a, n)

1 for i ←1 to n

2 do if ai= x

3 then return true

4 return false
22
Độ phức tạp thời gian của thuật toán

♦
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.