Bài giảng Tin học đại cương: Chương 7 - Trường ĐH Sư phạm TP. Hồ Chí Minh

Bài giảng Tin học đại cương: Chương 7 Bài toán và thuật toán, cung cấp cho người học những kiến thức như: 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 - Trường ĐH Sư phạm TP. Hồ Chí Minh Tin học đại cương Introduction to Information Technology IT -F P Nhóm biên soạn HP. Tin Học Đại Cương U Khoa Công Nghệ Thông Tin M Trường ĐHSP TP. Hồ Chí Minh C H Bộ môn Kĩ Thuật Dạy Học Chương 7: Bài toán và thuật toán IT -F P U M C H Bản quyền: Khoa CNTT 2011 2 Giớ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 IT 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 -F 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 P chƣơng trình ứng dụng phù hợp. U M  Đó cũng chính là mục tiêu của chƣơng này nhằm cung C cấp các khái niệm ban đâu về bài toán và thuật toán . H Đô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 3 Nội dung chính Chƣơng 7: Bài toán và thuật toán IT  Khái niệm vấn đề và bài toán. -F  Thuật toán và các phương pháp biểu diễn thuật toán. P U  Các bước để giải một bài toán trên máy tính. M  Chuyển đổi bài toán thành chương trình máy tính. C H Bản quyền: Khoa CNTT 2011 4 Khá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 IT nhiều đến tính toán -F  Pitago chia mọi vấn đề mà con ngƣời cần giải quyết thành hai loại: P Theorema: vấn đề cần khẳng định tính đúng – sai U Problema: vấn đề cần tìm giải pháp để để đạt đƣợc mục M tiêu từ những điều kiện ban đầu nào đó C H Bản quyền: Khoa CNTT 2011 5 Khá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 IT sơ đồ chung: -F AB  Trong đó: P A có thể là giả thiết, điều kiện ban đầu U B có thể là kết luận, mục tiêu cần đạt M  là suy luận, giải pháp cần xác định C H Bản quyền: Khoa CNTT 2011 6 Ví dụ về vấn đề - bài toán 1. Bài toán kiểm tra tính nguyên tố  Điều kiện ban đầu: Số nguyên dƣơng N IT  Mục tiêu cần đạt: N có là số nguyên tố hay không? -F 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 P trƣờng U  Mục tiêu cần đạt: Bảng thống kê, phân loại sinh viên theo M kết quả học tập C H Bản quyền: Khoa CNTT 2011 7 Bà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). IT  Ví dụ: -F  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. P  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 U M … C H Tất cả là bài toán trong tin học Là vấn đề mà ta muốn máy tính thực hiện để từ dữ liệu vào (Input) ta nhân được dữ liệu – thông tin ra cần thiết (output) Bản quyền: Khoa CNTT 2011 8 Ví 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 IT  Input: Hai số nguyên M,N -F  Output: ƢCLN 2. Bài toán xếp thời khóa biểu cho trƣờng học P  Input: Tên giáo viên, môn dạy U  Output: TKB của trƣờng M 3. Bài toán tìm điểm thi đại học của thí sinh C  Input: Số báo danh H  Output: Điểm thi Bản quyền: Khoa CNTT 2011 9 Giải bài toán trên máy tính nhƣ thế nào? Bài toán IT Input Output Bằng cách nào ? -F P Giải bài toán U M C Hướng dẫn các thao tác cho máy thực hiện H Thuật toán Bản quyền: Khoa CNTT 2011 ...