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

Bài giảng Phân tích thiết kế giải thuật: Chương 4 - B-Cây bao gồm những nội dung về cấu trúc dữ liệu trong bộ nhớ ngoài; truy cập đĩa; các thao tác lên một đĩa; hệ số phân nhánh; định nghĩa của B-cây; các thao tác lên một B-cây và một số nội dung khác. | Ch. 4: B-Trees B-Cây Ch. 4: B-Trees Cấu trúc dữ liệu trong bộ nhớ ngoài B-cây tổng quát hoá cây tìm kiếm nhị phân. “Hệ số phân nhánh” (branching factor) B-cây là cây tìm kiếm cân bằng được thiết kế để làm việc hữu hiệu trong bộ nhớ ngoài (đĩa cứng). Bộ nhớ chính (main memory) Bộ nhớ ngoài (secondary storage) Disk Track Page Thời gian chạy gồm số các truy cập vào đĩa thời gian CPU Ch. 4: B-Trees Truy cập đĩa Một nút của B-cây thường chiếm nguyên cả một disk page. Hệ số phân nhánh tùy thuộc vào tỉ lệ giữa kích thước của khóa và kích thước của disk page. Ch. 4: B-Trees Các thao tác lên một đĩa Cho x là một con trỏ đến một đối tượng (ví dụ: một nút của một B-cây). Đối tượng x có thể có nhiều trường Nếu x nằm trong bộ nhớ chính, truy cập các trường của x như thường lệ, ví dụ như key[x], leaf [x],. Nếu x còn nằm trên đĩa thì dùng DISK-READ(x) để đọc nó vào bộ nhớ chính. Nếu x đã thay đổi thì dùng DISK-WRITE(x) để trữ nó vào đĩa. Cách làm việc tiêu biểu với một đối tượng x . x một con trỏ đến một đối tượng nào đó DISK-READ(x) các thao tác truy cập/thay đổi các trường của x DISK-WRITE(x) các thao tác không thay đổi một trường của x . Ch. 4: B-Trees Hệ số phân nhánh Ví dụ một B-cây mà: mỗi nút có 1000 khóa (số trong mỗi nút là số khóa nó chứa), tức là B-cây có hệ số phân nhánh là 1001 1000 1000 1000 1000 1000 1000 1000 1001 1001 1001 1001 1 nút 1000 khóa 1001 nút khóa nút khóa root[T] Ch. 4: B-Trees Định nghĩa của B-cây Một B-cây T là một cây có gốc, mà gốc là root[T], có các tính chất sau Mỗi nút x có các trường sau n[x], số lượng khóa đang được chứa trong nút x các khóa: có n[x] khóa, được xếp theo thứ tự không giảm, tức là key1[x] key2[x] keyn[x ][x] leaf [x], có trị bool là TRUE nếu x là một lá FALSE nếu x là một nút trong Mỗi nút trong x chứa n[x] 1 con trỏ c1 [x], c2 [x], , cn[x ]+1[x] đến các nút con của nó. Ch. 4: . | Ch. 4: B-Trees B-Cây Ch. 4: B-Trees Cấu trúc dữ liệu trong bộ nhớ ngoài B-cây tổng quát hoá cây tìm kiếm nhị phân. “Hệ số phân nhánh” (branching factor) B-cây là cây tìm kiếm cân bằng được thiết kế để làm việc hữu hiệu trong bộ nhớ ngoài (đĩa cứng). Bộ nhớ chính (main memory) Bộ nhớ ngoài (secondary storage) Disk Track Page Thời gian chạy gồm số các truy cập vào đĩa thời gian CPU Ch. 4: B-Trees Truy cập đĩa Một nút của B-cây thường chiếm nguyên cả một disk page. Hệ số phân nhánh tùy thuộc vào tỉ lệ giữa kích thước của khóa và kích thước của disk page. Ch. 4: B-Trees Các thao tác lên một đĩa Cho x là một con trỏ đến một đối tượng (ví dụ: một nút của một B-cây). Đối tượng x có thể có nhiều trường Nếu x nằm trong bộ nhớ chính, truy cập các trường của x như thường lệ, ví dụ như key[x], leaf [x],. Nếu x còn nằm trên đĩa thì dùng DISK-READ(x) để đọc nó vào bộ nhớ chính. Nếu x đã thay đổi thì dùng DISK-WRITE(x) để trữ nó vào đĩa. Cách

• 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
• Truy cập đĩa
• Định nghĩa của B cây
• Thao tác lên một B cây
• Tìm trong một B cây
• 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