|  درخواست عضويت  |  رمز خود را فراموش کرده ايد؟  |  ورود اعضا [Sign in]
جستجوي پيشرفته مطالب   |  
 جستجو:  
روزنامه ايران85/11/14: آشنايي با طراحي الگوريتم ها
magiran.com  > روزنامه ايران >  فهرست مطالب شماره
مشخصات نشريه
آخرين شماره
آرشيو شماره هاي گذشته
جستجوي مطالب
سايت اختصاصي
تماس با نشريه
شماره جديد اين نشريه
شماره 7003
چهار شنبه 1 اسفند 1397


 راهنمای موضوعی نشريات
اين نشريه در گروه(های) زير قرار گرفته است:

?????


 
MGID2825
magiran.com > روزنامه ايران > شماره 3562 14/11/85 > صفحه 6 (دانش) > متن
 
      


آشنايي با طراحي الگوريتم ها


نويسنده: مناف ـ شريف زاده


    تلاش بي پايان ذهن انسان هاي كنجكاو براي كشف ناشناخته ها و حل مسائل جالب يكي از جنبه هاي زيباي زندگي است. تاريخ علم نشان مي دهد كه دانشمندان و رياضيدانان متعددي عمر طولاني خود را وقف حل معماهاي مختلف و شناسايي اسرارطبيعت و جامعه كرده و با حل هر مسأله نام خود را جاوداني كرده اند. تكنولوژي كامپيوتر با توجه به پيشرفت جهشي خود در ۶۰ سال اخير، هم به عنوان يك ابزار حل مسأله، هم به عنوان منبعي از كاربردهاي متنوع آن، روز به روز جذاب تر شده و در اين رابطه، الگوريتم به عنوان روش و مراحل حل مسأله، نقش كليدي را در اين فناوري ايفا مي كند. يك مثال ساده براي الگوريتم، دستورالعمل هاي لازم براي روي هم قرار دادن قطعات مدل هواپيماست. اين مونتاژ از قطعه خاصي شروع شده و سپس قطعات ديگر به ترتيب تا كامل شدن مدل، روي هم قرار مي گيرند. يك برنامه كامپيوتري كه براي پياده سازي و اجراي الگوريتم ها روي رايانه به كار مي رود، مجموعه متناهي از دستوراتي است كه به ترتيب معيني از نخستين دستور به ترتيب تا انتها بايد اجرا شوند.
    اين نوشته انواع الگوريتم ها را به صورت مختصر با عنوان مثال هايي براي هر كدام بررسي و مطالعه مي كند. منظور از انواع الگوريتم ها، ارائه يك راه حل جامع و كارآمد براي مسائل مختلف است. الگوريتم ها هسته مركزي راه حل مسائل متعددي در بخش هاي علوم پايه، مسائل تجاري، رشته هاي مهندسي مانند طراحي پل ها، سدها، خودروها، هواپيماها، پيش بيني وضع جوي و نقشه هاي مربوطه، تجزيه و تحليل ساختار مولكول ها و DNA، كشف ذخاير گاز و نفت و طراحي و بهينه سازي سيستم هاي كامپيوتري است.
    از لحاظ تاريخي كلمه الگوريتم برگرفته از نام رياضيدان معروف قرن نهم هجري، الخوارزمي است كه براي نخستين بار در كتاب معروف جبر و مقابله براي بعضي از مسائل رياضي مانند معادلات خطي و معادلات درجه دوم، راه حل نويني مطرح كرد كه تا آن مقطع زماني ارائه نشده بود. الگوريتم به عنوان مراحل حل يك مسأله يا انجام يك كار، مجموعه اي متناهي از دستورالعمل هايي است كه براي رسيدن به خروجي هاي مطلوب با شروع از يك حالت اوليه به كار مي رود. در تعريف رياضي الگوريتم به دستورالعمل ها يا رويه هاي خوش تعريف اطلاق مي شود كه به وسيله ماشين تورينگ كه يك مدل انتزاعي از كامپيوترهاي ديجيتال است، شبيه سازي و اجرا گردد.
    روش هاي زيادي براي گروه بندي الگوريتم ها با توجه به قابليت و توانايي هاي هر دسته وجود دارد. از يك ديدگاه كلي مي توان الگوريتم ها را به دو گروه عمده الگوريتم هاي ترتيبي و الگوريتم هاي موازي تقسيم كرد.
    الگوريتم هاي ترتيبي
    در اين گروه از الگوريتم ها، رايانه فقط از يك پردازنده براي اجراي دستورالعمل ها به صورت ترتيبي (سريال) استفاده مي كند. در اين نوع رايانه ها كه به نام معماري فون نيومن معروف است، برنامه و داده ها در حافظه ذخيره مي شوند. ريزپردازنده هر بار يكي از دستورات برنامه را بازيابي كرده، پس از تفسير آن را اجرا مي كند. چنين رايانه هايي را SLSD (جريان تك دستوري، جريان تك داده اي) مي گويند. در اينجا به ۲ روش از الگوريتم هاي ترتيبي اشاره مي شود.
    روش تقسيم و حل
    در اين روش، با استفاده از رويه هاي بازگشتي، مسأله اصلي را به زيرمسأله هاي كوچكتري تا جايي تقسيم مي كنند كه امكان تقسيم مجدد آن وجود نداشته باشد. سپس با حل ساده ترين زيرمسأله ها و تركيب آنها با يكديگر مي توان به حل مسأله اصلي نائل شد. رويه بازگشتي، الگوريتمي است كه با استفاده از فراخواني خودرويه، دستورات تشكيل دهنده آن را تا رسيدن به شرايط اوليه و خروج از آن، مكرر اجرا كند.
    روش تقسيم و حل، يك روش طراحي بالا به پائين است، يعني الگوريتم يك مسأله از سطح بالا به زيرمسأله ها تقسيم بندي مي شود. به عنوان مثال مي توان الگوريتم هاي جست وجوي دورويي در يك بردار (آرايه يك بعدي) يا در يك جدول (آرايه دوبعدي) ، مرتب سازي تركيب و مرتب سازي سريع ، مسأله برج هاي هانوي ، ضرب «ماتريس به روش استراسن»، عمليات محاسباتي مانند ضرب و جمع اعداد صحيح بسيار بزرگ و جدول مسابقات تيم ها در يك جام حذفي را با استفاده از روش تقسيم و حل انجام داد.
    الگوريتم برنامه نويسي پويا
    در برنامه نويسي پويا به عنوان يك روش طراحي الگوريتم، چون راه حل مسأله از طريق تقسيم آن به زيرمسأله ها به دست مي آيد، مشابه روش تقسيم وحل است ولي برعكس آن، يك روش پائين به بالا يا يك روش جز به كل است، يعني حل مسأله را از ساده ترين زيرمسأله شروع كرده و با قراردادن نتايج در يك آرايه، آنها را در محاسبات بعدي استفاده مي كنند. در صورتي كه روش تقسيم و حل فاقد حافظه است. اين روش طراحي الگوريتم، داراي شرايط بهينه سازي است وزيرمسأله ها هم بهينه هستند. به عنوان مثال، اگر برنامه نويسي پويا، براي مسأله كوتاه ترين مسير كه با يك گراف مدل سازي مي شود به كار مي رود، هر زيرگرافي هم بايد داراي ويژگي كوتاه ترين مسير بين رأس هاي متشكله آن باشد. اگر اصل بهينه سازي براي يك مسأله مفروض، صدق كند مي توان يك رابطه بازگشتي براي حل مسأله و زيرمسأله ها ارائه داد.
    الگوريتم فلويد براي تعيين كوتاه ترين مسير، ضرب زنجيري ماتريس ها، درخت هاي جست وجوي دورويي بهينه حاصل جمع بهينه ليستي از n عدد حقيقي، تعيين طولاني ترين زير مشترك در دو رشته دلخواه و مسأله فروشنده دوره گرد (TSP) با استفاده از روش برنامه نويسي پويا قابل انجام هستند.
    الگوريتم هاي حريصانه
    الگوريتم هاي حريصانه مشابه برنامه نويسي پويا، بيشتر براي حل مسائل بهينه سازي به كار مي روند. با اين اختلاف كه در برنامه سازي پويا از يك رابطه بازگشتي براي حل زيرمسأله ها استفاده مي كنند. در روش حريصانه، تقسيم مسأله ها به زير مسأله ها انجام نمي گيرد و روش تكرارشونده را به كار مي برند.
    در روش حريصانه در هر لحظه، با توجه به عناصر داده اي مفروض، عنصري را كه داراي ويژگي بهترين يا بهينه است (مانند كوتاه ترين مسير، بالاترين ارزش، كمترين سرمايه گذاري، بيشترين سود و ...) انتخاب مي كنند بدون اين كه انتخاب هاي قبلي ما بعدي را در نظر بگيرد ولي انتخاب هاي بهينه محلي همواره منجر به راه حل بهينه سراسري نمي شود. اين روش انتخاب، منجر به ارائه يك الگوريتم ساده و كارآمد مي شود.
    تعيين درخت هاي پوشالي مينيمم با استفاده از الگوريتم هاي پرايم، كروسكال محاسبه كوتاه ترين مسير تك منبع با كاربرد الگوريتم دايجسترا ، مسأله زمان بندي مانند بهينه سازي زمان انتظار و سرويس به كاربران براي دسترسي به ديسك گردان ها در يك شبكه رايانه اي، تعيين حداكثر بهره براي مشتريان در يك زمان معين و مسأله كوله پشتي (كسري، صفرو يك) با استفاده از روش حريصانه قابل اجرا هستند.
    الگوريتم عقبگرد
    الگوريتم عقبگرد، براي يافتن جواب مسأله اي با فضاي جست وجو به طور گسترده اي به كار مي رود و از آن به عنوان حالت اصلاح شده جست وجوي عمقي يك درخت نام مي برند. در اين روش، منظور از عقبگرد، پيدا كردن راه حل مسأله از طريق جست وجوي عمقي در درخت فضاي حالت براي يافتن گره هاي اميد بخش است. در صورتي كه موقع پيمايش درخت به يك گروه غيراميدبخش برخورد كند كه منجر يه يافتن جواب مسأله نمي شود، بايد به سمت ريشه درخت برگشته و عمل جست وجو را در ديگر شاخه ها ادامه داد. اين فرآيند را هرس كردن درخت فضاي حالت مي نامند.
    به عنوان مثال، مسأله n وزير، استفاده از الگوريتم مونت كارلو براي نخستين كارآيي يك الگوريتم عقبگرد، مسأله حاصل جمع زيرمجموعه ها، مسأله رنگ آميز گراف، مسأله مدارهاي هاميلتوني، مسأله كوله پشتي صفر و يك با استفاده از راهبرد عقبگرد، قابل حل هستند.
    الگوريتم شاخه وقيد
    روش شاخه و قيد با ايجاد درختي از زيرمسأله ها با توجه به مسأله اوليه و پيمايش درخت بدون قاعده خاصي، دنبال جواب هاي مسأله مي گردد. اين روش شكل بهبود يافته اي از الگوريتم عقبگرد است كه در آن شيوه خاصي را براي ملاقات گره ها اعمال نمي كند و در هر گره براي اميدبخش بودن آن گره، قيد يا عددي را محاسبه مي كند و فقط براي مسائل بهينه سازي استفاده مي شود. به عنوان مثال مسأله كوله پشتي صفر و يك، بهترين جست وجو با هرس كردن، ايجاد يك تور بهينه و محاسبه طول آن، مسأله فروشنده دوره گرد و استنباط با عكس العمل استفاده از روش شاخه و قيد اجرا مي شود.
    الگوريتم جست وجو و پيمايش
    اين روش روي دو گروه از مسائل قابل اعمال هستند:
    الف ـ روش هاي پيمايش
    در روش هاي پيمايش، بايد تك تك گره هاي يك درخت دودويي براي بررسي مقادير عددي آنها ملاقات و بررسي جست وجو شوند.
    ب ـ روش هاي جست وجو
    روش هاي جست وجو كه حالت عمومي تري نسبت به روش هاي پيمايش هستند، مي توانند روي رئوس يك گراف اعمال شوند.
    جست وجو و پيمايش در درخت هاي دودويي و جست وجو و پيمايش گراف ها به صورت عرضي يا عمقي به وسيله اين الگوريتم ها قابل حل هستند.
    الگوريتم ژنتيك
    اخيراً دانشمندان رشته رايانه از نظريه تاريخي داروين براي حل مسائل علمي پيچيده استفاده مي كنند تا بتوانند عمليات هوشمندانه را پيش ببرند. ۳ عامل اصلي نظريه داروين عبارتند از:
    * تنوع: مشخصات والدين متفاوت با يكديگر تركيب شده تا بتوانند موجودي را با خصوصيات برتر به وجود آورند.
    * تصادف: عاملي است كه تغييراتي را در موجود فرزند ايجاد مي كند.
    *انتخاب: محيط، موجوداتي را گزينش مي كند كه داراي شايستگي بالاتري از لحاظ ادامه حيات و توليد مثل باشند.
    مدلسازي در الگوريتم ژنتيك بر پايه فرايند طبيعي تكامل و اصل بقاي برتر است و مشابه طبيعت، عمل را با حفظ و تقويت جنس برتر و از بين رفتن جنس ضعيف انجام مي دهد. در نتيجه منجر به ايجاد قدرتمندترين ساختار يا بهينه ترين آن براي بقا در محيط مي شود. روش انتخاب ژنتيكي در طول ميليون ها سال، طبيعتي را پديد آورده كه براساس اصل بقاي برتر و جهش سازنده قادر به حل پيچيده ترين مسائل از جمله ساختارهاي پروتئيني برپايه بهترين جانشين آمينواسيدها عمل مي كند.
    
    
    


 روزنامه ايران، شماره 3562 به تاريخ 14/11/85، صفحه 6 (دانش)

