تکنیکهای طراحی الگوریتم - مقدمه
ممنون از مدیر محترم سایت که بخش الگوریتم را ایجاد کردند تا بتوانیم در رابطه با طراحی و ساختار الگوریتمها به بحث و اظهار نظر بپردازیم. همانطور که میدانید این بخش بصورت آزمایشی ایجاد شده و در صورت عدم استقبال بسته خواهد شد.
برای شروع تصمیم گرفتم که مطلبی را در رابطه با تکنیکهای طراحی الگوریتم بنویسم (در حقیقت ترجمهای ساده شده که تا حد امکانِ مطالب ریاضی آن حذف شده است). اگر مورد پسند واقع شد که ادامه میدهیم وگرنه موضوع دیگهای رو شروع میکنیم. در ضمن اگر در بکارگیری معادلهای فارسی ناشیگری یا اشتباهی دیدید لطفا گوشزد کنید.
--------------------------------------------------------------------------------------------------------
الگوهای الگوریتمی (Algorithmic Paradigms) عبارتند از راه حلهایی جامع برای حل کارآمد مسائل.
این راه حلها بدلایل زیر مورد توجه هستند:
- قالبهای مناسبی برای حل گسترهای از مسائل گوناگون فراهم میکنند.
- به راحتی میتوانند به ساختارهای فراهم شده توسط زبانهای سطح بالا (High-Level Languages) ترجمه شوند.
- کلیه اجزای الگوریتمهایی که از این الگوها حاصل میشوند با ریزبینی میتوانند مورد تجزیه و تحلیل قرار گیرند.
در ادامه این بحث الگوهای الگوریتمی زیر را مورد بررسی قرار میدهیم:
- تقسیم و تسخیر (Divide and Conquer)
- برنامهنویسی پویا (Dynamic Programming)
- روش سیری ناپذیر! (Greedy Method)
- بازگشت به عقب (Backtracking)
هرچند ممکن است بیشتر از یک تکنیک برای یک مسئله خاص جوابگو باشد، اما در اغلب موارد الگوریتم ساخته شده با یک الگو بطور روشنی از الگوریتمی معادل که با الگویی دیگر ساخته شده است، برتری دارد.
انتخاب یک الگوی الگوریتمی مناسب، جنبهای مهم در تعیین ساختار و ترکیب الگوریتم است.
نقل قول: تکنیکهای طراحی الگوریتم - مقدمه
سلام دوستان و اساتید
ببخشید دو سوال داشتم اگه میشه راهنمایی کنید ... چه طور میشه حلش کرد
سوال 1: دو رشته X و Y به ترتیب به طولهای m و n داده شدهاند. الگوریتمی طراحی کنید که طولانی ترین زیررشتهی مشترک X و Y را در زمان O(mn) با صرف حافظهی O(m+n) بدست آورد.
سوال 2: مختصات n در صفحه نقطه داده شدهاست. یک الگوریتم تقسیم و حل طراحی کنید که در زمان O(n log n) دو نقطه با کمترین فاصله از یکدیگر (نزدیک ترین دو نقطه) را پیدا کند.
ممنون میشم