intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Bài giảng Phân tích và Thiết kế giải thuật nâng cao: Phần 1 - PGS.TS. Trần Cao Đệ

Chia sẻ: Lê Kim Luông | Ngày: | Loại File: PPT | Số trang:79

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

Bài giảng Phân tích và Thiết kế giải thuật nâng cao: Phần 1 trình bày các nội dung về KT phân tích và thiết kế giải thuật, kỹ thuật thiết kế giải thuật. Tham khảo nội dung bài giảng để nắm bắt nội dung chi tiết.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Phân tích và Thiết kế giải thuật nâng cao: Phần 1 - PGS.TS. Trần Cao Đệ

  1. Phân tích & Thiết kế Giải thuật nâng cao Advanced Algorithm Analysis and Design Bài giảng cho Thạc sĩ Ngành HTTT PGS. TS. TRẦN CAO ĐỆ Đại Học Cần Thơ 1 2014
  2. Phần 1: KT phân tích và thiết kế giải thuật PGS. TS. TRẦN CAO ĐỆ Đại Học Cần Thơ 2014 2
  3. Chương 1: KỸ THUẬT PHÂN TÍCH GIẢI THUẬT PGS. TS. TRẦN CAO ĐỆ Đại Học Cần Thơ 2014 3
  4. Thuật toán  Giải thuật / Thuật toán (algorithm) – Xuất phát từ nhà toán học Arập Al-Khowarizmi (khoảng năm 825). – Giải thuật là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán, hoặc hành động cần thực hiện ... để cho ta lời giải của bài toán.  Ví dụ thuật toán Euclid . – Input: m, n nguyên dương – Output: g (ước chung lớn nhất của m và n) – Thuật toán : – Bước 1: Tìm r, phần dư của m cho n – Bước 2:  Nếu r = 0, thì g:=n và dừng lại.  Ngược lại (r 0) ,thì m:=n; n:=r và quay lại bước 1. 4
  5. Tính chất của thuật toán  Input: Mỗi thuật toán đều có một tập các giá trị đầu vào (có thể rỗng)  Output: Mỗi thuật toán có một tập dữ liệu ra đầu ra (output), tương ứng với input.  Tính xác định: các bước của thuật toán phải xác định (các thao tác phải rõ ràng, không gây nên sự nhập nhằng).  Tính chính xác: Thuật toán phải tạo ra các giá trị đầu ra chính xác tương ứng với giá trị đầu vào. Trong cùng một điều kiện hai bộ xử lý cùng thực hiện một thuật toán phải cho cùng một kết quả như nhau.  Tính hữu hạn: Với mọi bộ dữ liệu vào (hợp lệ), thuật toán phải dừng lại sau một số hữu hạn bước thực hiện.  Tính khả thi: Các phép toán có mặt trong thuật toán phải đủ đơn giản, có thể thực hiện được trong một lượng thời gian hữu hạn (có thể thực hiện bởi con người với giấy, bút trong một khoảng thời gian hữu hạn).  Tính tổng quát: phải áp dụng được cho một lớp bài toán. 5
  6. Vấn đề giải được & không giải được  Một bài toán: – Có một hoặc nhiều thuật toán giải.  Giải được  Lựa chọn thuật toán – Không tồn tại thuật toán để giải  gọi là vấn đề không giải được (bằng thuật toán).  Vd: – KHÔNG CÓ Thuật toán chắc thắng cho người thứ hai của cờ ca rô. – KHÔNG CÓ Thuật toán xem một máy Turing có dừng lại sau n bước hay không. 6
  7. Vấn đề chứng minh thuật toán  Tiếp cận khoa học – Tính đúng đắn của thuật toán  Thuật toán đúng đắn, chính xác  Thuật toán dừng – So sánh thuật toán: phân tích độ phức tạp thời gian.  Tiếp cận thực hành – Thuật toán đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình) – Thuật toán sử dụng tiết kiệm nhất các nguồn tài nguyên của máy tính, và đặc biệt chạy nhanh nhất có thể được. 7
  8. Thời gian thực hiện chương trình  Tiếp cận 1: tính số giây,  Tiếp cận 2: theo số phép phút, giờ, ngày cần thiết để toán cơ bản mà chương chạy chương trình trình phải thực hiện – Không chính xác: – Phép toán cơ bản  Phụ thuộc tốc độ máy  Số phép +,-,*,/,=;  Phụ thuộc vào tập dữ liệu  Số chỉ thị cơ bản của máy vào: có input chạy nhanh, tính) có input chạy chậm – Độc lập tốc độ máy – Không khả thi – Vẫn phụ thuộc vào đặc tính  Chỉ thực hiện được trên của input một số input  Trường hợp xấu nhất  Không chỉ ra được sự biến  Trường hợp tốt nhất thiên của thời gian theo độ dài input  Trường hợp ngẫu nhiên 8
  9. Độ phức tạp thời gian của giải thuật  Độ phức tạp thời gian của giải  Kí hiệu O: tiệm cận trên thuật là một hàm theo kích O(g(n)) = {f(n)/ c,n0>0: thước của input, T(n). n>n0, 0 ≤ f(n) ≤ cg(n) }  So sánh độ phức tạp thời gian: so sánh theo tỷ suất tăng của Ta viết: f(n)= O(g(n)) thay cho hàm thời gian. f(n) O(g(n))  Kí hiệu : tiệm cận xấp xỉ  Kí hiệu : tiệm cận dưới (g(n)) = {f(n)/ c1,c2,n0 >0 : (g(n)) = {f(n)/ c,n0>0: n>n0 , 0 ≤ c1g(n) ≤ f(n) ≤ n>n0, 0 ≤ cg(n) ≤ f(n)} c2g(n) } Ta viết: f(n)= (g(n)) thay cho f(n) (g(n)) Ta viết: f(n)= (g(n)) thay cho f(n) (g(n)) 9
  10. Ví dụ  f(n)= 3n3 + 2n2  f(n)= (n3)  f(n)= (n3)  f(n)= O(n3) 10
  11. Tỷ suất tăng – độ phức tạp thời gian  Định lý: f(n), g(n), f(n)= (g(n))  f(n)= O(g(n)) f(n)= (g(n))  Định lý f(n) ≥ 0, g(n): f(n)= (g(n))  Định nghĩa – nếu f(n)= (g(n)) ta nói f(n) có tỷ suất tăng là g(n). – nếu f(n) biễu diễn cho một hàm thời gian thực hiện chương trình và f(n)= (g(n)), ta nói f(n) có độ phức tạp (thời gian) là g(n). (1), (1), O(1) biểu diễn cho hằng số. 11
  12. Một số hàm cổ điển  Hàm đa thức  Hàm giai thừa Xấp xỉ Stirling P(n)=O(nd) log(n!) = (nlogn) 12
  13. Tính chất của các tiệm cận  Phản xạ f(n) = (f(n)) f(n) = (f(n) f(n) = O(f(n)  Đối xứng f(n)= (g(n)) g(n)= (f(n)  Bắc cầu f(n) = (g(n)) g(n) = (h(n)) f(n)= (h(n)) f(n) = (g(n)) g(n) = (h(n)) f(n)= (h(n)) f(n) = O(g(n)) g(n) = O(h(n)) f(n)= O(h(n)) 13
  14. Các độ phức tạp thời gian Ký hiệu O() của f(x) Độ phức thời gian O(1) Hằng O(logn) Logarit O(n) Tuyến tính O(nlogn) gần tuyến tính O(n2) Bình phương O(n3) Lập phương O(2n) Mũ O(n!) Giai thừa 14
  15. Cách tính độ phức tạp thời gian của giải thuật  Giải thuật không đệ qui  Giải thuật đệ qui – Qui tắc cộng – Thiết lập công thức truy hồi – Qui tắc nhân T(n) = aT(n/b) + c(n)  Ví dụ - Giải công thức truy hồi (phương trình đệ qui) For i:=1 to n do  Ví dụ: tính độ phức tạp của a[i]:=random(1000); quicksort For i:=1 to n-1 do – T(1)=1 for j:=i+1 to n do – T(n)=2T(n/2)+n if (a[i]>a[j]) then – Giải ra T(n)=O(nlogn) swap(a[i],a[j]); 15
  16. Phương trình hồi quy  T(1)=1  T(n) = aT(n/b) + d(n), n>1  Phương pháp giải – Phương pháp thay thế (n bởi n/b) – Phương pháp tổng quát với hàm nhân – Phương pháp tổng quát (Master theorem) 16
  17. Phương pháp thay thế  T(1)=1  T(n) = 4T(n/2) + n, n>1 Giả sử n=2k hay k=log2n Thay n bởi n/2 T(n)= 4T(n/2) + n = 4(4T(n/4)+n/2) + n = 42T(n/22)+4n/2+n … = 4iT(n/2i) + 4i-1n/2i-1+…+4n/2+n (bước i) = 4kT(n/2k) + 4k-1n/2k-1+…+4n/2+n (bước k) = 4k + 4k-1n/2k-1+…+4n/2+n = 4k + n (2k-1+…2+1)= n2 + n(2k-1) = n2 + n(n-1) Vậy T(n)=O(n2) 17
  18. Phương pháp tổng quát với hàm nhân  T(1)=1  T(n)=aT(n/b) + d(n) Giả sử : n=bk k=logbn Bằng thay thế k bước ta có: T(n)= ak + ∑j=0k-1ajd(bk-j) Nghiệm Nghiệm thuần nhất riêng Nếu d là hàm nhân, tức là d(m*n) = d(m)*d(n) Thì ta có thể giải được nghiệm riêng dễ dàng ∑j=0k-1ajd(bk-j) = d(b)k ∑j=0k-1(a/d(b))j = (ak-d(b)k)/(a/d(b)-1) 18
  19. Lời giải với d(n) là hàm nhân  Nếu a>d(b): T(n)=O(nlogba)  Nếu a1 d(n)=n là hàm nhân a=4, b=2, d(b) = 2 < a Vậy T(n) = O(nlog24) = O(n2) 19
  20. Phương pháp tổng quát Master Theorem  Cho T(n) = a · T(n/b) +  Nếu f(n) = O(nlogba− ) , f(n), với n nguyên với là hằng số dương dương, a ≥ 0 và b > 1 thì T(n) = Θ(nlogba). là các hằng số; f(n) là  f(n) = Θ(nlogbalogkn), với hàm tiệm cận không âm của n k≥0 thì T(n) = Θ(nlogbalogk+1n).  Lời giải  f(n) = Ω(nlogba+ ε), với ε> 0 và f(n) thỏa af(n/b) ≤cf(n) với c< 1 thì T(n) = Θ(f(n)). 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2