دفاع!

ساعت ۱۰:۳۰ امروز دفاع امیرمهدی احمدی‌نژاد است. ۲۰۱

پوشش موزههای هنر متعامد توسط kـ فرستندههای لغزان

https://projects.cs.dal.ca/cccg2014/proceedings/papers/paper12.pdf
سه شنبه ساعت ۱۲ اتاق ۷۲۶

طراحی مکانیزم‌های توزیع شده

http://theory.ce.sharif.edu/images/pdf/MrAsgharian.pdf

ٰVickrey auction: همان حراج دومین قیمت است که هیچ کس پیشنهاد بقیه را نمی‌بیند و کسی که بیشترین پیشنهاد را داده برنده می‌شود ولی قیمت نفر قبل از خودش را می‌پردازد.

Vickrey-Clarke-Groves (VCG): حراج دومین قیمت برای یک جنس تعریف شده است. اگر بخواهیم چند جنس را بفروشیم از این مدل استفاده می‌شود. uniform price auction یا حراج با قیمت یکنواخت، جمع سود و زیان خرید هر جنس را برای هر نفر ملاک قرار می‌دهد و هر جنس را مثل حراج دومین قیمت می‌فروشد.

هر دوی این روشها تضمین راستگویی را دارند، یعنی اگر کسی قیمت نادرست بگوید ضرر می‌کند.

http://en.wikipedia.org/wiki/Vickrey%E2%80%93Clarke%E2%80%93Groves_auction

مکانیزم توزیع شده‌ی VCG: توی این مقاله انگار هر کسی یک توان پردازشی دارد و می‌خواهد یک سری کار را اختصاص بدهد.

اول توضیح داده که چرا به سادگی نمی‌شود راستگویی را به دست آورد:

الگوریتم این طوری است که از هر کسی می‌پرسد که توان پردازشی‌ات چیست؟ و برای همه می‌فرستد. حالا کاری را که در حالت متمرکز پردازنده‌ی مرکزی انجام می‌داد، انجام می‌دهد و کار بهینه را بر اساس آن انتخاب می‌کند. مرکز سود دادن یک کار به یک نفر و ندادنش را حساب می‌کند. حالا قسمت آخر VCG را اجرا می‌کند و کارها را اختصاص می‌دهد.

(حالا کاری که ملت می‌کنند این است که در مورد توان پردازشی‌شان راست نمی‌گویند و مثلاً می‌توانند باعث شوند یک نفر که کمتر از بقیه گفته است کلاً حذف شود.)

http://www.eecs.harvard.edu/econcs/pubs/distr_vcg.pdf

انگار ثابت کرده است که برای مجموع سود افراد (VCG) بهترین کار راستگوییه. :)

visibility kernel of a simple polygon

کرنل مجموعه نقاطی هستند که از آنها همه‌ی چندضلعی قابل دیدن است.

منبع: http://www.iitg.ernet.in/rinkulu/compgeom/slides/kernel.pdf

در هندسه محاسباتی تمرین چندضلعی ستاره شکل همین را حساب می‌کرد که در واقع وسط ستاره جایی بود که همه‌ی قسمت‌های دیگر را می‌دید.

ارائه‌ی امروز ساعت ۱۰:۳۰ : http://theory.ce.sharif.edu/images/pdf/SHaratian.pdf

این هم در مورد Gap Navigation Tree:

file:///C:/Users/DELL/Desktop/Workshop_Presentation.ppt

On triple intersections of three families of unit circles

Let p1, p2, p3 be three distinct points in the plane, and, for i = 1, 2, 3, let Ci be a family of n unit circles that pass through pi. We address a conjecture made by Székely, and show that the number of points incident to a circle of each family is O(n11/6), improving an earlier bound for this problem due to Elekes, Simonovits, and Szabó [4]. The problem is a special instance of a more general problem studied by Elekes and Szabó [5] (and by Elekes and Rónyai [3]).

اسلایدهای مدرسه زمستانی هندسه محاسباتی

http://wscg.aut.ac.ir/wscg6/index.php?option=com_content&view=article&id=3&Itemid=2

شباهت منحنی‌ها

http://cs.au.dk/~ld/Thesis_Lasse_Deleuran_June_2012.pdf

http://ce.sharif.edu/~daneshpajouh/publications/posters/shervin-madalgo.pdf

اون تز اولی تهش مقاله‌های دکتر آبام و شروین دانش پژوه رو داره و دومی هم اسلایدهای خودشه.

cake cutting

http://iiis.tsinghua.edu.cn/~eccs/eczb6.pptx

شبکه‌های جهان کوچک

