مسایل فصل 1 کتاب وزیرانی

سوال 1:

برای اینکه از عدم وجود دور در گراف مطمئن باشیم از این روش استفاده می کنیم که به یک رأس یا وارد می شویم یا از آن خارج می شویم. در ایصورت در گراف جهت دار دوری نخواهیم داشت. 

طبق راهنمایی سؤال رئوس را به ترتیب دلخواه شماره گذاری می کنیم و و به این ترتیب کل یال ها را به دو دسته تقسیم می کنیم :

دسته اول یال هایی که از رأس با شماره بزرگتر به رأس با شماره کوچکتر می روند و یال هایی که از رأس با شماره کوچکتر به رأس با شماره بزرگتر می روند . از بین این دو دسته دسته بزرگتر را انتخاب می کنیم. بدیهی است که در اینصورت دور نداریم. 

و چون دست کم نصف یال ها را با این الگوریتم انتخاب خواهیم کرد و تعداد بهینه یال ها برای این الگوریتم حداکثر برابر کل تعداد یال ها در گراف اصلی است به وضوح این الگوریتم از فاکتور 1/2 است.

سؤال 2:

یک تطابق از گراف پیدا می کنیم. به این ترتیب که از یک رأس شروع می کنیم و با یکی از همسایگانش تطبیق می دهیم و از گراف حذف می کنیم. و به همین ترتیب ادامه می دهیم. این یک تطابق maximal از گراف می دهد که طبق راهنمایی سؤال از نصف تطابق ماکزیمم بیشتر است یعنی تطابق ماکزیمم از 2 برابر تطابق بیشینه کمتر است و از تطابق بیشینه بیشتر است( بدیهی است!) یعنی الگوریتمی با فاکتور 2

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

سؤال 3:

ابتدا نشان می دهیم که مجموعه انتخاب شده یک vertex cover برای گراف هست. با توجه به اینکه در پیمایش عمقی گراف برگ ها فقط به پدرشان یا به گره های جدشان یال دارند بنابراین با توجه به اینکه تمام گره های غیر برگ در این مجموعه قرار گرفته اند بنابراین نیازی به انتخاب برگ ها نیست چون برای تمام یال ها یک سرشان در این مجموعه قرار گرفته است و این یک VC است. 

حالا فاکتور 2 را اثبات می کنیم. برای این می دانیم که گره ها فقط به پدر یا اجدادشان یال دارند. بنابراین کافیست گره های غیر برگ در عمق های فرد را با گره های غیر برگ در عمق زوج تطابق دهیم و دو سر این تطابق را ( که یک تطابق ماکزیمال است ) به عنوان جواب گزارش کنیم. تعداد این تطابق حداکثر برابر نصف گره های غیر برگ است. ( این در حالتی اتفاق می افتد که تعداد گره ها در عمق زوج و فرد با هم برابر باشد.) که می دانیم تعداد این تطابق ها همیشه از کاردینالیتی کمتر است.( lower bound)  بنابراین فاکتور 2 اثبات می شود.

مثال tight : گراف دو بخشی است.  که به صورت زیگزاگ به هم یال دارند. 

سؤال 4: 

مثال tight  رو سر کلاس دکتر آبام گفتن. اما شکلش رو میذارم بعداً. حتماًً................. :)

سؤال 5: 

سؤال 9:

فرض کنید k  برابر OPT_VC روی گراف با گره هایی با وزن 1 باشد. راه حلی از مرتبه چند جمله ای برای پیدا کردن اینکه گراف دارای این VC هست یا نه نداریم. که بعد از آن بخواهیم می نیمم هزینه را برای این دربیاوریم! راه حل چند جمله ای ما در بهترین حالت از فاکتور 2 است. 

بنابراین این مسأله هم NP-optimization  است. در واقع این مسئله همان ورژن تصمیم گیری مسئله VC است. 

یک مثال از کتاب پرهامی

مسئله تهیه لیستی از اعداد اول در فاصله تعریف شده برای عدد داده شده N>0 می باشد. 

[1..N]

یک الگوریتم ساده برای انجام اینکار استفاده از روش غربال   Eratosthenes می باشد. بدین صورت که با لیستی از اعداد به صورت 1,2,3,..,N  که به صورت یک بردار که با 00..1000 مقدار دهی شده است نمایش می دهیم. در هر گام  عدد بعدی m که علامتدار نشده است (عددی که بیت مربوطه اش در بردار برابر 0 است. ) اول است. با پیدا کردن این عدد، شروع به حذف مضارب این عدد که با m² شروع می شود، می کنیم. زمانی که m²>n شود محاسبات تمام می شود و تمام اعدادی که با 0 علامتگذاری شده اند اول هستند. 

شکل زیر گام های محاسبات را برای N=30 نشان می دهد. 

در شکل بالا پیاده سازی این الگوریتم در تک پردازنده دیده می شود. متغیر عدد اول جاری با عدد 2 مقدار دهی اولیه می شود و در گام های بعدی آخرین عدد اولی که تا به حال پیدا شده است را در این متغیر نگه داری می کنیم. برای هر عدد اولی که پیدا می کنیم متغیر index  با مقدار مربع این عدد مقدار دهی می شود. و سپس با مقدار عدد اول جاری افزایش می یابد تا تمام ضرایب این عدد را علامتگذاری کند. 

