بهینه سازی محدب - استنفورد

https://class.stanford.edu/courses/Engineering/CVX101/Winter2014/pdfbook/1/

سوالهای امتحان

نمی دونم چرا قبلا ندیده بودم. روی فلشم هم بود! :) دقیقا سوالها از این مجموعه بود!

سوالها
حجم: 615 کیلوبایت

butterfly graphs

این سوال تمرین ما که هیچ جوری حل نمی شد: (به درخواست دوستان)

http://www.madalgo.au.dk/img/SS2010/Course%20Material/Tuesday_Patrascu_Handouts.pdf

سوال امتحان

الآن اینجا ثابت کرده که رادیکال n تا ناحیه رو قطع می کنه بعد من همینو نوشتم کم کردن ازم! :))

(مرجع همون پست قبلی)

تفاوت تدریس استاد من و استاد استاد من

http://www.madalgo.au.dk/img/SS2010/Course%20Material/Orthogonal%20Range%20Queries%20Basic%20Methods.pdf

پایان ترم هندسه محاسباتی شریف

1- الف) یک چندضلعی با n راس و h حفره k راسی داریم. تعداد مثلثهای مثلث بندی آن چقدر است؟

ب) یک ذوزنقه بندی داریم که در آن پاره خط ها متقاطع هستند (مجزا نیستند)، تعداد ذوزنقه ها و مثلث ها چقدر است؟ (ناحیه ها)

ج) در یک kd tree حداکثر ناحیه هایی که یک خط آنها را قطع می کند چندتا است؟

د) یک مثال کلی و قابل تعمیم بزنید که نمی توان چند ضلعی دارای حفره را با floor(n/3) نگهبان (مساله art gallery) پوشش داد.

2- الف) چند ضلعی ستاره شکل (قبلا توی وبلاگ گفته شده)

ب) یک پیش پردازش روی آن انجام بدهید که زمان O(n) ببرد و در زمان O(logn) بتوان گفت هر نقطه در درون آن چندضلعی است یا بیرون.

3- range tree

الف) برای یک مستطیل با اضلاع موازی y=x و y=-x

ب) برای یک مثلث با دو ضلع موازی محورهای مختصات و یک ضلع موازی y=-x

ج) برای مجموعه n خط که بخواهیم برای سه تایی های (t0,t1,t2)، خطوطی را برگردانیم که بالای (1,t0) و زیر (t1,1) و (2,t2) باشند. (جای مختصاتها را برعکس می نویسد شما درستش را بخوانید!)

LP

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

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

سوال هندسه

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 باشد که در همان رابطه بالا بگذاریم جواب به دست می آید.

تعداد نقاط درون مثلث

priority search tree