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

Dưới đây là bài giảng Phân tích thiết kế giải thuật: Chương 5 - Heap nhị thức. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về các heap hợp nhất được; thời gian chạy của các thao tác lên heaps hợp nhất được; định nghĩa cây nhị thức; đặc tính của cây nhị thức; tính chất của heap nhị thức và một sô kiến thức khác. | Chương 5: Heap nhị thức Các heap hợp nhất được Một heap hợp nhất được (mergeable heap) là một cấu trúc dữ liệu hỗ trợ năm thao tác sau (gọi là các thao tác heap hợp nhất được). MAKE-HEAP() tạo và trả về một heap trống. INSERT(H, x) chèn nút x, mà trường key của nó đã được điền, vào heap H . MINIMUM(H) trả về một con trỏ chỉ đến nút trong heap H mà khóa của nó là nhỏ nhất. EXTRACT-MIN(H) tách ra nút có khóa nhỏ nhất khỏi H, và trả về một con trỏ chỉ đến nút đó. UNION(H1, H2) tạo và trả về một heap mới chứa tất cả các nút của các heaps H1 và H2 . Các heaps H1 và H2 sẽ bị hủy bởi thao tác này. Chương 5: Heap nhị thức Thời gian chạy của các thao tác lên heaps hợp nhất được n là số nút của heap Thủ tục heap heap heap nhị phân nhị thức Fibonacci (worst-case) (worst-case) (khấu hao) MAKE-HEAP (1) (1) (1) INSERT (lg n) O(lg n) (1) MINIMUM (1) O(lg n) (1) EXTRACT-MIN (lg n) (lg n) O(lg n) UNION (n) O(lg n) (1) DECREASE-KEY (lg n) (lg n) (1) DELETE (lg n) (lg n) O(lg n) Chương 5: Heap nhị thức Heap nhị thức Các thao tác khác DECREASE-KEY(H, x, k) gán vào nút x trong heap H trị mới k của khóa, k nhỏ hơn hay bằng trị hiện thời của khóa. DELETE(H, x) xóa nút x khỏi heap H. Nhận xét: Heap nhị thức không hổ trợ thao tác SEARCH hữu hiệu. Do đó, các thao tác DECREASE-KEY và DELETE cần một con trỏ đến nút cần được xử lý. Chương 5: Heap nhị thức Định nghĩa cây nhị thức Chương 5: Heap nhị thức Định nghĩa cây nhị thức Cây nhị thức Bk với k = 0, 1, 2, là một cây có thứ tự được định nghĩa đệ quy: Cây nhị thức B0 gồm một nút duy nhất. Cây nhị thức Bk gồm hai cây nhị thức Bk - 1 được liên kết với nhau theo một cách nhất định: Nút gốc của cây này là con bên trái nhất của nút gốc của cây kia. Chương 5: Heap nhị thức Đặc tính của cây nhị thức Lemma (Đặc tính của một cây nhị thức) Cây nhị thức Bk có các tính chất sau: 1. có 2k nút, 2. chiều cao của cây là k, 3. có đúng nút tại độ sâu i với i = 0, .

• 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
• Heap nhị thức
• Tính chất cây nhị thức
• Đặc tính cây nhị thức
• Heaps hợp nhất được
• 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