کتاب Advanced Algorithms and Data Structures

کتاب Advanced Algorithms and Data Structures مقدمه‌ای بر الگوریتم‌ها و ساختارهای داده پیشرفته است. این کتاب در 18 فصل به آموزش مهم‌ترین الگوریتم‌ها و ساختمان داده‌های مهم در دنیای کامپیوتر می‌پردازد. همچنین با مثال‌هایی ساده و روان این الگوریتم‌ها را توضیح می‌دهد.

در ادامه مقدمه‌ای از کتاب Advanced Algorithms and Data Structures را از زبان نویسنده شرح خواهیم داد.

مقدمه‌ای بر کتاب Advanced Algorithms and Data Structures:

این کتاب در فصل 1، با مقدمه‌ای ساده در مورد نحوه بحث در مورد موضوعات در این کتاب شروع می‌شود، پیش‌نمایشی از آنچه در فصل معمولی خواهید یافت. با شروع از فصل 2، بقیه کتاب به سه بخش به اضافه ضمیمه‌ها تقسیم می‌شود. هر بخش بر روی موضوعی متمرکز است که می‌تواند یک هدف انتزاعی یا دسته‌ای از مسائل باشد که قصد حل آن را داریم.

بخش 1 بر کشف ساختارهای داده پیشرفته متمرکز است که به شما امکان می‌دهد برخی از عملیات‌های اساسی را بهبود بخشید، به عنوان مثال، ردیابی چیزها یا گروه‌هایی از چیزها. نکته کلیدی این است که به این ایده عادت کنیم که راه‌های زیادی برای انجام عملیات روی داده‌ها وجود دارد و بهترین راه به زمینه و الزامات بستگی دارد.

فصل 1 الگوریتم‌ها و ساختارهای داده را تعریف می‌کند، تفاوت‌های بین آن‌ها را توضیح می‌دهد، و از طریق یک مثال، فرآیند کاوش الگوریتم‌های مختلف برای حل یک مسئله و چگونگی استفاده از آن‌ها برای یافتن راه‌حل‌های بهتر را توضیح می‌دهد.

فصل 2 یک نوع پیشرفته از هپ‌های دوتایی، پشته d-way را معرفی می‌کند. همچنین ساختاری را که در هر فصل در این بخش برای توضیح موضوعات استفاده می‌کنیم، توضیح می‌دهد.

فصل 3 کتاب Advanced Algorithms and Data Structures، بیشتر به بررسی استفاده پیشرفته از heaps با treap می‌پردازد، ترکیبی بین درخت جستجوی دودویی و هیپ که همچنین می‌تواند در زمینه‌های مختلف کمک کند.

فصل 4 به فیلترهای بلوم تغییر می‌کند، شکلی پیشرفته از جدول هش که می‌تواند به صرفه‌جویی در حافظه و حفظ جستجوی مستهلک شده در زمان ثابت کمک کند.

فصل 5 کتاب Advanced Algorithms and Data Structures، چند ساختار داده جایگزین را معرفی می‌کند که برای پیگیری مجموعه‌های ناهمگون استفاده می‌شوند، سنگ بنای مورد نیاز برای ساخت الگوریتم‌های پیشرفته بی‌شماری و مورد استفاده در چندین برنامه کاربردی در دنیای واقعی.

فصل 6 دو ساختار داده را ارائه می‌کند که در مورد ذخیره‌سازی و جستجوی رشته‌ها از کانتینرهای همه‌منظوره بهتر عمل می‌کنند: trys و تلاش‌های ریشه، که به نام درخت‌های پیشوند فشرده نیز شناخته می‌شوند.

فصل 7 کتاب Advanced Algorithms and Data Structures، از ساختارهای داده ارائه شده تا کنون برای ساختن یک ساختار داده ترکیبی، LRU-cache، استفاده می‌کند تا به طور مؤثری حافظه پنهان را مدیریت کند. نوع LFU-cache نیز به طور طولانی مورد بحث قرار گرفته است، و همچنین مسائل مربوط به همگام‌سازی کانتینرهای مشترک در محیط‌های چند رشته‌ای.

