الگوریتم

[Sardar]

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

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

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

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


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

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

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

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

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

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


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

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

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


مثال
<:P:>فرض کنید آرایه ای از اعداد مرتب نشده تصادفی دارید وهدف ما پیدا کردن بزرگترین عدد است.با یک نگاه به مسئله متوجه می شوید که باید تمام اعداد آرایه را برسی کنید. با کمی فکر کردن متوجه می شوید که هر عدد را فقط یک بار باید بررسی کنید.با این جزییات در اینجا یک الگوریتم ساده برای آن آرایه شده است:


فرض کنید که اولین عضو آرایه بزرگترین عدد است.
عدد بعدی را با این عدد مقایسه کنید.
فقط در حالتی که آن عدد بزرگتر است،آنرا بزرگترین عدد فرض کنید.
مرحله 2 و 3 را تا پایان آرایه تکرار کنید.
<:P:>
در اینجا یک رمز گذاری رسمی تر یک الگوریتم در یک شبه برنامه که شبیه بیشتر زبان های برنامه نویسی است آمده است:

یک آرایه با نام "List" داریم.

largest = List1
counter = 2
while counter <= length(List):
if Listcounter > largest:
largest = Listcounter
counter = counter + 1
print largest


شرح نماد گذاری
نماد " = " که در اینجا مورد استفاده قرار گرفت تخصیص را نشان می دهد. یعنی مقدار سمت راست رابطه به متغیر سمت راست تخصیص داده می شود.
"Listcounter" نشان دهنده عنصرcounter ام آرایه می باشد. برای مثال، اگر مقدار counter"" برابر 5 باشد، "Listcounter" به پنجمین عنصر آرایه اشاره می کند.
"<=" علامت "کوچکتر از، یا مساوی با" است.
<:P:>
توجه کنید در این الگوریتم فرض می شود آرایه دست کم دارای یک عضو است. این الگوریتم برای یک آرایه خالی کار نمی کند. بیشتر الگوریتم ها برای ورودی شان شرط هایی را قرار می دهند که به آن پیش شرط «pre-conditional )گفته می شود.

بیشتر مردمی که با الگوریتم ها کار می کنند دوست دارند بدانند یک الگوریتم به چه میزان از یک منبع خاص (مثل زمان یا حافظه) نیاز دارد. برای به دست آوردن مقادیر کمی، روش هایی برای تحلیل الگوریتم ها آرایه شده است.برای مثال، اگر طول آرایه را با حرف O به همراه nنشان دهیم الگوریتم بالا به زمانی برابر با O("n") نیاز دارد.


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


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

تقسیم و موفقیت. الگوریتم تقسیم و موفقیت مرحله های یک مسئله را به مراحل کوچکتری از آن مسئله (معمولاً با استفاده از روش باز گشتی )تقسیم می کند، تا وقتی که مستقیماً قابل بیان با زبان برنامه نویسی موجود شود.
برنامه نویسی پویا. هنگامی که یک مسئله دارای زیر ساخت های بهینه است، یعنی هنگامی که راه حل بهینه ی یک مسئله شامل راه حل های بهینه زیر مسائل آن است (برای مثال، کوتاه ترین مسیر بین رأس های یک گراف شامل کوتاه ترین مسیر بین تمام رأس های آن است) این مسئله را از پایین به بالا با حل ساده ترین حالات در ابتدا و بعد حالات سخت تر، تا حل کامل مسئله ادامه می دهیم.این یک الگوریتم برنامه نویسی پویا نامیده می شود.
روش حریصgreedy method. الگوریتم حریص همانند الگوریتم برنامه نویسی پویا است، با این تفاوت که در هر مرحله لازم نیست راه حل تمام زیر مسئله ها را پیدا کنید و فقط آن هایی که در آن موقع مناسب تر است را انتخاب می کنید.
برنامه نویسی خطی. در روش برنامه نویسی خطی برنامه را به چندین نا مساوی خطی تبدیل و بعد سعی می کنیم ورودی ها را بیشینه (و یا کمینه) کنیم.بسیاری از مسائل (از جمله بیشینه شار برای رویه graph های جهت دار))را می توان به روش برنامه نویسی خطی بیان و بعد آن را با استفاده از یک الگوریتم "عمومی" مانند الگوریتمSimplex حل کرد.
جست و جو و شمارش بسیاری از مسائل (از جمله بازی شطرنج) را می توان به عنوان مسائل گراف ها الگودهی کرد. یک الگوریتم جست و جوی گراف قوانینی رابرای حرکت در یک گراف مشخص کرده و برای این گونه مسائل مناسب است. این دسته همچنین شامل الگوریتم های جست و جو و backtracking می شود.
الگوی احتمال و استدلال(probabilistic and heuristic) . الگوریتم های متعلق به این دسته بیشتراز بقیه با تعریف الگوریتم سازگارند. الگوریتم های احتمال انتخابی را به صورت تصادفی (یا شبه تصادفی)انجام می دهند. می توان ثابت کرد در بعضی مسائل سریعترین راه حل شامل مقداری شانس است. الگوریتم های عمومی برای یا فتن راه حل های یک مسائله عمل های تکاملی بیولوژیکی( (biologicalرابا چرخه ای از جهش های تصادفی که منجر به راه حل های درستی می شود، تقلید می کنند. به این صورت آن ها، تولیدمثل و "بقای قوی ترین" را شبیه سازی می کنند. با در نظر گرفتن اینکه خود الگوریتم "راه حلی" برای یک مسائله است در برنامه نویسی عمومی این روش تا الگوریتم ها گسترش می یابد. در الگوریتم های استدلالی هدف عمومی یافتن جواب آخر نیست، بلکه یافتن جوابی تقریبی در هنگامی که زمان و منابع یا فتن جواب کامل عملی نیست. یک نمونه از این الگوریتم ها simulated annealing است که الگوریتم های احتمالی استدلالی است و با یک مقدار تصادفی راه حل یک مسائله را تغییر می دهند. نامsimulated annealing به اصطلاح metallurgic به معنای گرم و سرد کردن آهن برای افزایش دوام مصونیت از ترک و عیب اشاره دارد. هدف از این مغایرت )variance) های تصادفی، یافتن راه حل های بهینه عمومی است نه راه حل های بهینه محلی، با این ایده که با نزدیک تر شدن الگوریتم به جواب این عنصر تصادفی کاهش می یابد.
<:P:>
معیار دیگر برای دسته بندی الگوریتم ها اجرای آن ها است. الگوریتم باز گشتی که در برنامه نویسی تابعی «functional programming) متداول است، الگوریتمی است، که تا رسیدن به حالتی خاص، مکرراً خود را فراخوانی می کند. الگوریتم ها با این فرض مورد بررسی قرار می گیرند که آن ها در یک زمان یک دستور از الگوریتم را اجرا می کنند.این کامپپیوتر ها را گاهی کامپیوتر های سری می نامند.الگوریتمی که برای چنین محیطی طراحی شود الگوریتم سری نامیده می شود در برابر الگوریتم موازی، که از معماری ای استفاده می کنند که در آن چند پردازنده می توانند در آن واحد بر یک مسائله کار کنند. احتمالاً الگوریتم های استدلالی مختلف در این دسته قرار می گیرند، همان گونه که اسم شان (مثل الگوریتم عمومی) عملشان را توصیف می کند.

لیست الگوریتم هایی که در Wikipedia مورد برسی قرار می گیرند نیز در دسترس می باشد.