این مطلب درخواستی یکی از دوستان است! :) برای اینکه مطلب مفهوم‌تر باشد سعی کردم از یک منبع کمک بگیرم!

مرجع: http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book-ch20.pdf

۱- درجه جدایی ۶:

یعنی در گراف آن با طی کردن ۶ یال از هر رأسی می‌توانیم به هر رأس دیگری برسیم.

داستان آن از اینجا شروع شده است که یک نفر یک سری نامه برای چند نفر فرستاده و خواسته که آنها برای یک آدم خاص بفرستند یا به کسی بفرستند که آن فرد را می‌شناسد. و به طور میانگین (expected) با ۶ گام نامه‌ها به مقصد رسیده‌اند.

۲- ساختار و تصادفی بودن:

گفتیم به صورت متوسط این اتفاق می‌افتد. این کار را با محاسبه امیدریاضی انجام می‌دهند. می‌شود ساختارهایی ساخت که این خاصیت را دارند، اما سوال اصلی این است که گرافی مثل شبکه‌ی اجتماعی چرا این خاصیت را دارد؟ چون مثلاً در گرافهایی که مطمئنیم این خاصیت برقرار است مثلاً در مثال زیر فرض می‌کنیم هر نفر ۳ دوست دارند که آنها هم ۳ دوست جدید دارند و ...، در حالی که در عمل این طور نیست و اکثراً بین دوست‌های افراد اشتراک هست.

برای اینکه مشکل تعداد دوست‌های جدید را حل کنیم، فرض می‌کنیم هر کسی تعداد دوست جدید کمی دارد ولی به جای آن دوست با فاصله‌ی زیاد از همسایه‌هایش به آن می‌دهیم. مثال زیر را در نظر بگیرید که در آن یک توری داریم و یک سری یال تصادفی به آن اضافه کرده‌ایم.

مدل Watts-Strogatz:

کافی است فقط تعدادی از افراد در شبکه تصادفی، لینک (یال) به یک فرد دور داشته باشند.

جستجوی غیرمتمرکز:

حالا سوال این است که از یک مبدأ به یک مقصد بدون دانستن لینک‌های تصادفی چطور باید یک بسته را بفرستیم؟

هر کسی به صورت محلی این طور عمل می‌کند که بسته را به نزدیک‌ترین همسایه‌اش به هدف می‌فرستد.

این کار در حالت عادی زمان زیادی می‌گیرد ولی اگر طول لینک‌های تصادفی از حدی بیشتر باشد این زمان کم می‌شود.

از اینجا به بعد وارد محاسبات شده است اگر خواستید خودتان بخوانید. من هم فقط سر یک talk رفتم در مورد این و چیز بیشتری نمی‌دانم و اگر بخواهم توضیح بدهم باید خودم اول بخوانم.

کدینگ

کدینگ در شبکه:

به جای اینکه خود اطلاعات را بفرستیم کد آنها را بفرستیم.

مثال: دو نفر می‌خواهند پیامشان را از طریق یک سرور ارسال کنند. هر دو پیام را به سرور می‌فرستند و در آنجا xor پیام محاسبه می‌شود و برای هر کس فرستاده می‌شود. با این کار هر دو پیام را با xor کردن با پیام خودشان به دست می‌آورند.

مثال: دو مبدأ می‌خواهند پیامشان را به دو مقصد بفرستند. هر کس وقتی پیام خودش را می‌فرستد، بقیه هم دریافت می‌کنند، اینجا بر خلاف قبل آن را دور نمی‌ریزند. در این صورت وقتی سرور xor پیام را می‌فرستد آنها هنوز قادرند پیام اولیه را به دست بیاورند.

در هر دو مثال بالا تعداد ارسال‌ها از ۴ گام به ۳ گام کاهش داده می‌شود.

کدینگ حافظه:

در پایگاه داده‌ها ما از افزونگی برای جلوگیری از نابودی اطلاعات به دلیل مشکل سخت‌افزاری استفاده می‌کنیم. Reed-Solomon یکی از این روش‌ها است. A+B و A+2B را به جای سه تا نمونه از هر کدام نگه می‌داشت. (اگر دو تا خراب بشه باز هم کار می‌کند.)

الگوریتم:

داده‌ها را به ۱۰ بلوک تقسیم می‌کنیم و با ۵ تا رابطه که هر کدام بر حسب ۵ تا بلوک هستند می‌توانیم جواب مسأله را حساب کنیم. اما می‌توان طوری این روابط را محاسبه کرد که تکراری داشته باشند و نیاز به ۲۵ عمل نداشته باشیم. برای ۲۰ تا رابطه‌ی آن ارائه شد. سوال: آیا کمتر هم می‌شود؟