Xem mẫu
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
1
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
2
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)
3
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
n
Dãy số học i n (n 1) (n 2) ... 2 1 0
i 0
n(n 1)
2
n Dãy hình học xi
i 0
xn 1 1
x1
if x 1
xi
i 0
1
1x if |x| < 1
4
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”
Input Algorithm Output
Ví dụ:
input: Dãy số.
output: Dãy số đã được sắp xếp thứ tự. 5
...
- tailieumienphi.vn
nguon tai.lieu . vn