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 3 - ThS. Nguyễn Lê Minh (Nhóm ngành Cơ khí)

Chia sẻ: Minh Nguyệt | Ngày: | Loại File: PDF | Số trang:47

Thêm vào BST
Báo xấu
23
lượt xem 2
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 3: Thuật toán" cung cấp cho người học các kiến thức: Khái niệm thuật toán, tính chất của thuật toán, các cách biểu diễn thuật toán, cấu trúc cơ bản của thuật toán, một số thuật toán cơ bản. Cuối bài giảng có phần bài tập để người học ôn tập và củng cố kiến thức.

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 3 - ThS. Nguyễn Lê Minh (Nhóm ngành Cơ khí)

  1. TIN HỌC ĐẠI CƯƠNG Chương 3: THUẬT TOÁN GV: Nguyễn Lê Minh Bộ môn: Công nghệ thông tin 6/2020
  2. Nội dung 1. Khái niệm thuật toán 2. Tính chất của thuật toán 3. Các cách biểu diễn thuật toán 4. Cấu trúc cơ bản của thuật toán 5. Một số thuật toán cơ bản 6. Bài tập 3/6/2020 2
  3. Nội dung 1. Khái niệm thuật toán 2. Tính chất của thuật toán 3. Các cách biểu diễn thuật toán 4. Cấu trúc cơ bản của thuật toán 5. Một số thuật toán cơ bản 6. Bài tập 3/6/2020 3
  4. 1. Khái niệm thuật toán Thuật toán là một tập hữu hạn các bước, các phép toán cơ bản được sắp xếp theo một trình tự nhất định để từ thông tin đầu vào của bài toán sau một tập hữu hạn các bước đó sẽ đạt được kết quả ở đầu ra như mong muốn. Input Algorithm Output 3/6/2020 4
  5. 1. Khái niệm thuật toán Thông thường, thuật toán dùng để giải một lớp các bài toán cụ thế. Gồm 2 thành phần chính: • Input : Thông tin bài toán đã cho • Output : Thông tin cần tìm hoặc trả lời câu hỏi cần thiết Ví dụ: S = a *b 3/6/2020 5
  6. 1. Khái niệm thuật toán Ví dụ : Giải phương trình bậc nhất P(x): ax + b = 0, (a, b là các số thực) • Input : a, b • Output : Kết quả P(x) o Mô tả thuật toán:  Nếu a = 0  Nếu b = 0 thì P(x) có nghiệm bất kì  Nếu b 0 thì P(x) vô nghiệm  Nếu a 0  P(x) có duy nhất một nghiệm x = -b/a 3/6/2020 6
  7. 1. Khái niệm thuật toán Ví dụ 2 : Kiểm tra một số nguyên X có chia hết cho 5 không ? • Input : X • Output : Kết quả kiểm tra Result o Mô tả thuật toán: o Bước 1: Tìm số dư r của phép chia x cho 5 o Bước 2: Kiểm tra  Nếu r = 0 thì result = True  Nếu r 0 thì result = False 3/6/2020 7
  8. Nội dung 1. Khái niệm thuật toán 2. Tính chất của thuật toán 3. Các cách biểu diễn thuật toán 4. Cấu trúc cơ bản của thuật toán 5. Một số thuật toán cơ bản 6. Bài tập 3/6/2020 8
  9. 2. Tính chất của thuật toán  Tính dừng  Tính xác định  Tính đúng  Ðầu vào và đầu ra (input/output)  Tính hiệu quả  Tính tổng quát 3/6/2020 9
  10. 2. Tính chất của thuật toán ■ Tính dừng : Thuật toán phải bao đảm được kết thúc sau một số hữu hạn bước. ■ Tính dừng là tính dễ bị vi phạm, thường là do sai sót khi trình bày thuật toán dẫn đến “Lặp vô tận”. 3/6/2020 10
  11. 2. Tính chất của thuật toán Thuật toán phải có tính xác định: các bước trong thuật toán phải được xác định rõ ràng, có thể thực thi được, không gây mập mờ, nhập nhằng, tùy chọn. 3/6/2020 11
  12. 2. Tính chất của thuật toán  Thuật toán phải có Tính đúng đắn: để đảm bảo kết quả tính toán hay các thao tác mà máy tính thực hiện được là chính xác.  Trong một kỳ thi kiểm tra không phải tất cả các học sinh điều đưa ra được lời giải “đúng”.  Khi thiết kế thuật toán cần kiểm nghiệm và chỉnh sửa nhiều lần để có được một thuật toán đúng. 3/6/2020 12
  13. 2. Tính chất của thuật toán o Ðầu vào và đầu ra (input/output): Mọi thuật toán đều có đại lượng vào và ra. o Tính hiệu quả: Một bài toán có thể có nhiều thuật toán khác nhau để giải, một thuật toán tốt thì nó phải hiệu quả, tính hiệu quả của thuật toán đượ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 khi thuật toán được thi hành. o Tính tổng quát: Thuật toán có tính tổng quát là thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không phải chỉ áp dụng được cho một số trường hợp riêng lẻ nào đó. 3/6/2020 13
  14. Nội dung 1. Khái niệm thuật toán 2. Tính chất của thuật toán 3. Các cách biểu diễn thuật toán 4. Cấu trúc cơ bản của thuật toán 5. Một số thuật toán cơ bản 6. Bài tập 3/6/2020 14
  15. 3. Các cách biểu diễn của thuật toán Liệt kê Sơ đồ khối Mã giả 3/6/2020 15
  16. 3. Các cách biểu diễn của thuật toán Phương pháp liệt kê o Tại mỗi bước sử dụng ngôn ngữ tự nhiên để diễn tả công việc phải làm. o Các bước được đánh số thứ tự, bước có số thứ tự nhỏ hơn được thực hiện trước. o Ưu điểm: Dễ hiểu, dễ thực hiện. o Khuyết điểm: Phụ thuộc cách trình bày của người thiết kế, khó áp dụng cho những thuật toán có tính phức tạp. 3/6/2020 16
  17. 3. Các cách biểu diễn của thuật toán Ví dụ : Giải phương trình bậc nhất P(x): ax +b = 0: ■ Input: a,b ■ Output: Kết quả giải phương trình. ■ Bước 1: Nhập vào 2 số thực a, b ■ Bước 2: Kiểm tra nếu a = 0 thực hiện: ■ Bước 2.1: Nếu b = 0 thì phương trình vô số nghiệm ■ Bước 2.2: Nếu b 0 thì phương trình vô nghiệm ■ Bước 3: Khi a 0 phương trình có nghiệm x=-b/a ■ Bước 4: Kết thúc thuật toán 3/6/2020 17
  18. 3. Các cách biểu diễn của thuật toán Phương pháp sơ đồ khối o Sử dụng các hình khối để biểu diễn các lệnh hay thao tác. o Sử dụng mũi tên để biểu diễn thứ tự thực hiện. o Ưu điểm: Diễn đạt khoa học, có tính nhất quán, dễ hiểu và dễ kiểm tra. o Khuyết điểm: Phải vẽ nhiều hình, cồng kềnh, không phù hợp với các thuật toán phức tạp. 3/6/2020 18
  19. 3. Các cách biểu diễn của thuật toán Hình Ý nghĩa Bắt đầu thuật toán Begin Kết thúc thuật toán End Nhập dữ liệu Input Xuất dữ liệu Output 3/6/2020 19
  20. 3. Các cách biểu diễn của thuật toán Hình Ý nghĩa Câu lệnh rẽ nhánh S - Nếu đúng thì thực hiện nhánh Đ Biểu thức - Nếu sai thì thực hiện nhánh S Đ Biểu diễn thực hiện công việc A End A Biểu diễn việc gọi chương trình con A A Hướng của thuật toán 3/6/2020 20
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
4=>1