Bài giảng Thiết kế và đánh giá thuật toán - Phân tích thuật tóan - Lê Nguyên Khôi

Tóm tắt Bài giảng Thiết kế và đánh giá thuật toán - Phân tích thuật tóan - Lê Nguyên Khôi: ...rước khi vòng for lặp bắt đầu  Duy trì: đúng trước một lần lặp thì đúng trước lần lặp tiếp theo  Kết thúc: tính bất biến giúp chứng minh thuật toán đúng 9 Chứng Minh Quy Nạp – Induction Proof  Trường hợp cơ bản (base case)  Trường hợp quy nạp (inductive case)  Chứng minh tính “Duy trì”...ậm chạy nhanh với một số dữ liệu đầu vào 13 Sắp Xếp Chèn – Mã Giả InsertionSort (5) 1 for 7 ← 2 to 5. 9: ;<= do 2 >:? ← 5[7] 3 B ← 7 − 1 4 while B > 0 and 5 B > >:? do 5 5 B + 1 ← 5[B] 6 B ← B − 1 7 5 B + 1 ← >:? Mã giả xem tr.18, tr.20 – 22 14 Sắp Xếp Chèn – Phân Tíc...rt) 19 Bài Tập – Exercise 2.1-4 Cộng 2 số n-bit:  Cho 2 số nguyên nhị phân n-bit, lưu trong 2 mảng n-phần tử A & B. Tổng 2 số này lưu trong mảng n+1-phần tử C dưới dạng nhị phân.  Viết mã giả cho thuật toán cộng 2 số này.  Phân tích độ phức tạp của thuật toán. 20 Bài Tập – Exercise 2.1...

pdf29 trang | Chia sẻ: havih72 | Lượt xem: 293 | Lượt tải: 0download
Nội dung tài liệu Bài giảng Thiết kế và đánh giá thuật toán - Phân tích thuật tóan - Lê Nguyên Khôi, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Thiết Kế & Đánh Giá Thuật Toán
Phân Tích Thuật Toán
TS. Lê Nguyên Khôi
Trường Đại Học Công Nghệ - ĐHQGHN
Nội Dung
 Thuật toán
 Bài toán sắp xếp
 Sắp xếp chèn
 Phân tích thời gian chạy sắp xếp chèn
1
Thuật Toán
 Một thủ tục tính toán được định nghĩa rõ ràng
 Một chuỗi các bước tính toán
 Nhận một tập các giá trị đầu vào
 Trả một tập các giá trị đầu ra
 Tính đúng đắn: với tất cả các tập giá trị đầu
vào, thuật toán đưa ra tập giá trị đầu ra đúng
2
Bài Toán
 Sắp xếp
 Tìm kiếm
 Mạng Internet (Định tuyến dữ liệu)
 Thương mại điện tử
 Doanh nghiệp sản xuất
 Đường đi ngắn nhất
 Chuỗi chung dài nhất
 Vân vân 
3
Một Số Vấn Đề Khác
 Cấu trúc dữ liệu
 Cách lưu trữ và tổ chức dữ liệu tạo điều kiện truy
cập và thay đổi một cách dễ dàng
 Hiệu quả:
 P: thuật toán có thể chạy trong thời gian đa thức
 NP-complete: không thể chạy trong khoảng thời gian
hợp lý
 Song song:
 Nhiều phép tính mỗi giây bằng nhiều lõi
4
Bài Toán Sắp Xếp
 Input: một dãy số , ,  , 
 Output: tổ hợp của dãy trên  ,  ,  ,  sao
cho  ≤  ≤ ⋯ ≤ 
 Ví dụ:
 Input: 8 2 4 9 3 6
 Output: 2 3 4 6 8 9
 Hiệu quả:
 Thời gian chạy của thuật toán sắp xếp dãy số?
 Thuật toán tốt nhất (chạy nhanh nhất)?
5
Thuật Toán Sắp Xếp
 Sắp xếp chèn (Insertion sort): 

 Sắp xếp trộn (Merge sort): 
 log 
 Với 
 = 2; 
 = 50;  = 10.000.000
 Sắp xếp chèn:
  	é	í
 	é	í/"#â% = 20.000	giây ≈ 5,5	giờ	
 Sắp xếp trộn:
*	.		.	+," é	í
	é	í/"#â% ≈ 1.163	giây < 20	phút
 Khi nào s.x. chèn nhanh hơn s.x. trộn?
