الگوریتم
از ویکیپدیا، دانشنامهٔ آزاد
الگوریتم (به انگلیسی: Algorithm) مجموعهای متناهی از دستورالعملها است، که اگر به ترتیب خاصی اجرا شوند، میتوانند مسئلهای را حل کنند. به عبارت دیگر، یک الگوریتم، روشی گام به گام را برای حل مسئله بیان میکند. شیوه محاسبه معدل در مدرسه، یکی از نمونههای الگوریتم است.
فهرست مندرجات |
[ویرایش] خصوصیات یک الگوریتم
تمام الگوریتمها باید شرایط و معیارهای زیر را دارا باشند:[۱]
- ورودی: یک الگوریتم باید هیچ یا چندین پارامتر را به عنوان ورودی بپذیرد؛
- خروجی: الگوریتم بایستی حداقل یک کمیت به عنوان خروجی (نتیجه عملیات) تولید کند؛
- قطعیت: دستورات الگوریتم باید با زبانی دقیق، و إبیابهام بیان شوند. هر دستوراالعمل نیز باید انجامپذیر باشد. دستوراتی نظیر «مقدار ۶ یا ۷ را به x اضافه کنید» یا «حاصل تقسیم پنج بر صفر را محاسبه کنید» مجاز نیستند؛ چراکه در مورد مثال اول، معلوم نیست که بالاخره چه عددی باید انتخاب شود، و در خصوص مثال دوم هم، تقسیم بر صفر در ریاضیات تعریف نشده است.
- محدودیت: الگوریتم باید دارای شروع و پایان مشخصی باشد، به نحوی که اگر دستورات آنرا دنبال کنیم، برای تمامی حالات، الگوریتم پس از طی مراحل محدودی خاتمه یابد. به علاوه، زمان لازم برای خاتمه الگوریتم هم باید به گونهای معقول، کوتاه باشد؛
[ویرایش] منشاء واژهٔ الگوریتم
واژهٔ الگوریتم از نام محمد ابن موسی خوارزمی گرفته شده است.[۲] کتاب معروف الجبر و المقابله خوارزمی که حاوی دستورالعملهای مختلف برای حل مسائل محاسباتی است، از راه ترجمه به زبان اسپانیایی در اروپا شناخته شد و نام عربی او، الخوارزمی، (از طریق آوانگاری آن در زبان اسپانیایی و سپس ورود آن به دیگر زبانهای اروپایی) مترادف شد با «دستورهای حل مسائل».
[ویرایش] نقش الگوریتمها در علوم رایانه
در علوم رایانه، یک الگوریتم را یک روال محاسباتی خوشتعریف میدانند، که مقدار یا مجموعهای از مقادیر را به عنوان ورودی (Input) دریافت کرده، و پس از طی چند گام محاسباتی، ورودی را به خروجی (Output) تبدیل میکند. بجز این، الگوریتم را ابزاری برای حل مسائل محاسباتی نیز تعریف کردهاند. [۳] ساخت و طراحی الگوریتم مناسب در مرکز فعالیت های برنامهسازی رایانه قرار دارد. یک برنامه رایانهای، بیان یک الگوریتم توسط یک زبان برنامهنویسی است.
[ویرایش] مفهوم الگوریتم
مفهوم الگوریتم را معمولاً با تشبیه به دستور آشپزی توضیح میدهند. مثلاً اگر بخواهیم آبگوشت درست کنیم (عمل مورد نظر) با فرض اینکه مواد خام را داریم (حالت اولیه) مراحل مشخصی را باید طبق دستور آشپزی طی کنیم (دستورالعملها) تا به آبگوشت آماده (حالت پایانی) برسیم. البته الگوریتمها معمولاً پیچیدهتر از این هستند.
الگوریتم گاه دارای مراحلی است که تکرار میشود (در مثال آبگوشت مثلاً چند بار باید نمک زد یا آب اضافه کرد) و یا در مرحلهای نیازمند تصمیمگیری است (اگر نمک کافی است دیگر نمک نمیزنیم، اگر کافی نیست نمک میزنیم).
اگر الگوریتم برای عمل مورد نظر مناسب نباشد و یا غلط باشد به نتیجه مورد نظر نمیرسیم. مثلاً اگر الگوریتم آبگوشت را با مواد اولیه کباب انجام دهیم واضح است که به آبگوشت نمیرسیم.
باید بدانیم برای هر الگوریتم تعریف متغیر ها و طراحی مرحله به مرحله بسیار مهم است. زیرا الگوریتم باید بداند بر روی چه متغیر هایی، چه اعمالی را انجام دهد و نتیجه را در غالب چه متغیر ها یا پارامتر هایی نشان دهد.
[ویرایش] تحلیل الگوریتم
معمولاً برای حل یک مسئله، روشها و الگوریتمهای گوناگونی وجود دارند؛ یک الگوریتم ممکن است عمل مورد نظر را با دستورات مختلف در مدت زمان و یا کار کمتر یا بیشتری نسبت به الگوریتم دیگر انجام دهد. به همین دلیل، انتخاب الگوریتم مناسب و کارا اهمیت زیادی در موفق بودن و کارایی برنامه رایانهای دارد. الگوریتمها به عنوان یک فناوری مطرح هستند [۴] و دانشمندان آنها را طراحی، تحلیل، و مطالعه میکنند. تحلیل الگوریتمها رشتهای است که به بررسی کارایی الگوریتمها میپردازد. تحلیل الگوریتمها یعنی پیشبینی منابع مورد نیاز برای اجرای یک الگوریتم، همچون: حافظه، پهنایباند ارتباطی، سختافزار، و از همه مهمتر، زمان.[۵] کارایی یا پیچیدگی هر الگوریتم را با تابعی نشان میدهند که تعداد مراحل لازم برای اجرای الگوریتم را برحسب طول داده ورودی، یا میزان محلهای لازم حافظه را بر حسب طول داده ورودی نشان میدهد.
[ویرایش] جنبه حقوقی
در بعضی کشورها، مثل امریکا اگر تعبیه فیزیکی الگوریتمی ممکن باشد (برای مثال، یک الگوریتم ضرب که میشود آن را در واحد محاسبهٔ یک ریز پردازنده تعبیه کرد) میشود آن الگوریتم را به ثبت رساند.
[ویرایش] پانویس
[ویرایش] منابع
- Knuth, Donald. The Art of Computer Programming (Volume 1 / Fundamental Algorithms), 2nd Printing. USA: Addison-Wesley Publishing, 1969.
- Cormen, Thomas H. (et al), Intorduction to Algorithms (2nd Edition), USA: McGraw-Hill, 2001. ISBN 0-07-013151-1
- هورویتز، الیس. طراحی الگوریتمها، چاپ دوم (مترجم: علیخانزاده، امیر). مشهد: پرتونگار، ۱۳۸۵. ISBN 964-6735-12-6
[ویرایش] منابع برای مطالعه بیشتر
- طراحی الگوریتمها - تالیف دكتر محمود نقیبزاده
- شيرعلی شهرضا و شيرعلی شهرضا - آموزش سریع الگوریتم ها
- درس و کنکور طراحي الگوريتم - نوشته مهندس حميد رضا مقسمي - انتشارات گسترش علوم پايه
- کتاب طراحی الگوریتم - جعفر نژاد قمی
- مقدمه ای بر الگوریتم ها - پدیدآورنده: تامس کورمن، چارلز لیزرسان، رونالد دیوست، کلیفورد اشتاین - گروه مهندسی-پژوهشی خوارزمی (مترجم) - ناشر: درخشش
- تحلیل و طراحی الگوریتم ها (رشته کامپیوتر) - پدیدآورنده: احمد فراهی، جعفر تنها - ناشر: دانشگاه پیام نور
[ویرایش] جستارهای وابسته
