Tin học đại cương - bài 6: phương pháp giải các bài toán tin học

Chia sẻ: Lê Trinh | Ngày: | Loại File: PPT | Số trang:20

Thêm vào BST

Báo xấu

54
lượt xem 5
download

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

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). Tính hiệu quả: Bộ nhớ, số phép tính, thời gian chạy, dễ hiểu, dễ cài đặt.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

www.uit.edu.vn TIN HỌC ĐẠI CƯƠNG BÀI 6 PHƯƠNG PHÁP GIẢI CÁC BÀI TOÁN TRONG TIN HỌC 1
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
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
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
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
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
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
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
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
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
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
LƯU ĐỒ Tính F = N! Tin học đại cương 12
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
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
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
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
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
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).  Bước 6: Vận hành, theo dõi và bảo dưỡng Tin học đại cương (Operation, follow-up and Maintenance). 18
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.  Cẩm nang thuật toán - Ứng dụng và cài đặt Tin học đại cương bằng C, Nguyễn Phúc Trường Sinh, NXB TK, 2002. 19
www.uit.edu.vn 20