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

Massive Data Algorithms

شماره درس: ۴۰۶۸۶ تعداد واحد: ۳
مقطع: کارشناسی ارشد نوع درس: نظری
پیش‌نیاز: – هم‌نیاز: –

اهداف درس

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

ریز مواد

  • Cache-aware Models (۱۰ جلسه)
    • معرفی مدل‌
    • الگوریتم‌های مرتب‌سازی و کران پایین آن
    • داده‌ساختارهای جست‌وجو: Persistent B-tree،Weighted B-tree ،B-tree و Buffer tree
    • داده‌ساختارهای هندسی: Priority search tree ،Interval tree ،Range tree و KD-tree
    • یک نمونه الگوریتم جاروب
    • الگوریتم‌های گراف: DFS ،BFS ،Algorithms on trees ،List ranking و MST
  • Cache-oblivious Models (۲ جلسه)
    • معرفی مدل
    • مرتب‌سازی
    • داده‌ساختارهای جست‌وجو
    • ضرب ماتریس‌ها
  • Streaming Models (۱۰ جلسه)
    • معرفی مدل
    • پیدا کردن اعداد با تکرار زیاد
    • پیدا کردن تعداد اعداد متمایز
    • معرفی تکنیک sketching
    • بررسی مسائل پایه‌ای گراف
    • بررسی مسائل هندسی و معرفی core-sets
    • خوشه‌بندی
    • نظریه ارتباطات و حد پایین
  • Sublinear Algorithms (۲ جلسه)
    • معرفی مدل
    • محاسبه میانگین درجه‌ی گراف
    • اشتراک دو گوژ محدب

ارزیابی

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

مراجع

  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.
  4. Erik Demaine. Cache oblivious algorithms and data structures. Lecture notes.
  5. U. Meyer, P. Sanders, and J. Sibeyn. Algorithms for memory hierarchies. Lecture notes, 2003.
  6. Norbert Zeh. I/O efficient graph algorithms. Lecture notes.