الگوریتم‌های داده‌های حجیم

Massive Data Algorithms

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

هدف کلی

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

سرفصل‌ها

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

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

  • آزمون: آزمون‌های میان‌ترم و پایان‌ترم (۱۴ نمره)
  • ارائه و گزارش پژوهشی (۳ نمره).
  • تمرین‌های نظری (۳ نمره)

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

  1. L. Arge. External memory geometric data structures. Lecture notes, 2005.
  2. A. Chakrabarti and D. College. Data streams algorithms. Lecture notes, 2011.
  3. A. Czumaj and C. Sohler. Sublinear-time algorithms. Lecture notes, 2010.
  4. E. Demaine. Cache-oblivious algorithms and data structures. Lecture notes, 2002.
  5. U. Meyer, P. Sanders, and J. Sibeyn. Algorithms for memory hierarchies. Lecture notes, 2003.
  6. N. Zeh. I/O efficient graph algorithms. Lecture notes, 2002.