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

واضح آرشیو وب فارسی:فان پاتوق: تلاش بی پایان ذهن انسان های كنجكاو برای كشف ناشناخته ها و حل مسائل جالب یكی از جنبه های زیبای زندگی است. تاریخ علم نشان می دهد كه دانشمندان و ریاضیدانان متعددی عمر طولانی خود را وقف حل معماهای مختلف و شناسایی اسرارطبیعت و جامعه كرده و با حل هر مسأله نام خود را جاودانی كرده اند.
تكنولوژی كامپیوتر با توجه به پیشرفت جهشی خود در ۶۰ سال اخیر، هم به عنوان یك ابزار حل مسأله، هم به عنوان منبعی از كاربردهای متنوع آن، روز به روز جذاب تر شده و در این رابطه، الگوریتم به عنوان روش و مراحل حل مسأله، نقش كلیدی را در این فناوری ایفا می كند. یك مثال ساده برای الگوریتم، دستورالعمل های لازم برای روی هم قرار دادن قطعات مدل هواپیماست. این مونتاژ از قطعه خاصی شروع شده و سپس قطعات دیگر به ترتیب تا كامل شدن مدل، روی هم قرار می گیرند. یك برنامه كامپیوتری كه برای پیاده سازی و اجرای الگوریتم ها روی رایانه به كار می رود، مجموعه متناهی از دستوراتی است كه به ترتیب معینی از نخستین دستور به ترتیب تا انتها باید اجرا شوند.
این نوشته انواع الگوریتم ها را به صورت مختصر با عنوان مثال هایی برای هر كدام بررسی و مطالعه می كند. منظور از انواع الگوریتم ها، ارائه یك راه حل جامع و كارآمد برای مسائل مختلف است. الگوریتم ها هسته مركزی راه حل مسائل متعددی در بخش های علوم پایه، مسائل تجاری، رشته های مهندسی مانند طراحی پل ها، سدها، خودروها، هواپیماها، پیش بینی وضع جوی و نقشه های مربوطه، تجزیه و تحلیل ساختار مولكول ها و dna، كشف ذخایر گاز و نفت و طراحی و بهینه سازی سیستم های كامپیوتری است.
از لحاظ تاریخی كلمه الگوریتم برگرفته از نام ریاضیدان معروف قرن نهم هجری، الخوارزمی است كه برای نخستین بار در كتاب معروف جبر و مقابله برای بعضی از مسائل ریاضی مانند معادلات خطی و معادلات درجه دوم، راه حل نوینی مطرح كرد كه تا آن مقطع زمانی ارائه نشده بود. الگوریتم به عنوان مراحل حل یك مسأله یا انجام یك كار، مجموعه ای متناهی از دستورالعمل هایی است كه برای رسیدن به خروجی های مطلوب با شروع از یك حالت اولیه به كار می رود.
در تعریف ریاضی الگوریتم به دستورالعمل ها یا رویه های خوش تعریف اطلاق می شود كه به وسیله ماشین تورینگ كه یك مدل انتزاعی از كامپیوترهای دیجیتال است، شبیه سازی و اجرا گردد.
روش های زیادی برای گروه بندی الگوریتم ها با توجه به قابلیت و توانایی های هر دسته وجود دارد. از یك دیدگاه كلی می توان الگوریتم ها را به دو گروه عمده الگوریتم های ترتیبی و الگوریتم های موازی تقسیم كرد.
● الگوریتم های ترتیبی
در این گروه از الگوریتم ها، رایانه فقط از یك پردازنده برای اجرای دستورالعمل ها به صورت ترتیبی (سریال) استفاده می كند. در این نوع رایانه ها كه به نام معماری فون نیومن معروف است، برنامه و داده ها در حافظه ذخیره می شوند. ریزپردازنده هر بار یكی از دستورات برنامه را بازیابی كرده، پس از تفسیر آن را اجرا می كند. چنین رایانه هایی را slsd (جریان تك دستوری، جریان تك داده ای) می گویند. در اینجا به ۲ روش از الگوریتم های ترتیبی اشاره می شود.
▪ روش تقسیم و حل
در این روش، با استفاده از رویه های بازگشتی، مسأله اصلی را به زیرمسأله های كوچكتری تا جایی تقسیم می كنند كه امكان تقسیم مجدد آن وجود نداشته باشد. سپس با حل ساده ترین زیرمسأله ها و تركیب آنها با یكدیگر می توان به حل مسأله اصلی نائل شد. رویه بازگشتی، الگوریتمی است كه با استفاده از فراخوانی خودرویه، دستورات تشكیل دهنده آن را تا رسیدن به شرایط اولیه و خروج از آن، مكرر اجرا كند.
روش تقسیم و حل، یك روش طراحی بالا به پائین است، یعنی الگوریتم یك مسأله از سطح بالا به زیرمسأله ها تقسیم بندی می شود. به عنوان مثال می توان الگوریتم های جست وجوی دورویی در یك بردار (آرایه یك بعدی) یا در یك جدول (آرایه دوبعدی) ، مرتب سازی تركیب و مرتب سازی سریع ، مسأله برج های هانوی ، ضرب «ماتریس به روش استراسن»، عملیات محاسباتی مانند ضرب و جمع اعداد صحیح بسیار بزرگ و جدول مسابقات تیم ها در یك جام حذفی را با استفاده از روش تقسیم و حل انجام داد.

این صفحه را در گوگل محبوب کنید

[ارسال شده از: فان پاتوق]

[مشاهده در: www.funpatogh.com]

[تعداد بازديد از اين مطلب: 273]