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

Advanced Data Structures

شماره درس: ۴۰۷۹۵.۲ تعداد واحد: ۳
مقطع: کارشناسی ارشد نوع درس: نظری
پیش‌نیاز: – هم‌نیاز: –

اهداف درس

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

ریز مواد

  1. درخت‌های تصادفی
    درخت‌های جست‌وجوی تصادفی، Treaps، Heaters
  2. پایایی (Persistence)
    درخت‌های جست‌وجوی پایا، روش رونوشت مسیر، گراف‌های پایا
  3. آبشار کسری (Fractional Cascading)
    جست‌وجوهای مکرر، لیست‌های پرشی (Skip lists)، درخت‌های پاره‌خطی
  4. آنتروپی و مجموعه‌های کاری
    جست‌وجوهای ایستا و پویا، درخت‌های جست‌وجوی نزدیک به بهینه، کاربرد در فشرده‌سازی داده‌ها
  5. درخت‌های نامتوازن
    درخت‌های چپ‌گرا، هرم‌های ادغام‌پذیر تصادفی، هرم‌های اریب (Skew heaps)
  6. داده‌ساختارهای سرشکنی
    هرم دوجمله‌ای، هرم فیبوناچی، داده‌ساختار مجموعه‌های مجزا
  7. داده‌ساختارهای خودتنظیم‌گر
    الگوریتم‌های سازمان‌دهی مجدد لیست‌ها، درخت‌های اسپلِی، بهینگی پویا، کوئیپ‌ها، درخت‌های تانگو
  8. جست‌وجو در فضای اعداد صحیح
    درخت‌های van Emde Boas، درخت‌های X/Y-سریع ویلیارد
  9. داده‌ساختارهای مخصوص رشته‌ها
    ریسمان‌ها، ترای‌ها، درخت‌های پاتریشیا، درخت‌های پسوندی، آرایه‌های پسوندی، ترای‌های سه‌تایی
  10. داده‌ساختارهای مخصوص درخت‌ها
    پرس‌وجوی کوچک‌ترین نیای مشترک، پرس‌وجوی کوچک‌ترین عضو یک بازه، پرس‌وجوی نیای سطحی
  11. جدول‌های درهم‌سازی
    درهم‌سازی جامع، درهم‌سازی کامل پویا، درهم‌سازی کوکو (Cuckoo)
  12. مباحث تکمیلی (در صورت فرصت)
    فیلتر بلوم، کران‌های پایین مبتنی بر وارسی سلول‌ها، داده‌ساختارهای غیرحساس به حافظه‌ی نهان

ارزیابی

  • آزمون‌های میان‌ترم و پایانی: ۱۰ نمره
  • سه تمرین نظری: ۶ نمره
  • پروژه‌ی پژوهشی: ۴ نمره

مراجع

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