الگوریتم

از ویکی‌پدیا، دانشنامهٔ آزاد.

الگوریتم، مجموعه‌ای متناهی از دستوالعمل‌هاست که به صورت دقیق و بدون ابهام بیان شده‌اند و اگر به ترتیب خاصی اجرا شوند، مسئله حل می‌شود. به عبارت دیگر، الگوریتم روشی گام به گام است که برای حل مسئله به کار می‌رود.

واژه الگوریتم از نام محمد ابن موسی خوارزمی گرفته شده است. کتاب معروف الجبر و المقابله خوارزمی که حاوی دستورالعمل‌های مختلف برای حل مسائل محاسباتی است از راه ترجمه اسپانیایی آن در اروپا شناخته شد و نام عربی او، الخوارزمی، (از طریق آوانگاری آن در زبان اسپانیایی و سپس ورود آن به دیگر زبان‌های اروپائی) مترادف شد با "دستورهای حل مسائل".

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

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

البته الگوریتم‌ها معمولاً پیچیده‌تر از این هستند.

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

اگر الگوریتم برای عمل مورد نظر مناسب نباشد و با غلط باشد به نتیجه مورد نظر نمی‌رسیم. مثلاً اگر الگوریتم آبگوشت را با مواد اولیه کباب انجام دهیم یا اگر در الگوریتم ما ذکری از گوشت نباشد واضح است که به آبگوشت نمی‌رسیم.

هر الگوریتم ممکن است عمل مورد نظر را با دستورات مختلف در مدت زمان، و میزان حافظه و کار کمتر یا بیشتری نسبت به الگوریتم دیگر انجام دهد. به همین دلیل انتخاب الگوریتم مناسب و کارآ اهمیت زیادی در موفق بودن و کارآئی برنامه رایانه‌ای دارد.

تحلیل الگوریتم‌ها رشته‌ای است که به بررسی کارآئی الگوریتم‌ها میپردازد.

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

[ویرایش] مرتبط

تولید اعداد تصادفی در رایانه شناخت مسایل و ارائه راه حل مناسب برای حل آنها به منظور ارایه راه حل مناسب برای یک مسأله بهترین کار بررسی آن یا به عبارت دیگر تجزیه و تحلیل مسأله است به این منظور و برای شناخت بهتر یک مسأله باید سه عامل مهم را در نظر بگیرید این عوامل عبارت‌اند از: 1-مقادیر معلوم 2-خواسته‌های مسأله (مجهولات) 3-وعملیات محاسباتی مقادیر معلوم: مقادیری که در اختیار مسأله قرار می‌‌گیرند و برای رسیدن به هدف مورد نظر در مسأله مورد نیاز هستند.

محاسبات:

برای رسیدن به نتایج مورد نظر معمولاً لازم است تا عملیاتی روی مقادیر معلوم انجام دهیدبخش عمده‌ای از این عملیات معمولاًبا استفاده از فرمولهای مختلف انجام می‌‌شود البته محاسبات می‌‌توانند با توجه به روابط منطقی که بین مقادیر معلوم وخواسته‌های مسأله وجود دارند انجام گیرند.

خواسته‌های مسأله: مقادیری هستند که معمولاً در اثر انجام عملیات روی مقادیر معلوم حاصل می‌‌شوند البته مجهولات می‌‌توانند از روابط منطقی که در حل مسأله دخالت می‌کنند نیز به وجود آمده و مورد استفاده قرار گیرند.

الگوریتم

پس از بررسی مسأله وشناخت سه عامل اصلی برای حل آن لازم است تا روشی برای حل مسأله ارایه شود. این روش‌ها می‌‌توانند با استفاده از تجارب قبلی در حل مسائل و به دلخواه کسی که مسأله را حل می‌‌کند به دست آید یا بااستفاده از روش‌های علمی مبتنی بر تحلیل‌های ریاضی و منطقی صورت پذیرد. الگو ریتم در واقع روشي است که مسائل را با استفاده از تحلیل‌های ریاضی ومنطقی موردبررسی قرار داده وراه حل مناسبی برای آن ارایه می‌‌کند

تحلیل الگوریتم ها

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

تعریف الگوریتم:

به مجموعه‌ای از دستور العملها که با زبان دقیق و قابل فهم به همراه جزئیات لازم وبه صورت مرحله به مرحله به گونه‌ای اجرا شده که هدف خاصی را دنبال می‌‌کندو شروع وخاتمه آن‌ها نیز مشخص باشد الگوریتم می‌‌گویند. به عبارت دیگر می‌‌توان الگوریتم را به یک ماشین تشبیه کرد که مقادیر معلوم را دریافت کرده روی آن محاسباتی انجام می‌‌دهد ودر پایان خواسته‌های مسأله را ارایه می‌‌کند.

همان طور که می‌‌بینید رابطه نزدیکی بین مفهوم الگوریتم ونحوه کار کامپیوتردرحل مسائل وجودداردبنابر این بااستفاده ازروش الگوریتم می‌‌توانید حل مسائل را به گونه‌ای طراحی کنید که برای تبدیل به زبان کامپیوتر نیز قابل فهم باشد.

مفهوم الگو ریتم:

الگوریتم در اصطلاح به معنی ومفهوم روش تکنیک وشیوه حل یک مسأله است الگوریتم یکی از مهم‌ترین مفاهیم در کامپیوتر می‌‌باشد که به فهرستی از دستور العمل‌ها اطلاق می‌‌شود که برای حل یک مسأله می‌‌بایست گام به گام طی نمود.

کاربرد الگوریتم:

برای آشنایی با کاربرد الگوریتم بد نیست به این نکته توجه کنید که همه در زندگی روزمره با مسائل مختلفی سروکار دارند که به طریقی نسبت به حل آنها اقدام می‌‌کنند.

در برخورد با یک مسأله شیوه‌های گوناگونی برای حل وجود دارد. حل مسأله را می‌‌توان به طور کلی دارای پنج گام دانست .

1-تعیین نیازهای مسأله 2-تجزیه وتحلیل مسأله3-طراحی الگوریتمی برای حل مسأله 4-پیاده سازی الگوریتم5- بررسی وآزمودن نتیجه شناسایی نیازهای مسأله مارا در رسیدن به روش مناسبی برای حل آن یاری می‌‌کند. به علاوه در این مرحله ابزارهای مورد نیاز نیز شناخته می‌‌شوند. گاهی ممکن است به این نتیجه مهم برسید که در جهت حل مسأله به همکاری افرادی نیاز دارید که اطلاعات بیشتری در مورد آن دارند. پس از شناسایی کامل مسأله نوبت به تجزیه وتحلیل آن می‌‌رسد. در این گام ورودی‌های مسأله یا همان مفروضات داده شده را می‌‌شناسیم سپس خروجی یا پاسخ مسأله را تأیین می‌‌کنیم و بالا خره روش حل و ابزارهای این کار را انتخاب می‌‌نماییم. اما بحث اساسی از گام سوم به بعد آغاز می‌‌شود.

مثال:

شخصی را در نظر بگیرید که تصمیم به تعویض یک چرخ ماشین پنچر شده خود دارد پس الگوریتم همانند زیر طراحی می‌‌شود:

  1. - شروع
  2. - جک را زیر اتومبیل بگذارید
  3. - پیچ‌های چرخ پنچر شده را باز کنید
  4. - چرخ را خارج کنید
  5. - چرخ یدکی را جای آن بگذارید
  6. - پیچها را محکم کنید
  7. - اگر پیچها سفت نشده‌اند به مرحله 6بروید
  8. - جک را پایین بیاورید
  9. - پایان

شرایط الگوریتم:

اکنون با مفهوم‌های الگو ریتم آشنا شدیدلازم است ویژگی‌های یک الگوریتم رابشناسید.

الف_ استفاده از زبان ساده دقیق و قابل فهم:

این ویژگی سبب می‌‌شود تا در انجام دستور العمل‌ها همواره یک برداشت یکسان حاصل شود در غیر این صورت برداشت‌های متفاوت سبب خواهد شد تا دستور العمل‌ها نتایج متفاوتی را به همراه داشته باشند. زبان الگوریتم نیز می‌‌تواند یکی از زبان‌های گفتاری ونوشتاری مانند فارسی انگلیسی ونظایرآن باشد.