قسمت 2 مورد خاص دیگری را در جستجو معرفی می‌کند: برخورد با داده‌های چند بعدی، نمایه‌سازی این داده‌ها و انجام پرس و جوهای فضایی(Spatial Queries). ما یک بار دیگر نشان خواهیم داد که چگونه ساختارهای داده موقتی می‌توانند پیشرفت‌های چشمگیری را نسبت به استفاده از الگوریتم‌های جستجوی اولیه ایجاد کنند. اما این بخش موضوعات مهم دیگری را نیز شرح می‌دهد: خوشه‌بندی، اهرم شدید پرس و جوهای فضایی، و محاسبات توزیع شده، به ویژه با مدل برنامه‌نویسی MapReduce.

فصل 8 مشکل نزدیکترین همسایه را معرفی می‌کند.

فصل 9 کتاب Advanced Algorithms and Data Structures، درختان k-d را توضیح می‌دهد، راه حلی برای جستجوی کارآمد در مجموعه داده‌های چند بعدی.

فصل 10 نسخه‌های پیشرفته‌تری از این درختان، ss-trees و r-trees را ارائه می‌کند.

فصل 11 کتاب Advanced Algorithms and Data Structures، بر کاربردهای جستجوی نزدیکترین همسایه متمرکز است، با یک مورد استفاده که به طور عمیق توضیح داده شده است (پیدا کردن نزدیکترین انبار که کالاها باید از آنجا برای مشتریان ارسال شوند).

فصل 12 مورد استفاده واقعی دیگری را ارائه می‌کند که از الگوریتم‌های جستجوی کارآمد نزدیکترین همسایه تاکنون ارائه شده است: سه الگوریتم خوشه‌بندی، k-means ،DBSCAN و OPTICS.

فصل 13 این بخش را با معرفی MapReduce، یک مدل محاسباتی قدرتمند برای محاسبات توزیع شده، و اعمال آن در الگوریتم‌های خوشه‌بندی که در فصل 12 مورد بحث قرار گرفت، به پایان می‌رساند.

بخش 3 بر روی یک ساختار داده واحد متمرکز است، نمودارها، که موضوع مشترک در معرفی چند تکنیک بهینه‌سازی است که تلاش های هوش مصنوعی و کلان داده امروزی را هدایت می‌کند.

فصل 14 کتاب Advanced Algorithms and Data Structures، مقدمه‌ای کوتاه بر نمودارها است که اصول اولیه این ساختار داده بنیادی را که برای درک قسمت 3 مورد نیاز است، فشرده می‌کند. همچنین الگوریتم‌های DFS, BFS, Dijkstra و A* را نشان می‌دهد و نحوه استفاده از آن‌ها را برای حل مسئله «مسیر حداقل فاصله» توضیح می‌دهد.

فصل 15 کتاب Advanced Algorithms and Data Structures، تعبیه‌های گراف، مسطح بودن و چند مسئله را معرفی می‌کند که در فصل‌های باقی‌مانده سعی خواهیم کرد حل کنیم: یافتن جاسازی حداقل عدد متقاطع (MCN) یک نمودار و ترسیم یک نمودار به زیبایی.

فصل 16 کتاب Advanced Algorithms and Data Structures، یک الگوریتم اساسی در یادگیری ماشین، نزول گرادیان را توضیح می‌دهد و نشان می‌دهد که چگونه می‌توان آن را بر روی نمودارها و جاسازی‌ها اعمال کرد.

فصل 17 مبتنی بر فصل قبل است و بازپخت شبیه‌سازی شده را ارائه می‌کند، یک تکنیک بهینه‌سازی قوی‌تر که سعی می‌کند بر کاستی‌های نزولی گرادیان غلبه کند، زمانی که باید با توابع غیر قابل تمایز یا توابع با حداقل‌های محلی متعدد سروکار داشته باشیم.

فصل 18، سرانجام، الگوریتم‌های ژنتیک را شرح می‌دهد، یک تکنیک بهینه‌سازی حتی پیشرفته‌تر که به همگرایی سریع‌تر کمک می‌کند. فصل‌ها ساختار خاصی را دنبال می‌کنند و شما را در مسیری از یک مشکل به طراحی ساختار داده برای راه‌حل آن، پیاده‌سازی آن راه‌حل و درک زمان اجرا و نیازهای حافظه آن راهنمایی می‌کنند. اما فعلا کافی است. در فصل 2 درباره این ساختار بیشتر خواهید آموخت.

