عنوان پایان‌نامه
تحلیل وطراحی الگوریتم هایی برای مسئله پیشینه کردن وزن عناصر انتخاب شونده از یک مجموعه به شرط حفظ مستقل خطی بودن عناصر انتخاب شده با استفاده از الگوریتم های تقریبی وتصادفی
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 42..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 58966
- تاریخ دفاع
- ۲۰ شهریور ۱۳۹۲
- دانشجو
- میثاق کردی
- استاد راهنما
- علی معینی
- چکیده
- دنیای علوم کامپیوتر سال ها ست که با مسئله های بغرنجی روبروست که برای هیچ یک از آن ها تاکنون راه حل ای ارائه نشده است و برای بدست آوردن جواب دقیق هر نمونه مسئله چاره ای به غر از بررسی تمامی راه حل های ممکن وجود ندارد. که این مسائل در دنیای علوم کامپیوتر به مسائل ان پی – سخت معرو ف می باشند. از آنجا که با گسترش علم و نیاز به حل مسائل با ورودی های بسیار بزرگ روز افزون شده است از این رو در دانشمندان این رشته در صدد پیدا کردن روش هایی برای حل این مسائل شده اند.که از جمله این راه حل ها می توان به روش های تقریبی و تصادفی اشاره نمود که با توجه این که امکان بدست آوردن جواب هایی نزدیک به جواب بهینه و یا بدست آوردن بهترین جواب با احتمال قابل قبول به وسیله این روش ها بسیار محتمل می باشد در نتیجه این روش ها در سال های اخیر بیشتر مورد توجه قرار گرفته اند. مسائل آنلاین از جمله مسائلی است که این روش ها جواب های بسیار بهینه تری نسبت به بقیه روش ها ارائه می کنند. از آنجا که گسترش و استفاده روز افزون اینترنت در دنیا، نیاز به پردازش و حل مسائل آنلاین را افزایش داده است از این رو استفاده از راه حل های تقریبی و احتمالاتی برای این مسائل مورد توجه قرار گرفته است. یکی از این مسائل تصمیم گیری آنلاین مسئله انتخاب آنلاین می باشد که با توجه به ورود پارامتر های رقیب و هم چنین زمان جواب این مسائل بسیار غیر قابل پیش بینی می باشد و در نتیجه روش های تصادفی و تقریبی بیشتر از روش های یادگیری مفید می باشند. در این پایان نامه در صدد هستیم مسئله های انتخاب منشی و هم چنین متروید انتخاب منشی را در حالت های مختلف را با استفاده از روش های تقریبی و تصادفی مورد بررسی قرار دهیم و برای هر یک از حالت های این مسائل الگوریتم ای جدید ارائه دهیم که ضریب تقریبی را در هر حالت بهبود دهد. فصل دو این پایان نامه را به حالت های مسئله متروید اختصاص داده ایم و هم چنیم برای هر حالت آخرین الگوریتم های ارائه شده را توضیح می دهیم. هم چنین در این فصل مروری بر چند ویژگی مهم متروید کرده که در ارائه و تحلیل الگوریتم های موجود تاثیر بسزایی دارند و هم چنین در این فصل با مقایسه حالت های مختلف مسئله و ارائه الگوریتم های موجود آخرین و بهترین ضریب های تقریبی بدست آمده را برای هر یک از این حالت های مسئله را مورد بررسی قرار داده ایم. فصل 3 این پایان نامه به ارائه الگوریتم جدید برای تمامی حالت ای مسئله های انتخاب منشی و هم چنین متروید پرداخته ایم. در این فصل در قسمت اول، ابتدا به ارائه الگوریتم جدید برای مسئله انتخاب منشی پرداخته ایم و آن را با الگوریتم های قبلی مقایسه کرده ایم. سپس با ارائه الگوریتم ای جدید برای مسئله انتخاب r منشی بر پایه الگوریتم اراه شده برای مسئله انتخاب منشی و هم چنین مقایسه ضریب تقریبی بدست آمده با ضریب تقریبی الگوریتم های قبلی بهبود و بهینگی این الگوریتم را نسبت به الگوریتم های قبلی توضیح داده ایم.در دنباله فصل به ارائه الگوریتم های جدید بر ای مسئله منشی پرداخته ایم و با توضیح اشکالات و نواقص الگوریتم های قبلی ارائه شده برای این مسائل و هم چنین توضیح چگونگی بر طرف کردن مشکلات الگوریتم های ارائه شده را با الگوریتم های قبلی مقایسه کرده و میزان بهینگی و بهبود هر الگوریتم را نسبت به الگوریتم های قبلی بدست آورده ایم. هم چنین در انتها فصل به ارائه الگوریتم ای برای یکی از حالت های مسئله متروید پرداخته ایم که تا کنون هیچ الگوریتم با ضریب تقریبی ثابت برای آن ارائه نشده بود و این مسئله به مدت 22 سال به عنوان یک مسئله باز مطرح بود که آیا برای این حالت مسئله الگوریتم با ضریب ثابت وجود دارد و یا خیر، که با ارائه اولین الگوریتم ضریب ثابت برای این الگوریتم به این سوال بعد از 22 سال پاسخ داده ایم و این حالت مسئله را برای اولین بار با ضریب تقریبی ثابت حل کرده ایم.
- Abstract
- We study a generalization of the classical secretary problem which we call the matroid secretary problem. We present a number of positive and negative results for variants of the matroid secretary problem. In this problem, the elements of a matroid are presented to an online algorithm in random order or in adversary order. When an element arrives, the algorithm observes its value and must make an irrevocable decision regarding whether or not to accept it. The accepted elements must form an independent set, and the objective is to maximize the combined value of these elements. Most notably, we design a constant-factor competitive algorithm for the “adversary assignment” model where the adversary assigned weights to the elements of a matroid, and then the elements arrive on-line in a random order. This is under the assumption that the matroid is known in advance. This resolves an open question posed by Babaioff et al. We also consider the classical secretary problem for the “random assignment” model where the weights are assigned randomly to the elements of a matroid, and then the elements arrive on-line in an adversarial orderand and alsomulti choice secretary problem and improve competitive ratio for both of them.