ب_ استفاده از جزئیات کافی:

این ویژگی سبب می‌‌شود تا دستور العمل‌ها به طور کامل اجرا شوند. وجود موارد نامشخص یا ارائه دستور العمل‌ها به صورت کلی ومبهم سبب مخدوش شدن نتایج خواهد شد

ج- شروع و پایان الگوریتم:

در یک الگوریتم باید شرع دستور العمل‌ها مشخص باشد. هر الگوریتم یک نقطه شروع دارد که به عنوان اولین دستور العمل از آن استفاده می‌‌شود به علاوه پایان و خاتمه الگوریتم نیز باید تعیین شود. یک الگوریتم می‌‌تواند بیش ازیک نقطه پایان داشته باشد.

د- ترتیب انجام دستور العمل ها:

یکی از ویژگی‌های مهم یک الگوریتم ترتیب اجرای دستور العمل‌ها است اگر این کار به درستی انجام نشود پیش بینی نتیجه کار مشخص نخواهد بود. دریک الگوریتم ترتیب انجام عملیات با استفاده از شماره گذاری دستور العمل‌ها از بالا به پایین انجام می‌‌شود که البته در صورت نیاز می‌‌توان ترتیب اجرای دستور العمل‌ها را نیز تغییر.


هـ- جامع بودن:

الگوریتم باید به شکلی طراحی شود تابا توجه به صورت مسأله و مفروضات آن در تمتم حالت‌ها نتایج مناسب و صحیحی را ارائه کرده و در حالت‌های خاص یا داده‌های ورودی متفاوت نتایج درستی را ایجاد کند

و- استفاده حد اقل دستور العمل ها:

در یک الگوریتم باید از دستورات اضافه که سبب افزایش حجم الگوریتم می‌‌شود خودداری نماییدچراکه این کارالگوریتم راشلوغ کرده و باعث سر در گمی می‌‌شود.

اجزاء اصلی الگوریتم:

یک طرح اصلی الگوریتم را می‌‌توان به سه قسمت 1-شروع2-پایان3-عملیات اجرایی تقسیم نمود که در زیر به تو ضیح آنها می‌‌پردازیم.

1- نقطه آغاز هرالگوریتم دارای نقطه آغازین می‌‌باشد که با کلمه شروع آغاز شده است 2- دستور العمل‌ها یا جملات اجرایی: بین نقطه آغاز و نقطه پایان هر الگوریتم دستور العمل‌ها یا جملات اجرایی قرار گرفته اند 3- نقطه پایان: نقطه پایانی هر الگو ریتم با کلمه پایان به اتمام می‌‌رسد. انواع جملات:

درطرح الگو ریتم از جملات گوناگونی استفاده می‌‌شود همانند جملات شرطی، جملات محاسباتی، جملات توضیحی وجملات مربوط به ورودی وخروجی که در زیر به توضیح آنها می‌‌پردازیم.

الف_ جملات شرطی در بسیاری از مسأله‌ها موضوع درک شرایط و تصمیم گیری درمورد چگونگی ادامه روند الگو ریتم اهمیت فراوانی دارد. گزاره‌هایی که درآنها بررسی شرط وتعیین اقدام بر اساس نتیجه آن وجود دارد گزاره‌های شرطی نامیده می‌‌شوند. در بیشتر گزاره‌های شرطی ساختار منطقی اگر.......آنگاه......به کار می‌‌رود در بخش "اگر" شرط بررسی می‌‌شود و در صورت پذیرش آن بخش "آنگاه" ادامه کار را تعیین می‌‌کند. در گزاره‌های شرطی سایر عملیات منطقی نظیر"و" و "یا" هم به کار می‌‌روند. مثال:الگو ریتمی بنویسید که عددی را از ورودی بخواند وبزرگ‌تر از15بودن آن را با پیامی مناسب اعلام نماید. 1- شروع 2- X راازورودی بخوان 3- اگر15x>آنگاه پیام "عدداز15بزرگ‌تر است" رادر خروجی بنویس 4- اگر15x<آنگاه پیام "عدداز15کوچک‌تراست" رادر خروجی بنویس 5- پایان

                                  دستور(ات)  Then         شرط(ها)    IF

