Bài giảng Tin học đại cương: Chương 4 - Lê Thị Ngọc Thảo
lượt xem 4
download
Bài giảng Tin học đại cương: Chương 4 Chương trình và giải thuật, cung cấp cho người học những kiến thức như Các khái niệm; Các phương pháp biểu diễn; Ngôn ngữ tự nhiên; Lưu đồ - sơ đồ khối; Mã giả. Mời các bạn cùng tham khảo!
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 4 - Lê Thị Ngọc Thảo
- CHƯƠNG 4: CHƯƠNG TRÌNH & GIẢI THUẬT ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 129
- Các khái niệm (1) Thuật toán • Cách hiểu đơn giản • Tập các hướng dẫn thực hiện một công việc. • Tập hữu hạn các hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết được vấn đề. • Một phương pháp thể hiện lời giải của vấn đề. • Algorithm: nhà toán học Trung Á • Muhammad Bin Musa Al-Khwarizmi • http://www2.sjsu.edu/depts/Museum/alkhwa.html ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 130
- Các khái niệm (2) Thuật toán (tt) • Trong khoa học máy tính • Một dãy hữu hạn các bước rõ ràng và thực thi được. • Quá trình hành động theo các bước này phải dừng và cho được kết quả như mong muốn. • Tính xác định • Hướng dẫn giải rõ ràng và đúng • Tính hữu hạn • Số bước hữu hạn và tính chất dừng ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 131
- Các khái niệm (3) Tính mập mờ: • Xem xét thực hiện công việc tìm một môn học nhiều đvht nhất: • Lập danh sách các môn học. • Sắp thứ tự các môn học. • Chọn ra một môn học nhiều đvht. • Kết quả:??? • Câu hỏi:??? ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 132
- Các khái niệm (4) Tính mập mờ (tt): • Vi phạm tính rõ ràng – không mập mờ • Hiểu đúng – Hiểu 1 nghĩa duy nhất • Sửa lại : • 1.Lập danh sách các môn học theo tên, số đvht • 2.Sắp thứ tự các môn học giảm dần theo số đvht • 3.Chọn ra một môn học có nhiều đvht nhất • Câu hỏi??? ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 133
- Các khái niệm (5) Tính mập mờ (tt): • Phân biệt mập mờ và chọn lựa có quyết định. • Mập mờ là thiếu thông tin hoặc có nhiều chọn lựa nhưng không đủ điều kiện để quyết định. • Chọn lựa có quyết định là hoàn toàn xác định duy nhất trong điều kiện cụ thể của vấn đề • Sửa lại: • 3.Chọn ra một môn học có nhiều đvht nhất. • 3.1 Nếu chỉ có một môn học nhiều đvht nhất: chọn một • 3.2 Nếu có nhiều môn học cùng số đvht: sắp xếp tăng dần theo tên môn học trong thứ tự từ điển rối chọn môn đầu tiên. ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 134
- Các khái niệm (6) Tính thực thi được: • Hiển nhiên • Chỉ xét trong điều kiện hiện tại của bài toán • Cho ví dụ về điều kiện hiện tại:??? Tính dừng: • Không dừng: Lặp vô tận, bị quẫn • Dễ vi phạm nhất ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 135
- Các khái niệm (7) Tính dừng -Ví dụ: • Tính tổng các số nguyên dương lẻ trong khoảng từ 1 đến n ta có thuật toán sau : • B1. Hỏi giá trị của n. • B2. S = 0 • B3. i = 1 • B4. Nếu i = n+1 thì sang bước B8, ngược lại sang bước B5 • B5. Cộng thêm i vào S • B6. Cộng thêm 2 vào i • B7. Quay lại bước B4. • B8. Tổng cần tìm chính là S. • Thuật toán luôn dừng??? ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 136
- Các khái niệm (8) Tính dừng -Ví dụ: • Chỉ dừng khi n chẵn • Khi n lẻ phải thay B4 bằng: • B4. Nếu i >= n+1 thì sang bước B8, ngược lại sang bước B5 Tính đúng: • Chứng minh thuật toán đúng!!! • Khó đạt được nhất ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 137
- Các khái niệm (9) Thuật toán thì cứng nhắc ! • Tính chất chặt chẽ và cứng nhắc. • Khả năng giải quyết vấn đề bị giới hạn. "làm mềm“: tính xác định và tính đúng • Thuật toán đệ quy. • Thuật giải. ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 138
- Các khái niệm (10) Các đặc trưng khác của thuật toán • Ðầu vào và đầu ra (input/output) . • Tính hiệu quả (effectiveness): theo tiêu chuẩn • Khối lượng tính toán, không gian và thời gian thi hành. • Là yếu tố quyết định để đánh giá, chọn lựa • Nhiều phương pháp để đánh giá tính hiệu quả của thuật toán. • Tính tổng quát (generalliness) : • Áp dụng được cho mọi trường hợp của bài toán • Không phải lúc nào cũng đảm bảo được tính tổng quát. • Có lúc chỉ cần xây dựng cho một dạng đặc trưng. ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 139
- Các khái niệm - Ví dụ (1) Thuật toán giải phương trình bậc hai ax2+bx+c=0 (a0) • 1. Yêu cầu cho biết giá trị của 3 hệ số a, b, c • 2. Nếu a=0 thì • 2.1. Yêu cầu đầu vào không đảm bảo. • 2.2. Kết thúc thuật toán. • 3. Trường hợp a khác 0 thì ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 140
- Các khái niệm - Ví dụ (2) • 3. Trường hợp a khác 0 thì • 3.1. Tính giá trị D = b2-4ac • 3.2. Nếu D > 0 thì • 3.2.1. Phương trình có hai nghiệm phân biệt x1,x2 • 3.2.2. Giá trị của hai nghiệm được tính theo công thức sau: −b + D −b − D x1 = , x2 = 2a 2a • 3.2.3. Kết thúc thuật toán. • 3.3 Nếu D=0 thì ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 141
- Các khái niệm - Ví dụ (3) • 3.3. Nếu D = 0 thì • 3.3.1. Phương trình có nghiệm kép x0 • 3.3.2. Giá trị của nghiệm kép là −b x= 2a • 3.3.3. Kết thúc thuật toán • 3.4. Nếu D < 0 thì • 3.4.1. Phương trình vô nghiệm. • 3.4.2. Kết thúc thuật toán. ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 142
- Các khái niệm - Ví dụ (4) Bài toán : Cho hai số nguyên dương a và b. Tìm ước số chung lớn nhất của a và b. Thuật toán Euclid • 1. Yêu cầu cho biết giá trị của a, b. • 2. a0 = a • 3. b0 = b • 4. i = 0 ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 143
- Các khái niệm - Ví dụ (5) • 5. Nếu ai khác bi thì thực hiện các thao tác sau, ngược lại qua bước 7. • 5.1 Tăng i lên 1. • 5.2. Nếu ai-1 > bi-1 thì • ai = ai-1 - bi-1 • bi = bi-1 • 5.3. Ngược lại • bi = bi-1 - ai-1 • ai = ai-1 • 6. Trở lại bước 5. • 7. Ước số chung lớn nhất của a, b là ai . ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 144
- Các phương pháp biểu diễn Thuật toán: • Một phương pháp thể hiện lời giải bài toán • Phải tuân theo một số quy tắc nhất định Có 3 phương pháp biểu diễn thuật toán : • Dùng ngôn ngữ tự nhiên. • Dùng lưu đồ-sơ đồ khối (flowchart). • Dùng mã giả (pseudocode). ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 145
- Ngôn ngữ tự nhiên Ngôn ngữ thường ngày: • Liệt kê các bước của thuật toán, quá trình thực hiện lần lượt (trừ khi có yêu cầu nhảy_ • Không thể hiện rõ cấu trúc của thuật toán • Dài dòng, có thể gây hiểu lầm hoặc khó hiểu • Không yêu cầu người viết hay đọc nắm quy tắc. • Không có một quy tắc cố định • Tính dễ đọc: • viết các bước con lùi vào bên phải • đánh số bước theo quy tắc phân cấp như 1, 1.1, ... ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 146
- Lưu đồ - sơ đồ khối (1) Công cụ trực quan diễn đạt thuật toán. • Biểu diễn bằng mô hình – hình vẽ Theo dõi được: • sự phân cấp các trường hợp • quá trình xử lý của thuật toán Được dùng trong những thuật toán • rắc rối • khó theo dõi được quá trình xử lý ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 147
- Lưu đồ - sơ đồ khối (2) Phân biệt hai loại thao tác: • Chọn lựa theo một điều kiện nào đó • Xử lý, hành động ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 148
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 | 419 | 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 | 15 | 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 | 8 | 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 | 9 | 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 | 78 | 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