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

طراحی الگوریتم دانش ساخت الگوریتم‌ها برای حل مسئله‌است. طراحی الگوریتم کاربردی را مهندسی الگوریتم می‌نامند. طراحی الگوریتم در بسیاری از راه حل‌های تئوری تحقیق در عملیات، شناسایی و گنجانیده شده‌است، مانند برنامه‌نویسی پویا و تقسیم و غلبه. الگوهای طراحی الگوریتم تکنیک‌های طراحی و اجرای طرح‌های الگوریتم هستند، در این روزها از طراحی الگوریتم می‌توان در فرایندهای بازیابی اینترنتی، مسیریابی استفاده نمود.
هم اکنون در ایران طراحی الگوریتم‌ها به عنوان درسی در رشته مهندسی کامپیوتر (نرم‌افزار و سخت‌افزار) و فناوری اطلاعات تدریس می‌شود.
در طراحی الگوریتم‌ها مباحثی همچون پیچیدگی زمانی، بازگشتی، روش تقسیم و غلبه، روش حریصانه، روش برنامه‌سازی پویا، تکنیک عقب‌گرد، نظریه P و NP تدریس می‌شود. زبان‌های برنامه‌نویسی رایانه‌های بزرگ مانند زبان ALGOL (برای زبان الگوریتمی)، زبان FORTRAN، زبان COBOL، زبان PL/I، زبان SAIL و SNOBOL ابزار محاسبات برای به اجرا درآوردن یک طراحی الگوریتم است اما یک طراحی الگوریتم (a/d) یک زبان نیست، یک a/d می‌تواند یک روش دست نوشته باشد، به‌طور مثال مجموعه‌ای از معادلات. یک سری از فرایندهای مکانیکی انجام شده توسط دست، قطعه آنالوگ از تجهیزات یا فرایند دیجیتال و پردازنده‌است. یکی از مهم‌ترین جنبه‌های طراحی الگوریتم، ایجاد یک الگوریتم است که دارای یک زمان اجرای کارآمد باشد، که به عنوان او بزرگ(big O)شناخته شده‌است.

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

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

تحلیل پیچیدگی زمانی

زمانی که یک الگوریتم انجام می‌شود با تعداد ورودی‌های الگوریتم افزایش می‌یابد.
تحلیل پیچیدگی زمانی یک الگوریتم، تعیین تعداد دفعاتی است که عمل اصلی به ازای هر مقدار از ورودی انجام می‌شود.
T(n) را پیچیدگی زمانی الگوریتم در حالت معمول می‌گویند.
W(n) را تحلیل پیچیدگی زمانی در بدترین حالت می‌نامند.
A(n) را پیچیدگی زمانی در حالت میانگین می‌گویند.
عمل اصلی:زمان نوشتن الگوریتم اندازهٔ داده‌ها را معین سپس چند دستور را معلوم می‌کنیم که تعداد دفعاتی که این دستورات اجرا می‌شود کل کار الگوریتم را نشان می‌دهد.
تحلیل پیچیدگی زمانی برای حالت معمول برای الگوریتم (جمع کردن عناصرآرایه)
عمل اصلی: افزودن یک عنصر از آرایه به sum.
اندازه ورودی: n، تعداد عناصر آرایه.
عمل اصلی همیشه n بار انجام می‌شود یعنی برابر است با T(n) = n
تحلیل پیچیدگی زمانی برای حالت معمول برای الگوریتم (مرتب‌سازی تعویضی)
عمل اصلی: مقایسه S [j] با S[i].
اندازه ورودی: تعداد عناصری که باید مرتب شوند.

بدترین حالت: T(n) = n

تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم (جستجوی ترتیبی)
عمل اصلی: مقایسه یک عنصر آرایه با x.
اندازه ورودی: , n تعداد عناصر موجود در آرایه.

بهترین حالت: T(n) = ۱

تحلیل پیچیدگی زمانی در بهترین حالت برای الگوریتم (جستجوی ترتیبی)
عمل اصلی: مقایسه یک عنصر آرایه با x.
اندازه ورودی: , n تعداد عناصر آرایه.
توضیح: در اولین بار عنصر مورد نظر پیدا شود.

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

الگوریتم‌ها یی با پیچیدگی زمانی ازقبیل n و100n را الگوریتم‌های زمانی خطی می‌گویند.
مجموعه کامل توابع پیچیدگی را که با توابع درجه دوم محض قابل دسته‌بندی باشند، n²) (θ می‌گویند.

مرتب‌سازی ادغامی

ادغام یک فرایند مرتبط با مرتب‌سازی است.

ادغام دوطرفه به معنای ترکیب دو آرایه مرتب شده در یک آرایهٔ مرتب است.
مرتب‌سازی ادغامی شامل مراحل زیر می‌شود:

۱- تقسیم آرایه به دو زیر آرایه، هر یک با n/2 عنصر.

۲- حل هر زیر آرایه با مرتب‌سازی آن.

۳- ترکیب حل‌های زیر آرایه‌ها از طریق ادغام آن‌ها در یک آرایه مرتب.

راهبرد طراحی تقسیم و حل شامل مراحل زیر است:

۱- تقسیم نمونه‌ای از یک مسئله به یک یا چند نمونه کوچکتر.

۲- حل هر نمونه کوچکتر. اگر نمونه‌های کوچک تربه قدر کافی کوچک نبودند، برای این منظور از بازگشت استفاده کنید.

۳- در صورت نیاز، حل نمونه‌های کوچک‌تر را ترکیب کنید تا حل نمونه اولیه به دست آید.

مرتب‌سازی سریع

در مرتب‌سازی سریع، ترتیب آن‌ها از چگونگی افراز آرایه‌ها ناشی می‌شود.

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

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

منابع:طراحی الگوریتم
تألیف:ریچارد نیپولیتان-کیومرث نعیمی پور
ترجمه:مهندس عین‌الله جعفرنژاد قمی