آموزش طراحی الگوریتم|صفحه 1
الگوریتم چیست؟
الگوریتم دنباله ای است از دستورات که با اجرای آنها، هدف خاصی برآورده میشود. هر الگوریتم مفاهیم ورودی،خروجی ،قطعیت، محدودیت و کارایی را دارد
نمادهای مجانبی الگوریتم
برای تخمین زمان اجرای الگوریتم و میزان پیچیدگی آن، از نمادهایی به نام نمادهای مجانبی (حدی) استفاده میشود. این نمادها عباتند از: O ، Ω، Θ و o، ω که هر کدام طبق روش خاصی محاسبه میشوند و در تحلیل الگوریتم کاربرد فراوانی دارند.
الگوریتم تقسیم و غلبه Divide and Conquer
در روش تقسیم و غلبه ابتدا مساله بزرگ به زیر مسائل کوچکتر تقسیم میشود و پس از آن زیر مسائل کوچکتر نیز در صورت لزوم به زیر مسائل کوچکتری تقسیم میشوند و در نهایت با حل مسائل کوچک، مساله اصلی حل میشود.
الگوریتم حریصانه greedy
الگوریتم حریصانه یا آزمند (greedy) به ترتیب داده ها را گرفته و هر بار عنصری را که طبق معیار معینی "بهترین" به نظر میرسد، بدون توجه به انتخاب های قبلی و انتخاب هایی که در آینده انجام خواهد شد، انتخاب میکند. این الگوریتم بسیار ساده هستند و معمولا برای مسائل بهینه سازی کاربرد دارند.
روش برنامه نویسی پویا در طراحی الگوریتم
در الگوریتم برنامه نویسی پویا، ابتدا مسائل کوچک حل میشوند و در یک مکان ذخیره میشوند و سپس به تدریج به حل مسئله اصلی میرسیم. روش پویا یک روش جزء به کل یا پایین به بالا (bottom - up) است و بصورت بازگشتی به جواب میرسد
آنالیز استهلاکی الگوریتم ها
در Amortized Analysis آنالیز استهلاکی برای تخمین زمان اجرای الگوریتم و پیچیدگی زمانی آن، n عمل انجام میشود و هزینه زمانی آن روی n عمل سرشکن میشود. در واقع ممکن است عملیات انجام شده هزینه های مختلفی داشته باشند و برخی هزینه زیادی داشته باشند ولی هزینه متوسط هر عمل کوچک باشد.
آشنایی با نظریه NP در طراحی الگوریتم
نظریهNP (نظریه پیچیدگی محاسباتی) شاخه ای از نظریه محاسبات و ریاضی و علوم کامپیوتری است که به بررسی دشواری حل مسائل بصورت الگوریتمی می پردازد.
الگوریتم های پیمایش گراف Graph
گراف (G = (V, E را میتوان با لیست ها یا با ماتریس مجاورتی نمایش داد. در اینجا چند الگوریتم پیمایش گرافها را معرفی خواهیم کرد: BFS، DFS، KRUSKAL و PRIM.