10-05-2019, 06:16 PM
الگوریتم یا خوارزمی مجموعه‌ای متناهی از دستورالعمل‌ها است، که به ترتیب خاصی اجرا می‌شوند و مسئله‌ای را حل می‌کنند. به عبارت دیگر یک الگوریتم، روشی گام به گام برای حل مسئله است. شیوه محاسبه معدل در مدرسه، یکی از نمونه‌های الگوریتم است.
![[تصویر: c4c69887-dd69-4d8c-be25-0ad794333c07.jpg]](https://zeus.ir/files/News/c4c69887-dd69-4d8c-be25-0ad794333c07.jpg)
[font=tahoma]خصوصیات یک الگوریتم
تمام الگوریتم‌ها باید شرایط و معیارهای زیر را داراباشند:
ورودی: یک الگوریتم باید هیچ یا چندین پارامتر را بهعنوان ورودی بپذیرد؛
خروجی: الگوریتم بایستی حداقل یک کمیت به عنوانخروجی (نتیجه عملیات) تولید کند؛
قطعیت: دستورات الگوریتم باید با زبانی دقیق، وبی‌ابهام بیان شوند. هر دستورالعمل نیز باید انجام‌پذیرباشد. دستورهایی نظیر «مقدار ۶ یا ۷ را به x اضافهکنید» یا «حاصل تقسیم پنج بر صفر را محاسبه کنید»مجاز نیستند؛ چرا که در مورد مثال اول، معلوم نیستکه بالاخره چه عددی باید انتخاب شود، و در خصوصمثال دوم هم تقسیم بر صفر در ریاضیات تعریفنشده‌است.
محدودیت: الگوریتم باید دارای شروع و پایانمشخصی باشد، به نحوی که اگر دستورات آن را دنبالکنیم، برای تمامی حالات، الگوریتم پس از طی مراحلشمارا و متناهی خاتمه یابد. به علاوه، زمان لازم برایخاتمه الگوریتم هم باید به گونه‌ای معقول، کوتاه باشد.
ریشه واژهٔ الگوریتم
خوارزمی
واژه الگوریتم از نام ریاضیدان و ستاره‌شناس وجغرافی‌دان نامی ایرانی، ابوجعفر محمد بن موسیخوارزمی (الخوارزمی)، گرفته شده است، که درخوارزم زاده شد و در دانشگاه «بیت الحکمه» بغداد بهاوج شهرت رسید. خوارزم یکی از شهرهای «ایرانبزرگ» بود، که امروزه در ازبکستان واقع شده است وخیوه نام دارد.
رساله ای که خوارزمی در قرن ۹ میلادی به عربینگاشته بود، در قرن ۱۲ به لاتین با نام “Algoritmi denumero Indorum” ترجمه شد؛ یعنی “[کتابیبدست]«الگوریتمی» در مورد اعداد هندی”، که«الگوریتمی» نام الخوارزمی بود که مترجم آن را درتبدیل به لاتین چنین آورده بود. در قرن ۱۳ میلادی واژهالگوریسموس(algorismus) به معنای «سیستمشمارش عربی(دهدهی)» (یعنی اعداد ۱ تا ۹ به علاوهصفر، و نیز مفهوم اعشار) بود؛ که هنوز هم یکی ازمعانی واژه الگوریسم(algorism) است. معنای دیگرالگوریسم «حساب کردن با کمک اعداد عربی» است؛یعنی فن انجام أعمال حسابی پایه، مانند جمع و ضرب،با قرار دادن اعداد در زیر هم و إعمال قواعدی خاص،که جایگزین به کارگیری اعداد رومی و استفاده ازچرتکه شد.
حتی روش انجام دستی تقسیم و جذر گرفتن(رادیکال) هم الگوریسم نامیده می شود. در قرن ۱۹ این کلمه در فرانسوی به algorithme تغییر شکل پیدا کرد، البته معنایش ثابت ماند. طولی نکشید که این کلمه به شکل algorithm وارد زبان انگلیسی شد؛ ولی فقط در اواخر قرن ۱۹ میلادی بود که معنای عام‌تر امروزی‌اش رایافت، و به «هر مجموعه قواعدی برای انجام یک رویه محاسباتی یا روال رایانه‌ای به کار رود» الگوریتم گفتهشد.
تبدیل نام الخوارزمی به الگوریسم و سپس الگوریتماحتمالا تحت تأثیر واژه یونانی arithmos (به معنایعدد) و arithmetic (به معنای محاسباتی) بوده است. برخی منابع هم کلمه لگاریتم را هم در تبدیل الگوریسمو الگوریتم بی تأثیر ندانسته اند.
نقش الگوریتم‌ها در علوم رایانه
در علوم رایانه، یک الگوریتم را یک روال محاسباتی خوش‌تعریف می‌دانند، که مقدار یا مجموعه‌ای از مقادیررا به عنوان ورودی (Input) دریافت کرده و پس ازطی چند گام محاسباتی، ورودی را به خروجی (Output) تبدیل می‌کند. بجز این، الگوریتم را ابزاریبرای حل مسائل محاسباتی نیز تعریف کرده‌اند. ساخت و طراحی الگوریتم مناسب در مرکز فعالیت‌های برنامه‌سازی رایانه قرار دارد. یک برنامه رایانه‌ای، بیانیک یا چند الگوریتم با یک زبان برنامه‌نویسی است.
مفهوم الگوریتم
مفهوم الگوریتم را معمولاً با تشبیه به دستور آشپزی توضیح می‌دهند. مثلاً اگر بخواهیم آبگوشت درست کنیم (عمل مورد نظر) با فرض اینکه مواد خام را داریم (حالت اولیه) مراحل مشخصی را باید طبق دستور آشپزی طی کنیم (دستورالعمل‌ها) تا به آبگوشت آماده (حالت پایانی) برسیم. البته الگوریتم‌ها معمولاً پیچیده‌تر از این هستند.
الگوریتم گاه دارای مراحلی است که تکرار می‌شود (در مثال آبگوشت مثلاً چند بار باید نمک زد یا آب اضافه کرد) و یا در مرحله‌ای نیازمند تصمیم‌گیری است (اگر نمک کافی است دیگر نمک نمی‌زنیم، اگر کافی نیست نمک می‌زنیم).
اگر الگوریتم برای عمل مورد نظر مناسب نباشد و یاغلط باشد به نتیجه مورد نظر نمی‌رسیم. مثلاً اگرالگوریتم آبگوشت را با مواد اولیه کباب انجام دهیم واضح است که به آبگوشت نمی‌رسیم.
باید بدانیم برای هر الگوریتم تعریف متغیرها و طراحی مرحله به مرحله بسیار مهم است. زیرا الگوریتم بایدبداند بر روی چه متغیر هایی، چه اعمالی را انجام دهد و نتیجه را در غالب چه متغیرها یا پارامتر هایی نشان دهد.
تحلیل الگوریتم
معمولاً برای حل یک مسئله، روش‌ها و الگوریتم‌های گوناگونی وجود دارند؛ یک الگوریتم ممکن است عمل مورد نظر را با دستورات مختلف در مدت زمان و یا کار کمتر یا بیشتری نسبت به الگوریتم دیگر انجام دهد. بههمین دلیل، انتخاب الگوریتم مناسب و کارا اهمیت زیادی در موفق بودن و کارایی برنامه رایانه‌ای دارد.
الگوریتم‌ها به عنوان یک فناوری مطرح هستند و دانشمندان آنها را طراحی، تحلیل، و مطالعه می‌کنند. تحلیل الگوریتم‌ها رشته‌ای است که به بررسی کاراییالگوریتم‌ها می‌پردازد. تحلیل الگوریتم‌ها یعنیپیش‌بینی منابع مورد نیاز برای اجرای یک الگوریتم، همچون: حافظه، پهنای‌باند ارتباطی، سخت‌افزار، و ازهمه مهمتر، زمان.
کارایی یا پیچیدگی هر الگوریتم را با تابعی نشان می‌دهند که تعداد مراحل لازم برای اجرای الگوریتم رابرحسب طول داده ورودی، یا میزان محل‌های لازمحافظه را بر حسب طول داده ورودی نشان می‌دهد.
روش های بیان الگوریتم
الف) بیان الگوریتم به زبان فارسی (شبه کد)
ب) بیان ریاضی الگوریتم
ج) بیان الگوریتم توسط اشکال (فلوچارت)[/font]
[font=tahoma]خصوصیات یک الگوریتم
تمام الگوریتم‌ها باید شرایط و معیارهای زیر را داراباشند:
ورودی: یک الگوریتم باید هیچ یا چندین پارامتر را بهعنوان ورودی بپذیرد؛
خروجی: الگوریتم بایستی حداقل یک کمیت به عنوانخروجی (نتیجه عملیات) تولید کند؛
قطعیت: دستورات الگوریتم باید با زبانی دقیق، وبی‌ابهام بیان شوند. هر دستورالعمل نیز باید انجام‌پذیرباشد. دستورهایی نظیر «مقدار ۶ یا ۷ را به x اضافهکنید» یا «حاصل تقسیم پنج بر صفر را محاسبه کنید»مجاز نیستند؛ چرا که در مورد مثال اول، معلوم نیستکه بالاخره چه عددی باید انتخاب شود، و در خصوصمثال دوم هم تقسیم بر صفر در ریاضیات تعریفنشده‌است.
محدودیت: الگوریتم باید دارای شروع و پایانمشخصی باشد، به نحوی که اگر دستورات آن را دنبالکنیم، برای تمامی حالات، الگوریتم پس از طی مراحلشمارا و متناهی خاتمه یابد. به علاوه، زمان لازم برایخاتمه الگوریتم هم باید به گونه‌ای معقول، کوتاه باشد.
ریشه واژهٔ الگوریتم
خوارزمی
واژه الگوریتم از نام ریاضیدان و ستاره‌شناس وجغرافی‌دان نامی ایرانی، ابوجعفر محمد بن موسیخوارزمی (الخوارزمی)، گرفته شده است، که درخوارزم زاده شد و در دانشگاه «بیت الحکمه» بغداد بهاوج شهرت رسید. خوارزم یکی از شهرهای «ایرانبزرگ» بود، که امروزه در ازبکستان واقع شده است وخیوه نام دارد.
رساله ای که خوارزمی در قرن ۹ میلادی به عربینگاشته بود، در قرن ۱۲ به لاتین با نام “Algoritmi denumero Indorum” ترجمه شد؛ یعنی “[کتابیبدست]«الگوریتمی» در مورد اعداد هندی”، که«الگوریتمی» نام الخوارزمی بود که مترجم آن را درتبدیل به لاتین چنین آورده بود. در قرن ۱۳ میلادی واژهالگوریسموس(algorismus) به معنای «سیستمشمارش عربی(دهدهی)» (یعنی اعداد ۱ تا ۹ به علاوهصفر، و نیز مفهوم اعشار) بود؛ که هنوز هم یکی ازمعانی واژه الگوریسم(algorism) است. معنای دیگرالگوریسم «حساب کردن با کمک اعداد عربی» است؛یعنی فن انجام أعمال حسابی پایه، مانند جمع و ضرب،با قرار دادن اعداد در زیر هم و إعمال قواعدی خاص،که جایگزین به کارگیری اعداد رومی و استفاده ازچرتکه شد.
حتی روش انجام دستی تقسیم و جذر گرفتن(رادیکال) هم الگوریسم نامیده می شود. در قرن ۱۹ این کلمه در فرانسوی به algorithme تغییر شکل پیدا کرد، البته معنایش ثابت ماند. طولی نکشید که این کلمه به شکل algorithm وارد زبان انگلیسی شد؛ ولی فقط در اواخر قرن ۱۹ میلادی بود که معنای عام‌تر امروزی‌اش رایافت، و به «هر مجموعه قواعدی برای انجام یک رویه محاسباتی یا روال رایانه‌ای به کار رود» الگوریتم گفتهشد.
تبدیل نام الخوارزمی به الگوریسم و سپس الگوریتماحتمالا تحت تأثیر واژه یونانی arithmos (به معنایعدد) و arithmetic (به معنای محاسباتی) بوده است. برخی منابع هم کلمه لگاریتم را هم در تبدیل الگوریسمو الگوریتم بی تأثیر ندانسته اند.
نقش الگوریتم‌ها در علوم رایانه
در علوم رایانه، یک الگوریتم را یک روال محاسباتی خوش‌تعریف می‌دانند، که مقدار یا مجموعه‌ای از مقادیررا به عنوان ورودی (Input) دریافت کرده و پس ازطی چند گام محاسباتی، ورودی را به خروجی (Output) تبدیل می‌کند. بجز این، الگوریتم را ابزاریبرای حل مسائل محاسباتی نیز تعریف کرده‌اند. ساخت و طراحی الگوریتم مناسب در مرکز فعالیت‌های برنامه‌سازی رایانه قرار دارد. یک برنامه رایانه‌ای، بیانیک یا چند الگوریتم با یک زبان برنامه‌نویسی است.
مفهوم الگوریتم
مفهوم الگوریتم را معمولاً با تشبیه به دستور آشپزی توضیح می‌دهند. مثلاً اگر بخواهیم آبگوشت درست کنیم (عمل مورد نظر) با فرض اینکه مواد خام را داریم (حالت اولیه) مراحل مشخصی را باید طبق دستور آشپزی طی کنیم (دستورالعمل‌ها) تا به آبگوشت آماده (حالت پایانی) برسیم. البته الگوریتم‌ها معمولاً پیچیده‌تر از این هستند.
الگوریتم گاه دارای مراحلی است که تکرار می‌شود (در مثال آبگوشت مثلاً چند بار باید نمک زد یا آب اضافه کرد) و یا در مرحله‌ای نیازمند تصمیم‌گیری است (اگر نمک کافی است دیگر نمک نمی‌زنیم، اگر کافی نیست نمک می‌زنیم).
اگر الگوریتم برای عمل مورد نظر مناسب نباشد و یاغلط باشد به نتیجه مورد نظر نمی‌رسیم. مثلاً اگرالگوریتم آبگوشت را با مواد اولیه کباب انجام دهیم واضح است که به آبگوشت نمی‌رسیم.
باید بدانیم برای هر الگوریتم تعریف متغیرها و طراحی مرحله به مرحله بسیار مهم است. زیرا الگوریتم بایدبداند بر روی چه متغیر هایی، چه اعمالی را انجام دهد و نتیجه را در غالب چه متغیرها یا پارامتر هایی نشان دهد.
تحلیل الگوریتم
معمولاً برای حل یک مسئله، روش‌ها و الگوریتم‌های گوناگونی وجود دارند؛ یک الگوریتم ممکن است عمل مورد نظر را با دستورات مختلف در مدت زمان و یا کار کمتر یا بیشتری نسبت به الگوریتم دیگر انجام دهد. بههمین دلیل، انتخاب الگوریتم مناسب و کارا اهمیت زیادی در موفق بودن و کارایی برنامه رایانه‌ای دارد.
الگوریتم‌ها به عنوان یک فناوری مطرح هستند و دانشمندان آنها را طراحی، تحلیل، و مطالعه می‌کنند. تحلیل الگوریتم‌ها رشته‌ای است که به بررسی کاراییالگوریتم‌ها می‌پردازد. تحلیل الگوریتم‌ها یعنیپیش‌بینی منابع مورد نیاز برای اجرای یک الگوریتم، همچون: حافظه، پهنای‌باند ارتباطی، سخت‌افزار، و ازهمه مهمتر، زمان.
کارایی یا پیچیدگی هر الگوریتم را با تابعی نشان می‌دهند که تعداد مراحل لازم برای اجرای الگوریتم رابرحسب طول داده ورودی، یا میزان محل‌های لازمحافظه را بر حسب طول داده ورودی نشان می‌دهد.
روش های بیان الگوریتم
الف) بیان الگوریتم به زبان فارسی (شبه کد)
ب) بیان ریاضی الگوریتم
ج) بیان الگوریتم توسط اشکال (فلوچارت)[/font]