Chương 4. Giải thuật xử lý thông
tin và ngôn ngữ lập trình
HỌC VIỆN KTQS
KHOA CÔNG NGHỆ THÔNG TIN
H c ph n: L P TRÌNH C B Nọ ầ Ậ Ơ Ả
Tài li u tham kh o ệ ả
Giải thuật xử lý thông tin và ngôn ngữ lập trình2
Giáo trình tin h c c s , H S Đàm, Đào Ki n Qu c, ọ ơ ở ồ ỹ ế ố
H Đc Ph ng. Đi h c S ph m, 2004 – Ch ng 7, ồ ắ ươ ạ ọ ư ạ ươ
9.
N I DUNGỘ
Khái ni m bài toán và gi i thu t ệ ả ậ
Đc tr ng (yêu c u) c a gi i thu tặ ư ầ ủ ả ậ
Các ph ng pháp di n đt gi i thu tươ ễ ạ ả ậ
S l c v đánh giá gi i thu tơ ượ ề ả ậ
Ngôn ng l p trình và các m c khác nhau c a ngôn ng ữ ậ ứ ủ ữ
l p trìnhậ
Quá trình th c hi n ch ng trình trên ngôn ng b c caoự ệ ươ ữ ậ
3 Giải thuật xử lý thông tin và ngôn ngữ lập trình
KHÁI NI M BÀI TOÁNỆ
Cho số tự
nhiên n
n có phải số
nguyên tố hay
không
“có” hay
“không”
Cho hồ sơ
điểm sinh viên
Tìm tất cả các sinh
viên có điểm trung
bình trên 8
Danh sách sv
thoả mãn
Thiết kế hình
học, tải trọng
Tính sức bền Độ bền
Input Yêu cầu Output
Cho một bài toán nghĩa là cho input,
và yêu cầu để tìm (tính) ra output
4 Giải thuật xử lý thông tin và ngôn ngữ lập trình
KHÁI NI M THU T TOÁNỆ Ậ
Thu t toán (algorithm) là m t quá trình g m m t dãy h u h n các ậ ộ ồ ộ ữ ạ
thao tác có th th c hi n đc s p x p theo m t trình t xác đnh ể ự ệ ượ ắ ế ộ ự ị
dùng đ gi i m t bài toán ể ả ộ
Ví d : thu t toán Euclid tìm c s chung l n nh t c a hai s t ụ ậ ướ ố ớ ấ ủ ố ự
nhiên. Thay vì ph i tính toán theo đnh nghĩa ch làm rõ c u trúc c a ả ị ỉ ấ ủ
USCLN (tích c a các c s chung v i s mũ nh nh t) thu t toán ủ ướ ố ớ ố ỏ ấ ậ
Euclid d a trên các tính ch t sau:ự ấ
USCLN(a,b) = USCLN (b,a))
Nếu a> b, USCLN(a,b) = USCLN (a-b,b)
USCLN(a,a)= a
5 Giải thuật xử lý thông tin và ngôn ngữ lập trình