الگوریتم امروز

ٰ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 مگابایت

۰ نظر

۰ ۲۵ مرداد ۹۳ ، ۱۷:۱۲

سپیده آقاملائی

قدیمی ترین مطالب مطالب قدیمی تر جدیدترین مطالب مطالب جدید تر