›
›

Bài giảng Mạng và hệ thống thông tin - Chương 1: Mở đầu về thuật toán và độ phức tạp - Nguyễn Văn Hạnh

Download
Chương 1  
Mở đầu về thuật toán  
và độ phức tạp  
Nguyễn Văn Hạnh  
Bộ môn Mạng và hệ thống thông tin  
Email: nvhanh@vnua.edu.vn  
Webpage: http://fita.vnua.edu.vn/nvhanh/  
Nội dung  
1. Thuật toán và độ phức tạp  
2. Đánh giá độ phức tạp thuật toán như thế nào?  
3. Dùng O(f(n)) để đánh giá độ phức tạp của thuật toán  
4. Các quy tắc để đánh giá độ phức tạp thuật toán  
5. Các thuật toán cơ bản và độ phức tạp  
Định nghĩa thuật toán  
Thuật toán: 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: Tìm UCLN của hai số nguyên dương.  
1. Input: 
m
,
n
là 2 số nguyên dương  
2. Output: 
g
(UCLN của 
m
và
n
)  
3. Phương pháp:  
Bước 1: Tìm 
r
, phân dư của phép chia
m
cho
n
.  
Bước 2: Nếu 
r
= 0
, thì
g
:=
n
(gán giá trị của
n
cho
g
) và dừng  
lại. Ngược lại (
r
≠
0
), thì
m
:=
n
;
n
:=
r
và quay lại bước 1.  
Các yêu cầu về thuật toán  
1. Input: là các giá trị cần đưa vào khi thuật toán bắt đầu làm việc. Ví dụ  
trong thuật toán Euclid, input là 2 số nguyên dương 
m
,
n
.  
2. Output: là các giá trị có quan hệ hoàn toàn xác định với các dữ liệu  
input, và là kết quả của sự thực hiện thuật toán. Ví dụ trong thuật toán  
Euclid, output là UCLN
g
.  
3. Tính xác định:  
Ở mỗi bước, các thao tác phải rõ ràng, không gây nên sự nhập  
nhằng.  
Thuật toán cần được mô tả trong các ngôn ngữ lập trình: các mệnh  
đề được tạo theo các quy tắc cú pháp nghiêm ngặt và chỉ có một  
nghĩa duy nhất.  
4. Tính khả thi: các phép toán có thể được thực hiện trực tiếp.  
5. Tính dừng: thuật toán phải dừng sau một số hữu hạn bước thực hiện.  
Vấn đề giải được và không giải được  
1. Vấn đề giải được: là vấn đề có thuật toán giải. Ví dụ, tìm nghiệm của hệ  
phương trình tuyến tính là vấn đề giải được.  
2. Vấn đề không giải được: là vấn đề không tồn tại thuật toán giải. Ví dụ,  
thuật toán chắc thắng cho người thứ 2 của cờ ca rô; thuật toán xác định  
xem một máy Turing có dừng lại sau
n
bước hay không.  
Các vấn đề liên quan đến thuật toán  
1. Thiết kế thuật toán: một số kỹ thuật thiết kế thuật toán:  
Phương pháp chia để trị (divide-and-conque)  
Phương pháp tham lam (greedy method)  
Phương pháp quy hoạch động  
•
•
•
2. Tính đúng đắn của thuật toán: khi thuật toán được thực hiện sẽ cho kết  
quả đúng với mọi dữ liệu vào hợp lệ.  
3. Phân tích thuật toán: với một bài toán có một số thuật giải
→
cần phân  
tích, đánh giá độ phức tạp của thuật toán để lựa chọn thuật toán nào.  
Đánh giá hiệu quả của thuật toán  
Hai tiêu chuẩn để lựa chọn thuật toán:  
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, chạy nhanh nhất có thể được: tính hiệu quả của thuật toán:  
Dung lượng không gian nhớ cần thiết để lưu các dữ liệu vào, các  
kết quả tính toán trung gian và kết quả của thuật toán.  
•
Thời gian để thực hiện thuật toán: một thuật toán hiệu quả nếu  
có thời gian chạy ít hơn so với các thuật toán khác.  
•
Biểu diễn thuật toán  
Phương pháp biểu diễn thuật toán:  
Phương pháp liệt kê từng bước  
Phương pháp sơ đồ khối  
Ngôn ngữ lập trình  
•
•
•
Phương pháp liệt kê từng bước  
Thuật toán: Giải phương trình bậc hai
ax
2
+
bx
+
c
= 0  
Bước 1: Xác định các hệ số a, b, c  
•
Bước 2: Kiểm tra các hệ số a, b, c có khác 0 hay không? Nếu a = 0 quay  
lại thực hiện bước 1.  
•
Bước 3: Tính 
Δ
=
b
2
−
4
ac  
•
•
Bước 4: Nếu
Δ
< 0
thông báo PT vô nghiệm và chuyển sang bước 8  
−b  
2
a  
Bước 5: Nếu
Δ
= 0
, tính x1 = x2 = và chuyển sang bước 7  
•
•
−b ∓ Δ  
Bước 6: Tính x1,2 =  
và chuyển sang bước 7  
2
a  
Bước 7: Thông báo các nghiệm x
1
,
x
2  
Bước 8: Kết thúc thuật toán  
•
•
Phương pháp sơ đồ khối  
Thuật toán: Giải phương trình bậc hai
ax
2
+
bx
+
c
= 0  
Ngôn ngữ lập trình Python  
Thuật toán: Giải phương trình bậc hai
ax
2
+
bx
+
c
= 0  
Độ phức tạp của thuật toán  
Tại sao lại cần thuật toán có hiệu quả?  
Đối với một vấn đề có thể có nhiều thuật toán giải, trong số đó có thể thuật  
toán này hiệu quả hơn thuật toán kia (chạy nhanh hơn).  
•
Đánh giá thời gian thực hiện thuật toán như thế nào?  
1. Phương pháp thử nghiệm: viết chương trình và cho chạy chương trình với  
các dữ liệu vào khác nhau trên một máy tính nào đó. Thời gian chạy chương  
trình phụ thuộc vào các nhân tố:  
Các dữ liệu vào  
•
•
•
Chương trình dịch để chuyển chương trình thành mã máy  
Tốc độ thực hiện các phép toán của máy tính được sử dụng  
→
không thể biểu diễn chính xác thời gian chạy là bao nhiêu đơn vị thời gian  
chuẩn.  
Độ phức tạp của thuật toán  
Đánh giá thời gian thực hiện thuật toán như thế nào?  
2. Phương pháp lý thuyết:  
Ta sẽ coi thời gian thực hiện thuật toán như là hàm số của cỡ dữ liệu vào.  
•
•
Cỡ của dữ liệu vào là một tham số đặc trưng cho dữ liệu vào, có ảnh hưởng  
quyết định đến thời gian thực hiện chương trình. Thông thường cỡ của dữ liệu  
vào là một số nguyên dương
n
.  
Ta sẽ sử dụng hàm số
T
(
n
)
, trong đó
n
là cỡ dữ liệu vào, để biểu diễn thời gian  
•
•
thực hiện một thuật toán.  
Thời gian thực hiện
T
(
n
)
là số phép toán sơ cấp cần phải tiến hành khi thực  
hiện thuật toán. Ví dụ các phép toán số học
+,
−
, * , /
 
