tailieunhanh - Bài giảng Toán rời rạc: Chương 1 - Nguyễn Lê Minh (2020)

Bài giảng "Toán rời rạc - Chương 1: 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. . | Bài giảng Toán rời rạc: Chương 1 - Nguyễn Lê Minh (2020) Toán rời rạc Chương 1: THUẬT TOÁN GV: Nguyễn Lê Minh Bộ môn: Công nghệ thông tin 4/19/20 1 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 4/19/20 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 4/19/20 3 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 4/19/20 4 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 4/19/20 5 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: v 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 v Nếu a 0 P(x) có duy nhất một nghiệm x = -b/a 4/19/20 6 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 4/19/20 7 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 4/19/20 8 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 .