›
›

Bài giảng Hệ thống thông tin - Chương 1, Phần 2: Giải quyết bài toán bằng máy tính - Ngô Văn Linh

pdf 9 trang Hùng Dũng 04/01/2024 1360
Download
Bạn đang xem tài liệu "Bài giảng Hệ thống thông tin - Chương 1, Phần 2: Giải quyết bài toán bằng máy tính - Ngô Văn Linh", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_he_thong_thong_tin_chuong_1_phan_2_giai_quyet_bai.pdf

Nội dung text: Bài giảng Hệ thống thông tin - Chương 1, Phần 2: Giải quyết bài toán bằng máy tính - Ngô Văn Linh

  1. Phần II: Giải quyết bài toán Ngo Van Linh Bộ môn Hệ thống thông tin Viện Công nghệ thông tin và Truyền thông Đại học Bách Khoa Hà Nội 1
  2. Nội dung phần này  Chương 1: Giải quyết bài toán bằng máy tính  Khái niệm về bài toán  Quá trình giải quyết bài toán bằng máy tính  Các phương pháp giải quyết bài toán bằng máy tính  Phân loại bài toán  Chương 2: Thuật toán  Định nghĩa thuật toán  Biểu diễn thuật toán  Một số thuật toán thông dụng  Thuật toán đệ quy  Thuật giải heuristic 2
  3. Chương 1: Giải quyết bài toán bằng máy tính Nguyễn Hồng Phương Email: phuongnh-fit@mail.hut.edu.vn Website: Bộ môn Hệ thống thông tin Viện Công nghệ thông tin và Truyền thông Đại học Bách Khoa Hà Nội 3
  4. Nội dung chương này  1.1. Khái niệm về bài toán  1.2. Các bước giải quyết bài toán bằng máy tính  1.3. Các phương pháp giải quyết vấn đề bằng máy tính  1.4. Phân loại bài toán 4
  5. 1.1. Khái niệm về vấn đề và bài toán  Vấn đề rộng hơn bài toán?  Pitago chia vấn đề ra:  Theorema là vấn đề cần được khẳng định đúng-sai  Problema 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.  Diễn đạt bằng sơ đồ: A B  A là giả thiết, điều kiện ban đầu  B là kết luận, mục tiêu cần đạt  là suy luận, giải pháp cần xác định 5
  6. 1.2. Các bước giải quyết bài toán bằng máy tính  Bước 1: Xác định vấn đề-bài toán  Bước 2: Lựa chọn phương pháp giải  Bước 3: Xây dựng thuật toán hoặc thuật giải  Bước 4: Cài đặt chương trình  Bước 5: Hiệu chỉnh chương trình  Bước 6: Thực hiện chương trình 6
  7. 1.3. Các phương pháp giải quyết vấn đề bằng máy tính  Giải quyết vấn đề theo hướng xác định trực tiếp lời giải  xác định trực tiếp lời giải qua thủ tục tính toán hoặc thủ tục bao gồm một số hữu hạn các thao tác sơ cấp.  Giải quyết vấn đề theo hướng tìm kiếm lời giải  nguyên lý "thử và sai"  các phương pháp  liệt kê hay vét cạn  thử ngẫu nhiên  quay lui  chia để trị 7
  8. 1.4. Phân loại bài toán  Bài toán đa thức  Bài toán không đa thức  NP Problems 8