اصلاحیه پست تمرین‌های سری اول پردازش موازی

این شکل جا مانده بود!

حل تمرین پردازش موازی

سوالهایی که از سر کلاس باقی موند: (قسمت حل نشده و راه‌حل دوم سوالها)

۱- سوال ۱.۲۳: کم کردن دو عدد در مبنای ۱ (بدون مکمل ۲)

Subtraction is similar, except that borrows, rather than carries, are propagated to the left. If the borrow extends past the end of the word it is said to have "wrapped around", a condition called an "end-around borrow". When this occurs, the bit must be subtracted from the right-most bit. This phenomenon does not occur in two's complement arithmetic.

  0000 0110      6
− 0001 0011     19
===========   ====
1 1111 0011    −12    —An end-around borrow is produced, and the sign bit of the intermediate result is 1.
− 0000 0001      1    —Subtract the end-around borrow from the result.
===========   ====
  1111 0010    −13    —The correct result (6 − 19 = -13)

منبع:

http://en.wikipedia.org/wiki/Ones'_complement

۲- تمرین ۱.۲۸ کتاب (هنوز جزو مسائل حل نشده است و من به عنوان اشکال پرسیدم!)

۳- در سوال ۱.۵۳ کتاب در مورد ارسال اطلاعات به دو طرف چه می‌توانیم بگوییم؟ (انگار ثابت شد که صورت سوال غلط است اگر ارسال اطلاعات پردازنده‌های مجاور را در نظر بگیریم.)

۴- ۱.۶۶: تعریف slow down (صفحه ۱۱ کتاب Leighton)

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

۵- ۱.۶۸ : یک ماتریس b-قطری پایین مثلثی داریم وارون آن را با یک آرایه پردازنده b*b به دست آورید.

تبریک به خودم

الآن از استاد درس داده کاویمون پرسیدم که نمره ام خوبه یا بده گفت نمره ی دوم-سوم کلاسی. :)

خواستم به خودم موفقیت ترم قبلم رو تبریک بگم!

دستورات Latex برای فرمولهای ترکیبیاتی

http://www.combinatorics.net/Resources/weblib/commands/command.html

مروری بر آنچه گذشت.. (هندسه محاسباتی پیشرفته)

۱- تقریب قطر

*تقریب ضریب ثابت: استفاده از نامساوی مثلث و ... برای به دست آوردن تقریب ثابت+تقریب قطر با دورترین نقطه از یک نقطه

*رند کردن ورودی: نقاط ورودی را به نزدیک ترین رأس توری رند می‌کردیم.

*رند کردن جهت‌ها: یک سری شعاع با فاصله یکسان می‌کشیدیم و در راستای آنها جواب را حساب می‌کردیم. + directional width

*روش ترکیبی: برای به دست آوردن جواب در یک خانه توری از یک روش دیگر استفاده می‌کردیم. (ترکیب دو روش تقریبی)

*دیاگرام ورونوی گسسته: یک توری می‌ساختیم و فقط دورترین نقطه به نقاط توری را پیدا می‌کردیم.

۲- تقریب عرض

*رند کردن در جهت‌ها و LP: رند کردن جهت‌ها و استفاده از LP در مرحله‌ی آخر به جای یک الگوریتم دیگر+ساخت توری تجانس یافته در یک جهت و رند کردن نقاط در آن جهت

*یک تقریب ثابت ساده برای عرض: دورترین نقطه نسبت به پاره خط واصل یک نقطه دلخواه و دورترین نقطه به آن

*اپسیلون-هسته: ساخت هسته با روش افزایشی روی ابعاد و تصویر کردن

*روش سریعتر برای محاسبه هسته: تبدیل آفین (ترکیب خطی برداری)‌+رند کردن به رئوس توری

-موارد دیگر: +دیاگرام ورونوی گسسته +تقریب هسته extent برای همه‌ی توابعی که به پوسته محدب وابسته اند.

۳- مدل جویبار داده (Streaming)

* روش لگاریتمی برای حفظ هسته: هسته دو مجموعه نقطه را به هسته برای اجتماع نقاط تبدیل می‌کند.(برای گستره نقاط)+روش لگاریتمی: ادغام (دو هسته) و کاهش (حذف هسته‌های قبلی)

*روش دوبرابر کردن برای حفظ هسته: نقاط را به صورت افزایشی اضافه می‌کنیم، هرجا تقریب از ۲ بیشتر شد به هسته نقطه اضافه می‌کنیم.

