Bài giảng Tin học đại cương: Chương 7 - Bài toán và thuật toán

Bài giảng Tin học đại cương: Chương 7 - Bài toán và thuật toán được biên soạn nhằm cung cấp cho các bạn những kiễn thức về khái niệm vấn đề và bài toán; thuật toán và các phương pháp biểu diễn thuật toán; các bước để giải một bài toán trên máy tính; chuyển đổi bài toán thành chương trình máy tính.
Nội dung trích xuất từ tài liệu:
Bài giảng Tin học đại cương: Chương 7 - Bài toán và thuật toánTin học đại cươngIntroduction to Information Technology Nhóm biên soạn HP. Tin Học Đại Cương Khoa Công Nghệ Thông Tin Trường ĐHSP TP. Hồ Chí Minh Bộ môn Kĩ Thuật Dạy HọcChương 7: Bài toán và thuật toán Bản quyền: Khoa CNTT 2011 2Giới thiệu Trong xu hướng phát triển của xã hội, công nghệ thông tin ngày càng đóng một vai trò rất quan trong giúp mọi người có thể hoàn thành công việc của mình trở nên nhanh chóng, hiệu quả và dễ dàng hơn thông qua các chương trình ứng dụng trên máy tính. Thuật toán và thuật giải là nền tảng để những lập trình viên có thể xây dựng những chương trình ứng dụng phù hợp. Đó cũng chính là mục tiêu của chương này nhằm cung cấp các khái niệm ban đâu về bài toán và thuật toán . Đông thời đưa ra qui trình cơ bản để giải quyết 1 bài toán trên máy tính như thế nào? Bản quyền: Khoa CNTT 2011 3Nội dung chínhChương 7: Bài toán và thuật toán Khái niệm vấn đề và bài toán. Thuật toán và các phương pháp biểu diễn thuật toán. Các bước để giải một bài toán trên máy tính. Chuyển đổi bài toán thành chương trình máy tính. Bản quyền: Khoa CNTT 2011 4Khái niệm vấn đề Vấn đề thường được dùng với nghĩa rộng hơn bài toán, bài toán là vấn đề mà để giải quyết nó phải liên quan ít nhiều đến tính toán Pitago chia mọi vấn đề mà con người cần giải quyết thành hai loại: Theorema: vấn đề cần khẳng định tính đúng – sai Problema: vấn đề cần tìm giải pháp để để đạt được mục tiêu từ những điều kiện ban đầu nào đó Bản quyền: Khoa CNTT 2011 5Khái niệm vấn đề (tt) Theo nhiều kết quả nghiên cứu: việc giải quyết vấn đề - bài toán mà Pitago nêu ra đều có thể diễn ra theo một sơ đồ chung: AB Trong đó: A có thể là giả thiết, điều kiện ban đầu B có thể là kết luận, mục tiêu cần đạt  là suy luận, giải pháp cần xác định Bản quyền: Khoa CNTT 2011 6Ví dụ về vấn đề - bài toán1. Bài toán kiểm tra tính nguyên tố  Điều kiện ban đầu: Số nguyên dương N  Mục tiêu cần đạt: N có là số nguyên tố hay không?2. Bài toán quản lý hồ sơ sinh viên  Điều kiện ban đầu: Hồ sơ gốc của các sinh viên trong trường  Mục tiêu cần đạt: Bảng thống kê, phân loại sinh viên theo kết quả học tập Bản quyền: Khoa CNTT 2011 7Bài toán trong tin học? Trong thực tế, không phải vấn đề nào cũng có thể là những bài toán có tính toán (bài toán của toán học). Ví dụ:  Làm sao giao dịch ngân hàng tự động không cần nhân viên  Làm sao để con người nói chuyện được với nhau mà không cần phải gặp mặt nhau.  Làm sao để xếp loại học sinh của trường học có 3000 học sinh một cách nhanh chóng … Tất cả là bài toán trong tin họcLà vấn đề mà ta muốn máy tính thực hiện để từ dữ liệu vào (Input) tanhân được dữ liệu – thông tin ra cần thiết (output) Bản quyền: Khoa CNTT 2011 8Ví dụ bài toán trong tin học 1. Bài toán tìm ước chung lớn nhất của hai số nguyên dương M,N  Input: Hai số nguyên M,N  Output: ƢCLN 2. Bài toán xếp thời khóa biểu cho trường học  Input: Tên giáo viên, môn dạy  Output: TKB của trường 3. Bài toán tìm điểm thi đại học của thí sinh  Input: Số báo danh  Output: Điểm thi Bản quyền: Khoa CNTT 2011 9Giải bài toán trên máy tínhnhư thế nào? Bài toán Input Output Bằng cách nào ? Giải bài toán Hướng dẫn các thao tác cho máy thực hiện Thuật toán Bản quyền: Khoa CNTT 2011 10 Thuật toán là gì?(Trích từ Wikipedia)Từ thuật toán (Algorithm) xuất phát từ tênmột nhà toán học người Trung Á làMuhammad ibn Musa al-Khwarizmi,thường gọi là al’Khwarizmi. Ông là tác giảmột cuốn sách về số học, trong đó ông đãdùng phương pháp mô tả rất rõ ràng, mạch lạc Muḥammad ibn Mūsā al-cách giải những bài toán. Sau này, phương Khwārizmī (Arabic: ‫محمد بن‬pháp mô tả cách giải toán của ông đã được ‫ ) موسى الخوارزمي‬was a Persian mathematician, astronomer,xem là một chuẩn mực và được nhiều nhà toán astrologer and geographer. Hehọc khác tuân theo. Từ algorithm ra đời dựa was born around 780, in either Khwarizm or Baghdad, and diedtheo cách phiên âm tên của ông. around 850. Bản ...