Lorem ipsum dolor sit amet, consectetur adipiscing elit. Vivamus suscipit, augue quis mattis gravida, est dolor elementum felis, sed vehicula metus quam a mi. Praesent dolor felis, consectetur nec convallis vitae.
» Công Nghệ Thông Tin
Bài giảng Phân tích thiết kế giải thuật: Thiết kế thuật toán và Phương pháp trực tiếp - GV. Hà Đại Dương
Download Vui lòng tải xuống để xem tài liệu đầy đủ
Bài giảng có nội dung trình bày: Thiết kế thuật toán (Modul hóa và phân tích từ trên xuống (top-down), một số phương pháp thiết kế và tối ưu thuật toán); Phương pháp trực tiếp (lược đồ chung và một số bài toán áp dụng). Để biết rõ hơn về nội dung chi tiết, mời các bạn cùng tham khảo.
![Pha Tich Thiet Ke Giai Thuat Hcmut Pha Tich Thiet Ke Giai Thuat Hcmut](/uploads/1/2/4/7/124796873/864972744.jpg)
Lưu
Nội dung Text: Bài giảng Phân tích thiết kế giải thuật: Thiết kế thuật toán và Phương pháp trực tiếp - GV. Hà Đại Dương
2/2/2017<br /><br />Phân tích và Thiết kế<br />THUẬT TOÁN<br />Hà Đại Dương<br />[email protected]<br />Web: fit.mta.edu.vn/~duonghd<br /><br />Bài 3 - Thiết kế thuật toán<br />và Phương pháp trực tiếp<br />PHÂN TÍCH VÀ THIẾT KẾ THUẬ TOÁN<br /><br />NỘI DUNG<br />I. Giới thiệu<br />II. Thiết kế thuật toán<br />1.<br />2.<br />3.<br /><br />Modul hóa và phân tích từ trên xuống (top-down)<br />Một số phương pháp thiết kế<br />Tối ưu thuật toán<br /><br />III. Phương pháp trực tiếp<br />1.<br />2.<br /><br />Lược đồ chung<br />Một số bài toán áp dụng<br /><br />IV. Bài tập<br /><br />1<br /><br />2/2/2017<br /><br />I. Giới thiệu<br /> Thiết kế thuật toán là vấn đề mang tính:<br />• Kỹ thuật<br />• Nghệ thuật<br /><br /> Đòi hỏi người thực hiện phải có:<br />• Kiến thức<br />• Kinh nghiệm<br />• Kỹ năng<br /><br /> Thuật toán được thiết kế phải:<br />• Đúng, đơn giản, dễ dùng<br />• Phù hợp với bộ nhớ của máy tính và có thời gian thực hiện hợp lý<br /><br />II. Thiết kế thuật toán<br />1. MODUL HÓA VÀ PHÂN TÍCH TOP-DOWN<br />• Các bài toán cần giải quyết trên máy tính ngày càng đa dạng, phức tạp<br />• Các thuật toán đòi hỏi có quy mô lớn, tốn nhiều thời gian và công sức<br />Bài toán cần giải quyết: A<br />Chia nhỏ bài toán thành các bài toán nhỏ: Bài toán cần giải quyết là modul<br />chính ->Chia bài toán thành các modul nhỏ hơn<br />Đây là cách tiếp cận thông thường của con người với hầu hết các vấn đề đặt ra<br />của cuộc sống.<br /><br />II. Thiết kế thuật toán<br />1. MODUL HÓA VÀ PHÂN TÍCH TOP-DOWN<br />A<br /><br />A1<br /><br />…<br /><br />A2<br /><br />A21<br /><br />A3<br /><br />A22<br /><br />2<br /><br />2/2/2017<br /><br />II. Thiết kế thuật toán<br />1. MODUL HÓA VÀ PHÂN TÍCH TOP-DOWN<br /><br />• Phương pháp phân tích top-down để giải một bài toán:<br />• Là quá trình phân tích bài toán được thực hiện từ trên<br />xuống dưới;<br />• Từ mức tổng quát là các ý tưởng giải quyết, các bước để<br />giải quyết bài toán, cho đến mức chi tiết là các câu lệnh<br />trong chương trình.<br />• Quá trình phân rã bài toán được thực hiện theo từng mức<br />khác nhau.<br /><br />II. Thiết kế thuật toán<br />1. MODUL HÓA VÀ PHÂN TÍCH TOP-DOWN<br /><br />• Phương pháp phân tích top-down để giải một bài toán:<br />• Mức có chỉ số thấp nhất (đầu tiên) được gọi là mức tổng quan. Ở mức<br />tổng quan có thể xem xét tổng thể lời giải bài toán thông qua các<br />nhiệm vụ chính.<br />• Mức tiếp theo là mức các nhiệm vụ chính để thực hiện lời giải bài toán.<br />Công việc chủ yếu ở mức này là mô tả cụ thể từng nhiệm vụ chính.<br />• Quá trình phân tích tiếp tục phân rã lời giải bài toán thành từng nhiệm<br />vụ cho tới khi nhận được các đơn thể (hàm hoặc thủ tục), trong đó mọi<br />công việc được hình dung khá rõ ràng và xác định.<br /><br />II. Thiết kế thuật toán<br />1. MODUL HÓA VÀ PHÂN TÍCH TOP-DOWN<br /><br />• Ví dụ - Bài toán: Chuẩn hóa xâu ký tự<br />Cho xâu ký tự S. Hãy sửa xâu S sao cho:<br />• Giữa hai âm tiết có đúng một dấu cách;<br />• Sau các dấu đặc biệt như dấu chấm phảy ';', dấu phảy '’,', dấu chấm<br />'.', dấu hai chấm “:” có đúng một kí tự trắng;<br />• Trước các dấu đặc biệt không có kí tự trắng và<br />• Đầu câu phải viết hoa.<br />• Ví dụ, cho S = ' học tập , phấn đấu .rèn luyện . ', cần sửa<br />thành 'Học tập, phấn đấu. Rèn luyện. '<br /><br />3<br /><br />2/2/2017<br /><br />II. Thiết kế thuật toán<br />1. MODUL HÓA VÀ PHÂN TÍCH TOP-DOWN<br /><br />• Ví dụ - Bài toán: Chuẩn hóa xâu ký tự<br />• Mức tổng quan: Hình dung toàn bộ những thao tác (nhiệm vụ chính)<br />phải thực hiện trên S. Có nhiều cách phân chia bài toán, ta xét một<br />trong nhiều cách phân chia nhiệm vụ như sau:<br />1. Xóa dấu trống ở đầu và cuối. Ví dụ, S = 'học tập , phấn đấu .rèn luyện .<br />'.<br />2. Xóa hết các kí tự trắng đứng liên tiếp: nghĩa là không để hơn một kí tự trắng đứng<br />cạnh nhau. Ví dụ S = 'học tập , phấn đấu .rèn luỵện . '.<br /><br />II. Thiết kế thuật toán<br />1. MODUL HÓA VÀ PHÂN TÍCH TOP-DOWN<br /><br />• Ví dụ - Bài toán: Chuẩn hóa xâu ký tự<br />• Mức tổng quan: Hình dung toàn bộ những thao tác (nhiệm vụ chính)<br />phải thực hiện trên S. Có nhiều cách phân chia bài toán, ta xét một<br />trong nhiều cách phân chia nhiệm vụ như sau:<br />3.<br />4.<br />5.<br /><br />Xóa hết kí tự trắng (nếu có) đứng trước các dấu “: ; , .”. Ví dụ S = 'học tập, phấn<br />đấu.rèn luyện. '.<br />Thêm kí tự trắng (nếu cần) vào sau các dấu “: ; , .”. Ví dụ S = 'học tập, phấn đấu. rèn<br />luyện. '.<br />Sửa (nếu cần) kí tự đầu câu thành viết hoa. Ví dụ S = 'Học tập, phấn đấu. Rèn luyện. '.<br /><br />II. Thiết kế thuật toán<br />1. MODUL HÓA VÀ PHÂN TÍCH TOP-DOWN<br /><br />• Ví dụ - Bài toán: Chuẩn hóa xâu ký tự<br />• Mức chi tiết 1: Mô tả chi tiết các nhiệm vụ chính<br /><br />4<br /><br />2/2/2017<br /><br />II. Thiết kế thuật toán<br />1. MODUL HÓA VÀ PHÂN TÍCH TOP-DOWN<br /><br />• Ví dụ - Bài toán: Chuẩn hóa xâu ký tự<br />• Mức chi tiết 1:<br /><br />II. Thiết kế thuật toán<br />1. MODUL HÓA VÀ PHÂN TÍCH TOP-DOWN<br /><br />• Ví dụ - Bài toán: Chuẩn hóa xâu ký tự<br />• Mức chi tiết 1:<br /><br />II. Thiết kế thuật toán<br />1. MODUL HÓA VÀ PHÂN TÍCH TOP-DOWN<br /><br />• Ví dụ - Bài toán: Chuẩn hóa xâu ký tự<br />• Mức chi tiết 1:<br /><br />5<br /><br />
1911lượt tải