*هسته تقریبا بهینه در مدل جویبار داده:‌ دوبرابر کردن+رسم مجدد توری با اپسیلون جدید در هر مرحله و محاسبه جواب توری جدید از روی قبلی

۴-کوچکترین توپ محیطی

*الگوریتم جویبار داده ساده با ضریب ۳/۲: مرکزهای متحرک (توپ‌های محیطی)

*الگوریتم تکراری +شمای تقریبی (تقریب ۱+اپسیلون): روش مرکزهای متحرک با اضافه شدن دورترین نقاط به جواب قبلی به صورت افزایشی

*هسته با اندازه یک بر اپسیلون برای هر بعدی: بهبود تحلیل روش قبل با محاسبه‌ی حداکثر تغییر در هر مرحله

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

*روش جستجوی شعاع ثابت (دو روش ساده مبتنی بر توری): فقط خانه‌های توری که نقطه دارند نگه دار و هنگام کوئری خانه‌های اطراف یک نقطه را به دست بیاور. روش۲: خانه‌های توری اطراف هر نقطه را نگه دار و هنگام کوئری یک دایره شامل نقطه کوئری را از بین همسایگی‌های نقاط برگردان.

*استفاده از درخت چهارتایی (نسخه‌های فشرده و متوازن):‌ توری سلسله مراتبی برای حل مشکل شعاع متغیر. استفاده از تقاطع دایره کوئری با خانه‌های توری‌های درخت چهارتایی

*کاهش ابعاد با لم JL: تصویر کردن تصادفی و استفاده از توری

۶-تجزیه زوج خوب از هم جدا شده (WSPD)

*تجزیه زوج از هم جدا شده:‌ برای ساخت آن از درخت چهارتایی فشرده استفاده می‌کنیم و تا وقتی که فاصله‌ی دایره‌های متناظر مجموعه نقاط به نسبت شعاع بر اپسیلون نرسیده است مجموعه نقاط را تقسیم می‌کنیم و در درخت پایین می‌رویم.

*کاربرد آن در پوشاننده‌ها و درخت پوشای کمینه‌ی اقلیدسی: نسبت کوتاهترین فاصله در گراف به فاصله اقلیدسی حداکثر t باشد به گراف t-spanner می‌گوییم. اگر از زوج‌های خوب جداشده هر دو نقطه را به هم وصل کنیم گرافی که به دست می‌آید ۱+اپسیلون پوشاننده است. درخت پوشای کمینه اقلیدسی را هم با اجرای الگوریتم درخت پوشای کمینه روی پوشاننده می‌توان به دست آورد. (با الگوریتم‌های معمولی MST مثل prim و kruskal)

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

https://www.cs.umd.edu/~mount/Papers/soda93-ann.pdf

لیست کنفرانسهای الگوریتم

http://academic.research.microsoft.com/RankList?entitytype=3&topdomainid=2&subdomainid=1&last=0

ساده سازی مسیرهای هندسی

دفاع آقای دانش پژوه بودیم! :)

حالت های مساله:

*حالت دو بعدی (صفحه)

*حالت دو و نیم بعدی (طول و عرض و ارتفاع): مثل حرکت روی زمین

روش های حل مساله:

*ساده سازی هموتوپیک: مسیری که می دهیم را بدون عبور از هیچ مانعی بتوان به مسیر اصلی تبدیل کرد. (در یک حالت به ازای هر قسمت از مسیر به صورت محلی این کار را می کرد و در حالت دیگر به ازای کل مسیر. فکر کنم اولی محدود بود دومی نامحدود.)

*ساده سازی با دنباله کانونی: دنباله ای که اگر مسیر از زیر یک نقطه عبور می کرد x_ و اگر از بالای آن عبور می کرد x- می گذاشتیم. با این کار دنباله را به صورت خطوط افقی و عمودی به دست می آوردیم.

*ساده سازی با مسیرهای x-یکنوا: به چند تا مسیر که بر حسب مولفه x شان یکنوا بودند تقسیم می کرد.

*ساده سازی با دید پذیری: ایده ی آن رسم شعاع از یک نقطه (نقطه شروع) بود و روی این شعاع ها تصویر می کردیم.

اینجا هم تعریف خطا در مساله تاثیر زیادی دارد (مثل داده کاوی). خطاهایی که در نظر گرفته بودند:

*اختلاف مساحت ها (مساحت جهت دار که در خود ارائه به آن گفتند مساحت قطبی ولی همان چیزی بود که ما همیشه حساب می کردیم. الآن که فکر می کنم می بینم تا حدی شبیه جمع مینکوفسکی هم هست!)

