tailieunhanh - Bài giảng Phân tích và thiết kế thuật toán: Các phương pháp giải quyết bài toán trên máy tính - Phạm Thế Bảo

Bài giảng Phân tích và thiết kế thuật toán này giới thiệu các phương pháp giải quyết bài toán trên máy tính. Trong bài giảng sẽ trình bày 2 phương pháp chính, đó là phương pháp trực tiếp và phương pháp gián tiếp hoặc tìm kiếm lời giải. để nắm bắt các nội dung chi tiết. | 03 04 2008 CÁC PHƯƠNG PHÁP GIẢI QUYẾT BÀI TOÁN TRÊN MÁY TÍNH Phạm Thế Bảo Khoa Toán - Tin học Trường Đại học Khoa học Tự nhiên Phân lọai 1. Phương pháp trực tiếp 2. Phương pháp gián tiếp hoặc tìm kiếm lời giải Phạm Thế Bảo 1 03 04 2008 r 1 1 r J J Ấ Phương pháp trực tiêp Xác định trực tiêp được lời giải qua một thủ tục tính toán công thức hệ thức định luật . hoặc qua các bước căn bản để có được lời giải. Việc giải quyêt vấn đề trên máy tính chỉ là thao tác lập trình hay là sự chuyển đổi lời giải từ ngôn ngữ tự nhiên sang ngôn ngữ máy tính kỹ thuật lập trình trên máy tính. Có ba loại cơ bản o Lọai thứ nhất dùng để biểu diễn cho các bài toán đã có lời giải chính xác bằng một công thức toán học nào đó. 1 ví dụ tính tổng n số nguyên dương. 1 2 2 o Loại thứ hai biểu diễn cho các bài toán có công thức giải gần đúng công thức tính sin cos giải phương trình siêu việt . . ví dụ giải phương trình bậc 2 o Loại cuối cùng biểu diễn các lời giải không tường minh bằng kỹ thuật đệ quy. Phạm Thế Bảo Chuyển đổi dữ liệu bài toán thành dữ liệu chương trình Nguyên lý 1 Dữ liệu của bài toán sẽ được biểu diễn lại dưới dạng các biên của chương trình thông qua các quy tắc xác định của ngôn ngữ lập trình cụ thể 1. Biên - phương tiện biểi diễn dữ liệu của chương trình 2. Thay đổi giá trị của biên - lệnh gán 3. Kiểu dữ liệu 4. Hằng số 5. Cấu trúc một chương trình Phạm Thế Bảo 2 03 04 2008 Chuyển đổi quá trình tính toán của bài toán thành các cấu trúc của chương trình Nguyên lý 2 Định lý Bohn-Jacopini Mọi quá trình tính toán đều có thể mô tả và thực hiện dựa trên ba cấu trúc cơ bản tuần tự rẽ nhánh và lặp. 1. Cấu trúc tuần tự 2. Cấu trúc rẽ nhánh 1. Rẽ nhánh có điều kiện if condition rẽ nhánh đơn if rẽ nhánh đôi if . else . 2. Rẽ nhiều nhánh case 3. Rẽ nhánh không có điều kiện LABEL và GOTO 3. Cấu trúc lặp 1. Lặp xác định 2. Lặp không xác định Phạm Thế Bảo Phân chia bài toán ban đầu thành những bài toán nhỏ hơn Nguyên lý 3 Mọi bài toán lớn đều có thể giải quyết bằng cách phân chia thành