داده‌ساختارهای پیشرفته

Advanced Data Structures

مقطع: تحصیلات تکمیلی گرایش: الگوریتم‌ها و محاسبات
نوع درس: نظری تعداد واحد: ۳
پیش‌نیاز: – هم‌نیاز: –

هدف کلی

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

سرفصل‌ها

  1. درخت‌های تصادفی (مانند تریپ‌ها و هیترها)
  2. داده‌ساختارهای پایا (Persistent) و روش‌های حفظ سابقه
  3. آبشار کسری و کاربردهای آن (جست‌وجوی مکرر، لیست‌های پرشی)
  4. آنتروپی و کاربردهای آن (درخت‌های جستجوی تقریبا بهینه)
  5. تحلیل سرشکن (هرم فیبوناچی و مجموعه‌های مجزا)
  6. درخت‌های نامتوازن (مانند درخت‌های چپ‌گرا و هرم‌های اریب)
  7. داده‌ساختارهای خودتنظیم‌گر (مانند درخت‌های اسپلی، تانگو و کوئیپ)
  8. جست‌وجو در فضای اعداد صحیح (درخت‌های ون‌امبدبوز و ویلیارد)
  9. داده‌ساختارهای مخصوص رشته‌ها (مانند درخت‌های پسوندی، پاتریشیا و ترای)
  10. پرس‌وجوی کوچک‌تری نیای مشترک، نیای سطحی و کوچک‌ترین عضو بازه
  11. جدول‌های درهم‌سازی (مانند درهم‌سازی کامل پویا و درهم‌سازی کوکو)
  12. مباحث تکمیلی (مانند فیلتر بلوم و داده‌ساختارهای غیرحساس به حافظه نهان)

ارزیابی پیشنهادی

منابع پیشنهادی

  1. P. Brass. Advanced Data Structures. Cambridge University Press, 2008.
  2. D. P. Mehta (ed.). Handbook of Data Structures and Applications. 2nd Edition, Chapman & Hall, 2018.