Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 2: Thiết kế và đánh giá TT - Nguyễn Thị Xuân Hương

Nội dung text: Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 2: Thiết kế và đánh giá TT - Nguyễn Thị Xuân Hương

1. TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG KHOA CÔNG NGHỆ THÔNG TIN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ths. Nguyễn Thị Xuân Hương 1
2. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.1. Khái niệm về giải thuật và độ phức tạp của giải thuật. 2.1.1 Giải thuật * Quan niệm 1: giải thuật là một dãy hữu hạn các chỉ thị (mệnh lệnh) được sắp xếp theo trình tự xác định, theo đó với mọi bộ dữ liệu vào thì cho kết quả. * Quan niệm 2: (Quan niệm hình thức) + Xem giải thuật như máy Turing / Hàm tính được/ Giải thuật Mackov/ Hàm đệ qui. * Các đặc trưng của giải thuật:Tính dừng, Tính xác định, Tính rời rạc, Tính phổ dụng, Đại lượng vào – ra, Tính hiệu quả. 2
3. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.1.2 Độ phức tạp của giải thuật •Chi phí của giải thuật Mô hình lý thuyết Mô hình ứng dụng - Bộ nhớ: dung lượng nhớ - Bộ nhớ: dung lượng nhớ chứa dữ liệu: vào, ra, phụ, chứa dữ liệu: vào, ra, phụ, chương trình. chương trình. - Thời gian: Số bước hoạt - Thời gian: Số phép toán cơ động cơ bản mà giải thuật trên bản (số học và logic) thực hiện máy turing thực hiện trên bộ dữ liệu vào. •Nhận xét: Với các bộ dữ liệu vào khác nhau thì chi phí về mặt thời gian cho thuật toán là khác nhau 3 .
4. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.1.2 Độ phức tạp của giải thuật • Độ phức tạp của giải thuật: là chi phí để thực hiện giải thuật về mặt thời gian và bộ nhớ. –Độ phức tạp trung bình: Tổng số chi phí cho n bộ dữ liệu/ số bộ dữ liệu n –Độ phức tạp cực đại (xấu nhất). • Thảo luận: Tại sao phải tính độ phức tạp của giải thuật? 4
5. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.2. Phương pháp chung để đánh giá giải thuật Hàm O lớn: T(n)=O(g(n)) nếu tồn tại các hàng số c và n0 sao cho T(n) = n0 và gọi là kí pháp chữ O lớn, hàm g(n) được gọi là giới hạn trên của hàm T(n). Các quy tắc: •Quy tắc cộng : Nếu lệnh P1 có thời gian thực hiện là T1 (n) = O( f(n) và lệnh P2 có thời gian thực hiện T2(n)= O(g(n)), khi đó: T1(n) +T2(n) = O ( f(n) +g(n)). •Quy tắc nhân : Nếu đoạn chương trình P có thời gian thực hiện T(n)= O(f(n)). Khi đó nếu thực hiện k(n) lần đoạn chương trình P với k(n)=O(g(n)) thì độ phức tạp tính toán sẽ là: O(f(n)*g(n)). 5
6. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.2. Phương pháp chung để đánh giá giải thuật Các quy tắc: •Quy tắc hằng số : Nếu đoạn chương trình P có thời gian thực hiện T(n)= O(c1f(n)) với c1 là một hằng số dương thì có thể coi đoạn chương trình P có độ phức tạp tính toán là T(n)=O(f(n)). •Quy tắc lấy Max : Nếu đoạn chương trình P có thời gian thực hiện T(n)= O( f(n)+g(n)) thì có thể coi đoạn chương trình đó có độ phức tạp tính toán là T(n)= O( max ( f(n), g(n))). 6
7. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.2. Phương pháp chung để đánh giá giải thuật Một số hàm độ phức tạp giải thuật: 1.O(c) 2.O(log2n) 3.O(n) 4.O(nlog2n) 5.O(n2) 6.O(n3), O(n4) 7.O( 2n) 8.O(an) 9.O(n!) 7
8. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.2. Phương pháp chung để đánh giá giải thuật •Thảo luận : Áp dụng các qui tắc xác định độ phức tạp của giải thuật như thế nào trong chương trình ? •Bài tập: Tính độ phức tạp giải thuật cho các bài tập chương 1 8
9. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.3. Thiết kế thuật toán 2.3.1 Kỹ thuật tinh chỉnh từng bước Giải một bài toán trên máy tính: Bước 1. Xác định rõ Dữ liệu vào (Input Data), Dữ liệu ra (Output Data) của bài toán và mối quan hệ giữa chúng. 9
10. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.3. Thiết kế thuật toán Giải một bài toán trên máy tính: Bước 2. Xác định thuật toán: a) Lựa chọn thuật toán • Mỗi thuật toán chỉ giải một bài toán nào đó, có thể có nhiều thuật toán khác nhau cùng giải một bài toán -> chọn một thuật toán phù hợp. • Quan tâm đến hai yếu tố: thời gian và bộ nhớ • Thực tế, người ta còn quan tâm đến tính đơn giản của thuật toán. • Căn cứ vào lượng tài nguyên mà thuật toán đòi hỏi và lượng tài nguyên thực tế cho phép. b) Diễn tả thuật toán: Liệt kê, sơ đồ khối hoặc ngôn ngữ lập10 trình
11. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.3. Thiết kế thuật toán Giải một bài toán trên máy tính: Bước 3: Viết chương trình: Là quá trình làm mịn dần, • Thể hiện dữ liệu vào, dữ liệu ra, dữ liệu trung gian bằng các cấu trúc dữ liệu lựa chọn trong NNLT • Hướng các bước thực hiện thuật toán về câu lệnh của ngôn ngữ lập trình. 11
12. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.3. Thiết kế thuật toán Giải một bài toán trên máy tính: Chú ý: Để xây dựng thuật toán giải, thông thướng ta hay áp dụng chiến lược chia để trị: Ý tưởng: chia bài toán ban đầu thành nhiều bài toán con cho đến khi nhận được các bài toán con có thể dễ dàng đưa ra lời giải, giải các bái toán con đó rôi tìm cách kết hợp nghiệm của các bài toán co để cho nghiệm của bài toán con lớn hơn, thực hiện cho đến khi tìm được nghiệm của bài toán ban đầu 12
13. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.3. Thiết kế thuật toán 2.3.1 Kỹ thuật tinh chỉnh từng bước VD: Cho một dãy số nguyên có n phần tử. Hãy tím số x cho trước xem x có xuất hiện trên dãy không? Giải: B1: Input: Dãy n phần tử a0, a1, an-1; số x Output: X có xuất hiện trên dãy hoặc không 13
14. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.3. Thiết kế thuật toán 2.3.1 Kỹ thuật tinh chỉnh từng bước B1: Xác đinh thuật toán C1: Duyệt lần lượt từng phần tử trên dãy và so sánh với số x, nếu số x = một giá trị ai nào trên dãy -> kết thúc và thông báo kết quả; ngược lại, khi đã duyệt hết mà không có ai nào =x thì thông báo là không tìm thấy/ 14
15. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.3. Thiết kế thuật toán 2.3.1 Kỹ thuật đệ quy •Định ngĩa đệ quy: trong nó chứa một thành phần của chính nó với kích thước nhỏ hơn. VD: 1. n! = 1 nếu n =0 n*(n-1)! nếu n>0 2. uscln(a,b) = a nếu b=0 uscln (b, a%b) nếu b 2 15
16. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.3. Thiết kế thuật toán 2.3.1 Kỹ thuật đệ quy •Hàm đệ qui: trong thân hàm chứa lời gọi đến chính nó (đệ quy trực tiếp) Hoặc chứa lời gọi đến hàm khác mà ham này chứa lới gọi đến nó (đệ quy gián tiếp). - Hoạt động của đệ quy: Khi thực hiện một hàm đệ qui, hàm sẽ phải chạy rất nhiều lần, trong mỗi lần chạy chương trình sẽ tạo nên một tập biến cục bộ mới trên ngăn xếp (các tham số, các biến riêng khai báo trong hàm) độc lập với lần chạy trước đó, từ đó dễ gây tràn ngăn xếp. - Đối với những bài toán có thể giải được bằng phương pháp lặp thì không nên dùng đệ qui. 16
17. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.3. Thiết kế thuật toán 2.3.1 Kỹ thuật đệ quy VD: Hàm tính n! Tính bằng phương pháp lặp: Phương pháp đệ quy: double gt(int n) double gt(int n) { { double F, int i; if (n==0) return 1; F = 1; else return n*gt(n-1); for ( i =1; i > n; cout << gt(n); } 17
18. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.3. Thiết kế thuật toán 2.3.1 Kỹ thuật đệ quy Cấu trúc của một hàm đệ quy: (ds tham số hình thức) { if (trường hợp suy biến) { trình bày cách giải // có thể giải ngay } else // trường hợp tổng quát { gọi lại hàm với tham số có “kích thước nhỏ hơn” } } 18
19. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.3. Thiết kế thuật toán 2.3.1 Kỹ thuật đệ quy Giải bài toán bằng kỹ thuật đệ quy: 1. Có trường hợp suy biến (có thể đưa ra lới giải ngay) 2. Lời gọi đệ quy 3. Hàm làm giảm kích thước của bộ dữ liệu Thảo luận: -Thuật toán Đệ quy có ưu, nhược điểm gì? - Ưu điểm: dễ dàng thiết kế thuật toán - Nhược điểm: tốn thời gian và bộ nhớ -Khi nào thì nên sử dụng giải thuật đệ quy? 19
20. Chương 2: THIẾT KẾ VÀ ĐÁNH GIÁ TT 2.3. Thiết kế thuật toán 2.3.1 Kỹ thuật đệ quy Khử đệ quy: loại bỏ lời gọi đệ quy trong thân hàm -C1: Sử dụng vòng lặp -C2: Sử dụng ngăn xếp (Stack) 20