TAILIEUCHUNG - Bài giảng Phân tích thiết kế giải thuật: Chương 2 - ĐH Bách khoa

Bài giảng Phân tích thiết kế giải thuật: Chương 2 được biên soạn nhằm trang bị cho các bạn những kiến thức về phân tích khấu hao với những nội dung chính như phương pháp để xác định phí tổn khấu hao (phương pháp gộp chung; phương pháp kế toán; phương pháp thế năng). | Phân Tích Khấu Hao Ch. 2: Amortized Analysis Phân tích khấu hao Gọi T(n) là thời gian cần thiết để thực thi một chuỗi n thao tác lên một cấu trúc dữ liệu. Ví dụ: thực thi một chuỗi PUSH, POP, MULTIPOP lên một stack. Phân tích khấu hao (amortized analysis): Thời gian thực thi một chuỗi các thao tác được lấy trung bình trên số các thao tác đã thực thi, T(n)/n , được gọi là phí tổn khấu hao. (Đây chỉ là một trong các định nghĩa của phí tổn khấu hao, các định nghĩa khác sẽ được trình bày trong các phần sau.) Ch. 2: Amortized Analysis Sơ lược Ba phương pháp để xác định phí tổn khấu hao: Phương pháp gộp chung (the aggregate method) Phương pháp kế toán (the accounting method) Phương pháp thế năng (the potential method) Sẽ minh họa các phương pháp trên thông qua việc phân tích các cấu trúc dữ liệu: stack bộ đếm nhị phân có k bits bảng động. Ch. 2: Amortized Analysis Cấu trúc dữ liệu stack Các thao tác lên một stack S PUSH(S, x) POP(S) MULTIPOP(S, k) MULTIPOP(S, k) 1 while not STACK-EMPTY(S) and k 0 2 do POP(S) 3 k k 1 Ch. 2: Amortized Analysis Bộ đếm nhị phân có k bit Bộ đếm nhị phân có k-bit (k-bit binary counter) là một mảng A[0k - 1] của các bit có độ dài, length[A], là k Dùng bộ đếm để trữ một số nhị phân x: x = A[k - 1] 2k - 1 + + A[0] 20 Để cộng 1 vào trị đang có trong bộ đếm (modulo 2k), ta dùng thủ tục sau INCREMENT(A) 1 i 0 2 while i Phân tích một stack Bài toán: xác định thời gian chạy của một chuỗi n thao tác lên một stack (ban đầu stack là trống). Giải: Bằng phân tích “thô sơ” Phí tổn trong trường hợp xấu nhất của MULTIPOP là O(n). Vậy phí tổn trong trường hợp xấu nhất của một thao tác bất kỳ lên stack là O(n). Do đó phí tổn của một chuỗi n thao tác là O(n2). Nhận xét: Chận O(n2) tìm được là quá thô. Tìm chận trên tốt hơn! Dùng phương pháp khấu hao. Ch. 2: .

• Kỹ thuật lập trình
• Phân tích thiết kế giải thuật
• Bài giảng Phân tích thiết kế giải thuật
• Kỹ thuật thiết kế giải thuật
• Thiết kế giải thuật
• Bài giảng thiết kế giải thuật
• Kỹ thuật phân tích thiết kế giải thuật
• Phân tích thuật toán
• Phương pháp phân tích thuật toán
• Vai trò của phân tích thuật toán
• Quá trình phân tích thuật toán
• Phân tích thiết kế thuật toán
• Thiết kế thuật toán
• Bài giảng Phân tích thiết kế thuật toán
• Giải thuật xấp xỉ
• Bài toán che phủ đỉnh
• Bài toán NP đầy đủ
• Phân tích thiết kế giải thuật chương 37
• Bài giảng Phân tích thiết kế
• Phân tích thiết kế dữ liệu
• Cắt tỉa Alpha Beta
• Tiêu chuẩn đánh giá giải thuật
• Phương pháp đánh giá giải thuật
• Phương pháp thiết kế thuật giải
• Thuật toán chính xác
• Thuật toán gần đúng
• Bước thiết kế một thuật giải
• Single Source Shortest Paths
• Phân tích thiết kế giải thuật chương 10
• Giải bài toán các đường đi ngắn nhất
• Biểu diễn các đường đi ngắn nhất
• Thuật toán sắp xếp
• Phân tích thuật toán sắp xếp
• Thuật toán tìm kiếm
• Phân tích thuật toán tìm kiếm
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• Cây khung nhỏ nhất
• Giải thuật tổng quát
• Giải thuật của Kruskal
• Giải thuật của Prim
• Phân tích giải thuật
• Hệ thức truy hồi
• Độ phức tạp giải thuật
• Phân tích giải thuật lặp
• Phân tích giải thuật đệ quy
• Phân tích thuật giải
• Thiết kế thuật giải
• Chiến lược thiết kế thuật giải
• Quy hoạch động
• Biểu diễn thuật giải
• Phân tích thiết kế thuật toán
• Kỹ thuật tối ưu hóa chương trình
• Mức thiết kế một chương trình
• Kỹ thuật tinh chế mã
• Kỹ thuật tối ưu hóa rẽ nhánh
• Phương pháp thiết kế thuật toán
• Tối ưu thuật toán
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Chia để trị
• Giải thuật quay lui
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• Giải thuật sắp xếp
• Chương trình sắp xếp
• Cấu trúc dữ liệu
• Giải thuật lưu trữ ngoài
• Giải thuật nâng cao
• Kỹ thuật phân tích giải thuật
• Hệ thống thông tin
• Giải thuật hình học
• Giải thuật so khớp chuỗi
• Hình học tính toán
• Giải thuật thô sơ
• Kỹ thuật quét
• Tính đúng đắn
• Kỹ thuật mã hóa
• Giải thuật đệ quy
• Thiết kế giải thuật đệ quy
• Đệ quy tuyến tính
• Đệ quy nhị phân