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

برای مثال، بسیاری از مسائل الگوریتمی دنیای واقعی را نمی توان به طور موثر با استفاده از ابزارهای الگوریتمی سنتی حل کرد، زیرا مسائل NP-hard هستند. هدف از درس الگوریتم های تقریب، آشنایی با مفاهیم و تکنیک های مهم الگوریتمی مورد نیاز برای مقابله موثر با چنین مسائلی است. این تکنیک‌ها زمانی اعمال می‌شوند که برای مسائل خاصی به راه‌حل بهینه نیاز نداریم، بلکه تقریبی نزدیک به راه‌حل بهینه است. خواهیم دید که چگونه می توان چنین تقریب هایی را به طور موثر پیدا کرد. پیش نیازها: برای گذراندن موفقیت آمیز این دوره، باید از قبل دانش پایه ای از الگوریتم ها و ریاضیات داشته باشید. در اینجا لیست کوتاهی از آنچه باید بدانید آمده است: - O-notation، Ω-notation، Θ-notation; نحوه تجزیه و تحلیل الگوریتم ها - حساب پایه: دستکاری جمع، حل عود، کار با لگاریتم و غیره. - نظریه احتمال پایه: رویدادها، توزیع های احتمال، متغیرهای تصادفی، مقادیر مورد انتظار و غیره. - ساختارهای داده پایه: لیست های پیوندی، پشته ها، صف ها، پشته ها - درختان جستجوی دودویی (متوازن). - الگوریتم های مرتب سازی اولیه، به عنوان مثال MergeSort، InsertionSort، QuickSort - اصطلاحات نمودار، نمایش گراف ها (لیست مجاورت و ماتریس مجاورت)، الگوریتم های اصلی گراف (BFS، DFS، مرتب سازی توپولوژیکی، کوتاه ترین مسیرها) مطالب این دوره بر اساس یادداشت های دوره است که در زیر برگه منابع یافت می شود.