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

http://www.renyi.hu/~geza/CONF/abstracts.html

(عنوانش دقیقا همین بود ولی یک مجموعه ی جالبی از ارائه های هندسی بود)

هسته برای کوچکترین توپ محیطی

http://www.renyi.hu/~geza/CONF/pankaj.pdf

هسته ها

دریافت
حجم: 402 کیلوبایت

فصل 8 وزیرانی: کوله پشتی

اگر یک مساله np-سخت بهینه سازی داشته باشیم که یک تابع هدف f دارد، الگوریتم A را برای این مساله یک شمای تقریبی می نامیم اگر به ازای ورودی های I و اپسیلون که I یک نمونه از مساله و اپسیلون مثبت پارامتر خطا است، جوابی که بر می گرداند اگر مساله کمینه سازی است 1+epsilon برابر جواب بهینه و اگر ماکسیمم کردن است 1-epsilon برابر جواب بهینه باشد.

اگر A به ازای هر اپسیلون مثبت در زمان چندجمله ای بر حسب نمونه I اجرا شود به آن شمای تقریبی با زمان چندجمله ای (PTAS) می گویند.

اگر A به ازای هر اپسیلون مثبت در زمان چندجمله ای بر حسب نمونه I و 1/epsilon اجرا شود به آن شمای تقریبی با زمان چندجمله ای کامل (FPTAS) می گویند.

بهترین جوابی که برای یک مساله np-سخت می توان داشت FPTAS است. کوله پشتی از این مساله ها است.

مساله کوله پشتی: مجموعه S={a1,...,an} از اشیا داده شده که هر کدام یک اندازه ی صحیح size(ai) دارند و سود صحیح profit(ai) و کوله پشتی هم ظرفیت B (صحیح) دارد. یک زیرمجموعه از اشیا که جمع آنها کمتر مساوی B و سود آنها ماکسیمم باشد پیدا کنید.

یک راه بدیهی برای این مساله مرتب کردن اشیا بر حسب نسبت سود به اندازه ی آنها و برداشتن حریصانه ی اشیا به این ترتیب است. می توان نشان داد که این مساله می تواند عملکرد خیلی بدی داشته باشد. (تمرین 8.1)

* الگوریتم شبه چندجمله ای برای کوله پشتی

ما تا حالا فرض می کردیم که اعداد باینری هستند (هزینه ی نمونه) ولی اگر اعداد را یونری (unary) در نظر بگیریم، اندازه ی مساله تعداد بیت های لازم برای نوشتن آن به صورت یونری است. به الگوریتمی که بر حسب اندازه ی نمونه چندجمله ای باشد کارا می گویند. (efficient).

به الگوریتمی که زمان اجرای آن روی نمونه I به اندازه ی یونری مساله وابسته باشد، شبه چندجمله ای می گویند.

کوله پشتی np-سخت است ولی الگوریتم شبه چندجمله ای دارد. همه ی الگوریتم های مسائل np-سخت که شبه چندجمله ای هستند با برنامه نویسی پویا حل می شوند. (dynamic programming)

P=ماکسیمم سود بین اشیا؛ در این صورت کران بالای بدیهی مساله nP است.

S(i,p) = به ازای هر i بین 1 تا n و هر p بین 1 تا nP : زیرمجموعه ای از اشیای 1 تا i که سود p دارد و اندازه ی آن کمینه است.

َA(i,p) = اندازه ی مجموعه ی S(i,p) و بینهایت اگر چنین مجموعه ای وجود نداشته باشد.

ما برای هر سود p مقدار A(1,p) را می دانیم (شی a1 را برداریم و سود آن را ببریم و در بقیه حالت ها بینهایت.)

دنباله ی بازگشتی زیر نجوه ی محاسبه ی مقادیر A(i,p) را در زمان O(n^2P) نشان می دهد:

بیشترین سودی که می توان با اشیای با مجموعه اندازه ی کمتر از B به دست آورد، ماکسیمم سود A(n,p) هایی است که کمتر مساوی B اند.

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

* یک FPTAS برای کوله پشتی

