الگوریتم واقعا چیست؟ *

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

در کتاب ساختمان داده‌ها در C++ هوروویتس و دیگران، آمده یک الگوریتم باید ورودی و خروجی داشته باشد، معین و بی‌ابهام باشد و محدود باشد. تاکید وی بیشتر بر معین و بی‌ابهام بودن الگوریتم است. مثلا دستور زیر برای مرتب کردن یک دنباله از اعداد را در نظر بگیرید:

 

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

 

در نگاه اول این عبارت به نظر Selection-Sort می‌آید، اما معلوم نیست که درجا (in-place) هست یا نه، چون عبارت قرار دادن ابهام دارد. همچنین این اعداد کجا هستند و به چه شکلی ذخیره شده‌اند؟ برای تبدیل این عبارت به الگوریتم باید عنوان شود که فرض کنید a آرایه‌ای از اعداد صحیح نامرتب است که در آن مکان iامین عدد به صورت a[i-1] و 1≤i≤n است و الی آخر.

در ماشین‌های تورینگ تمامی خصیصه‌های الگوریتم بودن به وضوح قابل مشاهده‌اند، به‌جز محدود بودن. ورودی ماشین تورینگ داخل نوار وجود دارد، دستورالعمل‌هایش بدون ابهام تعریف شده‌اند و کاملا مشخص است پس از اجرای هر دستور­العمل ماشین به چه وضعیتی خواهد رفت. خروجی آن هم وضعیت متوقف شدن آن است. ولی آیا یک ماشین تورینگ محدود است؟ به عبارت بهتر آیا یک ماشین تورینگ همیشه متوقف می‌شود؟ پاسخ این است که ماشین‌های تورینگ به ازای برخی ورودی‌ها و دستورالعمل‌ها ممکن است در حلقه بی‌پایان قرار گیرند. در این حالت گفته می‌شود این ماشین تورینگ الگوریتمی برای پذیرش ورودی مورد نظر ارائه نمی‌دهد. به عنوان مثال عبارت: برای گرامرهای بدون محدودیت الگوریتم عضویت وجود ندارد؛ بدین معنی است که ماشین تورینگ پذیرنده این زبان لزوما متوقف نمی‌شود و ممکن است در حلقه بی‌پایان قرار بگیرد.

Steve McConnell در قسمتی از کتاب Code Complete الگوریتم را با heuristic به شکل زیبایی مقایسه می‌کند.

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

یک heuristic روشی است که به شما کمک می‌کند به دنبال پاسخ بگردید. نتایجش گاها شانسی است، چرا که heuristic تنها به شما می‌گوید چگونه ببینید، نه که چه را پیدا کنید. او به طور مستقیم نمی‌گوید چگونه از نقطه الف به ب بروید، حتی ممکن است نداند که اصلا نقاط الف و ب کجا هستند. در عمل heuristic همان الگوریتم است که لباس دلقک­ها رو پوشیده. کمتر قابل پیش‌بینی است، بیشتر با آن خوش می‌گذرد و بدون تضمین برگشت سرمایه در 30 روز عرضه می­شود.»

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

 

پ.ن.

1. پس تکلیف الگوریتم‌های تصادفی چه می‌شود؟ ر.ک. کتاب طراحی الگوریتم‌ها نوشته هوروویتس و دیگران. بخش 2-4-1 الگوریتم‌های تصادفی: توصیف غیر رسمی

* این پست نسبت به پست اولیه تغییر کرده است.