PDA

View Full Version : تکنیکهای طراحی الگوریتم - مقدمه



Kambiz
دوشنبه 17 شهریور 1382, 02:35 صبح
ممنون از مدیر محترم سایت که بخش الگوریتم را ایجاد کردند تا بتوانیم در رابطه با طراحی و ساختار الگوریتمها به بحث و اظهار نظر بپردازیم. همانطور که می‌دانید این بخش بصورت آزمایشی ایجاد شده و در صورت عدم استقبال بسته خواهد شد.

برای شروع تصمیم گرفتم که مطلبی را در رابطه با تکنیکهای طراحی الگوریتم بنویسم (در حقیقت ترجمه‌ای ساده شده که تا حد امکانِ مطالب ریاضی آن حذف شده است). اگر مورد پسند واقع شد که ادامه می‌دهیم وگرنه موضوع دیگه‌ای رو شروع می‌کنیم. در ضمن اگر در بکارگیری معادلهای فارسی ناشیگری یا اشتباهی دیدید لطفا گوشزد کنید.

--------------------------------------------------------------------------------------------------------

الگوهای الگوریتمی (Algorithmic Paradigms) عبارتند از راه حل‌هایی جامع برای حل کارآمد مسائل.

این راه حلها بدلایل زیر مورد توجه هستند:
قالبهای مناسبی برای حل گستره‌ای از مسائل گوناگون فراهم می‌کنند.
به راحتی می‌توانند به ساختارهای فراهم شده توسط زبانهای سطح بالا (High-Level Languages) ترجمه شوند.
کلیه اجزای الگوریتمهایی که از این الگوها حاصل می‌شوند با ریزبینی می‌توانند مورد تجزیه و تحلیل قرار گیرند.
در ادامه این بحث الگوهای الگوریتمی زیر را مورد بررسی قرار می‌دهیم:
تقسیم و تسخیر (Divide and Conquer)
برنامه‌نویسی پویا (Dynamic Programming)
روش سیری ناپذیر! (Greedy Method)
بازگشت به عقب (Backtracking)
هرچند ممکن است بیشتر از یک تکنیک برای یک مسئله خاص جوابگو باشد، اما در اغلب موارد الگوریتم ساخته شده با یک الگو بطور روشنی از الگوریتمی معادل که با الگویی دیگر ساخته شده است، برتری دارد.

انتخاب یک الگوی الگوریتمی مناسب، جنبه‌ای مهم در تعیین ساختار و ترکیب الگوریتم است.

(امید)
سه شنبه 18 شهریور 1382, 07:42 صبح
سلام

من کاملا با این بخش موافقم.همچنین این بخش به بالا بردن کیفیت برنامه نویسی کمک می کند.
فکر می کنم اگر دوستان مشکلات برنامه نویسی مربوط به الگوریتم را در این بخش عنوان کنند قابل استفاده برای تمامی دوستان خواهد بود.
من به شخصه به بعضی از تاپیک ها اصلا سر نمی زنم. در حالی که شاید در آن بخشها مسایلی به عنوان مشکلات برنامه نویسی مطرح شود که مشکل من هم بوده ( حالا در یک زبان دیگر) .

با سپاس

shaniaki
سه شنبه 18 شهریور 1382, 15:29 عصر
با عرض ادب:
این بخش کمک خیلی خوبی به بالا بردن سواد برنامه نویسی همه داره معمولا خیلی از ما در برنامه هامون بیشتر کد نویس هستیم تا برنامه نویس و چند تا compontnt و تابع رو سرهم می کنیم به عنوان یک محصول می دیم بیرون در صورتی که از جهت تحلیلی و ریاضیاتی شاید ارزشی نداشته باشه. اگر فرصتی شد(و تنبلی اجازه داد) چند تا از الگوریتم های هوشمند رو در این قسمت معرفی خواهم کرد.

یه عشق برنامه نویسی خفن

Kambiz
سه شنبه 18 شهریور 1382, 22:53 عصر
ممنون دوستان.

اگر مطالب جدید رو با تاخیر می‌نویسم پوزش می‌خواهم. به غیر از آخر هفته‌ها بقیه روزها وقت کم میارم. :(

Sadegh_S
دوشنبه 03 آذر 1382, 15:04 عصر
دنباله مطالب رو همین جا می نویسید یا جای دیگه ؟

Kambiz
دوشنبه 03 آذر 1382, 23:01 عصر
مطالب مرتبط به این موضوع در تاپیکهای زیر هستند:
تحلیل مقدماتی الگوریتمها (http://www.barnamenevis.org/forum/viewtopic.php?t=2909)
تکنیکهای طراحی الگوریتم - روش تقسیم و تسخیر (http://www.barnamenevis.org/forum/viewtopic.php?t=2874)
تکنیکهای طراحی الگوریتم - روش برنامه نویسی پویا (http://www.barnamenevis.org/forum/viewtopic.php?t=3563)
تکنیکهای طراحی الگوریتم - روش سیری ناپذیر (http://www.barnamenevis.org/forum/viewtopic.php?t=3807)
تکنیکهای طراحی الگوریتم - روش بازگشت به عقب (http://www.barnamenevis.org/forum/viewtopic.php?t=3925)

Inprise
سه شنبه 04 آذر 1382, 15:04 عصر
ادامه بدید لطفا . استفاده میکنیم

houshmand
سه شنبه 04 آذر 1382, 16:33 عصر
ادامه بدید لطفا . استفاده میکنیم
و من هم :wink:

Kambiz
چهارشنبه 05 آذر 1382, 23:16 عصر
شرمنده که این چند وقت فرصت نکردم مطلبی اینجا بگذارم.
احتمال داره این کم کاری من تا اواخر دی ماه ادامه داشته باشه که پیشاپیش پوزش می‌خوام.

رضا جاسبی
یک شنبه 25 بهمن 1383, 19:31 عصر
من سه چهار روزه که عضو شدم و از همه کارم افتادم به خاطر این بخش ! :mrgreen: :oops: واقعا اگر کسی بخواد برنامه نویس باشه باید الگوریتم بدونه ! اگه یه وقتایی پرچونگی می کنم منو ببخشین ولی بحث الگوریتم خیلی خیلی مفیده ! از همتون ممنونم.

صبا
دوشنبه 26 بهمن 1383, 11:18 صبح
سلام
من فکرم می کنم که مهمترین بخش برنامه نویسی پیدا کردن الگوریتم مناسب برای این کار است .پس خیلی خوب است اگر این بخش ادامه پیدا کند. امیدوارم حداقل در کنکور به من کمک کند .
با تشکر

mohs_158
یک شنبه 23 اسفند 1383, 17:57 عصر
این معادل‌ها شاید بهتر باشد :
تقسیم و حل(devide and conquer)
حریصانه(greedy)
پس‌گرد(backtracking)

mhd.group
سه شنبه 13 تیر 1391, 09:45 صبح
سلام دوستان و اساتید
ببخشید دو سوال داشتم اگه میشه راهنمایی کنید ... چه طور میشه حلش کرد


سوال 1: دو رشته X و Y به ترتیب به طول‌های m و n داده شده‌اند. الگوریتمی طراحی کنید که طولانی ترین زیررشته‌ی مشترک X و Y را در زمان O(mn) با صرف حافظه‌ی O(m+n) بدست آورد.



سوال 2: مختصات n در صفحه نقطه داده شده‌است. یک الگوریتم تقسیم و حل طراحی کنید که در زمان O(n log n) دو نقطه با کمترین فاصله از یکدیگر (نزدیک ترین دو نقطه) را پیدا کند.



ممنون میشم