برای این کار ثابت کرده بودند که می شود مسیر را با اضافه کردن قسمت دیگری به شکل مساحت در آورد.

*ناحیه دید پذیر: تعداد پاره خطهایی که بعد از ساده سازی دیگر دیده نمی شوند.

از ایده هایی که در این زمینه توسط داورها داده شد:

*دادن تقریب برای حالتی بود که گوشه های نوک تیز داشته باشیم که مساحت کم دارند. گفتند نمی شود ولی به نظرم اگر ایده ای در مورد spanner ها جواب بدهد باید اینجا هم جواب بدهد. (این ایده ی آقای خسروی-دانشگاه تهران) بود.

*ایده ی دیگری که مطرح شد (باز هم آقای خسروی) این بود که روی  triangulated irregular network (TIN) مساله را حل کنند (کلا ایشون ایده می دادند به جای اینکه ایراد بگیرند! :دی) که البته جزو کارهایی که آقای دانش پژوه (ارائه دهنده) کرده بودند بود ولی فقط نتایج عملی داشت.

از ایرادهایی که گرفته شد:

*ایراد دکتر محدث (علوم کامپیوتر-امیرکبیر) گرفتند این بود که اگر دو نقطه x برابر داشته باشند چه کار می کنید. خود آقای دانش پژوه به عنوان ایراد این را قبول کردند اما من قبول ندارم چون ما در هندسه محاسباتی خیلی اوقات فرض general position (اینکه هیچ سه نقطه ای هم خط نباشند، هیچ چهار نقطه ای هم دایره و ..) می کنیم که استدلالمان هم این است که با اپسیلون تا جا به جا کردن نقطه می شود به این حالت رسید. با توجه به اینکه این کار ساده سازی هندسی هم بود خیلی به نظرم اپسیلون تا جا به جا کردن نقطه تاثیر نداشت.

*ایرادهای دکتر رزازی (نرم افزار -امیرکبیر) را که ما به دلیل پذیرایی نصفش را نشنیدیم ولی بیشتر در مورد ایده های اصلی کار و هدف کار بود و اینکه چرا بر حسب پارامترهای خطا تقریب ندارند که جواب آقای دانش پژوه هم این بود که تا همین حد از تضمین های تئوری در کارهای این زمینه نیست و روشی که تقریب خطاها را داده باشد اصلا نیست. (چون تقریب ها بر حسب میزان ساده سازی مسیر بود.)

*ایرادی که دکتر ضرابی زاده (استاد فعلی من!) گرفتند این بود که اگر الگوریتم را برای حالت جویبار داده استفاده می کنید باید زمان آن زیرخطی (sublinear) باشد و شما بر حسب k (تعداد نقاطی که در مسیر ساده شده از بین نقاط مسیر اصلی نگه داشته می شوند) است. جوابی که داده شد این بود که k در ورودی داده می شود که به نظر من قانع کننده نبود.

*ایراد دیگری که دکتر ضرابی زاده گرفتند این بود که شما فقط یک بار کوئری می زنید ولی به دو مرحله ی پیش پردازش و کوئری تقسیم کردید که جواب دادند برای سادگی کار بوده است.

جالب ترین قسمت برای من قسمتی بود که آقای دکتر قدسی (استاد پروژه) از دانشجویشان بابت زحمتهایی که کشیدند تشکر کردند و آقای دانش پژوه هم از ایشان تشکر کردند. ولی واقعا خیلی حس بدی است که آدم این همه برای پروژه زحمت می کشد و آخرش با ایراد گرفتن تمام شود. این تشکر به نظرم خیلی ارزشمند بود.

تمرین سری اول الگوریتم تقریبی

http://ce.sharif.edu/courses/92-93/2/ce726-1/assignments/files/assignDir3/exercises1.pdf

اصلاحیه 2

چقدر من اشتباه های وحشتناکی می کنم موقع مساله حل کردن! امروز که مرکز کوچکترین توپ محیطی رو نوشتم میانگین نقاط!! (اگر خوشه بندی بخواهیم حساب کنیم این معادل k-center است و چیزی که من نوشتم معادل k-means است!)

الآن هم دیدم که در حل تمرین های موازی که روی وبلاگ هست اشتباه های بسیار بسیار عالی هست!

فردا صبح باید بروم تمرین ها را پس بگیرم درستشان کنم! :) شما هم با دقت فراوان حل های من را به کار ببرید! (ترجیحا به کار نبرید فقط اگر هیچ ایده ای نداشتید ایده بگیرید!)