Toán học - 19 Thuật toán

19- Thuật toán TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009 1.Vấn đề là những vướng mắc, khó khăn trong cuộc sống mà chúng ta cần giải quyết. Bài toán là một trường hợp riêng của vấn đề. Định lí Là vấn đề cần khẳng định tính đúng sai dựa trên một hệ thống các tiên đề. Vấn đề Là vấn đề cần tìm giải pháp để đạt được một mục tiêu xác định từ những điều kiện ban đầu nào đó 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009 Ví dụ 1. Hãy chứng minh biểu thức (a+b)2=(a2+2ab+b2) 2. Hãy chứng minh rằng gia tốc của chuyển động tròn đều là gia tốc hướng tâm. Ví dụ 1. Hãy chỉ ra các bước dựng một tam giác với chiều dài a,b,c cho trước. 2. Với số vốn 1 tỷ đồng, cần đầu tư vào lĩnh vực sản xuất nào để có tiền lợi cao nhất. 3. Làm sao để giảm giá thành sản phẩm? 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009 A: là giả thuyết hoặc các điều kiện ban đầu =>: là suy luận, giải pháp cần xác định B: là kết luận hoặc mục tiêu cần đạt được 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009 Đ ộ kh ó tă n g Đ ộ r õ t ă n g 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009 2.Thuật toán là một tập hữu hạn các hướng dẫn rõ ràng. Việc nghiên cứu về thuật toán có vai trò rất quan trọng trong khoa học máy tính vì máy tính chỉ giải quyết được vấn đề khi đã có hướng dẫn rõ ràng và đúng. Thuật toán là một dãy hữu hạn các bước không mập mờ và có thể 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. 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009 Thuật toán Xác định Hữu hạn Đúng 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009 Ví dụ 1: Giả sử khi nhận một lớp học mới, BGH yêu cầu giáo viên chủ nhiệm chọn lớp trưởng mới theo các bước sau: 1. Lập danh sách tất cả các học sinh trong lớp. 2. Sắp thứ tự danh sách học sinh. 3. Chọn học sinh đứng đầu danh sách để làm lớp trưởng. Tính mập mờ 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009 1. Lập danh sách tất cả học sinh trong lớp theo hai thông tin: Họ và tên, Điểm trung bình cuối năm. 2. Sắp hạng học sinh dựa trên điểm trung bình theo thứ tự giảm dần. Hai học sinh có cùng điểm trung bình sẽ có cùng hạng. 3. Nếu chỉ có 1 học sinh hạng nhất thì chọn em đó làm lớp trưởng. Trường hợp có nhiều học sinh đồng hạng thì chọn học sinh có điểm môn Toán cao nhất làm lớp trưởng. 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009 Tính “dừng” Thuật toán tình tổng các số nguyên dương lẻ từ 1 -> n B1. Hỏi giá trị của n B2. S=0 B3. i=1 B4. Nếu i=n+1 thì sang bước 8, ngược lại sang bước 5. B5. Cộng thêm i vào S B6. Cộng thêm 2 vào i B7. Quay lại B4 B8. Tổng cần tìm chính là S. 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009 3 đặc trưng phụ của thuật toán 1. Đầu vào và đầu ra INPUT THUẬT TOÁN OUTPUT 2. Tính hiệu quả 3. Tính tổng quát 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009 3. Các phương pháp biểu diễn thuật toán 1. Dùng ngôn ngữ tự nhiên 2. Dùng sơ đồ (lưu đồ) khối (flowchart) 3. Dùng mã giả (pseudocode) 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009 Ví dụ: Cho n hộp có khối lượng khác nhau và một dĩa cân. Tìm hộp nặng nhất. Ngôn ngữ tự nhiên • Nếu chỉ có 1 hộp (n=1) thì 1.1. Hộp đó chính là hộp nặng nhất 1.2. Kết thúc thuật toán 2. Ngược lại nếu có từ 2 hộp trở lên (n>1) 2.1. Chọn 2 hộp bất kỳ và đặt lên bàn cân 2.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn vào chỗ khác 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009 3. Nếu còn hộp chưa được cân thực hiện các bước sau, nếu không còn hộp nào nữa chuyển sang bước 5 3.1. Chọn một hộp bất kỳ và để lên dĩa cân còn trống. 3.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác. 4. Trở lại bước 3. 5. Hộp còn lại trên cân chính là hộp nặng nhất. 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009 Lưu đồ khối 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009