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

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) بهترین کار راستگوییه. :)

tree metric

فصل 5.8 ویلیامسون

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

موتور جستجوی برنامه‌های شی گرا

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

از نظر اینکه پردازش کمتری می‌خواد این کار (یعنی اکثرش توی پیش‌پردازشه و زمان کوئری کمی داره، بر خلاف روش‌های بر مبنای آنتولوژی که مقایسه‌ی اون آنتولوژی کلی زمان می‌خواد اینجا فقط چند تا کلمه است مثل موتورهای جستجوی معمولی) خیلی بهتر بود.

تنها چیزی که استادهایش هم می‌دانستند integrated library system (ILS) بود که سعی می‌کردند هر تکرار کنند که ما گول بخوریم که بلدن. (امان از دست استادها! :)) )

از این نظر که مراحل موتور جستجو رو برای من مرور کرد خیلی خوب بود. یک سری ایده‌ی جدید بهم داد که نمی‌گم چون خودم لازمشون دارم. :)

ارائه‌ی پردازش موازی

اسلایدهایش رو آپلود نکرده بودم. یک جا اشکال تایپی داره.

دریافت
حجم: 1.06 مگابایت

Chamfer Distance

http://www.cs.cornell.edu/courses/cs664/2008sp/handouts/cs664-8-binary-matching.pdf

تصویر کردن ۳ بعد روی ۲ بعد

http://web.iitd.ac.in/~hegde/cad/lecture/L9_persproj.pdf

به دست آوردن ناحیه قابل دید ۳ بعدی مثل تصویر کردن یک شکل ۳ بعدی روی یک صفحه ۲ بعدی است، که اینجا صفحه‌ی ۲ بعدی همان وجه است و شکل ۳ بعدی خود ناحیه است.

به جز اینکه به جای کودا گفتم سی پلاس پلاس و به جای اینکه زمان چندوجهی ساده رو بگم زمان چندضلعی ساده رو گفتم، یک چیز دیگه رو هم اشتباه گفتم که این بود که اگر نقطه در بینهایت باشد یعنی عمودی تصویر کنیم، در حالی که این طوری نیست و فقط ماتریس تبدیلش فرق دارد. (لینک رو ببینید.)

راستی اسم الگوریتم‌ها هم z-buffer و painter's algorithm بود.

Sketching, streaming, and sub-linear space algorithms

http://people.csail.mit.edu/indyk/ita-web.pdf

ساختارهای ضمنی در هندسه ابعاد بالا

مرجع: http://people.csail.mit.edu/indyk/neumann.pdf

affine transformation

http://en.wikipedia.org/wiki/Affine_transformation

In geometry, an affine transformation, affine map^[1] or an affinity (from the Latin, affinis, "connected with") is a function between affine spaces which preserves points, straight lines and planes. Also, sets of parallel lines remain parallel after an affine transformation. An affine transformation does not necessarily preserve angles between lines or distances between points, though it does preserve ratios of distances between points lying on a straight line.