Skip to main content

جزوه طراحی الگوریتم
جزوه طراحی الگوریتم ؛ در قالب PDF و 172 صفحه کامل.

  • فصل اول : مرتبه الگوریتم ها و تحلیل الگوریتم هاي بازگشتی
  • مجموعه تست
  • پاسخ تشریحی
  • فصل دوم : روش تقسیم و حل
  • مجموعه تست
  • پاسخ تشریحی
  • فصل سوم : برنامه نویسی پویا
  • مجموعه تست
  • پاسخ تشریحی
  • فصل چهارم : روش حریصانه
  • مجموعه تست
  • پاسخ تشریحی
  • فصل پنجم : روش عقبگرد
  • مجموعه تست
  • پاسخ تشریحی
  • فصل ششم: پیچیدگی محاسباتی (مرتب سازي و جست و جو)
  • مجموعه تست
  • پاسخ تشریحی
  • فصل هفتم: نظریه
  • مجموعه تست
  • پاسخ تشریحی

 

» بخشی از متن:

فصل اول : مرتبه الگوریتم ها و تحلیل الگوریتم هاي بازگشتی

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

الگوریتم جست و جوي ترتیبی را برگرداند و (p) کلید قرار دارد؟ اگر در آرایه وجود داشت، موقعیت آن n با S[1..n] در آرایه x می خواهیم ببینیم که آیا کلید را با عناصر آرایه از ابتدا به سمت انتها مقایسه می کنیم. اگر به عنصر x اگر وجود نداشت، صفر برگرداند. در این جستجو، عنصردر آن قرار داشت را بر می گردانیم. اگر جستجو تا انتهاي آرایه انجام x مورد نظر برسیم، از حلقه خارج شده و شماره خانه آرایه که پیدا نشود، در این حالت متغیر حلقه از تعداد عناصر آرایه بیشتر شده است و صفر را بر می گردانیم.x شود و

int seqsearch (int n, const keytype S[ ], keytype x){

index p = 1;

while (p <= n && S[p] != x)

p++;

if (p > n) p=0;

return p;

}

براي متغیر صحیحی است که به عنوان اندیسبه کار میرود. index تذکر: نوع داده معرفی میکنیم. const تذکر : اگر نخواهیم روالی مقادیر را از طریق آرایه برگرداند، آن آرایه را با واژه الگوریتم جست و جوي دودوییرا با عنصر میانی آرایه مقایسه میکند. اگر مساوي بود، الگوریتم به پایان می- x ، هستیم، الگوریتم ابتدا x با فرض این که به دنبال کوچکتر از عنصر میانی بود، باید در نیمه نخست آرایه باشد (اگر وجود داشته باشد) و الگوریتم جست و جو در نیمه x رسد. اگربا عنصر میانی نیمه اول آرایه مقایسه میشود. اگر مساوي بود، الگوریتم به پایان میرسد و الی x نخست آرایه تکرار میگردد (یعنی x بزرگتر از عنصر میانی آرایه بود، جست و جو در نیمه دوم آرایه تکرار میشد. این رویه چندین بار تکرار میگردد تا x آخر). اگردر آرایه وجود ندارد. x پیدا شود یا معلوم گردد که

مثال: براي پیدا کردن عدد 9 در آرایه مرتب زیر با روش جستجوي دودویی، به چند مقایسه نیاز است؟

1 2 3 4 5 6 7 8 9

5 9 12 20 35 50 82 88 97

 

» تست کارشناسی ارشد

1 -کدام گزینه نادرست است؟ (علوم کامپیوتر – دولتی )

1) تمام مسائل P به وسیله یک الگوریتم غیر قطعی در زمان چند جمله اي حل می شوند.

2) تمام مسائل NP به وسیله یک الگوریتم غیر قطعی در زمان چند جمله اي حل می شوند.

3) تمام مسائل NP-hard به وسیله یک الگوریتم غیر قطعی در زمان چند جمله اي حل می شوند.

4) تمام مسائل NP-Complete به وسیله یک الگوریتم غیر قطعی در زمان چند جمله اي حل می شوند.

 

لینک دانلود