tailieunhanh - Bài giảng Tin học đại cương: Chương 3 - Trần Quang Hải Bằng

Nội dung trình bày trong chương 3 Lý thuyết thuật toán nằm trong bài giảng tin học đại cương nhằm trình bày về khái niệm thuật toán, chương trình máy tính, ngôn ngữ lập trình, tính chất của thuật toán, các cách biểu diễn của thuật toán. | TIN HỌC ĐẠI CƯƠNG Chương 3 Lý thuyết thuật toán bangtqh@ Nội dung 1. Khái niệm thuật toán. 2. Chương trình máy tính ngôn ngữ lập trình. 3. Tính chất của thuật toán. 4. Các cách biểu diễn thuật toán. 5. Thiết kế và phân tích thuật toán. 6. Đệ quy và thuật toán đệ quy. 7. Một số bài toán tìm kiếm sắp xếp đơn giản. 8. Bài tập. bangtqh@ Tin học đại cương - Chương 3 2 Thuật toán là gì Thuật toán thuật giải hay giải thuật đều dùng để chỉ một thuật ngữ tiếng Anh có tên là ALGORITHM. Chúng ta sẽ tìm hiểu q Thuật toán theo cách hiểu thông thường q Các thao tác trong thuật toán q Định nghĩa thuật toán trong tin học bangtqh@ B R rgB ffl raHflH lnugg ng 3 3 Thuật toán - cách hiểu thông thường q Bất cứ công yêu cầu gì cũng cần phải được giải quyết một cách khoa học Theo nghĩa rộng khái niệm thuật toán algorithm được sử dụng ở mọi nơi không riêng gì trong lĩnh vực tin học. q Theo cách hiểu thông tường Thuật toán là một loạt các thao tác operation có thứ tự order nhằm giải quyết một yêu cầu nào đó. q Ví dụ Thuật toán nấu cơm - Bước 0 Ước lượng gạo cần thiết - Bước 1 Vo gạo - Bước 2 Cho gạo và nước thích hợp vào nồi cơm điện NCĐ - Bước 3 Cắm điện chuyển chế độ cook - Bước 4 Chờ đến khi NCĐ chuyển sang chế độ warm - Bước 5 Chờ thêm 10 phút nữa - Bước 6 Cơm chín kết thúc. bangtqh@ Tin học đại cương - Chương 3 4 Trò chơi 5 quân bài q Chọn 5 quân bài ngẫu nhiên trong bộ bài 52 quân. q Yêu cầu Hãy tìm ra quân bài lớn nhất trong số các quân bài hiện có. - Mỗi lần chỉ được lật 1 quân bài trong số 5 quân. - Ghi lại quá trình tìm kiếm theo mỗi bước Tin học đại cương - Chương 3 bangtqh@ 5 Trò chơi 5 quân bài . Quân bài lớn nhất là bangtqh@ Tin học đại cương - Chương 3