và các phép toán so sánh  
= , < , > ,
≤
,
≥
là các phép toán sơ cấp.  
Độ phức tạp của thuật toán  
Ví dụ: xét bài toán xác định một đối tượng
a
có trong danh sách
n
phần tử  
(
a
1
,
a
2
, …
 
,
a
n
)
.  
So sánh a với từng phần tử có trong danh sách đi từ đầu tới cuối danh sách  
•
•
•
Khi gặp phần tử a
i
đầu tiên thoả mãn a
i
=
a thì dừng lại  
Hoặc khi đến cuối danh sách mà không gặp a
i
nào bằng a thì trong trường hợp  
này a không có trong danh sách.  
Các dữ liệu vào là a và danh sách
(
a
1
,
a
2
, …
 
,
a
n
)
. Cỡ của dữ liệu vào là
n
.  
Nếu xem thời gian thực hiện
T
(
n
)
là số các phép so sánh, ta có
T
(
n
)
≤
n
.  
T
(
n
) =
n
là độ phức tạp của thuật toán trong trường hợp xấu nhất.  
•
•
•
•
Độ phức tạp trung bình của thuật toán là thời gian trung bình T
tb
(
n
)
trên tất cả  
các dữ liệu vào cỡ
n
.  
Dùng O(f(n)) để đánh giá độ phức tạp của thuật toán  
Định nghĩa  
Giả sử
n
là số nguyên dương. T(n) và f(n) là các hàm thực không âm. Ta  
viết T(n) = O(f(n)) nếu và chỉ nếu tồn tại các hằng số dương c
,
n
0
sao cho  
T
(
n
)
≤
cf
(
n
)
, với mọi n
≥
n
0
.  
•
Nếu một thuật toán có độ phức tạp T(n) = O(f(n)), ta nói thuật toán có độ  
phức tạp cấp f(n).  
•
Ví dụ: Giả sử
T
(
n
) = 3
n
2
+ 4
n
+ 5
. Ta có  
T
(
n
)
≤
3
n
2
+ 4
n
2
+ 5
n
2
= 12
n
2, với mọi
n
≥
1
.  
Vậy
T
(
n
) =
O
(
n
2
)
: thuật toán có độ phức tạp cấp
n
2  
Dùng O(f(n)) để đánh giá độ phức tạp của thuật toán  
Tính chất  
Nếu T(n) = O(f(n)) và f(n) = O(g(n)) thì T(n) = O(g(n)).  
•
Thật vậy, T(n) = O(f(n)) và f(n) = O(g(n)) nên tồn tại c
1
,
c
2
,
n
1
,
n
2
để  
T
(
n
)
≤
c
1
f
(
n
)
với mọi n
≥
n
1
và f
(
n
)
≤
c
2
g
(
n
)
với mọi n
≥
n
2
.  
•
Khi đó T
(
n
)
≤
c
1
c
2
g
(
n
)
với mọi n
≥
n
0
=
max
(
n
1
,
n
2
)
. Nên ta có T(n) =  
•
O(g(n)).  
Khi biểu diễn cấp của độ phức tạp thuật toán bởi hàm f(n), ta sẽ chọn f(n)  
là hàm nhỏ nhất, đơn giản nhất có thể sao cho T(n) = O(f(n)).  
•
Dùng O(f(n)) để đánh giá độ phức tạp của thuật toán  
Danh sách sắp xếp theo thứ tự tăng dần của độ phức tạp thuật toán  
Dùng O(f(n)) để đánh giá độ phức tạp của thuật toán  
Ví dụ:  
Thuật toán A có độ phức tạp T
A
(
n
) =
O
(
n2
)
, thuật toán B có độ phức tạp  
T
B
(
n
) =
O
(
nlogn
)
.  
•
Với n = 1024, thuật toán A cần 1048576 phép toán sơ cấp, còn thuật toán B  
cần 10240 phép toán sơ cấp.  
•
•
•
•
Nếu cần 1 micro-giây cho một phép toán sơ cấp thì thuật toán A cần  
khoảng 1,05 giây, thuật toán B cần khoảng 0,01 giây.  
Với n = 1024x2 = 2048 thì thuật toán A cần khoảng 4,2 giây, thuật toán B  
cần khoảng 0,02 giây.  
Với n càng lớn thì thuật toán A càng đòi hỏi thời gian thực hiện nhiều hơn  
rất nhiều so với thuật toán B.  
Các quy tắc để đánh giá độ phức tạp của thuật toán  
Quy tắc tổng: Nếu T
1
(
n
) =
O
(
f
1
(
n
))
và T
2
(
n
) =
O
(
f
2
(
n
))
thì  
T
1
(
n
) +
T
2
(
n
) =
O
(
max
(
f
1
(
n
),
f
2
(
n
)))  
Áp dụng: Giả một thuật toán được phân thành 3 phần với độ phức tạp của  
từng phần lần lượt là T
1
(
n
) =
O
(1);
T
2
(
n
) =
O
(
n2
)
và T
3
(
n
) =
O
(
n
)
. Khi đó  
độ phức tạp của thuật toán là:  
•
T
(
n
) =
T
1
(
n
) +
T
2
(
n
) +
T
3
(
n
) =
O
(
max
(1,
n2
,
n
)) =
O
(
n2
)  
Quy tắc để đánh giá độ phức tạp của các câu lệnh đơn, khối  
1. Câu lệnh (đơn): các phép gán, đọc, viết, goto có độ phức tạp O(1).  
2. Lệnh hợp thành (hoặc khối): S
1
,
S
2
, …
 
,
S
n
là câu lệnh thì  
Begin S
1
,
S
2
, …
 
,
S
n
End  
gọi là lệnh hợp thành: Độ phức tạp được xác định bằng luật tổng.  
Tải về để xem bản đầy đủ
pdf 35 trang yennguyen 13580 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Mạng và hệ thống thông tin - Chương 1: Mở đầu về thuật toán và độ phức tạp - Nguyễn Văn Hạnh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_mang_va_he_thong_thong_tin_chuong_1_mo_dau_ve_thua.pdf