لينک کوتاه به اين مطلب:   
 


    دفعات مطالعه اين مطلب: 4215 بار
    

 

 
 
چاپ مطلب
ارسال مطلب به دوستان

معرفی سايت به ديگران
گزارش اشکال در اطلاعات
اشتراک نشريات ديگر



 

اعتماد
ايران
دنياي اقتصاد
رسالت
شرق
كيهان
 پيشخوان
پژوهش نامه قرآن و حديث
متن مطالب شماره 23، پاييز و زمستان 1397را در magiran بخوانيد.

 

 

سايت را به دوستان خود معرفی کنيد    
 1397-1380 کليه حقوق متعلق به سايت بانک اطلاعات نشريات کشور است.
اطلاعات مندرج در اين پايگاه فقط جهت مطالعه کاربران با رعايت شرايط اعلام شده است.  کپی برداري و بازنشر اطلاعات به هر روش و با هر هدفی ممنوع و پيگيرد قانوني دارد.
 

پشتيبانی سايت magiran.com (در ساعات اداری): 77512642  021
تهران، صندوق پستی 111-15655
فقط در مورد خدمات سايت با ما تماس بگيريد. در مورد محتوای اخبار و مطالب منتشر شده در مجلات و روزنامه ها اطلاعی نداريم!
 


توجه:
magiran.com پايگاهی مرجع است که با هدف اطلاع رسانی و دسترسی به همه مجلات کشور توسط بخش خصوصی و به صورت مستقل اداره می شود. همکاری نشريات عضو تنها مشارکت در تکميل و توسعه سايت است و مسئوليت چگونگی ارايه خدمات سايت بر عهده ايشان نمی باشد.



تمامي خدمات پایگاه magiran.com ، حسب مورد داراي مجوزهاي لازم از مراجع مربوطه مي‌باشند و فعاليت‌هاي اين سايت تابع قوانين و مقررات جمهوري اسلامي ايران است