6
Sắp Xếp Chèn – Minh Họa
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
2 3 4 8 9 6
2 3 4 6 8 9
7
Sắp Xếp Chèn – Mã Giả
InsertionSort (5)
1 for 7 ← 2 to 5. 9:;<= do
2 >:? ← 5[7]
3 B ← 7 − 1
4 while B > 0 and 5 B > >:? do
5 5 B + 1 ← 5[B]
6 B ← B − 1
7 5 B + 1 ← >:?
Mã giả xem tr.18, tr.20 – 22
8
Sắp Xếp Chèn – Tính Đúng Đắn
 Khái niệm tính bất biến (loop invariant):
 Bắt đầu mỗi vòng lặp for dãy con 5[1 7 − 1] chính
là dãy ban đầu nhưng đã được sắp xếp.
 Khởi tạo: đúng trước khi vòng for lặp bắt đầu
 Duy trì: đúng trước một lần lặp thì đúng trước
lần lặp tiếp theo
 Kết thúc: tính bất biến giúp chứng minh thuật
toán đúng
9
Chứng Minh Quy Nạp – Induction Proof
 Trường hợp cơ bản (base case)
 Trường hợp quy nạp (inductive case)
 Chứng minh tính “Duy trì” sử dụng chứng
minh quy nạp:
 Cho rằng 5[1> − 1] đã được sắp xếp
 Chỉ ra 5[1>] cũng được sắp xếp
 Xem chứng minh tr.19 – 20
10
Phân Tích Thuật Toán – Giả Định
 Kiến trúc Random Access Machine
 Xử lý tuần tự các phép toán
 Các phép toán (thao tác) cơ bản
=, +, -, *, /, %, , , 
load, store, copy, 
điều khiển, rẽ nhánh, 
Mỗi phép toán thực hiện trong thời gian cố
định 
 (cận trên)
 Dữ liệu đầu vào  được biểu diễn 
 log  bit
 Không bộ nhớ ảo, cache
11
Phân Tích Thuật Toán – Thời Gian Chạy
 Thời gian chạy phụ thuộc vào dữ liệu đầu
vào: dãy đã sắp xếp ≠ dãy chưa sắp xếp
 Thời gian chạy phụ thuộc vào độ lớn dữ
liệu đầu vào: dãy ngắn ≠ dãy dài
 Thông thường xét cận trên (trường hợp
xấu nhất)
12
Phân Tích Thuật Toán – Thời Gian Chạy
 Trường hợp xấu nhất: (thông thường)
 F() = thời gian lâu nhất thuật toán chạy với dữ liệu
đầu vào cỡ  bất kỳ
 Trường hợp trung bình: (đôi khi)
 F() = thời gian trung bình thuật toán chạy với tất cả
dữ liệu đầu vào
 Cần giả thiết về hàm phân phối xác xuất cho dữ liệu
đầu vào
 Trường hợp tốt nhất: (hiếm)
 Lợi dụng thuật toán chậm chạy nhanh với một số dữ
liệu đầu vào
13
Sắp Xếp Chèn – Mã Giả
InsertionSort (5)
1 for 7 ← 2 to 5. 9:;<= do
2 >:? ← 5[7]
3 B ← 7 − 1
4 while B > 0 and 5 B > >:? do
5 5 B + 1 ← 5[B]
6 B ← B − 1
7 5 B + 1 ← >:?
Mã giả xem tr.18, tr.20 – 22
14
Sắp Xếp Chèn – Phân Tích Thời Gian
InsertionSort (5)
15
1 
  for 7 ← 2 to 5. 9:;<= do
2 
  − 1 >:? ← 5[7]
3 
G  − 1 B ← 7 − 1
4 
H I<J

JK
while B > 0 and 5 B > >:? do
5 
* I<J − 1

JK
5 B + 1 ← 5[B]
6 
L I<J − 1

JK
B ← B − 1
7 
M  5 B + 1 ← >:?
Sắp Xếp Chèn – Phân Tích Thời Gian
 Tổng thời gian:
F 
= 
 + 
  − 1 + 
G  − 1 + 
H I<J

JK
+ 
* I<J − 1

JK
+ 
L I<J − 1

JK
+ 
M  − 1
 <J: số lần lặp vòng while
16
Sắp Xếp Chèn – Phân Tích Thời Gian
 Trường hợp tốt nhất (<J = 1):
F 
= 
 + 
  − 1 + 
G  − 1
+ 
H  − 1 + 
M  − 1
= 
 + 
 + 
