Workshop on Massive Geometric Data Sets (in connection with SoCG 05)

http://wwwmath.uni-muenster.de:8010/u/jan/IOWorkshop/

Colonel Blotto

http://umdrightnow.umd.edu/news/umd-led-team-first-solve-well-known-game-theory-scenario
http://www.cs.umd.edu/~saeedrez/blotto.html
من الآن این را دیدم. ما که نظریه بازی‌ها بلد نیستیم از همین که مغزهای فرار کرده به موفقیت می‌رسند بیخودی ذوق می‌کنیم!
** موندم چرا کسی نگفت زودتر! می‌خواستم به خودشان ایمیل بزنم تبریک بگم دیدم دیره الآن و یک جوری ضایع است.

Planarity of Streamed Graphs

http://www.dia.uniroma3.it/~dalozzo/media/presentations/ciac2015-streamed.pdf
در این مقاله الگوریتم جویبار داده برای رسم گرافهای پویا (که یال به آنها اضافه / کم می‌شود) ارائه شده است. هدف این است که آخرین یالهایی که اضافه شده‌اند را بدون جا به جا کردن رأسها و یالهای قبلی (که درون پنجره‌ای با طول مشخص قرار دارند) اضافه کنیم بدون اینکه تقاطع به وجود بیاید.
** یکی از بچه‌ها دارد این گرافهای داینامیک را به عنوان موضوع انتخاب می‌کند. دلم می‌خواست من هم می‌توانستم اما بلد نیستم.

حل تمرین‌های کتاب لینچ فصل ۳

۳.۱ جزئیات دقیق‌تر اثبات درستی الگوریتم LCR را بنویسید.

الگوریتم LCR برای انتخاب رهبر در یک حلقه در مدل سنکرون است. اسم الگوریتم از اول اسم آدمهایی که پیدایش کردند می‌آید و معنی خاصی ندارد. این الگوریتمی است که با O(n^2) پیام رهبر را پیدا می‌کند.

اولین جای خالی که در اثبات کتاب هست استقرا برای اثبات این است که در راند r پردازنده‌ی (i_max+r) mod n شناسه‌ی u_max را دارد.

پایه استقرا: در راند ۰ شناسه‌ی u_max در i_max است پس حکم برقرار است.

فرض استقرا: برای راند r حکم برقرار است.

حکم استقرا: برای راند r+1 که r+1<n است حکم برقرار است.

اثبات: در راند r پردازنده‌ی (i_max+r) mod n شناسه بزرگترین را داشته است که در آن راند روی خروجی خودش قرار داده است. پس در شروع راند r+1 در ورودی پردازنده‌ی بعدی آن یعنی (i_max+r+1) mod n هست. در راند r+1 این پردازنده ورودی‌اش را دریافت می‌کند پس شناسه‌ی ماکسیمم در این پردازنده خواهد بود.

البته فکر کنم منظورش فرمال بوده که در این صورت:

incoming = u_max است. طبق تابع انتقال مقدار آن با u پردازنده (i_max+r+1) mod n مقایسه می‌شود چون u_max است حتماً بزرگتر خواهد بود پس send این پردازنده مقدار u_max را می‌گیرد.

اثبات قسمت دیگر: در راند r=n-1 چه اتفاقی می‌افتد که باعث می‌شود در راند n جواب پیدا شده باشد.

طبق لم ۲ (که الآن اثبات کردیم) در راند n-1 پردازنده‌ی (i_max+n-1( mod n شناسه‌ی ماکسیمم را در send اش دارد. در راند n پردازنده‌ی (i_max+n-1+1( mod n یعنی همان i_max شناسه‌ی u_max را دریافت می‌کند. طبق تابع transition با تشخیص مساوی بودن این شناسه با شناسه‌ی خودش، خودش را به عنوان رهبر انتخاب می‌کند (status خودش را leader می‌کند).

لم ۳: پس از r راند، اگر i <> i_max باشد و j هر پردازنده در بازه‌ی [i_max,i) باشد (بازه برعکس افتاد به دلیل تایپ، ولی مساوی i_max می‌تواند باشد و شامل i نیست)، آنگاه send پردازنده j شامل u_i نیست.

اثبات با استقرا.

پایه استقرا: در راند ۰، هیچ پردازنده‌ای به جز i مقدار u_i در send اش نیست. (شناسه‌ها متمایزند)

فرض استقرا: برای راند r

حکم استقرا: برای راند r+1

طبق فرض استقرا در راند r هیچ پردازنده‌ j در بازه‌ی [i_max,i) در send اش u_i نبوده است. در راند r+1 در send هر پردازنده [i_max,i+1

الگوریتم‌های پارامتر ثابت (مدرسه زمستانی هندسه محاسباتی)

http://wscg.aut.ac.ir/wscg8/images/Downloads/SeminarPresentations/WSCG8_Seminar_KhodaKarami.pdf
خوبی این ارائه این است که همه‌ی روشها را روی یک مسئله توضیح داده است.

Numerical Linear Algebra in the Streaming Model - IBM

researcher.ibm.com/files/us-dpwoodru/stoc09.ppt

MapReduce Algorithmics

http://www.aparat.com/v/fyP24

Randomized Composable Core-sets for Submodular Maximiza

http://www.aparat.com/v/bCKcT/Randomized_Composable_Core-sets_for_Submodular_Maximiza