intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Tin học đại cương: Chương 4 - Lê Thị Ngọc Thảo

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:29

Thêm vào BST
Báo xấu
6
lượt xem 4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Tin học đại cương: Chương 4 - Lê Thị Ngọc Thảo

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

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

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
44=>2