tailieunhanh - Bài giảng Phân tích thiết kế thuật toán: Chương 4 - Nguyễn Văn Linh

Bài giảng "Phân tích thiết kế thuật toán - Chương 4: Cấu trúc dữ liệu và giải thuật lưu trữ ngoài" cung cấp cho người học các kiến thức: Mô hình và đánh giá các xử lý ngoài, sắp xếp ngoài, lưu trữ thông tin trong tập tin. nội dung chi tiết. | CHƯƠNG 4: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT LƯU TRỮ NGOÀI Nguyễn Văn Linh Khoa Công nghệ Thông tin & Truyền thông ĐẠI HỌC CẦN THƠ nvlinh@ Nguyễn Văn Linh NỘI DUNG Mục tiêu. Mô hình và đánh giá các xử lý ngoài. Sắp xếp ngoài. Lưu trữ thông tin trong tập tin: Tập tin tuần tự Tập tin bảng băm Tập tin chỉ mục Tập tin B-cây MỤC TIÊU Biết mô hình xử lý ngoài. Hiểu tiêu chuẩn để đánh giá giải thuật xử lý ngoài. Vận dụng trong việc cải tiến giải thuật xử lý ngoài. Hiểu giải thuật sắp xếp trộn để sắp xếp ngoài và phương pháp cải tiến tốc độ sắp xếp trộn. Hiểu cách thức tổ chức lưu trữ và các giải thuật tìm kiếm, xen, xoá thông tin trên các tập tin tuần tự, tập tin chỉ mục, tập tin bảng băm. Vận dụng được cách thức tổ chức lưu trữ và các giải thuật tìm kiếm, xen, xoá thông tin trên tập tin B-cây. Tại sao phải xử lí ngoài Trong các giải thuật mà chúng ta đã đề cập từ trước tới nay, chúng ta đã giả sử rằng số lượng các dữ liệu vào là khá nhỏ để có thể chứa hết ở bộ nhớ trong (main memory). Nhưng điều gì sẽ xảy ra nếu ta muốn xử lý phiếu điều tra dân số toàn quốc hay thông tin về quản lý đất đai cả nước chẳng hạn? Trong các bài toán như vậy, số lượng dữ liệu vượt quá khả năng lưu trữ của bộ nhớ trong. Ðể có thể giải quyết các bài toán đó chúng ta phải dùng bộ nhớ ngoài để lưu trữ và xử lý. Các thiết bị lưu trữ ngoài như băng từ, đĩa từ đều có khả năng lưu trữ lớn nhưng đặc điểm truy nhập hoàn toàn khác với bộ nhớ trong. Chúng ta cần tìm các cấu trúc dữ liệu và giải thuật thích hợp cho việc xử lý dữ liệu lưu trữ trên bộ nhớ ngoài Mô hình xử lí ngoài Hệ điều hành chia bộ nhớ ngoài thành các khối (block) có kích thước bằng nhau, kích thước này thay đổi tùy thuộc vào hệ điều hành nhưng nói chung là từ 512 bytes đến 4096 bytes. Có thể xem một tập tin bao gồm nhiều mẩu tin được lưu trong các khối. Mỗi khối lưu một số nguyên vẹn các mẩu tin. Kiểu dữ liệu tập tin là kiểu thích hợp nhất cho việc biểu diễn dữ liệu được lưu trong bộ nhớ ngoài. Bộ nhớ trong Bộ nhớ ngoài Bộ nhớ | CHƯƠNG 4: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT LƯU TRỮ NGOÀI Nguyễn Văn Linh Khoa Công nghệ Thông tin & Truyền thông ĐẠI HỌC CẦN THƠ nvlinh@ Nguyễn Văn Linh NỘI DUNG Mục tiêu. Mô hình và đánh giá các xử lý ngoài. Sắp xếp ngoài. Lưu trữ thông tin trong tập tin: Tập tin tuần tự Tập tin bảng băm Tập tin chỉ mục Tập tin B-cây MỤC TIÊU Biết mô hình xử lý ngoài. Hiểu tiêu chuẩn để đánh giá giải thuật xử lý ngoài. Vận dụng trong việc cải tiến giải thuật xử lý ngoài. Hiểu giải thuật sắp xếp trộn để sắp xếp ngoài và phương pháp cải tiến tốc độ sắp xếp trộn. Hiểu cách thức tổ chức lưu trữ và các giải thuật tìm kiếm, xen, xoá thông tin trên các tập tin tuần tự, tập tin chỉ mục, tập tin bảng băm. Vận dụng được cách thức tổ chức lưu trữ và các giải thuật tìm kiếm, xen, xoá thông tin trên tập tin B-cây. Tại sao phải xử lí ngoài Trong các giải thuật mà chúng ta đã đề cập từ trước tới nay, chúng ta đã giả sử rằng số lượng các dữ liệu vào là khá nhỏ để có thể chứa hết ở bộ nhớ trong (main .

crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.