tizixinh_yeuchipxinh9x
New Member
Luận văn: Một số kiểu dữ liệu trừu tượng ứng dụng trong hình học tính toán : Luận văn ThS. Công nghệ thông tin : 60 48 05
Nhà xuất bản: ĐHCN
Ngày: 2011
Chủ đề: Cấu trúc dữ liệu
Hình học tính toán
Công nghệ thông tin
Hệ thống thông tin
Miêu tả: 80 tr. + CD-ROM
Luận văn ThS. Hệ thống thông tin -- Trường đại học Công nghệ. Đại học Quốc gia Hà Nội, 2011
Trình bày các vấn đề cơ bản của hình học tính toán, các đối tượng của hình học và một số kỹ thuật thuật toán giải quyết các bài toán như tìm cặp đoạn thẳng bất kỳ cắt nhau, tìm bao lồi, tìm cặp điểm gần nhất. Nghiên cứu cơ sở lý thuyết về những cấu trúc dữ liệu để giải quyết các bài toán trong hình học tính toán. Tìm kiếm phạm vi trực giao với phạm vi truy vấn là hình chữ nhật song song với trục tọa độ sử dụng cấu trúc dữ liệu như Range trees và Kd-trees. Cấu trúc dữ liệu hình học như Interval trees, Segment trees và Priority search trees trong đó Interval trees, Segment trees dựa trên tiếp cận stabbing và Priority search trees giải quyết các truy vấn không bị giới hạn bên trái, nghĩa là phạm vi truy vấn có dạng. Biến thể của các cấu trúc dữ liệu hình học như Partition trees, Multi-level partition trees, Cutting trees với phạm vi truy vấn là nửa mặt phẳng hay hình tam giác. Tiến hành cài đặt thực nghiệm các kiểu dữ liệu trừu tượng như Kd-trees, Range trees, Interval trees và Segment trees
MỞ ĐẦU
Hình học tính toán xuất hiện từ lĩnh vực phân tích và thiết kế thuật toán trong cuối những năm 1970 và lớn mạnh trở thành một môn học với tạp chí riêng, hội nghị riêng và có một cộng đồng lớn các nhà nghiên cứu hoạt động.
Hình học tính toán là một chuyên ngành khoa học máy tính nghiên cứu các thuật toán giải quyết các bài toán hình học. Hình học tính toán có ứng dụng trong nhiều lĩnh vực khác nhau như đồ họa máy tính, hệ thống thông tin địa lý, người máy, thống kê và những lĩnh vực khác mà trong đó các thuật toán hình học đóng vai trò cơ bản. Vấn đề hình học tính toán với đầu vào là mô tả kiểu cụ thể của tập hợp các đối tượng hình học, ví dụ như tập hợp các điểm, tập hợp các đoạn thẳng, hay tập hợp các đỉnh của một đa giác theo thứ tự ngược chiều kim đồng hồ. Đầu ra là đáp ứng với truy vấn về các đối tượng như các đường thẳng cắt nhau, hay có thể là một đối tượng hình học mới, ví dụ như bao lồi của tập hợp các điểm.
Các đối tượng hình học như điểm, đường thẳng và đa giác là cơ sở của một loạt các ứng dụng quan trọng và làm tăng tính thú vị của tập hợp các vấn đề về thuật toán. Ngày nay, máy tính được sử dụng ngày càng nhiều hơn để giải quyết các bài toán hình học với quy mô lớn hơn. Lời giải tốt cho các bài toán thuật toán có tính chất hình học chủ yếu dựa trên hai thành phần. Một là sự hiểu biết thấu đáo các tính chất hình học của bài toán, hai là ứng dụng các kỹ thuật thuật toán và cấu trúc dữ liệu thích hợp.
Trong luận văn sẽ trình bày một số kiểu dữ liệu trừu tượng và cấu trúc dữ liệu trong hình học tính toán. Những ứng dụng của các cấu trúc dữ liệu này không chỉ giới hạn trong các đối tượng hình học mà còn cho phép thiết kế những thuật toán hiệu quả, có thể xử lý các loại dữ liệu khác nhau của nhiều bài toán khác nhau.
Luận văn được tổ chức thành 3 chương như sau:
Chương 1 - Trình bày tổng quan về hình học tính toán như các đối tượng của hình học, một số bài toán hình học và thuật toán.
Chương 2 - Mô tả kiểu dữ liệu trừu tượng trong hình học tính toán như mô hình quản lý đối tượng một chiều, hai chiều và nhiều chiều.
Chương 3 - Cài đặt các cấu trúc dữ liệu, kết quả cài đặt thử nghiệm, đánh giá hiệu suất của thuật toán và chương trình.
Chương 1 - TỔNG QUAN VỀ HÌNH HỌC TÍNH TOÁN
1.1 Các bài toán của hình học tính toán
Hình học tính toán là một chuyên ngành của khoa học máy tính nghiên cứu các thuật toán có nội dung hình học. Một số bài toán hình học phát sinh hoàn toàn từ việc nghiên cứu các thuật toán hình học tính toán và các bài toán này cũng được xem là một phần của hình học tính toán. Hình học tính toán nghiên cứu sự phức tạp của các bài toán hình học, xây dựng cấu trúc dữ liệu để lưu trữ các loại dữ liệu hình học, thiết kế thuật toán cho các bài toán hình học và khám phá các tính chất hình học. Những vấn đề cốt lõi trong hình học tính toán có thể được chia với nhiều cách khác nhau, theo nhiều tiêu chí khác nhau. Ở đây, có thể phân loại các bài toán trong hình học tính toán thành các lớp bài toán như dưới đây [1].
1.1.1 Bài toán tĩnh
Trong các bài toán tĩnh cho trước đầu vào và đầu ra tương ứng cần được xây dựng hay được tìm thấy. Một số bài toán cơ bản của loại này là:
Convex Hull: Cho tập hợp các điểm và yêu cầu tìm đa giác lồi nhỏ nhất chứa tất cả các điểm đó.
Line segment intersection: Cho tập hợp các đoạn thẳng và yêu cầu tìm điểm cắt nhau giữa các đoạn thẳng trong tập hợp cho trước.
Polygon cutting: Chia đa giác thành các dạng hình học khác sao cho tổng chiều dài được chia là nhỏ nhất.
Delaunay triangulation.
Voronoi diagram: Cho tập hợp các điểm và yêu cầu tìm phân vùng không gian theo các điểm đó.
Linear programming.
Closest pair of points: Cho tập hợp các điểm và yêu cầu tìm cặp điểm có khoảng cách nhỏ nhất.
Euclidean shortest path: Nối hai điểm trong không gian Euclide bởi một đường đi ngắn nhất.
Polygon triangulation: Cho trước một đa giác và yêu cầu phân chia phần trong của đa giác thành các tam giác.
Độ phức tạp tính toán cho lớp các bài toán này là ước tính về thời gian và không gian cần thiết để giải quyết một trường hợp bài toán nhất định.
1.1.2 Bài toán động
Thêm một lớp chính là các bài toán động, với mục tiêu là để tìm thuật toán hiệu quả cho việc tìm lời giải nhiều lần sau mỗi lần sửa đổi gia tăng dữ liệu đầu vào. Các thuật toán cho bài toán thuộc loại này thường liên quan đến cấu trúc dữ liệu động. Bất kỳ các bài toán hình học tính toán tĩnh có thể được chuyển đổi thành một bài toán động. Bài toán tìm kiếm phạm vi có thể được chuyển đổi thành bài toán tìm kiếm phạm vi động, bằng cách cung cấp bổ sung hay xóa các điểm. Các bài toán bao lồi động là để lưu vết các bao lồi, chẳng hạn như đối với tập hợp các điểm thay đổi động, khi các điểm đầu vào được chèn hay xóa.
1.1.3 Bài toán truy vấn hình học
Bài toán truy vấn hình học thường gọi là bài toán tìm kiếm hình học, đầu vào bao gồm hai phần: không gian tìm kiếm và truy vấn với thay đổi trong các trường hợp bài toán. Không gian tìm kiếm thường phải được xử lý trước, trong cùng một cách mà nhiều truy vấn có thể được trả lời một cách hiệu quả. Một số bài toán truy vấn hình học cơ bản là:
Range Searching: Xử lý trước tập hợp các điểm và yêu cầu đếm số lượng các điểm nằm trong vùng truy vấn một cách hiệu quả.
Points Location: Cho phân vùng của không gian thành các ô và yêu cầu tạo ra cấu trúc dữ liệu hiệu quả cho ô nơi điểm truy vấn được định vị.
Nearest neighbor: Cho tập hợp các điểm và yêu cầu tìm điểm nằm gần nhất với điểm truy vấn một cách hiệu quả.
Ray tracing: Cho tập hợp các đối tượng trong không gian và yêu cầu tạo ra cấu trúc dữ liệu hiệu quả cho đối tượng có tia truy vấn cắt đầu tiên.
Nếu không gian tìm kiếm là cố định, độ phức tạp tính toán cho bài toán truy vấn hình học được ước tính bởi thời gian và không gian cần thiết để xây dựng các cấu trúc dữ liệu tìm kiếm và thời gian trả lời các truy vấn.
1.1.4 Các biến thể
Một số bài toán có thể được xem là thuộc một trong các loại trên, tùy thuộc vào bối cảnh. Chẳng hạn xét bài toán: Point in polygon - Xác định một điểm nằm trong hay nằm ngoài đa giác cho trước. Trong một vài tình huống của bài toán truy vấn có thể kỳ vọng hợp lý vào thứ tự các truy vấn, hay có thể được...
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download.
Password giải nén nếu cần: ket-noi.com | Bấm vào Link, đợi vài giây sau đó bấm Get Website để tải:
Nhà xuất bản: ĐHCN
Ngày: 2011
Chủ đề: Cấu trúc dữ liệu
Hình học tính toán
Công nghệ thông tin
Hệ thống thông tin
Miêu tả: 80 tr. + CD-ROM
Luận văn ThS. Hệ thống thông tin -- Trường đại học Công nghệ. Đại học Quốc gia Hà Nội, 2011
Trình bày các vấn đề cơ bản của hình học tính toán, các đối tượng của hình học và một số kỹ thuật thuật toán giải quyết các bài toán như tìm cặp đoạn thẳng bất kỳ cắt nhau, tìm bao lồi, tìm cặp điểm gần nhất. Nghiên cứu cơ sở lý thuyết về những cấu trúc dữ liệu để giải quyết các bài toán trong hình học tính toán. Tìm kiếm phạm vi trực giao với phạm vi truy vấn là hình chữ nhật song song với trục tọa độ sử dụng cấu trúc dữ liệu như Range trees và Kd-trees. Cấu trúc dữ liệu hình học như Interval trees, Segment trees và Priority search trees trong đó Interval trees, Segment trees dựa trên tiếp cận stabbing và Priority search trees giải quyết các truy vấn không bị giới hạn bên trái, nghĩa là phạm vi truy vấn có dạng. Biến thể của các cấu trúc dữ liệu hình học như Partition trees, Multi-level partition trees, Cutting trees với phạm vi truy vấn là nửa mặt phẳng hay hình tam giác. Tiến hành cài đặt thực nghiệm các kiểu dữ liệu trừu tượng như Kd-trees, Range trees, Interval trees và Segment trees
MỞ ĐẦU
Hình học tính toán xuất hiện từ lĩnh vực phân tích và thiết kế thuật toán trong cuối những năm 1970 và lớn mạnh trở thành một môn học với tạp chí riêng, hội nghị riêng và có một cộng đồng lớn các nhà nghiên cứu hoạt động.
Hình học tính toán là một chuyên ngành khoa học máy tính nghiên cứu các thuật toán giải quyết các bài toán hình học. Hình học tính toán có ứng dụng trong nhiều lĩnh vực khác nhau như đồ họa máy tính, hệ thống thông tin địa lý, người máy, thống kê và những lĩnh vực khác mà trong đó các thuật toán hình học đóng vai trò cơ bản. Vấn đề hình học tính toán với đầu vào là mô tả kiểu cụ thể của tập hợp các đối tượng hình học, ví dụ như tập hợp các điểm, tập hợp các đoạn thẳng, hay tập hợp các đỉnh của một đa giác theo thứ tự ngược chiều kim đồng hồ. Đầu ra là đáp ứng với truy vấn về các đối tượng như các đường thẳng cắt nhau, hay có thể là một đối tượng hình học mới, ví dụ như bao lồi của tập hợp các điểm.
Các đối tượng hình học như điểm, đường thẳng và đa giác là cơ sở của một loạt các ứng dụng quan trọng và làm tăng tính thú vị của tập hợp các vấn đề về thuật toán. Ngày nay, máy tính được sử dụng ngày càng nhiều hơn để giải quyết các bài toán hình học với quy mô lớn hơn. Lời giải tốt cho các bài toán thuật toán có tính chất hình học chủ yếu dựa trên hai thành phần. Một là sự hiểu biết thấu đáo các tính chất hình học của bài toán, hai là ứng dụng các kỹ thuật thuật toán và cấu trúc dữ liệu thích hợp.
Trong luận văn sẽ trình bày một số kiểu dữ liệu trừu tượng và cấu trúc dữ liệu trong hình học tính toán. Những ứng dụng của các cấu trúc dữ liệu này không chỉ giới hạn trong các đối tượng hình học mà còn cho phép thiết kế những thuật toán hiệu quả, có thể xử lý các loại dữ liệu khác nhau của nhiều bài toán khác nhau.
Luận văn được tổ chức thành 3 chương như sau:
Chương 1 - Trình bày tổng quan về hình học tính toán như các đối tượng của hình học, một số bài toán hình học và thuật toán.
Chương 2 - Mô tả kiểu dữ liệu trừu tượng trong hình học tính toán như mô hình quản lý đối tượng một chiều, hai chiều và nhiều chiều.
Chương 3 - Cài đặt các cấu trúc dữ liệu, kết quả cài đặt thử nghiệm, đánh giá hiệu suất của thuật toán và chương trình.
Chương 1 - TỔNG QUAN VỀ HÌNH HỌC TÍNH TOÁN
1.1 Các bài toán của hình học tính toán
Hình học tính toán là một chuyên ngành của khoa học máy tính nghiên cứu các thuật toán có nội dung hình học. Một số bài toán hình học phát sinh hoàn toàn từ việc nghiên cứu các thuật toán hình học tính toán và các bài toán này cũng được xem là một phần của hình học tính toán. Hình học tính toán nghiên cứu sự phức tạp của các bài toán hình học, xây dựng cấu trúc dữ liệu để lưu trữ các loại dữ liệu hình học, thiết kế thuật toán cho các bài toán hình học và khám phá các tính chất hình học. Những vấn đề cốt lõi trong hình học tính toán có thể được chia với nhiều cách khác nhau, theo nhiều tiêu chí khác nhau. Ở đây, có thể phân loại các bài toán trong hình học tính toán thành các lớp bài toán như dưới đây [1].
1.1.1 Bài toán tĩnh
Trong các bài toán tĩnh cho trước đầu vào và đầu ra tương ứng cần được xây dựng hay được tìm thấy. Một số bài toán cơ bản của loại này là:
Convex Hull: Cho tập hợp các điểm và yêu cầu tìm đa giác lồi nhỏ nhất chứa tất cả các điểm đó.
Line segment intersection: Cho tập hợp các đoạn thẳng và yêu cầu tìm điểm cắt nhau giữa các đoạn thẳng trong tập hợp cho trước.
Polygon cutting: Chia đa giác thành các dạng hình học khác sao cho tổng chiều dài được chia là nhỏ nhất.
Delaunay triangulation.
Voronoi diagram: Cho tập hợp các điểm và yêu cầu tìm phân vùng không gian theo các điểm đó.
Linear programming.
Closest pair of points: Cho tập hợp các điểm và yêu cầu tìm cặp điểm có khoảng cách nhỏ nhất.
Euclidean shortest path: Nối hai điểm trong không gian Euclide bởi một đường đi ngắn nhất.
Polygon triangulation: Cho trước một đa giác và yêu cầu phân chia phần trong của đa giác thành các tam giác.
Độ phức tạp tính toán cho lớp các bài toán này là ước tính về thời gian và không gian cần thiết để giải quyết một trường hợp bài toán nhất định.
1.1.2 Bài toán động
Thêm một lớp chính là các bài toán động, với mục tiêu là để tìm thuật toán hiệu quả cho việc tìm lời giải nhiều lần sau mỗi lần sửa đổi gia tăng dữ liệu đầu vào. Các thuật toán cho bài toán thuộc loại này thường liên quan đến cấu trúc dữ liệu động. Bất kỳ các bài toán hình học tính toán tĩnh có thể được chuyển đổi thành một bài toán động. Bài toán tìm kiếm phạm vi có thể được chuyển đổi thành bài toán tìm kiếm phạm vi động, bằng cách cung cấp bổ sung hay xóa các điểm. Các bài toán bao lồi động là để lưu vết các bao lồi, chẳng hạn như đối với tập hợp các điểm thay đổi động, khi các điểm đầu vào được chèn hay xóa.
1.1.3 Bài toán truy vấn hình học
Bài toán truy vấn hình học thường gọi là bài toán tìm kiếm hình học, đầu vào bao gồm hai phần: không gian tìm kiếm và truy vấn với thay đổi trong các trường hợp bài toán. Không gian tìm kiếm thường phải được xử lý trước, trong cùng một cách mà nhiều truy vấn có thể được trả lời một cách hiệu quả. Một số bài toán truy vấn hình học cơ bản là:
Range Searching: Xử lý trước tập hợp các điểm và yêu cầu đếm số lượng các điểm nằm trong vùng truy vấn một cách hiệu quả.
Points Location: Cho phân vùng của không gian thành các ô và yêu cầu tạo ra cấu trúc dữ liệu hiệu quả cho ô nơi điểm truy vấn được định vị.
Nearest neighbor: Cho tập hợp các điểm và yêu cầu tìm điểm nằm gần nhất với điểm truy vấn một cách hiệu quả.
Ray tracing: Cho tập hợp các đối tượng trong không gian và yêu cầu tạo ra cấu trúc dữ liệu hiệu quả cho đối tượng có tia truy vấn cắt đầu tiên.
Nếu không gian tìm kiếm là cố định, độ phức tạp tính toán cho bài toán truy vấn hình học được ước tính bởi thời gian và không gian cần thiết để xây dựng các cấu trúc dữ liệu tìm kiếm và thời gian trả lời các truy vấn.
1.1.4 Các biến thể
Một số bài toán có thể được xem là thuộc một trong các loại trên, tùy thuộc vào bối cảnh. Chẳng hạn xét bài toán: Point in polygon - Xác định một điểm nằm trong hay nằm ngoài đa giác cho trước. Trong một vài tình huống của bài toán truy vấn có thể kỳ vọng hợp lý vào thứ tự các truy vấn, hay có thể được...
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download.
Password giải nén nếu cần: ket-noi.com | Bấm vào Link, đợi vài giây sau đó bấm Get Website để tải:
You must be registered for see links
Last edited by a moderator: