1
Chương 1:
Các phương pháp phân tích thuật
toán
Trịnh Huy Hoàng
Khoa Công nghệ thông tin
Đại học Sư phạm TPHCM
2
Nội dung
Một số kiến thức Toán cần thiết
Thuật toán là gì?
Vai trò của phân tích thuật toán
Các phương pháp phân tích thuật toán
Bộ khung cho quá trình phân tích thuật toán
–Mã giả
–RAM
–Thời gian thực hiện chương trình
–Độ phức tạp của chương trình
3
Một số kỹ thuật Toán học thường
dùng
Chứng minh qui nạp
–Chứng minh mệnh đề đúng với trường hợp đầu
tiên (n=n0)
–Giả sử mệnh đề đúng đến trường hợp thứ k (n=k)
–Chứng minh mệnh đề đúng với trường hợp thứ
k+1 (n=k+1)
–Kết luận mệnh đề đúng với mọi trường hợp (mọi
n >= n0)
4
Một số kỹ thuật Toán học thường
dùng (tt)
Các tổng dãy số thường dùng
2
1)n(n
012...2)(n1)(nni
n
0i
Dãy s h cố ọ
x-1
1
x
0i
i
if |x| < 1
1-x
1x
x
1n
n
0i
i
Dãy hình h cọif x 1
5
Thuật toán là gì?
“Thuật toán là một thủ tục tính toán được
định nghĩa rõ ràng để biến đổi các đầu vào
thành các đầu ra nhằm đạt được quan hệ
đầu vào – đầu ra mong muốn”
AlgorithmInput Output
Ví dụ:
input: Dãy số.
output: Dãy số đã được sắp xếp thứ tự.