توصیف درس
امروزه شاهد حجم زیادی از داده‌ها در زمینه‌های فراوانی هستیم. یکی از عواملی که موجب شده حجم داده‌ها در زمینه‌های مختلف زیاد شود، استفاده روزافزون از سامانه‌های نرم افزاری و توسعه این سامانه‌ها است. دلیل جالب دیگری که موجب علاقه‌مندی پژوهشگران علوم داده به حجم بالای داده شده این است که پیشرفت‌های جدید، مخصوصا در زمینه یادگیری ماشین، نشان داده که بعضا ضعف در توان محاسباتی را می‌توان با حجم زیادتر داده جبران کرد. برای پردازش داده‌های حجیم، وقتی حجم داده‌ها زیاد است، مثلا وقتی از حافظه یک کامپیوتر بزرگ‌تر است، نیاز به الگوریتم‌های جدیدی خواهیم داشت. در این الگوریتم‌ها بعضا زمان‌های اجرای با بزرگی درجه دو نیز غیرقابل قبول هستند.
برخی از زمینه‌هایی که در آن ها حجم داده‌ها بسیار زیاد است شامل اینترنت، یادگیری ماشین (و مخصوصا یادگیری عمیق)، ترافیک شبکه، پردازش سیگنال است.
مباحث درس
درس شامل ارائه برخی الگوریتم‌های سریع و اثبات برخی محدودیت‌های الگوریتمی در حوزه الگوریتم‌های مه داده است.
- کاهش بُعد: الگوریتم‌هایی برای کاهش ویژگی‌های داده در عین حفظ ساختار هندسی داده
- الگوریتم‌های عددی برای جبر خطی: الگوریتم‌هایی برای کار با ماتریس‌های بزرگ شامل تحلیل رگرسیون، تقریب با رتبه کم، و کامل کردن ماتریس.
- سنجش فشرده: بازیابی (تقریبی) داده با داشتن تعداد اندکی ترکیب خطی از داده
- تبدیل فوریه تُنُک: محاسبه سریع تقریبی تبدیل فوریه به شرط تنک بودن داده در حوزه فرکانس
پیش‌نیاز
ساختمان داده، آنالیز الگوریتم، احتمال.
منابع درس
منبع اصلی درس، جزوه‌های درس Data Big for Algorithms Sketching است که در سال ۲۰۱۷ توسط آقایان Indyk و Nelson تدریس شده است. البته نسخه سال ۲۰۲۰ همین درس جزوه‌های مرتب‌تری دارد که احیانا ممکن است از آن استفاده شود.
به نظر می‌رسد این منبع کمی فشرده باشد. اگر لازم شد از جزوه‌های درس‌های دیگر نیز استفاده می‌کنیم. مثلا:
- درس Data Stream Algorithms توسط آقای Amit Chakrabarti سال ۲۰۲۰
- مبحث Streaming Algorithm از درس Great Ideas in TCS توسط آقایان Kurt Mehlhorn و He Sun سال ۲۰۱۴
- درس Algorithms for Big Data توسط آقای Jelani Nelson سال ۲۰۱۵
- مبحث Data Stream Algorithms در کارگاه The 2009 Barbados Workshop on Computational Complexity توسط آقای S. Muthu Muthukrishnan سال ۲۰۰۹
توجه
دانشجویان درس باید هم زمان هم در درس سه واحدی به شماره ۲۲۸۰۳ و هم در سمینار یک واحدی با شماره ۲۲۸۰۰ ثبت نام کنند.
ارزیابی
درس شامل موارد زیر است:
- میان‌ترم ۳ نمره
- پایان‌ترم ۴ نمره
- تمرین ۴ نمره
- کوئیز ۲ نمره
- پروژه ۲ نمره
- جزوه‌نویسی ۲ نمره (وابسته به تعداد دانشجویان است)
- پرسش در کلاس ۳ نمره
پرسش در کلاس به این معناست که در حین جلسه مجازی سوال‌های بسیار ساده از روند درس پرسیده می‌شود و همان زمان باید در یک سیستم برخط توسط دانشجویان حاضر پاسخ داده شود.
توجه کنید با توجه به مجازی بودن ترم، ممکن است برخی نمره‌بندی‌ها تغییر کند.
تمرین
جزوه‌نویسی
پیوند به فایل اختصاص دانشجو به جلسه‌های کلاس برای جزوه‌نویسی.