Tìm kiếm
Đang tải khung tìm kiếm
Kết quả 1 đến 1 của 1

    THẠC SĨ Tìm kiếm thông tin dựa vào cấu trúc dữ liệu Heap

    D
    dream dream Đang Ngoại tuyến (18495 tài liệu)
    .:: Cộng Tác Viên ::.
  1. Gửi tài liệu
  2. Bình luận
  3. Chia sẻ
  4. Thông tin
  5. Công cụ
  6. Tìm kiếm thông tin dựa vào cấu trúc dữ liệu Heap

    Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


    iv
    MỤC LỤC

    Lời cam đoan . i
    Lời cảm ơn . iii
    Mục lục iv
    Danh mục các bảng . vi
    Danh mục các hình vii
    MỞ ĐẦU 1
    1. Lý do chọn đề tài 1
    2. Đối tượng và phạm vi nghiên cứu 2
    3. Những nội dung nghiên cứu chính . 2
    4. Phương pháp nghiên cứu 3
    5. Ý nghĩa khoa học của đề tài 3
    Chương 1. KHÁI QUÁT VỀ TÌM KIẾM VÀ VẤN ĐỀ TỔ CHỨC DỮ LIỆU 4
    1.1. Khái quát về tìm kiếm . 4
    1.1.1 Thông tin 4
    1.1.2. Một số loại tìm kiếm thông tin 7
    1.1.2.1. Tìm kiếm trên danh sách 7
    1.1.2.3. Tìm kiếm đường đi . 11
    1.2. Tổ chức dữ liệu trong tìm kiếm thông tin 13
    1.2.1. Giới thiệu 13
    1.2.2. Một số cấu trúc dữ liệu 15
    1.2.2.1. Stack 15
    1.2.2.2. Queue 15
    1.2.2.4. Heap 16
    Chương 2. MỘT SỐ THUẬT TOÁN THAO TÁC TRONG HEAP . 18
    2.1. Biểu diễn Heap 18
    Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


    v
    2.2. Khởi tạo Heap rỗng . 19
    2.3. UpHeap . 19
    2.4. DownHeap 27
    2.5. Thêm một phần tử vào Heap . 36
    2.6. Đọc một phần tử đỉnh Heap 37
    2.7. Lấy một phần tử ở gốc khỏi Heap . 38
    2.8. Cập nhật một phần tử trong Heap 40
    2.9. Tìm kiếm đường đi theo lựa chọn tốt nhất . 42
    Chương 3. XÂY DỰNG CHƯƠNG TRÌNH TÌM ĐƯỜNG ĐI TRONG THÀNH
    PHỐ THANH HÓA . 46
    3.1. Phân tích yêu cầu bài toán . 46
    3.2. Phân tích, lựa chọn công cụ . 48
    3.2.1. Mô tả dữ liệu 48
    3.2.2 Thiết kế các bước thực hiện . 48
    3.2.3. Ngôn ngữ lập trình 51
    3.3. Một số kết quả chương trình 51
    KẾT LUẬN . 55
    TÀI LIỆU THAM KHẢO 56
    Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


    vi
    DANH MỤC CÁC BẢNG
    Trang
    Bảng 2.1. Biểu diễn Heap bằng mảng 1 chiều 18
    Bảng 2.2. Bảng kết quả tính toán theo thuật toán . 44
    Bảng 3.1. Trọng số các cạnh của đồ thị 49

    Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


    vii
    DANH MỤC CÁC HÌNH
    Trang
    Hình 1.1. Thông tin dạng văn bản . 5
    Hình 1.2. Thông tin dạng hình ảnh . 6
    Hình 1.3. Thông tin dạng âm thanh 6
    Hình 1.4. Mô hình Stack trong thực tế 15
    Hình 1.5. Mô hình Queue trong thực tế 16
    Hình 1.6. Heap Max chứa các phần tử có thể giống nhau 17
    Hình 2.1. Chỉ số con trái và con phải một nút trong Heap . 18
    Hình 2.2. Heap Max trong quá trình UpHeap . 20
    Hình 2.3. Vị trí cần UpHeap . 21
    Hình 2.4. Gán giá trị Heap[9] = 7 . 21
    Hình 2.5. Gán giá trị Heap[4] = 8 . 22
    Hình 2.6. Gán giá trị Heap[2] = 9 và kết thúc . 22
    Hình 2.7. Sơ đồ thuật toán UpHeap 23
    Hình 2.8. Đổi chỗ 2 giá trị Heap[9] và Heap[4] cho nhau 25
    Hình 2.9. Đổi chỗ 2 giá trị Heap[4] và Heap[2] cho nhau 25
    Hình 2.10. Sơ đồ thuật toán UpHeap dùng đệ qui 26
    Hình 2.11. Heap Max trong quá trình UpHeap . 28
    Hình 2.12. Heap[1] bị thay đổi giá trị . 28
    Hình 2.13. Gán giá trị mới cho Heap[1] . 29
    Hình 2.14. Gán giá trị mới cho Heap[2] . 29
    Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


    vii
    i
    Hình 2.15. Gán giá trị mới cho Heap[4] . 30
    Hình 2.16. Gán giá trị mới cho Heap[9] . 30
    Hình 2.17. Sơ đồ thuật toán DownHeap . 31
    Hình 2.18. Heap[1] bị thay đổi giá trị trong UpHeap đệ qui 33
    Hình 2.19. Đổi chỗ Heap[2] và Heap[1] cho nhau . 33
    Hình 2.20. Đổi chỗ Heap[4] và Heap[2] cho nhau . 34
    Hình 2.21. Đổi chỗ Heap[9] và Heap[4] cho nhau . 34
    Hình 2.22. Sơ đồ thuật toán DownHeap dùng đệ quy 35
    Hình 2.23. Sơ đồ thuật toán thêm một phần tử vào Heap . 37
    Hình 2.24. Sơ đồ thuật toán đọc một phần tử ở đỉnh Heap . 38
    Hình 2.25 Sơ đồ thuật toán lấy một phần tử ở đỉnh Heap 39
    Hình 2.26. Cập nhật Heap . 40
    Hình 2.27. Sơ đồ khối thuật toán cập nhật một phần tử trong Heap 41
    Hình 2.28. Minh họa đường đi 43
    Hình 3.1. Bản đồ giao thông thành phố Thanh Hóa . 47
    Hình 3.2. Một vùng bản đồ giao thông của thành phố Thanh Hóa . 49
    Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


    1
    MỞ ĐẦU
    1. Lý do chọn đề tài
    Hiện nay, công nghệ thông tin với tốc độ phát triển rất nhanh. Các nhà
    khoa học khẳng định rằng chưa có một ngành khoa học – công nghệ nào lại
    có nhiều ứng dụng rộng rãi như công nghệ thông tin. Việc ứng dụng công
    nghệ thông tin trong giáo dục đã trở thành mối ưu tiên hàng đầu của nhiều
    quốc gia, trong đó có Việt Nam. Sự tiến bộ về công nghệ và sự phổ cập của
    các hệ thống phần mềm tiên tiến đã đưa đến những sự thay đổi cách đào tạo
    chuyên gia trong lĩnh vực tin học. Các kiến thức giải thuật được coi là đỉnh
    cao trước đây bây giờ đã trở thành “bảng cửu chương” mà ai cũng phải biết
    và phải thuộc. Những giải thuật ít dùng và phức tạp thì không nhất thiết phải
    biết hoặc nhớ vì bất cứ ai và lúc nào cũng có thể tra cứu, tìm kiếm chúng trên
    internet khi cần thiết. Thử thách bây giờ là ở chỗ ta có thể tìm ra những giải
    pháp hữu hiệu giải quyết một cách có hiệu quả các bài toán, các vấn đề có mô
    hình toán học đơn giản nhưng có kích thước lớn hay không?
    Để đạt được mục đích đó, người lập trình phải tận dụng tối đa khả năng
    mà phần cứng và hệ điều hành cung cấp, khai thác tối đa khả năng của công
    cụ lập trình, sử dụng linh hoạt các cấu trúc dữ liệu. Trong đó, Heap là một cấu
    trúc dữ liệu quan trọng, có nhiều ứng dụng trong tính toán, truy vấn cơ sở dữ
    liệu và xử lí tín hiệu. Bên cạnh đó, việc tìm kiếm đường đi tối ưu bằng các
    phương pháp của khoa học tính toán với nguồn dữ liệu khổng lồ để cho ra kết
    quả nhanh và chính xác nhất.
    Trong khuôn khổ luận văn thạc sĩ, tôi chọn đề tài nghiên cứu: “Tìm
    kiếm thông tin dựa vào cấu trúc dữ liệu Heap”, nghiên cứu về Heap và thực
    hiện một phương pháp tiếp cận mới, nhanh chóng và linh hoạt để tìm đường
    đi tối ưu trong thành phố Thanh Hóa.
    Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


    2
    2. Đối tượng và phạm vi nghiên cứu
    Đối tượng và phạm vi nghiên cứu của luận văn tập trung vào tìm hiểu
    về Heap và từ đó xây dựng ứng dụng tìm đường đi trong thành phố thành phố
    Thanh Hóa.
    3. Những nội dung nghiên cứu chính
    Chương 1. Khái quát về tìm kiếm và vấn đề tổ chức dữ liệu
    Trong ngành khoa học máy tính tìm kiếm là một thuật toán lấy đầu vào
    là một bài toán và trả về kết quả là một lời giải cho bài toán đó, thường là sau
    khi cân nhắc giữa một loạt các lời giải có thể. Hầu hết các thuật toán được
    nghiên cứu bởi các nhà khoa học máy tính để giải quyết các bài toán đều là
    các thuật toán tìm kiếm.
    Vấn đề tổ chức dữ liệu là công việc hết sức quan trọng, khi ta có một
    thuật toán tốt và chọn lựa cấu trúc dữ liệu phù hợp để lưu trữ thì bài toán được
    giải quyết một cách nhanh chóng. Đôi khi một bài toán có thuật toán tốt
    nhưng chúng ta lại chọn lựa cấu trúc dữ liệu không phù hợp thì có thể dẫn đến
    việc giải quyết bài toán đó trở nên khó khăn và phức tạp hơn.
    Chương 2. Một số thuật toán thao tác trong Heap
    Khi làm việc với Heap, thì trên Heap có một số thao tác nhưng nó có hai
    thao tác rất quan trọng là DownHeap và UpHeap.
    Chương 3. Xây dựng chương trình tìm đường đi trong thành phố
    Thanh Hóa
    Đây là chương trình ứng dụng tìm đường đi ngắn nhất giữa hai địa điểm
    bất kỳ trong thành phố Thanh Hóa. Nó giúp người sử dụng chọn nhanh và chính
    xác được đường đi tối ưu nhất.
    Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


    3
    4. Phương pháp nghiên cứu
    Phương pháp nghiên cứu lí thuyết: Tổng hợp tài liệu, suy diễn, quy
    nạp, các phương pháp hình thức, .
    Phương pháp thực nghiệm: xử lí thống kê, đối sánh, .
    Phương pháp trao đổi khoa học, tổng hợp các kết quả của các nhà
    nghiên cứu liên quan đến lĩnh vực nghiên cứu, lấy ý kiến chuyên gia.
    5. Ý nghĩa khoa học của đề tài
    Đề tài đưa ra một phương pháp nhanh chóng, hiệu quả và linh hoạt để
    tìm Min, Max trong một tập hợp động. Điều này mang ý nghĩa thiết thực
    trong việc hỗ trợ tìm đường đi tối ưu trong thành phố Thanh Hóa.

    Xem Thêm: Tìm kiếm thông tin dựa vào cấu trúc dữ liệu Heap
    Nội dung trên chỉ thể hiện một phần hoặc nhiều phần trích dẫn. Để có thể xem đầy đủ, chi tiết và đúng định dạng tài liệu, bạn vui lòng tải tài liệu. Hy vọng tài liệu Tìm kiếm thông tin dựa vào cấu trúc dữ liệu Heap sẽ giúp ích cho bạn.
    #1
  7. Đang tải dữ liệu...

    Chia sẻ link hay nhận ngay tiền thưởng
    Vui lòng Tải xuống để xem tài liệu đầy đủ.

    Gửi bình luận

    ♥ Tải tài liệu

social Thư Viện Tài Liệu

Từ khóa được tìm kiếm

Nobody landed on this page from a search engine, yet!

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
DMCA.com Protection Status