intTypePromotion=1
ADSENSE

Tin học đại cương part 2 - Phương pháp giải các bài toán trong tin học

Chia sẻ: Raizar Hidie | Ngày: | Loại File: PPT | Số trang:0

348
lượt xem
22
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài toán và giải quyết bài toán được biểu diễn dưới dạng: A → B giả thiết giải pháp mục tiêu Cần xác định A, B, và các thao tác để đi từ A đến B. A, B không rõ ràng? Các điều kiện của cách giải ko minh bạch?

Chủ đề:
Lưu

Nội dung Text: Tin học đại cương part 2 - Phương pháp giải các bài toán trong tin học

  1. www.uit.edu.vn TIN HỌC ĐẠI CƯƠNG BÀI 2 PHƯƠNG PHƯƠNG PHÁP GIẢI CÁC BÀI BÀI TOÁN TRONG TIN HỌC 1
  2. NỘI DUNG  Khái niệm về vấn đề và bài toán.  Các bước giải quyết vấn đề - bài toán trên máy tính.  Thuật toán và thuật giải.  Biểu diễn thuật toán và thuật giải. Tin học đại cương 2
  3. KHÁI NIỆM VỀ VẤN ĐỀ - BÀI TOÁN  Bài toán và giải quyết bài toán được biểu diễn dưới dạng: → A B giả thiết giải pháp mục tiêu  Cần xác định A, B, và các thao tác để đi từ A đến B.  A, B không rõ ràng? Tin học đại cương !!!  Các điều kiện của cách giải ko minh bạch? 3
  4. MỘT SỐ NHẬN XÉT  Việc xác định bài toán là rất quan trọng.  Thông báo về A và B mang tính biểu tượng gợi nhớ về giả thiết và mục tiêu.  Bước đầu để xác định bài toán và phát biểu lại theo ngôn ngữ của riêng mình để hiểu.  Tiếp theo là tìm hiểu thông tin Input A và Output B và các mối liên hệ. Tin học đại cương  Thường nên xét một vài trường hợp cụ thể để hiểu rõ hơn bài toán. 4
  5. CÁC BƯỚC GIẢI QUYẾT BT Bước 1: Xác định vấn đề - bài toán. Nhằm phát biểu chính xác vấn đề - bài toán, làm rõ những yêu cầu, xác định tính khả thi. Bước 2: Lựa chọn phương pháp giải. Thường có nhiều cách khác nhau → Tùy theo nhu cầu thực của bài toán mà chọn lựa p/pháp phù hợp. Bước 3: Xây dựng thuật toán hoặc thuật giải. Chi tiết hóa phương pháp đã lựa chọn. Thường theo cấu trúc phân tích → Vấn đề TOP-DOWN. Bước 4: Cài đặt chương trình. Từ thuật giải, dùng NNLT để hiện thực hóa. Tin học đại cương Bước 5: Hiệu chỉnh & Thực hiện chương trình. Sửa lỗi, gồm: lỗi cú pháp và lỗi ngữ nghĩa. Bước 6: Lưu trữ, Bảo trì. 5
  6. XÁC ĐỊNH CẤU TRÚC DỮ LIỆU  Niklaus Wirth: Cấu trúc dữ liệu + Thuật giải = Ch. trình  Dữ liệu và cấu trúc dữ liệu đóng vai trò quan trọng trong việc kết hợp và đưa ra cách giải quyết bài toán.  Một số lưu ý về CTDL:  Phải biểu diễn đầy đủ thông tin.  Phù hợp các thao tác của thuật toán. Tin học đại cương  Phù hợp điều kiện cho phép của NNLT. 6
  7. THUẬT TOÁN VÀ THUẬT GIẢI  Thuật toán: Một dãy hữu hạn các chỉ thị có thể thi hành để đạt mục tiêu đề ra nào đó.  Các đặc trưng của thuật toán:  Tính có đại lượng vào và ra.  Tính xác định.  Tính hữu hạn dừng.  Tính đúng đắn.  Tính phổ dụng (tổng quát). Tin học đại cương  Tính hiệu quả: Bộ nhớ, số phép tính, thời gian chạy, dễ hiểu, dễ cài đặt. 7
  8. THUẬT TOÁN VÀ THUẬT GIẢI  Thuật giải: Khái niệm mở rộng của thuật toán.  Với một số đặc điểm chẳng hạn:  Có những bài toán không xác định (có) thuật toán cụ thể.  Hoặc có thuật toán nhưng không thực hiện được (chẳng hạn vì thời gian dài).  Hoặc có cách giải vi phạm thuật toán nhưng vẫn được chấp nhận. Tin học đại cương  Heuristic: Giải quyết bài toán với kết quả đúng (gần đúng) trong p. vi cho phép. 8
  9. BIỂU DIỄN THUẬT TOÁN  Ngôn ngữ tự nhiên.  Sơ đồ khối.  Mã giả.  Ngôn ngữ lập trình. Tin học đại cương 9
  10. NGÔN NGỮ TỰ NHIÊN  NN tự nhiên thông qua các bước được tuần tự liệt kê để BD thuật toán.  Ưu điểm:  Đơn giản, không cần kiến thức về về cách biểu diễn (mã giả, lưu đồ,...)  Nhược điểm:  Dài dòng, không cấu trúc. Tin học đại cương  Đôi lúc khó hiểu, không diễn đạt được thuật toán. 10
  11. LƯU ĐỒ  Là hệ thống các nút, cung hình dạng khác nhau thể hiện các chức năng khác nhau. A A Thực hiện A Gọi hàm A Vào / Ra dữ liệu Đúng Begin B End Sai Tin học đại cương Nút giới hạn bắt đầu / Điều kiện rẻ nhánh B kết thúc chương trình 11
  12. LƯU ĐỒ Tính F = N! Tin học đại cương 12
  13. MÃ GIẢ  Ngôn ngữ tựa ngôn ngữ lập trình.  Dùng cấu trúc chuẩn hóa, chẳng hạn tựa Pascal, C.  Dùng các ký hiệu toán học, biến, hàm.  Ưu điểm:  Đỡ cồng kềnh hơn lưu đồ khối.  Nhược điểm: Tin học đại cương  Không trực quan bằng lưu đồ khối. 13
  14. MÃ GIẢ Algorithm LargestNumber Input: Danh sách khác rỗng các con số L. Output: largest - giá trị số lớn nhất trong d. sách L. largest ← L0 for each item in danh sách L≥1, do if the item > largest, then largest ← the item return largest  “←” thể hiện phép gán. Tin học đại cương  “return” dùng để dừng thuật toán và trả về giá trị. 14
  15. LẬP TRÌNH  Dùng ngôn ngữ máy tính (C, Pascal,...) để diễn tả thuật toán, CTDL thành câu lệnh.  Kỹ năng lập trình đòi hỏi cần học tập và thực hành (nhiều).  Dùng phương pháp tinh chế từng bước để chuyển hoá bài toán sang mã chương trình cụ thể. Tin học đại cương 15
  16. THỰC HIỆN VÀ HIỆU CHỈNH CT  Chạy thử.  Lỗi và cách sửa.  Lỗi thuật toán.  Lỗi trình tự.  Lỗi cú pháp.  Xây dựng bộ test.  Cập nhật, thay đổi chương trình theo yêu Tin học đại cương cầu (mới). 16
  17. TIÊU CHUẨN CỦA CHƯƠNG TRÌNH  Tính tin cậy.  Giải thuật + Kiểm tra cài đặt.  Tính uyển chuyển.  Đáp ứng quy trình làm phần mềm.  Tính trong sáng.  Dễ hiểu và dễ chỉnh sửa.  Tính hữu hiệu. Tin học đại cương  Tài nguyên + giải thuật. 17
  18. QUY TRÌNH LÀM PHẦN MỀM  Bước 0: Ý tưởng (concept).  Bước 1: Xác định yêu cầu (Requirements Specification).  Bước 2: Phân tích (Analysis).  Bước 3: Thiết kế (Design).  Bước 4: Cài đặt (Implementation).  Bước 5: Thử nghiệm (Testing). Tin học đại cương  Bước 6: Vận hành, theo dõi và bảo dưỡng (Operation, follow-up and Maintenance). 18
  19. TÀI LIỆU THAM KHẢO  Phương pháp giải các bài toán trong tin học, Trần Đức Huyên, NXB GD, 1997.  Giáo trình tin học đại cương, Hoàng Kiếm (...), DH QG Tp. HCM, 2000.  Ngôn ngữ lập trình Pascal, Quách Tuấn Ngọc, NXB GD, 1996.  Lập trình căn bản, Đoàn Nguyên Hải (...), ĐH BK Tp. HCM, 1994. Tin học đại cương  Cẩm nang thuật toán - Ứng dụng và cài đặt bằng C, Nguyễn Phúc Trường Sinh, NXB TK, 2002. 19
  20. www.uit.edu.vn 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2