دقت کنید که اگر سود اشیا کوچک باشد، مثلا کمتر از چندجمله ای بر حسب n باشد، در این صورت این الگوریتم چندجمله ای معمولی خواهد بود چون زمان آن چندجمله ای بر حسب اندازه ی نمونه است. (باینری). ایده ی اصلی به دست آوردن FPTAS استفاده از همین است: ما بیتهای کم ارزش سود اشیا را بسته به اپسیلون در نظر نمی گیریم، در نتیجه سود جدید می تواند به صورت چندجمله ای بر حسب n و 1/epsilon دیده شود. این به ما امکان پیدا کردن جواب با سود حداقل 1-epsilon برابر بهینه در زمان چندجمله ای بر حسب n و 1/epsilon را می دهد.

الگوریتم 8.2: FPTAS برای کوله پشتی

1) یک اپسیلون مثبت داده شده، K=epsilon*P/n قرار بده.

2) به ازای هر شی ai، سود جدید آن را کف سود قبلی تقسیم بر K قرار بده.

3) با این سودهای جدید الگوریتم dp را اجرا کن و مجموعه با بیشترین سود را به دست بیاور. S'

4) S' را برگردان.

لم 8.3. اگر A زیرمجموعه ای باشد که الگوریتم بر می گرداند، آنگاه:

profit(A) >= (1-epsilon)*OPT

اثبات: فرض کنید O زیرمجموعه بهینه باشد. به ازای هر شی a به دلیل رند کردن به پایین K*profit'(a) می تواند از profit(a) کمتر باشد، اما نه بیشتر از K.

{

طبق تعریف جزء صحیح می دانیم که حداکثر K تا از مقدار کم شده (در واقع K-1) پس برای هر شی داریم:

K * (profit(ai)-(K-1))/K <= K.profit'(ai) ==>

profit(ai) - K <= K*profit'(ai) ==>

profit(ai)-K*profit'(ai) <= K ==>

(sum): profit(O)-K*profit'(O) <= |O|*K <= n*K

}

پس:

profit(O)-K*profit'(O) <= nK

در گام dp باید جوابی که برمی گردد حداقل به خوبی O برحسب سودهای جدید باشد. پس:

...

جواب سوال سمیه!

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

می خواهم N عدد k بیتی را مرتب کنیم. یک آرایه از پردازنده ها داریم که k سطر (معادل هر بیت عدد) و N ستون (معادل هر عدد) دارد. حالت خاص زیر را در نظر بگیرید (بیتهای پر ارزش در سطرهای بالا و کم ارزش در سطرهای پایین اند)

x 0 0 ... 0

0 1 1 ... 1

0 0 0 ... 0

...

1 0 0 ... 0

همه ی اعداد به جز عدد اولی با هم مساویند. حالا گفته است که بیت آخر جواب آرایه مرتب شده اگر x=0 باشد 1 است و اگر x=1 باشد 0 است. یعنی باید مقدار پردازنده 1و1 به پردازنده ی k,N برسد. که این یعنی قطر شبکه را طی کند.

http://mycourse.blog.ir/1392/12/05/%D8%AD%D8%AF-%D9%BE%D8%A7%DB%8C%DB%8C%D9%86-%D8%A8%D8%B1%D8%A7%DB%8C-%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%D9%87%D8%A7%DB%8C-%D9%85%D9%88%D8%A7%D8%B2%DB%8C

تمرین سری اول هندسه پیشرفته

http://ce.sharif.edu/courses/92-93/2/ce795-1/assignments/files/assignDir/A1.pdf

Discrepancy

http://www.cs.princeton.edu/~chazelle/pubs/book.pdf

این کتاب را قبل از خواب بخوانید تا کابوس ببینید! :)

الگوریتم های پردازش داده های بزرگ (کارسوق سال 2009)

http://www2.cse.iitk.ac.in/~fsttcs/2009/wapmds/schedule.php

هم اسلاید ارائه ها هست هم فایل ارائه.

کتاب هندسه گسسته Matousek

همین الآن فهمیدم که این کتاب را نداشتم! :) البته کیفیت این کتابی که اینجاست اسکن است.

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

همسایه نزدیک تقریبی

http://www.cs.uml.edu/~kdaniels/courses/ALG_504_S10/OLD/CG_Lecture8.ppt