تبلیغات
انجمن ریاضی پژوهشسرای جوان - الگوریتم

انجمن ریاضی پژوهشسرای جوان

الگوریتم

سه شنبه 20 آذر 1386

الگوریتم

یک الگوریتم مجوعه‌ی متناهی از دستورالعمل های خوش تعریف برای انجام یک عمل است که با داشتن یک حالت اولیه به حالت پایانی مشخص و متناظری خواهد رسید. (با استدلالی ( heuristic )مقایسه شود).

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

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

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


الگوریتم های رسمی شده(formalized algorithms )

الگوریتم ها به خاطر روش پردازش اطلاعات توسط کامپیوتر اساسی و حیاتی هستند، چون یک برنامه کامپیوتری اساساً یک الگوریتم است که به کامپیوتر می گوید برای انجام یک عمل خاص مثل محاسبه حقوق کارمندان و یا چاپ ورقه گزارش دانش آموزان،چه مراحل خاصی را (با چه نظم خاصی) اجرا کند،.به این صورت، یک الگوریتم را می توان هر دنباله از دستوراتی که قابل اجرا توسط یک Turing complete باشد به حساب آورد.

به طور نمونه ای هنگامی که الگوریتم کار پرازش اطلاعات را انجام می دهد، داده از طریق یک وسیله یا منبع ورودی گرفته، به یک وسیله خروجی یاsink نوشته و / یا برای استفاده در زمانی دیگر ذخیره می شود. داده ذخیره شده به عنوان بخشی از حالت درونی(internal state) نهاد مجری الگوریتم تلقی می گردد.

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

چون الگوریتم ها لیست دقیقی از گام های دقیق است، نظم محاسبه تقریباً همیشه برای کار کرد الگوریتم اساسی می باشد. همواره فرض می شود دستور ها روشن هستند، و گفته می شود از" بالا آغاز" و"تا پایین کشیده می شوند"، اندیشه ای که به طور رسمی تر توسط جریان کنترل توصیف می شود.

تا اینجا ی بحث، رسمی سازی قواعد و قوانین برنامه نویسی امری(imperative programming) را به خود گرفت. این عام ترین مفهوم است، و تلاش دارد با وسایل "مکانیکی" مجزا کاری را توصیف کند؛ عملیات تخصیص، تعیین مقدار یک متغیر، برای این مفهوم از الگوریتم رسمی شده یکتا می باشد .در زیر مثالی از این تخصیص آمده است.

