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 Đệ
lượt xem 13
download
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.
Bình luận(0) Đăng nhập để gửi bình luận!
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 Đệ
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Độ 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
- Ví dụ f(n)= 3n3 + 2n2 f(n)= (n3) f(n)= (n3) f(n)= O(n3) 10
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Phân tích và thiết kế hệ thống thông tin: Chương 3 - PGS.TS. Nguyễn Mậu Hân
134 p | 48 | 6
-
Bài giảng Phân tích và thiết kế thuật toán: Bài 4 – Hà Đại Dương
23 p | 29 | 4
-
Bài giảng Phân tích và thiết kế hệ thống thông tin: Chương 1 - PGS.TS. Nguyễn Mậu Hân
82 p | 54 | 3
-
Bài giảng Phân tích và thiết kế hệ thống thông tin: Phân 1 - ĐH Phạm Văn Đồng
62 p | 59 | 3
-
Bài giảng Phân tích và thiết kế hệ thống thông tin: Chương 2 - PGS.TS. Nguyễn Mậu Hân
113 p | 46 | 3
-
Bài giảng Phân tích và thiết kế hệ thống: Chương 9 - Nguyễn Nhật Quang
44 p | 7 | 2
-
Bài giảng Phân tích và thiết kế hệ thống: Chương 6 - Nguyễn Nhật Quang
66 p | 8 | 2
-
Bài giảng Phân tích và thiết kế hệ thống: Chương 5 - Nguyễn Nhật Quang
35 p | 10 | 2
-
Bài giảng Phân tích và thiết kế hệ thống: Chương 1 - Nguyễn Nhật Quang
12 p | 15 | 2
-
Bài giảng Phân tích và thiết kế hệ thống: Chương 3.1
11 p | 73 | 2
-
Bài giảng Phân tích và thiết kế thuật toán: Bài 2 – Hà Đại Dương
25 p | 43 | 2
-
Bài giảng Phân tích và thiết kế thuật toán: Bài 3 – Hà Đại Dương
26 p | 35 | 2
-
Bài giảng Phân tích và thiết kế hệ thống: Chương 3.2
19 p | 77 | 2
-
Bài giảng Phân tích và thiết kế hệ thống: Chương 10 - Nguyễn Nhật Quang
58 p | 13 | 2
-
Bài giảng Phân tích và thiết kế thuật toán: Bài 1 – Hà Đại Dương
18 p | 36 | 1
-
Bài giảng Phân tích và thiết kế hệ thống: Chương 7 - Nguyễn Nhật Quang
71 p | 11 | 1
-
Bài giảng Phân tích và thiết kế mạng: Chương 1 – Vũ Chí Cường
14 p | 34 | 0
-
Bài giảng Phân tích và thiết kế thuật toán
26 p | 115 | 0
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn