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...
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:
- bai_giang_thiet_ke_va_danh_gia_thuat_toan_phan_tich_thuat_to.pdf