موضوع مقاله: طراحی الگوریتم | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # طراحی الگوریتم | مقدمه: در پاسخ به سوال الگوریتم چیست باید گفت که به مراحل گام به گام حل یک مسئله، الگوریتم گفته می‌شود. | ## بخش 1: طراحی الگوریتم | از آنجایی که برنامه‌نویسی با مسائل پیچیده‌ای سر و کار دارد و برنامه نویسان موظف به حل مسائل مختلف به صورت قدم به قدم هستند؛ الگوریتم‌نویسی یک ابزار و ایده مناسب در جهت مشخص کردن طرز صحیح پیاده‌سازی یک برنامه می‌باشد. ما با یک تکنولوژی جدید و ساخته شده توسط ناسا یا گوگل سر و کار نداریم؛ بلکه صرفا قصد داریم از یک مفهوم کاربردی تحت عنوان الگوریتم استفاده کنیم. حتی انسان‌های اولیه برای شکار و رفع گرسنگی از الگوریتم‌های مشخصی استفاده می‌کردند. یعنی مجموعه‌ای از دستورالعمل‌های متوالی و با جزئیات کامل که برای حل یک مسئله استفاده می‌کنیم. این دستورات باید دقیق و جامع بوده و به درستی بیان کننده هدفی خاص باشند؛ به طوری که ابهامی در دستورالعمل الگوریتم وجود نداشته باشد. همانطور که پیش از این گفته شد، در زندگی روزمره نیز همواره در حال استفاده کردن از الگوریتم‌های مختلف هستیم. مغز ما برای هر کاری که می‌خواهیم انجام دهیم، شروع به پیاده‌سازی بهترین مراحل می‌کند. به عنوان مثال، در حال حاضر تشنه شدیم و شیشه حاوی آب بر روی میز قرار داشته و یخچال هم در طبقه پایین مستقر است. در ابتدا که تصمیم می‌گیریم به جای رفتن به طبقه پایین و مراجعه به یخچال، از شیشه آب روی میز استفاده کنیم. حال برای استفاده از شیشه، الگوریتم زیر را داریم: شروع شیشه آب را بردار درب شیشه را باز کن آب کافی را درون لیوان کنار شیشه خالی کن شیشه را روی میز بگذار اکنون به آرامی آب را بنوش درب شیشه آب را مجددا ببند پایان در مثال بالا، مغز ما یک الگوریتم حاوی ۷ مرحله در جهت نوشیدن آب از شیشه تولید کرد. ما به صورت پی در پی در حال استفاده از این الگوریتم‌ها هستیم؛ بدون آنکه خودمان متوجه شده یا بدان اهمیتی بدهیم. در زندگی و اجتماع، آن فردی موفق‌تر است که الگوریتم‌های بهتری برای انجام کارهای خود پیاده‌سازی کند. می‌دانیم که سیستم‌های کامپیوتری برای اجرای کارها و انجام وظایف خود نیازمند برنامه یا Program هستند. هر کدام از این برنامه ها، حاوی دستوالعمل‌هایی بوده که به صورت گام به گام اجرا و اعمال می‌شوند. | ## بخش 2: طراحی الگوریتم | یعنی اگر قرار است کامپیوتر ما پیامی را برای کسی ارسال کند، باید از قبل به صورت قدم به قدم مشخص کرده باشیم که برنامه را باز کن، فلان متن را از کاربر دریافت کن، اتصال به اینترنت را چک کن و پیام را برای فلان شخص بفرست. با توجه به موارد گفته شده می‌توانیم دریابیم که برنامه نویسی، نقطه شروع تولید یک برنامه نیست. بلکه پیش از شروع برنامه‌نویسی و پیاده‌سازی کدها، بایستی مراحل گام به گام انجام یک کار را داشته باشیم. پس ما برای نوشتن یک برنامه که در کامپیوتر اجرا شود، ابتدا نیازمند الگوریتم آن برنامه یا بازی خواهیم بود. تا خودمان ندانیم که قرار است چه اتفاقی، چگونه و از چه طریقی رخ دهد، قادر به نوشتن برنامه برای کامپیوتر نخواهیم بود.. روش‌های طراحی الگوریتم کارایی، تحلیل و مرتبه الگوریتم‌ها نوشتن الگوریتم به زبان فارسی دو ایراد دارد: نوشتن الگوریتم‌های پیچیده به این شیوه دشوار است. تحلیل الگوریتم‌ها تعیین مقدار میزان کارایی یک الگوریتم در حل مسئله با تحلیل الگوریتم انجام می‌شود. تحلیل پیچیدگی زمانی زمانی که یک الگوریتم انجام می‌شود با تعداد ورودی‌های الگوریتم افزایش می‌یابد. تحلیل پیچیدگی زمانی یک الگوریتم، تعیین تعداد دفعاتی است که عمل اصلی به ازای هر مقدار از ورودی انجام می‌شود. عمل اصلی:زمان نوشتن الگوریتم اندازهٔ داده‌ها را معین سپس چند دستور را معلوم می‌کنیم که تعداد دفعاتی که این دستورات اجرا می‌شود کل کار الگوریتم را نشان می‌دهد. تحلیل پیچیدگی زمانی برای حالت معمول برای الگوریتم (جمع کردن عناصر آرایه) عمل اصلی: افزودن یک عنصر از آرایه به sum. عمل اصلی همیشه n بار انجام می‌شود یعنی برابر است با T(n) = n تحلیل پیچیدگی زمانی برای حالت معمول برای الگوریتم (مرتب‌سازی تعویضی) عمل اصلی: مقایسه S [j] با S[i]. بدترین حالت: T(n) = n تحلیل پیچیدگی زمانی در بدترین حالت برای الگوریتم (جستجوی ترتیبی) عمل اصلی: مقایسه یک عنصر آرایه با x. بهترین حالت: T(n) = ۱ تحلیل پیچیدگی زمانی در بهترین حالت برای الگوریتم (جستجوی ترتیبی) عمل اصلی: مقایسه یک عنصر آرایه با x. | ## بخش 3: طراحی الگوریتم | B (n) = ۱ مرتبه الگوریتم الگوریتم‌هایی با پیچیدگی زمانی از قبیل n و 100n را الگوریتم‌های زمانی خطی می‌گویند. مجموعه کامل توابع پیچیدگی را که با توابع درجه دوم محض قابل دسته‌بندی باشند، n²) (θ می‌گویند. آشنایی بیشتر با مرتبه الگوریتم‌ها برای یک تابع پیچیدگی مفروض ƒ(n),O (ƒ (n) "O بزرگ» مجموعه‌ای از توابع پیچیدگی g (n) است که برای آن‌ها یک ثابت حقیقی مثبت c و یک عدد صحیح غیر منفی N وجود دارد به قسمی که به ازای همهٔ N =<n داریم: g (n)>= c × ƒ (n) برای یک تابع پیچیدگی مفروض ƒ(n)، (Ω (ƒ(n)مجموعه‌ای از توابع پیچیدگی g (n) است که برای آن‌ها یک عدد ثابت حقیقی مثبت c و یک عدد صحیح غیر منفی N وجود دارد به قسمی که به ازای همهٔ N =<n داریم: g (n) =<c × ƒ (n) برای یک تابع پیچیدگی مفروض ƒ(n)، داریم: θ (ƒ(n = O (ƒ(n ∩ Ω (ƒ(n یعنی θ(ƒ(n مجموعه‌ای از توابع پیچیدگی g (n) است که برای آن‌ها ثابت‌های حقیقی مثبت c وd و عدد صحیح غیر منفی N وجود دارد به قسمی که: c × ƒ (n) <= d × ƒ(n) برای یک تابع پیچیدگی ƒ(n) مفروض، (o(ƒ(n) ”o کوچک” عبارت ازمجموعه کلیه توابع پیچیدگیg (n) است که این شرط را برآورده می‌سازند: به ازای هرثابت حقیقی مثبت c، یک عدد صحیح غیر منفی N وجود دارد به قسمتی که به ازای همهٔ N =<n داریم: g (n) =<c × ƒ (n) روش تقسیم و حل روش تقسیم و حل یک روش بالا به پایین است. حل یک نمونه سطح بالای مسئله با رفتن به جزء و بدست آوردن حل نمونه‌های کوچکتر حاصل می‌شود. هنگام پی ریزی یک الگوریتم بازگشتی، باید: ۱- راهی برای به دست آوردن حل یک نمونه از روی حل یک نمونه از روی حل یک یا چند نمونه کوچک‌تر طراحی کنیم. انواع روش‌های مرتب‌سازی: مرتب‌سازی ادغامی ادغام یک فرایند مرتبط با مرتب‌سازی است. ادغام دوطرفه به معنای ترکیب دو آرایه مرتب شده در یک آرایهٔ مرتب است.مرتب‌سازی ادغامی شامل مراحل زیر می‌شود: ۱- تقسیم آرایه به دو زیر آرایه، هر یک با n/2 عنصر. راهبرد طراحی تقسیم و حل شامل مراحل زیر است: ۱- تقسیم نمونه‌ای از یک مسئله به یک یا چند نمونه کوچکتر. اگر نمونه‌های کوچک تربه قدر کافی کوچک نبودند، برای این منظور از بازگشت استفاده کنید. ۳- در صورت نیاز، حل نمونه‌های کوچک‌تر را ترکیب کنید تا حل نمونه اولیه به دست آید. مرتب‌سازی سریع در مرتب‌سازی سریع، ترتیب آن‌ها از چگونگی افراز آرایه‌ها ناشی می‌شود. همه عناصر کوچک‌تر از عنصر محوری در طرف چپ آن و همه عناصر بزرگ‌تر، در طرف راست آن واقع هستند. | ## جمع‌بندی | مرتب‌سازی سریع، به‌طور بازگشتی فراخوانی می‌شود تا هر یک از دو آرایه را مرتب کند، آن‌ها نیز افراز می‌شوند و این روال ادامه می‌یابد تا به آرایه‌ای با یک عنصر برسیم.