IF شرط(ها) Then دستور(ات) در حالت اول ابتدا شرط یا شرط‌های ارائه شده بررسی می‌‌شوند ودر صورتی که نتیجه بررسی درست باشد دستور یا دستورات پس از Then اجرا می‌‌شوند در غیر این صورت دستور العملی که پس از دستور العمل شرطی قرار گرفته اجرا خواهد شد بدون آنکه دستور یا دستورات پس از Then اجرا شود. در حالت دوم شکل کامل تری از دستور العمل شرطی را ملاحظه می‌‌کنید که در ابتدا شرط یا شرط‌ها مورد بررسی قرار می‌‌گیرند اگر نتیجه ارزیابی آنها درست باشد دستورات موجود در بخش Then اجرا می‌‌شوند سپس دستور العملی که پس از دستور العمل شرطی قرار گرفته است اجرا می‌‌شود اما اگر نتیجه ارز یابی شرط یا شرط‌ها نا درست باشدبدون آنکه دستورات بخش Then اجرا شوند دستورات موجود در بخش Else اجرا خواهند شد سپس دستور العملی که پس از دستور العمل شرطی قرار دارد اجرا می‌‌شود ب_ جملات محاسباتی این جملات در واقع نحوه ارائه و استفاده از فرمول‌ها وانجام عملیات ریاضی و محاسباتی را تعیین می‌کنند و معمولاً برای اجرای آنها از همان شکلی که در ریاضیات وجود دارد استفاده می‌‌شود یعنی در سمت راست تساوی عملیات محاسباتی ودر سمت چپ تساوی نام یک متغیر به کار می‌‌رود البته به جای علامت تساوی از علامت فلش () نیز استفاده شود.(متغیرها مکان‌هایی هستند که توانایی نگهداری و ذخیره سازی انواع داده‌ها را دارند). ج_جملات توضیحی جملات توضیحی تنها جهت توضیحی عملیات اجرائی و یا الگوریتم می‌‌باشد وهیچ گونه اثری در اجرای الگوریتم ندارد مانندجمله: این برنامه میزان حقوق بازنشستگی را محاسبه می‌‌کند.

د_جملات ورودی وخروجی جملات ورودی وخروجی اصولاً شامل متغیرها و مقا دیر آنها می‌‌باشد که در ابتدابه منظور اختصاص مقداری به متغیر به‌عنوان جمله ورودی ویا پس از محاسبات مقدار نتیجه خروجی به عنوان جمله خروجی محسوب می‌‌گردد. دستور العمل‌های تکرار(حلقه ها): بعضی اوقات لازم است تا برخی از دستور العمل‌ها را به دفعات مشخصي تکرار نمایید در این موارد از دستور العمل هاي تکرار یا همان حلقه هااستفاده می‌‌شود . يك حلقه از اجزای مختلفی تشکیل می‌‌شود که عبارت‌اند از:

شمارنده حلقه: یک متغیر عددی است که تعداد دفعات تکرار دستور العمل‌ها رادر حلقه کنترل می‌‌کند .مقدار شمارنده در هر بار اجرای حلقه افزایش یا کاهش می‌‌یابد. مقدار اولیه: مقدار اولیه حلقه قبل از شروع حلقه تعیین می‌‌شود و به وسیله آن می‌‌توان مقدار اولیه را برای شمارنده حلقه تعیین کرد. شرط حلقه: برای کنترل تعداد دفعات تکرار حلقه باید از یک شرط استفاده کرد شرط موجود در حلقه نقطه پایان تکرار دستور العمل هارا در حلقه مشخص می‌‌کند و باید به گونه‌ای تنظیم شود تا از ایجاد حلقه بي- نهايت جلو گیری کند. برای ایجاد شرط در یک حلقه می‌‌توان از دستور العمل‌های شرطی استفاده کرد. دستورات حلقه: بخش دیگر در حلقه دستور العمل‌هایی هستند که در داخل حلقه تکرار می‌‌شوند. این دستور العمل‌ها با توجه به نیاز مسأله انتخاب می‌‌شوند [1]