G + 
H + 
M  + N
=  + N
 F  hàm tuyến tính
 Khi mảng đã sắp xếp tăng dần
17
Sắp Xếp Chèn – Phân Tích Thời Gian
 Trường hợp xấu nhất
F 
= 
 + 
  − 1 + 
G  − 1
+ 
H
  + 1
2 − 1 + 
*
  − 1
2
+ 
L
  − 1
2 + 
M  − 1
=   +   +  =  + N + 
 F  hàm bậc hai
 Khi mảng đã sắp xếp giảm dần
18
Bài Tập
 Exercise: 2.1-4 tr.22
 Cộng 2 số n-bit
 Exercise: 2.2-2 tr.29
 Sắp xếp lựa chọn (selection sort)
 Problem: 2-2 tr.40
 Sắp xếp nổi bọt (bubble sort)
19
Bài Tập – Exercise 2.1-4
Cộng 2 số n-bit:
 Cho 2 số nguyên nhị phân n-bit, lưu trong 2 
mảng n-phần tử A & B. Tổng 2 số này lưu trong
mảng n+1-phần tử C dưới dạng nhị phân.
 Viết mã giả cho thuật toán cộng 2 số này.
 Phân tích độ phức tạp của thuật toán.
20
Bài Tập – Exercise 2.1-4
BinaryAdder (5, O, P, )
1 Q:RBS:Q ← 0
2 for 7 ←  downto 1 do
3 P 7 + 1 ← 5 7 + O 7 + Q:RBS:Q
4 Q:RBS:Q ← P 7 + 1 	div	2
5 P 7 + 1 ← P 7 + 1 	mod	2
6 P 1 ← Q:RBS:Q
Thời gian chạy:
F  = 
 + 
  + 1 + 
G + 
H + 
* + 
L
= 
 + 
G + 
H + 
*  + N =  + N
21
Bài Tập – Exercise 2.2-2
Sắp xếp lựa chọn (selection sort):
 Sắp xếp n số trong mảng A theo cách tìm phần
tử nhỏ nhất của A và đổi chỗ với A[1]. Tìm
phần tử nhỏ nhất thứ hai của A và đổi chỗ với
A[2]. Tiếp tục như vậy cho n-1 phần tử đầu tiên
của A.
 Viết mã giả cho thuật toán trên.
 Tính bất biến (loop invariant) của thuật toán?
 Tại sao chỉ cần chạy với n-1 phần tử đầu tiên.
 Phân tích độ phức tạp của thuật toán (trường
hợp tốt nhất & xấu nhất)
22
Bài Tập – Exercise 2.2-2
SelectionSort (5)
1 for B ← 1 to 5. 9:;<= − 1 do
2 WR99:W< ← B
3 for 7 ← B + 1 to 5. 9:;<= do
4 if 5 7 < 5[WR99:W<]
5 WR99:W< ← 7
6 exchange 5 B with 5[WR99:W<]
23
Bài Tập – Exercise 2.2-2
SelectionSort (5)
Thời gian chạy:
F 
= 
 + 
  − 1 + 
G I<J

JK
+ 
H I<J − 1

JK
+ 
* I<J − 1

JK
+ 
L I<J − 1

JK
=   +   +  =  + N + 
24
Bài Tập – Problem 2-2
 Sắp xếp nổi bọt (bubble sort):
25
Bài Tập – Problem 2-2
BubbleSort (5)
1 do
2 :X
= ← Y9W:
3 for 7 ← 5. 9:;<= downto 2 do
4 if 5 7 < 5[7 − 1]
5 exchange 5 7 with 5 7 − 1
6 :X
= ← <QZ:
7 while (:X
= = <QZ:)
26
Bài Tập – Problem 2-2
BubbleSort (5)
1 for B ← 1 to 5. 9:;<= − 1 do
2 for 7 ← 5. 9:;<= downto B + 1 do
3 if 5 7 < 5[7 − 1]
4 exchange 5 7 with 5[7 − 1]
27
Tổng Kết
 Phân tích thời gian chạy dựa trên độ lớn
dữ liệu đầu vào
 Phân tích thời gian chạy thuật toán trong
trường hợp xấu nhất
 Thời gian chạy của sắp xếp chèn là hàm
bậc hai đối với độ lớn dữ liệu đầu vào
28

File đính kèm:

  • pdfbai_giang_thiet_ke_va_danh_gia_thuat_toan_phan_tich_thuat_to.pdf