Bài giảng Phân tích thiết kế giải thuật: Chương 3 - Trịnh Huy Hoàng

Bài giảng Phân tích thiết kế giải thuật: Chương 3 của Trịnh Huy Hoàng bao gồm những nội dung về kỹ thuật tối ưu hóa chương trình (các mức thiết kế một chương trình, các kỹ thuật tối ưu hóa chương trình như kỹ thuật tinh chế mã, kỹ thuật tối ưu hóa rẽ nhánh, kỹ thuật tối ưu hóa các vòng lặp tối ưu hóa chương trình bằng bảng truy cập, tối ưu bằng cách giảm thiểu gọi chương trình con).
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế giải thuật: Chương 3 - Trịnh Huy Hoàng Chương 3:Kỹ thuật tối ưu hóa chương trình Trịnh Huy Hoàng Khoa Công nghệ thông tin Đại học Sư phạm TPHCMNội dung Các mức thiết kế một chương trình Các kỹ thuật tối ưu hóa chương trình – Kỹ thuật tinh chế mã – Kỹ thuật tối ưu hóa rẽ nhánh – Kỹ thuật tối ưu hóa các vòng lặp – Tối ưu hóa chương trình bằng bảng truy cập – Tối ưu bằng cách giảm thiểu gọi chương trình conCác mức thiết kế một chương trình1. Đặc tả bài toán2. Thiết kế cấu trúc hệ thống3. Cấu trúc dữ liệu và thuật toán4. Tinh chế mã (tối ưu hóa chương trình)5. Tính độ phức tạp của thuật toánLưu ý Trước khi viết chương trình: + Không nên mã hóa 1 chương trình ngay khi chỉ mới có ý tưởng đầu tiên mà phải xem xét tất cả các mức thiết kế có thể để chọn ra 1 thiết kế làm tăng tốc nhanh nhất với phí tổn ít nhất. + Nên thử nhiều mức thiết kế khác nhau bằng cách giải quyết bài toán trên nhiều mặt từ đó chọn được 1 thiết kế tối ưu về không gian và thời gian.Kỹ thuật tinh chế mã Tacó thể tối ưu chương trình về mặt thời gian hoặc không gian (rất khó thực hiện được cả hai), nếu muốn tối ưu cả hai khía cạnh trên thì ta phải thay đổi thuật toán. Ở chương này ta xét các kỹ thuật tối ưu chương trình về mặt cấu trúc, tìm 1 thuật giải có độ phức tạp tốt nhất có thể.Ví dụ 1: Viết chương trình tính tổng S=1+x/1!+x2/2!+…+xn/n! s=1;  s=1;p=1; for(i=1;iKỹ thuật tối ưu hóa rẽ nhánh Quitắc 1: Sắp xếp biểu thức điều kiện dạng A1 and A2 and …An theo xác suất sai của các điều kiện Aigiảm dần Quitắc 2: Sắp xếp biểu thức điều kiện dạng A1 or A2 or …An theo xác suất đúng của các điều kiện Ai giảm dầnVí dụ: Cho 2 dãy số nguyên A, B lầnlượt có số phần tử là m và n. A=B? if((m=n)&& Chua(a,b) && Chua(b,a) printf(“Hai day bang nhau”); else printf(“Hai day khong bang nhau”); Ví dụ: Nhập số tự nhiên n, nếu n là số có 1 trong các tính chất (lẻ, nguyên tố, chính phương, hoàn hảo) thì thực hiện S1, ngược lại S2. if (le(n)||nguyento(n)||chinhphuong(n)||hoanhao(n)) printf(“Thuc hien S1”); else printf(“Thuc hien S2”);Kỹ thuật tối ưu hóa các vòng lặp Quitắc 1: Giảm số vòng lặp bằng cách thực hiện nhiều hơn cho mỗi vòng lặp và chú ý vòng lặp ít hơn thì đặt ở ngoài.Ví dụ: Giải bài toán cổ (gà - chó…) for(x=1;xKỹ thuật tối ưu hóa các vòng lặp Quitắc 2: Tách các lệnh không phụ thuộc vào chỉ số lặp ra khỏi vòng lặpVí dụ: Viết ct tính tổngS=1/1!+3/2!+…+(2n-1)/n! s=0;  s=0; for(i=1;iKỹ thuật tối ưu hóa các vòng lặp Qui tắc 3: Hợp các vòng lặp có thể Ví dụ: Viết ct tính tổng các phần tử trên đường chéo chính (S1) và đường chéo phụ (S2) của 1 ma trận vuông cấp ns1=0; s1=0;for(i=1;iKỹ thuật tối ưu hóa các vòng lặp Qui tắc 4: Làm nhiều hơn trong 1 vòng lặpVí dụ:Cải tiến phương pháp sắp xếpDouble sort i=1; i=1; while(iTối ưu hóa chương trình bằng bảngtruy cập Nếu viết các hệ số trong khai triển nhị thức Newton ta có thể thiết kế đoạn chương trình sau: Int ckn(int k,int n) { if((k==0)||(k==n)) return 1; else return ckn(k,n-1)+ckn(k-1,n-1);}Cải tiến for(i=1;iTối ưu bằng cách giảm thiểu gọichương trình con So sánh 2 chương trình và cho lời nhận xét