Tiểu Luận Phân tích thiết kế thuật toán tham lam

MỤC LỤC

LỜI NÓI ĐẦU 01

PHẦN 1: BÀI TOÁN CHỌN HOẠT ĐỘNG 03

1.2. Giới thiệu bài toán 03

1.2. Cấu trúc con tối ưu của bài toán chọn hoạt động 04

1.3. Giải pháp đệ quy 06

1.4. Biến đổi một giải pháp quy hoạch động thành một giải pháp tham lam 06

1.5. Giải pháp tham lam đệ quy 08

1.6. Giải pháp tham lam lặp 09

PHẦN 2: CÁC THÀNH PHẦN CỦA CHIẾN LƯỢC THAM LAM 13

2.1. Tính lựa chọn tham lam 14

2.2. Cấu trúc con tối ưu 15

2.3. Thuật toán tham lam mâu thuẫn với quy hoạch động 16

PHẦN 3: MÃ HUFFMAN 19

3.1. Mã tiền tố 19

3.2. Xây dựng mã Huffman 22

3.3. Tính đúng đắn của giải thuật Huffman 24

PHẦN 4: CƠ SỞ LÝ THUYẾT CỦA PHƯƠNG PHÁP

THAM LAM 27

4.1. Matroid 27

4.2. Giải thuật tham lam trên một matroid trọng số 29

PHẦN 5: BÀI TOÁN LẬP LỊCH LÀM VIỆC 34

Phụ lục: CÁC BÀI TẬP TỔNG HỢP 38

1. Bài toán cái ba lô 38

2. Giải thuật xây dựng cây mã hóa Huffman 43

3. Bài toán cây khung nhỏ nhất – Thuật toán Kruskal 49

4. Bài toán cây khung nhỏ nhất – Thuật toán Prim 53

CÁC CHÚ Ý TRONG ĐỀ TÀI 58