TAILIEUCHUNG - Bài giảng Phân tích thiết kế giải thuật - Chương 7: Các cấu trúc dữ liệu cho các tập rời nhau

Bài giảng Chương 7: Các cấu trúc dữ liệu cho các tập rời nhau trình bày nội dung chính về các thao tác lên cấu trúc dữ liệu các tập rời nhau, ứng dụng của các tập rời nhau, biểu diễn các tập rời nhau dùng danh sách liên kết. Mời các bạn tham khảo. | Các Cấu Trúc Dữ Liệu cho các Tập Rời Nhau Chương 7: C¸ác cấu trúc dữ liệu cho các tập rời nhau Các thao tác lên cấu trúc dữ liệu các tập rời nhau Cấu trúc dữ liệu các tập rời nhau được định nghĩa bởi Một tập S của các tập động rời nhau, S = {S1 , S2 ,., Sk} Mỗi tập Si được tượng trưng bởi một phần tử đại diện là một phần tử nào đó của nó. Các thao tác MAKE-SET(x): tạo một tập mới chỉ gồm x. Vì các tập là rời nhau nên x không được đang nằm trong một tập khác. UNION(x, y): tạo tập hội của các tập động Sx và Sy lần lượt chứa x và y, với điều kiện là Sx và Sy là rời nhau. FIND-SET(x): trả về một con trỏ chỉ đến phần tử đại diện của tập chứa x. Để cho gọn, sẽ dùng “các tập rời nhau” để gọi “cấu trúc dữ liệu các tập rời nhau”. Chương 7: C¸ác cấu trúc dữ liệu cho các tập rời nhau Các thao tác lên các tập rời nhau (tiếp) Phân tích thời gian chạy của các thao tác sẽ dựa trên hai tham số sau n, số các thao tác MAKE-SET m, số tổng cộng các thao tác MAKE-SET, UNION, và FIND-SET. Nhận xét: Sau n 1 lần gọi UNION lên các tập rời nhau thì còn lại đúng một tập. m n. Chương 7: C¸ác cấu trúc dữ liệu cho các tập rời nhau Một ứng dụng của các tập rời nhau Xác định các thành phần liên thông của một đồ thị vô hướng Thủ tục CONNECTED-COMPONENTS xác định các thành phần liên thông của một đồ thị vô hướng. V[G] là tập các đỉnh của đồ thị G, E[G] là tập các cạnh của G. CONNECTED-COMPONENTS(G) 1 for mỗi đỉnh v V[G] 2 do MAKE-SET(v) 3 for mỗi cạnh (u, v) E[G] 4 do if FIND-SET(u) FIND-SET(v) 5 then UNION(u, v) Chương 7: C¸ác cấu trúc dữ liệu cho các tập rời nhau Một ứng dụng của các tập rời nhau (tiếp) Thủ tục SAME-COMPONENT xác định hai đỉnh có cùng một thành phần liên thông hay không. SAME-COMPONENT(u, v) 1 if FIND-SET(u) = FIND-SET(v) 2 then return TRUE 3 else return FALSE Chương 7: C¸ác cấu trúc dữ liệu cho các tập rời nhau Thao tác lên các tập rời nhau Ví dụ: một đồ thị với 4 thành phần .

• 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
• Cấu trúc dữ liệu
• Cấu trúc dữ liệu các tập rời nhau
• Các thao tác lên cấu trúc dữ liệu
• Ứng dụng của các tập rời nhau
• 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
• 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