TAILIEUCHUNG - Bài giảng Phân tích và Thiết kế giải thuật nâng cao: Chương 4 - PGS.TS. Trần Cao Đệ

Bài giảng Phân tích và Thiết kế giải thuật nâng cao: Chương 4 nhằm giúp bạn đọc hiểu hơn về các vấn đề của giải thuật hình học như dữ liệu nhiều chiều, cây tìm kiếm phạm vi, tìm kiếm 1 chiều trong phạm vi, hiệu quả của giải thuật,. Tham khảo nội dung bài giảng để nắm bắt nội dung chi tiết. | Chương 4: Các giải thuật hình học Computational Geometry PGS. TS. TRẦN CAO ĐỆ Đại Học Cần Thơ 2013 Dữ liệu nhiều chiều Các giải thuật hình học liên quan tới dữ liệu không gian đa chiều. Một điểm trong mặt phẳng (x,y) Một điểm trong không gian (x,y,z) Các ứng dụng máy học, xử lí ảnh cần xử lí dữ liệu hàng trăm, hàng ngàn chiều. Các bài toán thống kê, điều khiển cũng cần xử lí dữ liệu nhiều chiều Một số bài toán quan trọng Tìm kiếm theo phạm vi (range searching query) Tìm bao lồi (convex hull) Cây tìm kiếm phạm vi Một điểm trong không gian d chiều được biểu diễn theo tọa độ bởi (x0,x1, ,xd-1). Tìm kiếm theo phạm vi là tìm kiếm các điểm trong một phạm vi nào đó. Ví dụ tìm các điểm gần với (xq,yq) trong khoảng cách r. Kết quả tìm kiếm là tất cả các điểm hình tròn ((xq,yq),r) Giải thuật tìm kiếm thường tổ chức dữ liệu theo cây cân bằng – gọi là cây TK phạm vi. Tìm kiếm 1 chiều theo phạm vi Cho một tự điển (tập hợp các phần tử) có thứ tự findAllInRange(k1,k2): trả về các phần tử thỏa: k1 ≤ x ≤ k2 Dùng cấu trúc cây TKNP để lưu trữ các phần tử Giải thuật tìm kiếm 1DTreeRangeSearch(k1,k2,v) Nếu v là nút ngoài (V=NULL): dừng Nếu v là nút trong Key(v)k2: tìm đệ qui trên cây con trái của v. Giải thuật 1DTreeRangeSearch 1DTreeRangeSearch(k1,k2,v){ if (v) return ; if (k1 ≤ key(v) ≤ k2) { L= 1DTreeRangeSearch(k1,k2,(v)); R= 1DTreeRangeSearch(k1,k2,(v)); return L U {element(v)} U R; } else if (key(v) Chương 4: Các giải thuật hình học Computational Geometry PGS. TS. TRẦN CAO ĐỆ Đại Học Cần Thơ 2013 Dữ liệu nhiều chiều Các giải thuật hình học liên quan tới dữ liệu không gian đa chiều. Một điểm trong mặt phẳng (x,y) Một điểm trong không gian (x,y,z) Các ứng dụng máy học, xử lí ảnh cần xử lí dữ liệu hàng trăm, hàng ngàn chiều. Các bài toán thống kê, điều khiển cũng cần xử lí dữ liệu nhiều chiều Một số bài toán quan trọng Tìm kiếm theo phạm vi (range searching query) Tìm bao lồi (convex hull) Cây tìm kiếm phạm vi Một điểm trong không gian d chiều được biểu diễn theo tọa độ bởi (x0,x1, ,xd-1). Tìm kiếm theo phạm vi là tìm kiếm các điểm trong một phạm vi nào đó. Ví dụ tìm các điểm gần với (xq,yq) trong khoảng cách r. Kết quả tìm kiếm là tất cả các điểm hình tròn ((xq,yq),r) Giải thuật tìm kiếm thường tổ chức dữ liệu theo cây cân bằng – gọi là cây TK phạm vi. Tìm kiếm 1 chiều theo phạm vi Cho một tự điển (tập hợp các phần tử) có thứ tự findAllInRange(k1,k2): trả về các .

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã 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.