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

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PPT | Số trang:21

Thêm vào BST

Báo xấu

100
lượt xem 10
download

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

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).

Chủ đề:

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

Lưu

Nội dung Text: 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 TPHCM
Nộ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 con
Các mức thiết kế một chương trình 1. Đặc tả bài toán 2. Thiết kế cấu trúc hệ thống 3. Cấu trúc dữ liệu và thuật toán 4. Tinh chế mã (tối ưu hóa chương trình) 5. Tính độ phức tạp của thuật toán
Lư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;i
Kỹ 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ần
Ví dụ: Cho 2 dãy số nguyên A, B lần lượ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;x
Kỹ 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ặp
Ví dụ: Viết ct tính tổng S=1/1!+3/2!+…+(2n-1)/n!  s=0;  s=0;  for(i=1;i
Kỹ 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;i
Kỹ 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ặp
Ví dụ:Cải tiến phương pháp sắp xếp Double sort  i=1; i=1; while(i
Tối ưu hóa chương trình bằng bảng truy 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;i
Tối ưu bằng cách giảm thiểu gọi chương trình con  So sánh 2 chương trình và cho lời nhận xét