الگوریتم های تقریب قسمت اول

الگوریتم های تقریب، بخش اول چقدر کارآمد می توانید اشیاء را در حداقل تعداد جعبه بسته بندی کنید؟ چگونه می توانید گره ها را به گونه ای خوشه بندی کنید که شبکه را به قطعاتی در اطراف چند مرکز به طور ارزان تقسیم کنید؟ اینها نمونه هایی از مسائل بهینه سازی ترکیبی NP-hard هستند. به احتمال زیاد حل چنین مسائلی به طور موثر غیرممکن است، بنابراین هدف ما ارائه یک راه حل تقریبی است که بتوان آن را در زمان چند جمله ای محاسبه کرد و در عین حال دارای ضمانت های قابل اثبات در هزینه آن نسبت به بهینه باشد. این دوره دانش یک دوره استاندارد الگوریتم در مقطع کارشناسی را در نظر می گیرد، و به ویژه بر الگوریتم هایی تأکید می کند که می توان با استفاده از برنامه نویسی خطی، یک تکنیک مورد علاقه و شگفت انگیز موفق در این زمینه، طراحی کرد. با گذراندن این دوره، شما در معرض طیف وسیعی از مشکلات در مبانی علم کامپیوتر نظری و تکنیک های قدرتمند طراحی و تجزیه و تحلیل قرار خواهید گرفت. پس از تکمیل، شما قادر خواهید بود، زمانی که با یک مسئله بهینه سازی ترکیبی جدید مواجه می شوید، تشخیص دهید که آیا این مسئله به یکی از معدود مسائل اساسی شناخته شده نزدیک است یا خیر، و قادر خواهید بود برنامه نویسی آرام سازی خطی طراحی کنید و از گرد کردن تصادفی برای تلاش برای حل مشکل خود استفاده کنید. مشکل خود محتوای دوره و به ویژه تکالیف درسی ماهیت نظری و بدون تکالیف برنامه نویسی دارد. این اولین دوره از یک دوره دو قسمتی در مورد الگوریتم های تقریب است.