شکل زیر اولین راه حل ما برای اجرای موازی این الگوریتم با P پردازنده را نشان می دهد. لیست اعداد و عدد اول جاری (the current prime) را در یک حافظه اشتراکی ذخیره می کنیم. که برای همه پردازنده ها قابل دسترسی است. 

در این روش هر پردازنده که بیکار است به حافظه اشتراکی مراجعه کرده و عدد اول جاری را به روز می کند. و با استفاده از ایندکس این عدد از در میان لیست حرکت کرده و و مضارب این عدد اول را علامتگذاری می کند. 

در نتیجه این تقسیم کار به صورت خودکار انجام می شود. در شکل زیر فعالیت های یک پردازنده را در این روش شرح می دهد. برای n=1000 , p>=1  , p<= 3 

دقت کنید که در این روش حل موازی افزایش پردازنده ها بیشتر از 3 زمان محاسبات را کاهش نخواهد داد. زیرا کار پردازنده اول 500 استپ زمان نیاز خواهد داشت. 

تلاش بعدی ما با تقسیم داده کار می کند بدین صورت که بردار بیتی که نماینده n عدد صحیح هستند به p تا قطعه مساوی تقسیم می کنیم. که هر قطعه در یک حافظه خصوصی یک پردازنده ذخیره می شود. فرض می کنیم که P<= sqrt(n  به طوریکه هر عدد اولی که در لیست باقی خواهد ماند در قطعه مربوط به پردازنده اول نیز ضرایبی خواهد داشت. پردازنده اول نقش هماهنگ کننده خواهد داشت: این پردازنده مسئول پیدا کردن عدد اول بعدی و برودکست آن به پردازنده های دیگر است. و آن ها سپس شروع به علامت زدن ضرایب در زیر لیست خودشان هستند. کل زمان مربوط به این الگوریتم به دو بخش تقسیم می شود: زمان برودکست اعداد اول به پردازنده ها و زمان صرف شده توسط پردازنده های برای علامتگذاری اعداد درون لیست. 

اشتباه در عکس 35-1 کتاب لایتون

فکر می کنم در این عکس باید ترتیب X_i ها برعکس باشه تا نتیجه ضرب در پردازنده ها ظاهر بشه.

Prefix Computation

مسئله محاسبه نقلی با رشته های s, p , g  به طور خلاصه تر می تواند با Prefix Computation بیان شود. به صورت دقیق تر X_i نشاندهنده مقدار s,p,g برای iامین بیت از سمت راست جمع است. 

ضمن این باید چک کنیم که عملگر باینری در این محاسبات می بایستی شرکت پذیر باشد. 

کافیست جدول بالا را چک کنیم. هر مسئله ای که بتوان عملگر دودویی به طریقی که در اینجا تعریف شد برایش تعریف کنیم را می توان با همین روش و با یک درخت باینری کامل در 2D + 1 گام حل کرد. که D عمق درخت باینری است.

در جمع با پیش بینی نقلی در واقع عمل جمع شامل دو فاز متناوب می شود. در فاز اول هر گره داخلی حاصل دو داده ورودی را محاسبه می کند و در فاز دوم این نتیجه را به سمت پایین می فرستد به طوریکه برگ iام شامل ith prefix خواهد بود.

بخش 1-2-1 جمع صحیح با الگوریتم پیش بینی نقلی

این الگوریتم جمع دو عدد N-bit  در1 + lg N * 2 گام با درخت N برگی کامل. و افزایش سرعت زیاد نسبت به روش ترتیبی با N گام. 

به سادگی با یک پردازنده می توان دو عدد N بیتی را در N+1 جمع کرد.

در نگاه اول به نظر میاد که نمیشه اینکار رو سریع تر از N گام انجام داد. اما با کمی هوشمندی و درخت دودویی کامل می توان اینکار را سریع تر انجام داد. با روش پیش بینی نقلی می توان با 1 + lg N * 2  میتوان دو عدد N بیتی  را جمع زد.

نکته کلیدی در این روش در این است که نتیجه جمع دو بیت آیا نقلی را stop ، generate، یا propagate می کند. برای مثال جفت {0 , 0} بیت نقلی را STOP  می کند. { 0 , 1 } بیت نقلی را propagate و { 1 , 1 } بیت نقلی را generate  می کند. 

در این روش نقلی ورودی از بیت i ام برابر است با سمت چپ ترین غیر p بیت های سمت راست. 

در این ساختار محاسبه آخرین carry  گام های مورد نیاز برابر 1 + lg N * 2 خواهد بود. در این روش در هر گام مقدار نود داخلی برابر سمت چپ ترین غیر P خواهد بود. 

هر نود داخلی علاوه بر اینکه ورودی های خودش را از پسرانش دریافت می کند. مقدار فرزند سمت راست را به جای مقدار سمت چپ قرار داده و مقدار سمت راست را حذف می کند. و همینطور این پروسه ادامه پیدا می کند تا به یک برگ برسیم. و هر پردازنده برگ منتظر اولین ورودی non-p خود میماند.