برای مفاهیم فرعی ) (alternative تشکیل دهنده یک الگوریتم برنامه نویسی تابعی و برنامه نویسی منطقی را ببینید.


اجرای الگوریتم

الگوریتم ها نه تنها توسط برنامه های کامپیوتری بلکه اغلب توسط دستگاه های دیگر، از جمله شبکه بیولوژیکی عصبی (برای مثال چگونگی انجام محاسبات توسط مغز انسان و یا اینکه یک حشره چگونه غذا را رد یابی می کند)، یا مدارهای الکتریکی و در دستگاه های مکانیکی به کار گرفته می شود.

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

بعضی برنامه نویسان تعریف "الگوریتم" را به رویه هایی که سر انجام پایان می پذیرند محدود می کنند. بعضی دیگر با این بهانه که برای انجام این اعمال دایمی به نهادی نیاز است، رویه های پایان نا پذیر را شامل می کنند. در حالت دوم پیروزی نتیجه را نمی توان توقف با یک خروجی معنادارتوصیف نمود.در عوض موفقیت باید برای سری های خروجی نا محدود تعریف شوند. برای مثال، الگوریتمی که مشخص می کند در یک سری دودویی نامحدود تصادفی تعداد صفرها بیشتر است یا یک ها، برای کارا بودن باید تا ابد در حال اجرا باشد. خروجی یک الگوریتم در صورت اجرای صحیح مفید خواهد بود: چون تا هنگامی که سری را برسی می کند اگر تعداد 0 های شمارش شده از 1 ها بیشتر شود.الگوریتم پاسخی مثبت می دهد، و بر عکس. برای این الگوریتم موفقیت را می توان به این صورت تعریف کرد که اگر تعداد 0 ها در این سری واقعاً از تعداد 1 ها بیشتر باشد، که یک پاسخ مثبت و در تمام حالات دیگر ترکیبی از جواب مثبت و منفی بدهد.

تاریخچه 

کلمه "الگوریتم" در اصل از نام ریاضی دان قرن نهم ، الخوارزمی ، گرفته شده است.کلمه الگوریسم(حساب) در اصل تنها به قوانین انجام محاسبات با اعداد عربی اطلاق می شد، اما در قرن 18 به "الگوریتم "بسط یافت. در حال حاضر این کلمه شامل تمام روش های معین حل مسئله یا انجام یک کار می شود. اولین الگوریتم نوشته شده برای کامپیوتر، یادداشت هایی بر موتورهای تحلیلی از ادا بایرون (Ada Byron) بود که در سال 1842م نوشته شد و به خاطر آن، بسیاری او را اولین برنامه نویس می دانند. به هر حال، چون چارلز بابیج هرگز موتور تحلیلی خود را کامل نکرد، این الگوریتم بر آن اجرا نشد. نبود دقت ریاضی درتعریف " رویه های خوش تعریف (well-defined routines )" مشکلاتی را برای ریاضی دان ها، و منطق دانان قرن 19 و اوایل قرن 20 پدیدآورد. این مشکل تا حد زیادی با معرفی ماشین تورینگ، مدلی انتزاهی از کامپیوتر که توسط الن تورینگ تنظیم شد، و این بیان که هر روش توصیف "رویه های خوش تعریف" با یک ماشین تورینگ قابل شبیه سازی است، رفع شد (این جمله به قضیه Church-Turing معروف است). تعریف رسمی امروزی یک الگوریتم این است: یک الگوریتم، رویه ای است که بر یک ماشین تورینگ کاملا خاص و یا یکی از شکل های مشابه اش قابل اجرا باشد.علاقه اولیه تورینگ به مسئله توقف(halting problem)، یعنی تعیین زمانی که الگوریتم یک رویه ی پایان بخش را بیان می کند، بود. در شرایط کاربردی نظریه پیچیدگی محاسبه مهم تر می باشد. این نظریه شامل مسئله گیج کننده ی الگوریتم های موسوم به NP-complete است که معمولاً بیشتر از چند شکلی ها زمان می گیرد.


انواع الگوریتم

راه های زیادی برای دسته بندی الگوریتم ها وجود دارد، تواناییها و قابلیت های هر دسته بندی موضوع بحث کنونی بوده است. یکی از معیار های دسته بندی اسلوب شناسی طرح و یا الگو می باشد. تعداد معینی الگو برای یک الگوریتم وجود دارد که هر کدام از بقیه متمایز است. از این گذشته هر دسته شامل نوع های مختلفی از الگوریتم ها می شود.چند تا از الگو های متداول عبارت است از:

 

  • تقسیم و موفقیت:الگوریتم تقسیم و موفقیت مرحله های یک مسئله را به مراحل کوچکتری از آن مسئله (معمولاً با استفاده از روش باز گشتی )تقسیم می کند، تا وقتی که مستقیماً قابل بیان با زبان برنامه نویسی موجود شود.

  • برنامه نویسی پویا: هنگامی که یک مسئله دارای زیر ساخت های بهینه است، یعنی هنگامی که راه حل بهینه ی یک مسئله شامل راه حل های بهینه زیر مسائل آن است (برای مثال، کوتاه ترین مسیر بین رأس های یک گراف شامل کوتاه ترین مسیر بین تمام رأس های آن است) این مسئله را از پایین به بالا با حل ساده ترین حالات در ابتدا و بعد حالات سخت تر، تا حل کامل مسئله ادامه می دهیم.این یک الگوریتم برنامه نویسی پویا نامیده می شود.

  • روش حریصgreedy method: الگوریتم حریص همانند الگوریتم برنامه نویسی پویا است، با این تفاوت که در هر مرحله لازم نیست راه حل تمام زیر مسئله ها را پیدا کنید و فقط آن هایی که در آن موقع مناسب تر است را انتخاب می کنید.

  • برنامه نویسی خطی: در روش برنامه نویسی خطی برنامه را به چندین نا مساوی خطی تبدیل و بعد سعی می کنیم ورودی ها را بیشینه (و یا کمینه) کنیم.بسیاری از مسائل (از جمله بیشینه شار برای رویه گرافهای جهت داررا می توان به روش برنامه نویسی خطی بیان و بعد آن را با استفاده از یک الگوریتم "عمومی" مانند الگوریتمSimplex حل کرد.

  • سه شنبه 20 آذر 1386 - 06:12 ق.ظ ]
    [ویرایش شده در : سه شنبه 20 آذر 1386 - 06:12 ق.ظ]

    [ پیام ()|| محمدامین ملاحسینی ومصطفی یغمائی ] [عمومی , ] [+]