صفحه نخست           پست الکترونیک           ارشیو مطالب           طراح قالب

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

 طراحی الگوریتم های برنامه نویسی


این مطلب برای تست میباشد

موضوع:   | نویسنده: احسان رضایی | تاریخ: شنبه بیست و ششم تیر 1389 | و

این مطلب برای تست میباشد

تحلیل و بررسی الگوریتم کروسکال

موضوع: طراحی الگوریتم  | نویسنده: احسان رضایی | تاریخ: شنبه پانزدهم خرداد 1389 | و

عمل اصلی: یک دستور مقایسه.

اندازه ورودی : n ، تعداد رئوس و m  تعداد یال ها.

نکته: الگوریتم کروسکال همواره یک درخت پوشای کمینه تولید می کند.
 
اثبات : اثبات از طریق استقرا با شروع از مجموعه ای تهی از یال ها آغاز می شود.
 
void kruskal ( int n , int m,set _ of _ edges E,set _ of _edges & F )
index i , j ;
set _pointer p , q;
edge e ;
sort the m edges in E by weight in
nondecreasing order;
F = Ø ;
intitial (n) ;
while( number of edges in F is less than n-1){
e = edge with least weight not yet
considered ;
i , j = indices of vertices connected by e;
p = find (i) ;
q = find (i) ;
if (! equal ( p, q )) {
merge ( p , q ) ; add e to F ;
}


جهت مشاهده کامل متن به ادامه مطلب رجوع کنید


راهبرد عقبگرد

موضوع: طراحی الگوریتم  | نویسنده: احسان رضایی | تاریخ: جمعه چهاردهم خرداد 1389 | و

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

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

درخت های پو شای کمینه

موضوع: طراحی الگوریتم  | نویسنده: احسان رضایی | تاریخ: جمعه چهاردهم خرداد 1389 | و

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

(T (n) = 2 ( n – 1) ( n – 1) Є θ ( n²

 


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

موضوع: طراحی الگوریتم  | نویسنده: احسان رضایی | تاریخ: جمعه چهاردهم خرداد 1389 | و

الگوریتم پریم با زیر مجموعه ای تهی از یال های F و زیرمجموعه ای از رئوس Y آغاز می شود، زیرمجموعه حاوی یک راس دلخواه است. به عنوان مقداراولیه، {v1}

را به Y می دهیم . نزدیک ترین را س به Y ، راسی در V – Y است که توسط یالی با وزن کمینه به راسی در Y  متصل است.

void prim ( int n,const number W[ ] [ ],set_ of_edges & F )
{
index i , vnear;
number min;
edge e;
index nearest [2..n];
number distance [2..n];
F = Ø ;
for ( i = 2 ; i ≤ n ; i ++) {
narest [i] = 1 ;
distance [i] = W [1] [i] ;
}
repeat ( n-1 times ) {
min = ∞ ;

برای مشاهده کامل الگوریتم به ادامه مطلب رجوع کنید


ادامه مطلب

روش حریصانه در طراحی الگوریتم

موضوع: طراحی الگوریتم  | نویسنده: احسان رضایی | تاریخ: جمعه چهاردهم خرداد 1389 | و

 الگوریتم حریصانه ، به ترتیب عناصر را گرفته ، هر بار آن عنصری را که طبق ملاکی معین ”بهترین“ به نظر   می رسد، بدون توجه به انتخاب هایی که قبلا انجام داده یا در آینده انجام خواهد داد، بر می دارد.

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

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

ادامه مطلب

تحلیل الگوریتم درخت های جست و جوی دودویی بهینه

موضوع: طراحی الگوریتم  | نویسنده: احسان رضایی | تاریخ: جمعه چهاردهم خرداد 1389 | و

1: void search ( node _ pointer tree ,keytype keyin, node _ poiner & p)
2: {
3: bool found ;
4: p = tree;
5: found = false;
6: while (! found)
7: if ( p - > key == keyin )
8: found = true ;
9: else if ( keyin < p - > key )
10: p = p -> left ;
11: else
12: p = p - > right ;
13: }

اندازه ورودی: n ، تعداد کلید.

(T(n) = n ( n -1) ( n + 4 ) / 6  Є θ ( n³

جهت مشاهده تحلیل الگوریتم و توضیحات بیشتر به ادامه مطلب رجوع کنید


ادامه مطلب

برنامه نویسی پویا و مسائل بهینه سازی

موضوع: طراحی الگوریتم  | نویسنده: احسان رضایی | تاریخ: جمعه چهاردهم خرداد 1389 | و

حل بهینه ، سومین مرحله از بسط یک الگوریتم برنامه نویسی پویا برای مسائل بهینه سازی است. مراحل بسط چنین الگوریتمی به شرح زیر است:

1- ارائه یک ویژگی بازگشتی که حل بهینه ی نمونه ای از مسئله را به دست می دهد.

2- محاسبه مقدار حل بهینه به شیوه ی جزء به کل.

3- بنا کردن یک حل نمونه به شیوه ی جزء به کل.

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

ضریب دو جمله ای با استفاده از برنامه نویسی پویا

موضوع: طراحی الگوریتم  | نویسنده: احسان رضایی | تاریخ: چهارشنبه دوازدهم خرداد 1389 | و

int bin2 ( int n , int k )
{
index i , j ;
int B [0..n][0..k]
for ( i = 0; i ≤ n ; i ++)
if ( j == 0 || j == i )
B [i] [j] = 1;
else
B [i] [j] = B [ i – 1 ] [ j -1 ] + B [ i -1 ] [j];
return B[n] [k]:
}

عمل اصلی: دستورهای موجود در حلقه for . اندازه ورودی:n ، تعداد رئوس گراف

(T (n) = n × n × n = n³ Є θ (n³


برنامه نویسی پویا

موضوع: طراحی الگوریتم  | نویسنده: احسان رضایی | تاریخ: چهارشنبه دوازدهم خرداد 1389 | و

برنامه نویسی پویا، از این لحاظ که نمونه به نمونه های کوچکتر تقسیم می شود ، مشابه روش تقسیم و حل است ولی در این روش:

 - نخست نمونه های کوچک تر را حل می کنیم ،

 - نتایج را ذخیره می کنیم

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

مراحل بسط یک الگوریتم برنامه نویسی پویا به شرح زیر است:

 1- ارائه یک ویژگی بازگشتی برای حل نمونه ای از مسئله .

 2- حل نمونه ای از مسئله به شیوه جزء به کل با حل نمونه های کوچک تر.

 


تحلیل و بررسی الگوریتم ضرب ماتریس استراسن

موضوع:   | نویسنده: احسان رضایی | تاریخ: چهارشنبه دوازدهم خرداد 1389 | و

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

مسئله : تعیین حاصلضرب دو ماتریس n ×n که در آن n توانی از 2 است.

void starssen ( int n,n × n _ matrix A,n × n _ matrix B,n × n _ matrix & C)
{
if ( n <= threshold)
compute C = A × B using the standard algorithm;
partition A into four submatrics A11, A12 , A21,A22;
partition B into four submatrics B11, B12 , B21,B22;
compute C = A × B using Starssen’s Method;
}

تحلیل الگوریتم مرتب سازی سریع

موضوع:   | نویسنده: احسان رضایی | تاریخ: چهارشنبه دوازدهم خرداد 1389 | و

عمل اصلی: مقایسه[S [i  با pivotitem .

اندازه ورودی: n = high – how +1 ، تعداد عناصرموجود در زیر آرایه.

T(n) = n - 1

عمل اصلی: مقایسه[S [i  با pivotitem  در روال partition .

اندازه ورودی: n ، تعداد عناصر موجود درآرایه S.

    T(n)     =      T(0)   +   T( n – 1)   +   n – 1

(W (n) = n (n – 1) / 2  Є θ (n²

برای مشاهده و تحلیل الگوریتم به ادامه مطلب رجوع کنید


ادامه مطلب

مرتب سازی سریع (quicksort)

موضوع:   | نویسنده: احسان رضایی | تاریخ: چهارشنبه دوازدهم خرداد 1389 | و

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

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

روش تقسیم و حل 2

موضوع:   | نویسنده: احسان رضایی | تاریخ: چهارشنبه دوازدهم خرداد 1389 | و

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

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

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

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


تحلیل الگوریتم مرتب سازی ادغامی

موضوع:   | نویسنده: احسان رضایی | تاریخ: چهارشنبه دوازدهم خرداد 1389 | و

  عمل اصلی: مقایسهU  با V.

 اندازه ورودی:h  وm ،تعداد عناصر موجود در هر یک از دو آرایه ورودی.

پیچیدگی زمانی در بدترین حالت:  W ( h , m) = h + m - 1

عمل اصلی: مقایسه ای که درادغام صورت می پذیرد.

اندازه ورودی: n ، تعداد عناصر آرایه S.

    W (n)      =       W (h)    +    W ( m)    +      h  + m – 1

W (n)  = 2 W( n / 2)  + n -1

(W( n )  Є θ ( n lg n

برای مشاهده و تحلیل الگوریتم به ادامه مطلب رجوع کنید


ادامه مطلب

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

موضوع:   | نویسنده: احسان رضایی | تاریخ: چهارشنبه دوازدهم خرداد 1389 | و

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

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

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

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

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

 


روش تقسیم و حل

موضوع:   | نویسنده: احسان رضایی | تاریخ: چهارشنبه دوازدهم خرداد 1389 | و

 
روش تقسیم و حل یک روش بالا به پایین است.

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

1- راهی برای به دست آوردن حل یک نمونه از روی حل یک نمونه ازروی حل یک یا چند نمونه کوچک تر طراحی کنیم.

2- شرط(شرایط ) نهایی نزدیک شدن به نمونه(های) کوچک تر را تعیین کنیم.

3- حل را در حالت شرط (شرایط)نهایی تعیین کنیم.


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

موضوع:   | نویسنده: احسان رضایی | تاریخ: جمعه هفتم خرداد 1389 | و

 

الگوریتم ها یی با پیچیدگی زمانی ازقبیل n و 100nرا الگوریتم های زمانی خطی می گویند.

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

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

ادامه مطلب

اهمیت ساخت الگوریتم های کارآمد

موضوع:   | نویسنده: احسان رضایی | تاریخ: پنجشنبه ششم خرداد 1389 | و

تعداد مقایسه های انجام شده توسط جستجوی دودویی

تعداد مقایسه های انجام شده توسط جستجوی ترتیبی

اندازه ارایه

8

128

128

11

1024

1024

21

1048576

1048576

33

4294967294

4294967294

جست و جوی دودویی معمولا بسیار سریع تر ازجست و جوی ترتیبی است.

تعداد مقایسه های انجام شده توسط جست و جوی دودویی برابر با lg n + 1  است .

تحلیل و بررسی الگوریتم جست و جوی دودویی

موضوع:   | نویسنده: احسان رضایی | تاریخ: پنجشنبه ششم خرداد 1389 | و

0: Void binsearch (int n,const keytype S[ ],keytype x,index& location)
1: {
2: index low, high, mid;
3: low = 1 ; high = n;
4: location = 0;
5: while (low <= high && location = = 0) {
6: mid = Į(low + high)/2⌡;
7: if ( x = = S [mid])
8: location = mid;
9: else if (x < S [mid])
10: high = mid – 1;
11: else
12: low = mid + 1;
13:   }
14: }

n - عددی از جنس عدد صحیح

S - متغیر اصلی که جست و جو را در ان انجام میدهیم (ارایه ای)

x- مقدار مورد جستجو

location- اشاره گری برای پیمایش روی ارایه

۰: ایجاد تابعی با عنوان seqsearch و پارامتر های int n,const keytype S[ ],keytype x,index& location

۲: تعریف متغیر های low, high, mid

۳: مقدار دهی متغیر low با عدد یک و ریختن عدد n درون high

۴: مقدار دهی  اشاره گر location با عدد ۰

۵: تا زمانی که low کوچکتر یا مساوی high و location برابر ۰ بود حلقه تکرار می شود

۶: low + high وتقسیم بر ۲ شده و درون متغیر mid ریخته می شود

۷: اگر x کوچکتر از [S [mid بود، mid – 1 شده و درون high ریخته می شود و در غیر این صورت mid + 1 شده و درون low ریخته می شود


تحلیل و بررسی الگوریتم جست و جوی ترتیبی

موضوع:   | نویسنده: احسان رضایی | تاریخ: پنجشنبه ششم خرداد 1389 | و

0: Void seqsearch ( int n,const keytype S[ ],keytype x,index& location)
1: {
2: location = 1;
3: while (location <= n && S[location] ! = x)
4: location++;
5: if (location > n )
6: location = 0 ;
7: }

n - عددی از جنس عدد صحیح

S - متغیر اصلی که جست و جو را در ان انجام میدهیم (ارایه ای)

x- مقدار مورد جستجو

location- اشاره گری برای پیمایش روی ارایه

توضیح خطوط برنامه:

۰: ایجاد تابعی با عنوان seqsearch و پارامتر های int n,const keytype S[ ],keytype x,index& location

۲:مقدار دهی  اشاره گر location با عدد ۱

۳: تا زمانی که location کوچکتر یا مساوی n باشد و S با متغیر مورد جست و جو برابر نباشد حلقه تکرار خواهد شد

۴: افزودن یک واحد به اشاره گر location

۵: اگر location بزرگتر از n شد، مقدار location را برار با صفر کن 


بیان مفهوم های مرتبط

موضوع:   | نویسنده: احسان رضایی | تاریخ: شنبه یکم خرداد 1389 | و

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

1- نوشتن الگوریتم  های پیچیده به این شیوه دشوار است.

2- مشخص نیست از توصیف فارسی الگوریتم چگونه می توان یک برنامه کامپیوتری ایجاد کرد


بهبود پیچیدگی یک برنامه

موضوع:   | نویسنده: احسان رضایی | تاریخ: پنجشنبه سی ام اردیبهشت 1389 | و

الگوریتم‌ها بر دو مبنای صرفه جویی در زمان و صرفه جویی در هزینه استفاده از حافظه استوارند که اولی تحت عنوان پیچیدگی زمانی و

دومی تحت عنوان پیچیدگی حافظه از آن یاد می‌شود که به ترتیب

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

یا به طور متوسط چندبار اجرا می‌شوند و یا چه میزان حافظه را به خود تخصیص می‌دهند.

بنابراین روش‌های گوناگونی طراحی شده‌است تا به کمک آن‌ها الگوریتم‌هایی نوشته و براساس آن‌ها برنامه نویسی‌هایی انجام گیرد تا

بهترین کارایی از لحاظ پیچیدگی زمانی و مکانی حاصل شود که روش‌های زیر از جمله مهم ترین آن‌ها بوده و در کتب طراحی الگوریتم مورد

بحث قرار گرفته‌است:

 الف)روش تقسیم و غلبه

ب)برنامه نویسی پویا

ج)روش حریصانه

د)روش عقبگرد

ه) روش شاخه و حد

برای محاسبه پیچیدگی روابط می‌توانید از قضایای زیادی استفاده نمایید که مهم ترین آن‌ها قضیه اصلی(master theorem) می‌باشد

که بسیار کاراست و در کتابCLRS به وضوح توضیح داده شده‌است.


نمایش پیچیدگی الگوریتم

موضوع:   | نویسنده: احسان رضایی | تاریخ: پنجشنبه سی ام اردیبهشت 1389 | و

برای نمایش پیچیدگی الگوریتم‌ها از تعاریف زیر استفاده می‌شود:

Big-O (حدبالا)

تابعf را نظر بگیرید که برای کلیه n≥۰ است، می‌گوئیم((f(n) = O(g(n) اگر ثابت‌های مثبت n و c وجود داشته باشند به طوریکه از یک n

به بعد همیشه f(n) < cg(n) برقرار باشد.

این نماد حدبالائی برای تابع (f(n می‌دهد و وقتی بکار می‌رود که رفتار الگوریتم بدترین حالت و بیشترین زمان اجرا را برای مقادیر

معین ورودی دارد

Big-Ω (حدپائین)

تابع (f(n را نظر بگیرید که برای کلیه n≥۰ است، می‌گوئیم f(n) = Ω (g(n)) اگر ثابت‌های مثبت n۰ و c وجود داشته باشند به طوریکه از

یک n۰ به بعد همیشه f(n)≥ cg(n) برقرار باشد.

این نماد حد پائینی برای تابع f(n) می‌دهد و وقتی بکار می‌رود که رفتار الگوریتم بهترین حالت و کمترین زمان اجرا را برای مقادیر

معین ورودی دارد

Big-Θ (حدمتوسط)

تابع (f(n را نظر بگیرید که برای کلیه n≥۰ است، می‌گوئیم((f(n) = Θ(f(n)) اگر ثابت‌های مثبت n۰، c۱ و c۲ وجود داشته باشند به

طوریکه از یک n۰ به بعد همیشه c۱g(n) ≤f(n) ≤ c۲g(n) برقرار باشد.

این نماد حدمتوسطی برای تابع(f(n می‌دهد و زمان اجرای الگوریتم را به صورت میانگینی از تعداد عملیات انجام شده با کلیه نمونه ورودی های مسئله نشان می‌دهد.

اگر زمان الگوریتم وابسته به ورودی نباشد با نماد O(۱) نشان داده می‌شود؛وبرای تحلیل الگوریتم باید به اندازه کافی الگوریتم را درک

کرده باشیم تا بهترین و بدترین رفتار را تولید و محاسبه کنیم.

چون برآورد رفتار آماری ورودی‌ها امری دشوار است، در اکثر موارد به بدترین حالت قناعت می‌کنیم.

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

را بعنوان پیچیدگی کل الگوریتم درنظرمی گیریم.

غالبا پیچیدگی (g(n یکی از توابع زیر است: n (پیچیدگی خطی)، log n (لگاریتمی)، na (چندجمله‌ای) و an که a≥۲ (نمائی).

در زیر مربته اجرائی چند تابع به ترتیب صعودی نوشته شده‌است.

(!O(۱)۲) < O(n۳) < O(۲n) < O(n)


پیچیدگی زمانی

موضوع:   | نویسنده: احسان رضایی | تاریخ: پنجشنبه سی ام اردیبهشت 1389 | و

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

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

منظور از واحد زمانی، واحدهای زمانی واقعی مانند میکرو یا نانو ثانیه نمی‌باشد بلکه منظور واحدهای منطقی است که رابطه بین بزرگی

(n) یک فایل یا یک آرایه و زمان مورد نیاز برای پردازش داده‌ها را شرح می‌دهد.(توجه کنید که هر دستور یک واحد زمانی اشغال می‌کند.)

مثلاً دستورات a=b و c/d-e* a=b هر کدام یک واحد زمانی را دربردارند.

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

یک گام یا مرحله برنامه، یک قسمت یا بخش با معنی برنامه‌است (از لحاظ مفهومی یا نحوی) که زمان اجرای آن مستقل از مشخصات نمونه‌است.

بعنوان مثال تمام عبارت زیر یک مرحله‌است.

return (a+b-c) / (a+b)+۴٫۰ ;

بنابراین تعداد مراحل برای هر عبارت یک برنامه بستگی به نوع عبارت دارد، بطوریکه در عبارات توضیحی برابر صفر و در دستور انتسابی

بدون فراخوانی برابر یک می‌باشد. و در دستورات غیربازگشتی حلقه for، while، repeat until به تعداد تکرار حلقه در نظر گرفته می‌شود.

هدف از محاسبه پیچیدگی زمانی یک الگوریتم این است که بفهمیم نیازمندی یک الگوریتم به زمان با چه تابعی رشد می‌کند و هدف اصلی بدست

آوردن این تابع رشد است.

برای مثال هرچه زبان برنامه نویسی(compiler) به زبان ماشین نزدیک تر باشد، برنامه با سرعت بیشتری به جواب خواهد رسید

زمان اجرا مقدار زمانی از کامپیوتر است که برنامه برای اجرای کامل مصرف می‌کند.

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

تعداد تکرارعملیات اصلی الگوریتم محاسبه می‌شود و به صورت تابع f بیان می‌شود. سپس تابع g، که مرتبه بزرگی تابع f را وقتی اندازه

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

مختلف

با استفاده از نمادها O، Θ وΩ که در بخش بعدی با آنها آشنا می‌شویم، بیان می‌شود.


ارزیابی کارائی الگوریتم‌ها

موضوع:   | نویسنده: احسان رضایی | تاریخ: پنجشنبه سی ام اردیبهشت 1389 | و

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

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

آنالیز کارائی یک تخمین اولیه‌است با دو معیار:

•۱.پیچیدگی زمانی time complexity

•۲. پیچیدگی حافظه space complexity


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

بعد از پیاده سازی الگوریـتم با یک زبان برنامه نویسی، آمار حقیقی درباره زمان و حافظه مصرف شده توسط الگوریتم در حین اجرا جمع

آوری می‌شود.


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

موضوع:   | نویسنده: احسان رضایی | تاریخ: پنجشنبه سی ام اردیبهشت 1389 | و

الگوریتم یا خوارزمی (به انگلیسی: Algorithm) مجموعه‌ای متناهی از دستورالعمل‌ها است، که به ترتیب خاصی اجرا می‌شوند و مسئله‌ای را حل می‌کنند. به عبارت دیگر یک الگوریتم، روشی گام به گام برای حل مسئله است. شیوه محاسبه معدل در مدرسه، یکی از نمونه‌های الگوریتم است.

منشاء واژهٔ الگوریتم: واژهٔ الگوریتم از نام دانشمند ایرانی، محمد ابن موسی خوارزمی، گرفته شده است. کتاب معروف الجبر و المقابله خوارزمی که حاوی دستورالعمل‌های مختلف برای حل مسائل محاسباتی است، از راه ترجمه به زبان اسپانیایی در اروپا شناخته شد و نام عربی او، الخوارزمی، (از طریق آوانگاری آن در زبان اسپانیایی و سپس ورود آن به دیگر زبان‌های اروپایی) مترادف شد با «دستورهای حل مسائل».

نقش الگوریتم‌ها در علوم رایانه: در علوم رایانه، یک الگوریتم را یک روال محاسباتی خوش‌تعریف می‌دانند، که مقدار یا مجموعه‌ای از مقادیر را به عنوان ورودی (Input) دریافت کرده و پس از طی چند گام محاسباتی، ورودی را به خروجی (Output) تبدیل می‌کند. بجز این، الگوریتم را ابزاری برای حل مسائل محاسباتی نیز تعریف کرده‌اند. ساخت و طراحی الگوریتم مناسب در مرکز فعالیت‌های برنامه‌سازی رایانه قرار دارد. یک برنامه رایانه‌ای، بیان یک یا چند الگوریتم با یک زبان برنامه‌نویسی است.

مفهوم الگوریتم:

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

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

اگر الگوریتم برای عمل مورد نظر مناسب نباشد و یا غلط باشد به نتیجه مورد نظر نمی‌رسیم. مثلاً اگر الگوریتم آبگوشت را با مواد اولیه کباب انجام دهیم واضح است که به آبگوشت نمی‌رسیم.

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


عناوین آخرین مطالب ارسالی

اخرین دست نوشته های وبلاگ



***