سوال هندسه

http://www.cs.tulane.edu/~carola/teaching/cs6463/fall06/homework/homework4.pdf

قسمت اول سوال که تمرین خودمون بود و معادله ی خط های دوگان این نقطه ها را به دست می آوریم، خط جدا کننده دوگانش نقطه ای است که زیر همه ی خط های آبی و بالای همه ی خط های قرمز باشه (یا برعکس).

برای قسمت دوم سوال می توانیم دوگان نگیریم، همین طوری بگیم که معادله ی خط هایی که نقطه های قرمز بالای اونها هستند و نقطه های آبی زیر اونها هستند.

این یکی از سوالهای تمرین های همین سری خودمون بود، فقط یک فرق کوچک داده بود توش ولی ایده همین بود. جواب سوال (حالتهای چک کردن نبودن جواب را حذف کردم چون طولانی بود):

تحلیل:

دلیل d/(i-d) هم این است که d تا ابرصفحه جواب vi-1 را تعریف کرده اند و ما d تا از بین i تا صفحه را انتخاب کرده ایم، پس احتمال اینکه یکی از صفحه های جواب خارج از مجموعه انتخابی ما باشد انقدر می شود.

با استقرا روی تعداد ابعاد ثابت کرده است که اگر برای d-1 بعدی ثابت Cd-1 باشد، برای d بعدی ثابت Cd است که حداکثر d برابر ثابت قبلی است.

ب) بدترین حالت چیست؟ آن را تحلیل کنید و مثال بزنید.

بدترین حالت این است که هر بار صفحه هایی را انتخاب کنیم که جواب نباشند! برای مقدارش هم باید xi=1 باشد که در همان رابطه بالا بگذاریم جواب به دست می آید.