Bài giảng Toán rời rạc: Chương 6 - TS. Đặng Xuân Thọ

Bài giảng Toán rời rạc: Chương 6 Thuật toán cung cấp cho người học những kiến thức như: Thuật toán (algorithm) là một trong những khái niệm quan trọng trong lĩnh vực tin học; Phương pháp nào để biểu diễn thuật toán. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Chương 6 - TS. Đặng Xuân Thọ TOÁN RỜI RẠC(DISCRETE MATHEMATICS) Bùi Thị Thủy Đặng Xuân Thọ Support2  Full name: Đặng Xuân Thọ  Mobile: 091.2629.383  Email: thodx@hnue.edu.vn  Website: http://fit.hnue.edu.vn/~thodx/ Toán rời rạc - ĐHSPHN NỘI DUNG3  Chương 1. Logic mệnh đề  Chương 2. Lý thuyết tập hợp  Chương 3. Một số công thức tổ hợp  Chương 4. Suy luận và kiểm chứng chương trình  Chương 5. Đại số Boole và cấu trúc mạch logic  Chương 6. Thuật toán  Chương 7. Lý thuyết đồ thị Toán Rời Rạc - ĐHSPHN Chương 6. Thuật toán4  Thuật toán (algorithm) là một trong những khái niệm quan trọng trong lĩnh vực tin học.  Khái niệm thuật toán  Các đặc trưng của thuật toán  Phương pháp nào để biểu diễn thuật toán?  Mô tả từng bước  Sơ đồ khối  Ngôn ngữ giả mã Toán Rời Rạc - ĐHSPHN5 Khái niệm thuật toán Toán Rời Rạc - ĐHSPHN Khái niệm bài toán6  Bài toán trong phạm vi Tin học?  In dòng chữ ra màn hình  Giải phương trình bậc 2  Quản lý hồ sơ cán bộ …  Dùng máy tính giải bài toán, 2 yếu tố quan tâm  INPUT  OUTPUT Toán Rời Rạc - ĐHSPHN Phát biểu bài toán7  Ví dụ 1: Bài toán tìm ước chung lớn nhất?  Ví dụ 2: Bài toán sắp xếp?  Ví dụ 3: Bài toán kiểm tra tính nguyên tố?  Ví dụ 4: Bài toán quản lý hồ sơ cán bộ? BLACK OUTPUT INPUT BOX Toán Rời Rạc - ĐHSPHN Khái niệm giải thuật8  Giải thuật hay còn gọi là thuật toán, thuật giải.  Định nghĩa: Là tập hữu hạn có thứ tự các bước tác động trên một đối tượng dữ liệu Input để sau một số hữu hạn lần thực hiện sẽ cho ta kết quả Output. Toán Rời Rạc - ĐHSPHN Ví dụ về giải thuật9  Bài toán: Cho 3 số nguyên a, b, c. Mô tả giải thuật tìm số lớn nhất trong 3 số đã cho.  Phân tích:  Input: 3 số nguyên a, b, c.  Output: số lớn nhất trong 3 số. Toán Rời Rạc - ĐHSPHN Ví dụ về giải thuật10  Bài toán: Cho 3 số nguyên a, b, c. Mô tả giải thuật tìm số lớn nhất trong 3 số đã cho.  Thuật toán:  Bước 1. Gán max := a;  Bước 2. Nếu b > max thì gán max := b;  Bước 3. Nếu c > max thì gán max := c;  Tư tưởng của thuật toán là duyệt lần lượt giá trị của từng số và giữ lại giá trị lớn nhất vào biến max.  Kết thúc thuật toán max cho số nguyên lớn nhất trong 3 số đã cho. Toán Rời Rạc - ĐHSPHN11 Bước 1: Gán max=a Max =a ; Bước 2: nếu max Ví dụ về giải thuật12  Bài toán: Cho 3 số nguyên a, b, c. Mô tả giải thuật tìm số lớn nhất trong 3 số đã cho.  Theo dõi quá trình thực hiện của thuật toán với giá trị cụ thể của a, b, c.  a := 1;  b := 5;  c := 3; Toán Rời Rạc - ĐHSPHN Ví dụ về giải thuật13 a = 1 b = 5 c = 3 Bước 1. Gán giá trị của a vào biến max max = 1 Bước 2. Do b > max (5 > 1) nên max gán bằng b max = 5 Bước 3. Do c < max (3 < 5) nên ko thực hiện gán max = 5 Toán Rời Rạc - ĐHSPHN Ví dụ về giải thuật14  Một vài nhận xét:  Giải thuật nhận đầu vào là 3 số a, b, c và đưa kết quả ở đầu ra là Max.  Các bước của giải thuật được mô tả chính xác.  Giải thuật kết thúc sau 3 bước và đưa ra lời giải của bài toán, vì vậy giải thuật là hữu hạn  Nếu đầu vào là đã xác định, kết quả tại mỗi bước của giải thuật được xác định duy nhất.  Giải thuật luôn đưa ra giá trị của số lớn nhất trong 3 số bất kì, như vậy giải thuật có tính tổng quát. Toán Rời Rạc - ĐHSPHN Các đặc trưng của giải thuật15  Đầu vào (Input): Giải thuật nhận dữ liệu vào từ một tập nào đó.  Đầu ra (Output): Với một tập các dữ liệu đầu vào, giải thuật đưa ra các dữ liệu tương ứng với lời giải của bài toán.  Chính xác (Precision): Các bước của giải thuật được mô tả chính xác.  Hữu hạn (Finiteness): Giải thuật phải đưa được đầu ra sau một số hữu hạn bước với mọi đầu vào.  Đơn trị (Uniqueness): Các kết quả trung gian của từng bước thực hiện giải thuật được xác định một cách đơn trị và chỉ phụ thuộc đầu ...