الگوریتم امروز

وبلاگ تخصصی الگوریتم

الگوریتم امروز

وبلاگ تخصصی الگوریتم

وبلاگ علمی و مخصوص مباحث الگوریتمی است.
نظر خصوصی نگذارید چون جواب نمی‌دهم نظر عمومی بگذارید بدون نام هم که باشد همانجا جواب می‌دهم.

بایگانی

۵۰ مطلب با موضوع «پروژه» ثبت شده است

امروز دفاع یکی به اسم احسان نوعی بود که از روی توضیحاتی که توی stackoverflow و ... بود میومد مشخصات برنامه‌ها رو پیدا می‌کرد که وقتی یکی دنبال یک برنامه می‌گرده ولی اسمش رو نمی‌دونه خودش توضیحات اضافه پیدا می‌کرد و بر اساس اون جواب می‌داد.

از نظر اینکه پردازش کمتری می‌خواد این کار (یعنی اکثرش توی پیش‌پردازشه و زمان کوئری کمی داره، بر خلاف روش‌های بر مبنای آنتولوژی که مقایسه‌ی اون آنتولوژی کلی زمان می‌خواد اینجا فقط چند تا کلمه است مثل موتورهای جستجوی معمولی) خیلی بهتر بود.

تنها چیزی که استادهایش هم می‌دانستند integrated library system (ILS) بود که سعی می‌کردند هر تکرار کنند که ما گول بخوریم که بلدن. (امان از دست استادها! :)) )

از این نظر که مراحل موتور جستجو رو برای من مرور کرد خیلی خوب بود. یک سری ایده‌ی جدید بهم داد که نمی‌گم چون خودم لازمشون دارم. :)

۰ نظر موافقین ۰ مخالفین ۰ ۲۶ مرداد ۹۳ ، ۱۰:۱۱
سپیده آقاملائی

http://www.cs.cornell.edu/courses/cs664/2008sp/handouts/cs664-8-binary-matching.pdf

۰ نظر موافقین ۰ مخالفین ۰ ۲۵ مرداد ۹۳ ، ۱۵:۱۱
سپیده آقاملائی

http://people.csail.mit.edu/indyk/ita-web.pdf

۰ نظر موافقین ۰ مخالفین ۰ ۲۲ مرداد ۹۳ ، ۱۴:۳۹
سپیده آقاملائی

مرجع: http://people.csail.mit.edu/indyk/neumann.pdf

۰ نظر موافقین ۰ مخالفین ۰ ۲۲ مرداد ۹۳ ، ۱۴:۲۵
سپیده آقاملائی

http://math.mit.edu/~goemans/18433S13/polyhedral.pdf

۰ نظر موافقین ۰ مخالفین ۰ ۲۲ مرداد ۹۳ ، ۱۳:۳۴
سپیده آقاملائی

http://www-math.mit.edu/~goemans/18433S13/18433.html

۰ نظر موافقین ۰ مخالفین ۰ ۲۲ مرداد ۹۳ ، ۱۳:۱۶
سپیده آقاملائی

مرجع: فصل ۱۷ کتاب وزیرانی (سوال تمرین زمانبندی روی ماشین‌های مستقل)

اینجا LP برای مسأله جواب (تقریبی) نمی‌دهد (integrality gap نامحدود دارد یعنی نسبت جواب LP و جواب بهینه نامحدود است).

پس خودمان کاری می‌کنیم که تقریب مورد نظرمان اتفاق بیفتد. برای اینکه یک جواب تقریبی از جواب بهینه باشد، طبق مطالب فصل ۱ و ۲ باید تقریبی از کران مسأله باشد. در کمال بدبختی ما این کران را هم نداریم. برای همین یک پارامتر را می‌گیریم که بتواند کران مناسبی برای مسأله باشد (ولی نمی‌توانیم در زمان کمی حسابش کنیم) و روی آن مثلاً جستجوی دودویی (یا هر جستجوی دیگری!) به کار می‌بریم تا تقریبی از این پارامتر به دست بیاید. در نتیجه با تقریب زدن این پارامتر، می‌توانیم مسأله را هم تقریب بزنیم. (خلاصه اینکه در دو ضرب مسأله را حل می‌کنیم.)

البته از LP هم این استفاده را می‌کنیم که نقاط صحیح جواب را به دست بیاوریم و فقط دنبال بقیه جواب بگردیم.

۰ نظر موافقین ۰ مخالفین ۰ ۲۲ مرداد ۹۳ ، ۰۹:۵۰
سپیده آقاملائی

چه زمانی جستجوی محلی برای تقریب زدن کار می‌کند؟ وقتی که جواب بهینه‌ی محلی و بهینه‌ی واقعی تقریبی از هم باشند. به این نسبت locality gap می‌گویند.

http://pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/projects/project-notes-2.pdf

۰ نظر موافقین ۰ مخالفین ۰ ۲۲ مرداد ۹۳ ، ۰۹:۳۶
سپیده آقاملائی

http://en.wikipedia.org/wiki/Multi-objective_optimization

۰ نظر موافقین ۰ مخالفین ۰ ۲۲ مرداد ۹۳ ، ۰۹:۲۴
سپیده آقاملائی

http://statweb.stanford.edu/~tibs/stat315a/LECTURES/em.pdf

۰ نظر موافقین ۰ مخالفین ۰ ۱۵ مرداد ۹۳ ، ۱۵:۲۲
سپیده آقاملائی