در پایان کتاب Advanced Algorithms and Data Structures، بخش اضافی برای ضمائم وجود دارد که موضوعات مهمی را پوشش می‌دهد که برای پیمایش در میان موضوعات این کتاب مورد نیاز است. ضمائم ساختار متفاوتی نسبت به فصل‌ها دارند، زیرا براساس مثال‌ها ساخته نشده‌اند، بلکه خلاصه‌ای از مطالبی را ارائه می‌کنند که خواننده باید قبل از شروع ماجراجویی در فصل‌ها با آن آشنا باشد. بیشتر موضوعات ضمیمه‌ها در کلاس‌های الگوریتم پایه پوشش داده شده‌اند و فصل‌ها چندین مرجع به ضمیمه‌ها دارند تا به خوانندگان کمک کنند تا در زمان مناسب از آن‌ها استفاده کنند، اما پیشنهاد ما این است که حداقل قبل از رفتن به فصل 2 آن‌ها را مرور کنید.

پیوست A نمادی را که برای شبه کد خود برای توصیف الگوریتم‌ها استفاده می‌کنیم، معرفی می‌کند.

ضمیمه B نمای کلی از نمادگذاری big-O و تجزیه و تحلیل زمان-فضا را ارائه می‌دهد.

ضمیمه C و ضمیمه D خلاصه‌ای از ساختارهای داده اصلی را ارائه می‌دهند که به عنوان بلوک‌های سازنده ساختارهای پیشرفته در کتاب Advanced Algorithms and Data Structures استفاده می‌شوند.

پیوست E بازگشت، یک تکنیک برنامه‌نویسی چالش‌برانگیز را توضیح می‌دهد که اغلب به تعاریف واضح‌تر و مختصرتر از الگوریتم‌ها اجازه می‌دهد – همانطور که خواهیم دید، با برخی معاوضه‌ها.

ضمیمه F تعریف الگوریتم‌های تصادفی، هر دو نوع مونت کارلو و لاس وگاس را ارائه می‌دهد و مسائل و معیارهای طبقه بندی را برای راه حل های تصادفی معرفی می‌کند.

همچنبن شما می‌توانید برای مطالعه بر روی زبان جاوا و ساختار داده در آن از کتاب Introduction to Java Programming and Data Structures نیز استفاده نمائید.

سرفصل‌های کتاب Advanced Algorithms and Data Structures:

• foreword
• preface
• acknowledgments
• about this book
• about the author
• about the cover illustration
• 1 Introducing data structures
• Part 1 Improving Over Basic Data Structures
  • 2 Improving priority queues: d-way heaps
  • 3 Treaps: Using randomization to balance binary search trees
  • 4 Bloom filters: Reducing the memory for tracking content
  • 5 Disjoint sets: Sub-linear time processing
  • 6 Trie, radix trie: Efficient string search
  • 7 Use case: LRU cache
• Part 2 Multidemensional Queries
  • 8 Nearest neighbors search
  • 9 K-d trees: Multidimensional data indexing
  • 10 Similarity Search Trees: Approximate nearest neighbors search for image retrieval
  • 11 Applications of nearest neighbor search
  • 12 Clustering
  • 13 Parallel clustering: MapReduce and canopy clustering
• Part 3 Planar Graphs And Minimum Crossing Number
  • 14 An introduction to graphs: Finding paths of minimum
  • 15 Graph embeddings and planarity: Drawing graphs with minimal edge intersections
  • 16 Gradient descent: Optimization problems (not just) on graphs
  • 17 Simulated annealing: Optimization beyond local minima
  • 18 Genetic algorithms: Biologically inspired, fast-converging optimization
• appendix A A quick guide to pseudo-code
• appendix B Big-O notation
• appendix C Core data structures
• appendix D Containers as priority queues
• appendix E Recursion
• appendix F Classification problems and randomnized algorithm metrics
• index

فایل کتاب Advanced Algorithms and Data Structures به همراه کدهای مورد بحث در آن را می‌توانید پس از پرداخت، دریافت کنید.