Bài giảng Toán ứng dụng - Chương 3: Ma trận

Nội dung text: Bài giảng Toán ứng dụng - Chương 3: Ma trận

1. 19- Thuật toán 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í Vấn đề Là vấn đề cần khẳng Là vấn đề cần tìm giải định tính đúng sai dựa pháp để đạt được một trên một hệ thống các mục tiêu xác định từ tiên đề. những điều kiện ban đầu nào đó TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009
2. 19- Thuật toán (tt) Ví dụ Ví dụ 1. Hãy chứng minh biểu thức 1. Hãy chỉ ra các bước dựng (a+b)2=(a2+2ab+b2) một tam giác với chiều dài a,b,c cho trước. 2. Hãy chứng minh rằng gia 2. Với số vốn 1 tỷ đồng, cần tốc của chuyển động tròn đầu tư vào lĩnh vực sản đều là gia tốc hướng tâm. 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? TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009
3. 19- Thuật toán (tt) A: là giả =>: là suy B: là kết thuyết luận, giải luận hoặc hoặc các pháp cần mục tiêu điều kiện xác định cần đạt ban đầu được TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009
4. 19- Thuật toán (tt) Độ khó Độ khó tăng Độ rõ tăngĐộ rõ TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009
5. 19- Thuật toán (tt) 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. TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009
6. 19- Thuật toán (tt) Xác định Thuật toán Hữu hạn Đúng TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009
7. 19- Thuật toán (tt) Tính mập mờ 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. TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009
8. 19- Thuật toán (tt) 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. TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009
9. 19- Thuật toán (tt) 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. TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009
10. 19- Thuật toán (tt) 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 TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009
11. 19- Thuật toán (tt) 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) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009
12. 19- Thuật toán (tt) 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 TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009
13. 19- Thuật toán (tt) 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. TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009
14. 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009
15. 19- Thuật toán (tt) Lưu đồ khối TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009
16. 19- Thuật toán (tt) TOÁN ỨNG DỤNG Chương 3: MA TRẬN HDXB-2009