آموزش طراحی و تحلیل الگوریتم قسمت اول

1395/1/18 --- 18707

سلام عرض میکنم خدمت همه ی شما دوستان عزیز . در خدمت شما هستم با آموزش طراحی و تحلیل الگوریتم ها .

در جلسه ی اول قصد دارم درباره ی مقدمات الگوریتم و فلوچارت و همچنین مشخصات یک الگوریتم مطالبی رو عرض کنم . همچنین درباره ی کارآمدی الگوریتم هم کمی صحبت می کنیم .

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

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

مبحث الگوریتم معمولا مستقل از زبان برنامه نویسی هست و یکی از مهمترین مباحث موجود در علوم کامپیوتر به حساب میاد . یک الگوریتم باید ویژگی هایی داشته باشه از جمله :

1-دارای آغاز و پایان مشخص باشه .

2- هر مرحله دارای جزئیات دقیق باشه .

3- مراحل دارای یک ترتیب درست باشه .

 

خب اما میشه دستور العمل هارو به انواع مختلفی تقسیم کرد برخی از انواع دستور العمل ها هم عبارت هستند از :

 

1-محاسباتی و انتسابی : میشه عملیات محاسباتی انجام داد یا مقداری رو به مقداری دیگر نسبت بدیم .

2-شرطی : با این دستورالعمل میشه انواع شروط رو بررسی کرد .

3-خروجی : در این دستور العمل هم مقادیری به چاپ میرسند .

بیاید الگوریتم یک مسئله ی ساده رو بررسی کنیم :

الگوریتمی که دو عدد رو دریافت کنه و تعیین کنه مجوعشون از 40 بزرگتر هست یا نه .

1-شروع

2-دو عدد aوb از ورودی دریافت کن

3- a+b رو محاسبه کن

4-آیا a+b > 40 هست ؟ اگر بله برو به مرحله ی 7

5-"خیر" را چاپ کن.

6-به مرحله ی 8 برو

7-" بله" را چاپ کن

8-پایان

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

حالا فلوچارت چیه ؟؟

 

فلوچارت یک راه استاندارد برای نمایش الگوریتم هست که توی اون باید از یک سری شکل های استاندارد برای نمایش دستور العمل ها ی مختلف استفاده کرد .

فلوچارت

شکل های بالا همون شکل هایی هستند که به عنوان استاندارد در فلوچارت ها مورد استفاده قرار می گیرند..

شکل اول " شروع " یا " پایان " الگوریتم رو مشخص میکنه .

شکل دوم که یک "فلش" هست ، جهت جریان منطقی در یک برنامه رو نشون میده

شکل سوم یعنی متوازی الاضلاع ، دستور العمل های ورودی و خروجی رو مشخص میکنه

شکل چهارم هم دستور العمل های انتساب و محاسبات رو نشون میده

و در شکل آخر هم دستورات شرطی بررسی میشن

 

حالا یه مثال هم از فلوچارت با هم میبینیم

فلوچارت

این فلوچارت مربوط به الگوریتمی هست که 3 عدد رو میگیره و تشخیص میده آیا میتونن تشکیل یک مثلث بدن یا خیر

خب حالا که با مفاهیم پایه ای فلوچارت و الگوریتم آشنا شدیم کمی راجع به بحث کارایی الگوریتم صحبت می کنیم ..

گاهی برای حل یک مسئله با چند راه حل رو به رو هستیم و در این زمان هست که باید الگوریتم با بیشترین کارآمدی رو انتخاب کنیم .

ملاک و معیار کارایی یک الگوریتم هم 2 چیز هست :

1- زمان اجرای الگوریتم 2- میزان حافظه برای اجرا

اصطلاحا به اولی پیچیدگی زمانی و به دومی پیچیدگی فضا هم میگن ..

به دلایلی معمولا اولی رو بیشتر مورد بررسی قرار میدن و ماهم در ادامه ی آموزش هامون سعی میکنیم بیشتر با این موضوع آشنا بشیم .

خب حالا همین ابتدا سوالی پیش میاد :

❓چرا با وجود اینکه سرعت کامپیوتر ها در حال افزایش هست و حافظه هم در حال ارزانتر شدن ، بررسی کارایی یک الگوریتم ضرورت پیدا میکنه ؟

جواب رو بایک مثال متوجه خواهیم شد :

در ریاضیات یکی از موضوعات کاربردی ، دنباله ی فیبوناچی هست . برای پیدا کردن یکی از جملات این دنباله 2 راه حل داریم . یکی الگوریتم بازگشتی هست و دیگری الگوریتم تکراری .

int fibo (int n ) 
{
 if (n<=1)
 return n;
 else return fibo(n-1) + fibo (n-2) ;
}

الگوریتم بازگشتی محاسبه ی جمله ی n ام دنباله ی فیبوناچی

int fibo (int n)
{
index i ; 
int f[0.n];
f [0] = 0 ;
if (n>0) {
 f [1] = 1;
 for ( i=2; i<= n ; i++)
 f[ i ] = f [i-1] + f [i-2] ;
} return f[n]; 
}

الگوریتم تکراری محاسبه ی جمله ی n ام دنباله ی فیبوناچی

 

فرض کنیم بخوایم جمله ی 100 ام این دنباله رو حساب کنیم . اگر با الگوریتم تکراری اینکارو کنیم ، 101 نانو ثانیه طول میکشه در حالی که با الگوریتم بازگشتی اینکار در 13 روز انجام خواهد پذیرفت . اگر جمله ی 120 ام رو بخوایم حساب کنیم ، با الگوریتم تکراری 121 نانو ثانیه وقت میخوایم ولی با روش بازگشتی 36 سال طول میکشه ..!!!!!!

خب مشخصه که بحث کارایی بحث خیلی مهمیه ..

این دقیقا بحث زمان اجراست و حالا باید دید چرا این زمان ها متفاوته و این اختلاف بسیار زیاده .. این همون پیچیدگی زمانی الگوریتم هست که در جلسه ی بعدی راجع به اون صحبت می کنیم

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