https://people.cs.umass.edu/~mcgregor/slides/07-orderslides.pdf
طبقه بندی موضوعی
-
نظریه الگوریتمی بازی‌ها
(۴۰) -
الگوریتم پیشرفته
(۲۵) -
حل‌های من
(۱۱) -
پروژه
(۱۶) -
بهینه‌سازی ترکیبیاتی
(۶) -
الگوریتم‌های پارامتری
(۱۴) -
درس ارائه شده در دانشگاه‌های دیگر
(۲۱) -
بهینه‌سازی محدب
(۱۶) -
الگوریتم‌های داده‌های حجیم
(۵۷) -
سخنرانی‌ها
(۸) -
مدل نگاشت-کاهش (Map-Reduce)
(۲۸) -
مبانی علوم داده
(۱۶) -
communication complexity
(۳) -
نظریه سیستم‌های توزیع شده
(۹) -
سیستم عامل پیشرفته
(۷) -
سوالات امتحان
(۱) -
جزوه و اسلاید درس
(۱) -
Expanders
(۲۹) -
متفرقه
(۹)
کلمات کلیدی
بایگانی
- اسفند ۱۴۰۰ (۱)
- شهریور ۱۳۹۹ (۲)
- خرداد ۱۳۹۹ (۱)
- ارديبهشت ۱۳۹۹ (۲)
- فروردين ۱۳۹۹ (۱)
- اسفند ۱۳۹۸ (۱)
- دی ۱۳۹۸ (۲)
- خرداد ۱۳۹۸ (۱)
- ارديبهشت ۱۳۹۸ (۲)
- فروردين ۱۳۹۸ (۵)
- بهمن ۱۳۹۷ (۲)
- آبان ۱۳۹۷ (۴)
- تیر ۱۳۹۷ (۲)
- بهمن ۱۳۹۶ (۳)
- دی ۱۳۹۶ (۱)
- مهر ۱۳۹۶ (۲)
- خرداد ۱۳۹۶ (۳)
- فروردين ۱۳۹۶ (۶)
- اسفند ۱۳۹۵ (۳۱)
- دی ۱۳۹۵ (۱۴)
- آذر ۱۳۹۵ (۱۰)
- آبان ۱۳۹۵ (۵)
- مهر ۱۳۹۵ (۱۵)
- شهریور ۱۳۹۵ (۱۵)
- مرداد ۱۳۹۵ (۵)
- تیر ۱۳۹۵ (۵)
- خرداد ۱۳۹۵ (۱)
- ارديبهشت ۱۳۹۵ (۶)
- فروردين ۱۳۹۵ (۳)
- اسفند ۱۳۹۴ (۸)
- دی ۱۳۹۴ (۱۳)
- آذر ۱۳۹۴ (۲)
- آبان ۱۳۹۴ (۷)
- مهر ۱۳۹۴ (۲۵)
- شهریور ۱۳۹۴ (۶)
- مرداد ۱۳۹۴ (۴)
- تیر ۱۳۹۴ (۷)
- خرداد ۱۳۹۴ (۱۰)
- ارديبهشت ۱۳۹۴ (۱۱)
- بهمن ۱۳۹۳ (۲)
- دی ۱۳۹۳ (۹)
- آذر ۱۳۹۳ (۶)
- آبان ۱۳۹۳ (۳)
- مهر ۱۳۹۳ (۶)
- شهریور ۱۳۹۳ (۷)
- مرداد ۱۳۹۳ (۳)
- تیر ۱۳۹۳ (۱۷)
آخرین مطالب
- ۰۰/۱۲/۱۶جزوه نظریه بازیهای دکتر صفری
- ۹۹/۰۶/۱۸فارسی نوشتن در Adobe Reader
- ۹۹/۰۶/۱۶کتاب طراحی الگوریتم جف اریکسون
- ۹۹/۰۳/۰۸الگوریتم‌های پارامتری (کتاب)
- ۹۹/۰۲/۱۷ساختمان داده پیشرفته
- ۹۸/۱۲/۲۱Clustering powers of sparse graphs
- ۹۸/۱۰/۱۷Distance-Sensitive Hashing
پیوندهای روزانه
https://people.cs.umass.edu/~mcgregor/slides/06-defense.pdf
http://www.cs.rutgers.edu/~muthu/mapreduce_spr11.html
http://www.umiacs.umd.edu/~jimmylin/MapReduce-book-final.pdf
http://people.cs.umass.edu/~mcgregor/slides/13-michigan.pdf
اینجا برای خلاصه‌سازی هموتوپیک روی داده‌های حجیم از sketch استفاده می‌کنند.
https://sites.google.com/site/algoresearch/mytalks
این دو تا را من دوست داشتم اما باز هم در مورد نظریه بازی‌ها هم مثلاً مطلب دارد.
- PODS 2011 Invited Tutorial on Data Streams Research: Where to Go.
- DIMACS 2020:
- Talk on Mapreduce with parallelizable reduce.
https://people.cs.umass.edu/~mcgregor/slides/09-barbados1.pdf
https://people.cs.umass.edu/~mcgregor/slides/09-barbados2.pdf
به جای مدل رقیب (adversary) و اگر بشود فرض کرد که جویبار داده به ترتیب تصادفی داده می‌شود (همان داده‌ها هستند اما ترتیبشان تصادفی است. مثلاً اگر بدترین حالت خیلی به ترتیب داده‌ها بستگی داشته باشد، ممکن است حذف شود) می‌شود به کران پایین‌های بهتری رسید.
به جای مدل رقیب (adversary) و اگر بشود فرض کرد که جویبار داده به ترتیب تصادفی داده می‌شود (همان داده‌ها هستند اما ترتیبشان تصادفی است. مثلاً اگر بدترین حالت خیلی به ترتیب داده‌ها بستگی داشته باشد، ممکن است حذف شود) می‌شود به کران پایین‌های بهتری رسید.
در این ارائه trade-off بین تعداد عبورها و حافظه بحث می‌شود و از مسئله‌ی Index استفاده می‌شود.
مسئله‌ی 2level index هم جالب بود: بر خلاف ایندکس معمولی، آلیس این بار t تا عدد tبیتی دارد (x^..ها) و باب t عدد بین 1 تا t دارد (y) و چارلی یک عدد بین ۱ تا t دارد (i). در واقع چارلی یکی از اعداد آلیس را انتخاب می‌کند و باب به ازای هر عدد یک اندیس دارد که می‌فرستد. این مسئله با ۲ راند حداقل به t بیت تبادل داده نیاز دارد.
مرجع: http://sublinear.wikischolars.columbia.edu/file/view/scribe1.pdf/559708247/scribe1.pdf
به نظرم مهم‌ترین قسمتش به جز تمرین الگوریتم تصادفی، شکل دیگری از نامساوی چبیشف است که می‌گوید که در واقع یک نتیجه است اما این را خیلی راحت‌تر می‌شود حفظ کرد!
http://math.sharif.ir/faculties/foroughmand/page/show/130
http://theory.stanford.edu/~jvondrak/CS369P.html
http://theory.stanford.edu/~jvondrak/CS369P.html
http://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/Draft-Survey-Sublinear.pdf