Bài giảng Tin học đại cương: Chương 7 - Bài toán và thuật toán
lượt xem 8
download
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.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Tin học đại cương: Chương 7 - Bài toán và thuật toán
- Tin học đại cương Introduction 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ọc
- Chương 7: Bài toán và thuật toán 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 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 3
- Nội dung chính Chƣơ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 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 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 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 sơ đồ chung: AB 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 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 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 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). 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ọ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 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 9
- Giải bài toán trên máy tính nhƣ 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ên mộ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. He học khác tuân theo. Từ algorithm ra đời dựa was born around 780, in either Khwarizm or Baghdad, and died theo cách phiên âm tên của ông. around 850. Bản quyền: Khoa CNTT 2011 11
- Khái niệm thuật toán Thuật toán là khái niệm cơ sở của toán học và tin học Thuật toán là một dãy các chỉ thị rõ ràng và có thể thi hành được để hƣớng dẫn thực hiện hành động nhằm đạt đƣợc mục tiêu đặt ra Thuật toán là sự thể hiện của một phương pháp để giải quyết vấn đề Bản quyền: Khoa CNTT 2011 12
- Lƣu ý Cùng một bài toán có thể có nhiều thuật toán khác nhau để giải Thuật toán đơn giản, dễ hiểu, có độ chính xác cao, đƣợc bảo đảm về mặt toán học, dễ triển khai trên máy, thời gian thao tác ngắn, đƣợc gọi là thuật toán tối ưu Nghiên cứu thuật toán là một trong những vấn đề quan trọng của tin học Lý thuyết về thuật toán giải quyết một số vấn đề sau: Những bài toán nào giải đƣợc bằng thuật toán, những bài toán nào không giải đƣợc bằng thuật toán Tìm thuật toán tốt nhất, tối ƣu Triển khai thuật toán trên máy tính Bản quyền: Khoa CNTT 2011 13
- Đặc trƣng của thuật toán Nhập (input). Các thuật toán thƣờng có giá trị đầu vào Xuất (output). Từ giá trị vào thuật toán cho ra kết quả. Tính xác định(definiteness). Các bƣớc trong thuật toán phải chính xác rõ ràng. Tính hữu hạn(finiteness). Thuật toán phải cho ra lời giải (hay kết quả) sau một số bƣớc hữu hạn. Tính hiệu quả(Effectiveness). Tính hiệu quả đƣợc đánh giá dựa trên một số tiêu chuẩn nhƣ khối lƣợng tính toán, không gian và thời gian sử dụng (khi thực hiện thuật toán trên máy tính). Tính tổng quát(Generalliness) Thuật toán phải áp dụng đƣợc cho tất cả các bài toán cùng dạng, chứ không chỉ áp dụng đƣợc cho một số trƣờng hợp riêng lẻ nào đó. 14 Bản quyền: Khoa CNTT 2011
- Ví dụ về thuật toán giải phƣơng trình bậc nhất Bƣớc 1 : Nhập a, b. Bƣớc 2 : Nếu a = 0 thì B2.1: Nếu b=0 thì thông báo pt vô số nghiệm rồi qua bƣớc 5 B2.2: Nếu b khác 0 thì thông báo pt vô nghiệm rồi qua bƣớc 5 Bƣớc 3 : Gán cho x giá trị -b/a, rồi qua bƣớc 4. Bƣớc 4: Xuất ra giá trị x rồi qua bƣớc 5 Bƣớc 5 : Kết thúc. Bản quyền: Khoa CNTT 2011 15
- Cấu trúc cơ bản của thuật toán Tuần tự: thực hiện hết lệnh này đến lệnh khác Rẽ nhánh: tùy theo dữ liệu đầu vào mà ta quyết định thực hiện câu lệnh gì tiếp theo Lặp: thực hiện lại nhiều lần một số câu lệnh nào đó cho đến khi điều kiện không còn thỏa mãn nữa Bản quyền: Khoa CNTT 2011 16
- Các phƣơng pháp biễu diễn thuật toán Ngôn ngữ tự nhiên Lƣu đồ - sơ đồ khối Mã giả Bản quyền: Khoa CNTT 2011 17
- Biểu diễn thuật toán bằng phƣơng pháp ngôn ngữ tự nhiên Liệt kê các thao tác, các chỉ thị bằng ngôn ngữ tự nhiên Ví dụ: Có 43 que diêm. Hai ngƣời chơi luân phiên bốc diêm. Mỗi lƣợt, mỗi ngƣời bốc từ 1 đến 3 que diêm. Ngƣời nào bốc cuối cùng sẽ thắng cuộc Giải thuật để ngƣời đi trƣớc luôn thắng cuộc đƣợc diễn tả bằng cách liệt kê từng bƣớc nhƣ sau: Bước 1: Bốc 3 que rồi đợi đối phƣơng đi Bước 2: Đối phƣơng bốc (giả sử x que, 0
- Biễu diễn thuật toán bằng phƣơng pháp lƣu đồ (lowchart) Là một phƣơng tiện hình học giúp ta diễn tả giải thuật một cách trực quan Đƣợc tạo bởi các kiểu khối cơ bản, nối với nhau bằng các đƣờng có hƣớng Thuật ngữ tiếng Anh là Flow Chart Bản quyền: Khoa CNTT 2011 19
- Các ký hiệu cơ bản trong phƣơng pháp lƣu đồ bắt đầu điều kiện kết thúc nhập thao tác hoặc xuất chƣơng trình con hƣớng xử lý Bản quyền: Khoa CNTT 2011 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng tin học đại cương - trường ĐH Tôn Đức Thắng
175 p | 1024 | 287
-
Bài giảng Tin học đại cương - Chương 1: Các vấn đề cơ bản về CNTT
167 p | 417 | 31
-
Bài giảng Tin học đại cương: Bài 1 - ĐH Bách khoa Hà Nội
33 p | 263 | 21
-
Bài giảng Tin học đại cương: Bài 4 - ĐH Bách khoa Hà Nội
8 p | 155 | 13
-
Bài giảng Tin học đại cương: Chương 2 - Tin học và công nghệ thông tin
12 p | 183 | 10
-
Bài giảng Tin học đại cương: Bài 3 - ĐH Bách khoa Hà Nội
14 p | 143 | 8
-
Bài giảng Tin học đại cương - Nguyễn Vũ Duy
95 p | 43 | 8
-
Bài giảng Tin học đại cương: Phần 1 - ThS. Phạm Thanh Bình
18 p | 93 | 6
-
Bài giảng Tin học đại cương: Chương 1 - Đại cương về tin học
16 p | 124 | 5
-
Bài giảng Tin học đại cương: Chương 1 - Thông tin
29 p | 150 | 5
-
Bài giảng Tin học đại cương: MS Excel - ThS. Ngô Cao Định
31 p | 11 | 4
-
Bài giảng Tin học đại cương: Tổng quan về máy tính - ThS. Ngô Cao Định
38 p | 13 | 4
-
Bài giảng Tin học đại cương: Biểu diễn và xử lý thông tin - ThS. Ngô Cao Định
56 p | 7 | 3
-
Bài giảng Tin học đại cương: Mạng và Internet - ThS. Ngô Cao Định
55 p | 9 | 3
-
Bài giảng Tin học đại cương: Hệ điều hành - ThS. Ngô Cao Định
86 p | 6 | 2
-
Bài giảng Tin học đại cương: Chương 1 - Trần Quang Hải Bằng (ĐH giao thông Vận tải)
31 p | 80 | 2
-
Bài giảng Tin học đại cương: Bài 13 - Bùi Thị Thu Cúc
10 p | 77 | 2
-
Bài giảng Tin học đại cương: Tổng quan về cơ sở dữ liệu - ThS. Ngô Cao Định
11 p | 7 | 2
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn