عنوان پایان‌نامه
ا لگوریتم ها وساختمان داده هایی برای مسئله جستجوی محدود
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 93..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 75964;کتابخانه پردیس یک فنی شماره ثبت: 93..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 75964
- تاریخ دفاع
- ۲۹ دی ۱۳۹۴
- دانشجو
- مجید ایمانی
- استاد راهنما
- علی معینی
- چکیده
- در این پایان نامه ساختمان داده های اصلی مسئله جستجوی محدوده متعامد را در دو بعد و یا ابعاد بالاتر مورد بررسی قرار می دهیم. به طور خاص در حالت دوبعدی مسئله به صورت این صورت بیان می شود که با در اختیار داشتن نقطه در در صفحه می خواهیم مجموعه نقاط موجود در یک ناحیه مستطیلی را بررسی نماییم. اصلی ترین ساختمان داده های ارائه شده برای حل این مسئله درخت کی دی و درخت محدوده می باشند. از طرفی مدل های محاسباتی زیادی وجود دارند که دو ساختمان داده اشاره شده در این مدل ها به روش های گوناگونی طراحی شده اند. ابتدا روش های ارائه شده در مدل محاسباتی RAM را مورد بررسی قرار خواهیم داد و سپس به تشریح مدل های محاسباتی جدید حافظه نهان فراموشکار می پردازیم و آنگاه روش های طراحی این ساختمان داده ها را در مدل حافظه نهان فراموشکار شرح می دهیم. خواهیم دید که چگونه می توان ساختمان داده ای ارائه داد که تعداد انتقال بلاک ها بین دو سطح از سلسله مراتب حافظه را کاهش دهد. در راستای آشنایی بهتر با تکنیک های طراحی ساختمان داده های بازگشتی در مدل حافظه نهان فراموشکار، برخی از پیاده سازی ها را نشان می دهیم. هدف از نمایش این پیاده سازی ها، درک پیچیده بودن طراحی الگوریتم ها در این مدل می باشد. سرانجام از آنجایی که طراحی الگوریتم ها در مدل حافظه نهان فراموشکار پیچیدگی خاص خود را به همراه دارد ساختمان داده تصادفی را ارائه خواهیم داد که تا حد مطلوبی پیچیدگی طراحی درخت کی دی را در مدل حافظه نهان فراموشکار کاهش می دهد و ثابت خواهیم کرد که این ساختمان داده همچنین مقدار مورد انتظار انتقال بلاک ها برای ساختن درخت کی دی در مدل حافظه نهان فراموشکار را کاهش خواهد داد.
- Abstract
- We study orthogonal range search data structures in two or more dimensions. Specially, in case of 2d the problem is finding a rectangular area of N points in the plane. Kd-trees and range trees are main data structures that already proposed. We study these data structures using the various models of computation. First, we review propoesd methodologies in RAM model, and then we described a new model of computation, known as cache-oblivious model. We will present that how can it give a data structure that reduces the number of block transfers between each two levels of memory hierarchy. We present some implementations for better understanding of the design of recursive data structures in cache-oblivious model. Our purpose is understanding of existing complexity in design of cache-oblivious algorithms. Finally, we propose a randomized version cache-oblivious Kd-trees, and we show that our data structure reduces the number of block transfers in construction phase. This data structure is also more simple than cache-oblivious Kd-tree. Keywords: Orthogonal Range Searching, Kd-tree, Model of Computation, Range Tree.
