Nghiên cứu khoa học: Cây 2-3-4 - Lý thuyết và mô phỏng

Đề tài nghiên cứu khoa học "Cây 2-3-4 - Lý thuyết và mô phỏng" được thực hiện nhằm tìm hiểu và đánh giá các thuật toán trên cây 2-3-4, đồng thời xây dựng một phần mềm mô phỏng các thuật toán này nhằm hỗ trợ cho việc học, nghiên cứu và tiến tới dạy các thuật toán trên cây 2-3-4. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Nghiên cứu khoa học: Cây 2-3-4 - Lý thuyết và mô phỏngCây 2-3-4 – Lý thuyết và mô phỏngNghiên Cứu Khoa HọcMỤC LỤC----------------------------------------------------------------------------------1LỜI MỞ ĐẦUI.LÝ DO CHỌN ĐỀ TÀI---------------------------------------------------2II.MỤC ĐÍCH NGHIÊN CỨU ĐỀ TÀI-----------------------------------2III.NHIỆM VỤ NGHIÊN CỨU ĐỀ TÀI-----------------------------------3IV. ĐỐI TƢỢNG NGHIÊN CỨU--------------------------------------------3V.PHƢƠNG PHÁP NGHIÊN CỨU----------------------------------------3PHẦN NỘI DUNG-------------------------------------------------------------------------4CHƢƠNG 1. LÝ THUYẾT CÂY 2-3-4---------------------------------------------4I.Giới thiệu về cây 2-3-4.-----------------------------------------------------4II.Tổ chức cây 2-3-4.----------------------------------------------------------6III.Tìm kiếm.---------------------------------------------------------------------8IV.Tách node.-------------------------------------------------------------------81. Tách node con.------------------------------------------------------------82. Tách node gốc.----------------------------------------------------------113. Tách theo hướng đi xuống.--------------------------------------------12V.Chèn node.------------------------------------------------------------------14VI.Tính hiệu quả của Cây 2-3-4---------------------------------------------15VII. Chuyển từ cây 2-3-4 sang cây đỏ đen.----------------------------------16CHƢƠNG 2. MÔ PHỎNG THUẬT TOÁN TRÊN CÂY 2-3-4--------------21I.Tổng quan về mô phỏng thuật toán.-------------------------------------211. Khái niệm thuật toán và các đặc trưng của thuật toán.----------212. Khái niệm mô phỏng thuật toán.-------------------------------------21II.Các yêu cầu mô phỏng thuật toán.--------------------------------------22III.Quá trình thiết kế nhiệm vụ mô phỏng thuật toán.--------------------23IV.Mô phỏng thuật toán trên Cây 2-3-4------------------------------------231. Giới thiệu ngôn ngữ mô phỏng.--------------------------------------232. Phân tích và thiết kế thuật toán mô phỏng.------------------------24a. Phân tích.-----------------------------------------------------------24b. Thiết kế.-------------------------------------------------------------24TÀI LIỆU THAM KHẢO---------------------------------------------------------------36Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT1Cây 2-3-4 – Lý thuyết và mô phỏngNghiên Cứu Khoa HọcLỜI MỞ ĐẦUI. Lý do chọn đề tàiTrong hai thập kỉ qua, mô phỏng thuật toán đã được các nhà sư phạm củangành công nghệ thông tin sử dụng như một công cụ hỗ trợ cho việc giảng dạy cácthuật toán trên máy tính. Nguyên nhân của việc mô phỏng thuật toán được sử dụngnhư một công cụ trợ giúp cho việc giảng dạy là do nó có thể cung cấp các môphỏng động bằng đồ họa của một thuật toán và các thay đổi trong cấu trúc dữ liệucủa nó trong suốt quá trình thực thi.Như một phần của quá trình học thuật toán, việc mô phỏng các thuật toáncòn góp phần giúp các em học sinh, sinh viên khi mới bắt đầu làm quen với giảithuật có thể vừa dễ dàng theo dõi các bước duyệt ở lý thuyết vừa nhìn thấy cácbước chạy ở thực tế như thế nào. Tư đó có thể giúp các em tư duy thuật toánnhanh hơn và ngày càng yêu thích giải thuật.Mô phỏng thuật toán ngày càng trở nên hữu ích và trở thành một giáo cụtrực quan rất quan trọng trong hầu hết các lĩnh vực, nhất là trong môi trường giáodục. Với các nhà sư phạm của ngành công nghệ thông tin thì mô phỏng thuật toáncó tác dụng như một tài liệu hướng dẫn trong việc dạy các thuật toán bằng máytính.Cây 2-3-4 là một cây nhị phân tìm kiếm giải quyết tốt hơn các trường hợpxấu nhất cho cây nhị phân tìm kiếm bình thường. Và đây còn là một nội dung khámới mẻ và phức tạp đối với nhiều học sinh, sinh viên. Vì vậy vấn đề “Cây 2-3-4 –Lý thuyết và mô phỏng” được chọn làm đề tài nghiên cứu.II. Mục đích nghiên cứu đề tàiMục đích nghiên cứu của khóa luận này nhằm tìm hiểu và đánh giá cácthuật toán trên Cây 2-3-4, đồng thời xây dựng một phần mềm mô phỏng các thuậttoán này nhằm hỗ trợ cho việc học, nghiên cứu và tiến tới dạy các thuật toán trênCây 2-3-4.Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT2Cây 2-3-4 – Lý thuyết và mô phỏngNghiên Cứu Khoa HọcIII .Nhiệm vu nghiên cứu đề tài.Nghiên cứu tổng quan về mô phỏng thuật toán, các yêu cầu, phương pháptiếp cận, phương pháp thiết kế một mô đun mô phỏng thuật toán.Thiết kế minh họa các mô đun minh họa các thuật toán trên Cây2-3-4.IV. Đối tượng nghiên cứu.Đề tài nghiên cứu đi sâu vào nghiên cứu và cài đặt một số thuật toán:- Thuật toán tìm kiếm trên Cây 2-3-4- Thuật toán chèn một node và chèn một giá trị vào Cây 2-3-4- Thuật toán tách node trên Cây 2-3-4- Thuật toán xóa node và xóa một giá trị trên Cây 2-3-4V. Phưong pháp nghiên cứu.Phương pháp nghiên cứu chủ yếu tham khảo các tài liệu tham khảo liênquan đến Cây nhị phân tìm ki ...