پاورپوینت کامل درس طراحی الگوریتم ها (روش تقسیم و حل) ۴۸ اسلاید در PowerPoint

توجه : این فایل به صورت فایل power point (پاور پوینت) ارائه میگردد

 پاورپوینت کامل درس طراحی الگوریتم ها (روش تقسیم و حل) ۴۸ اسلاید در PowerPoint دارای ۴۸ اسلاید می باشد و دارای تنظیمات کامل در PowerPoint می باشد و آماده ارائه یا چاپ است

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

لطفا نگران مطالب داخل پاورپوینت نباشید، مطالب داخل اسلاید ها بسیار ساده و قابل درک برای شما می باشد، ما عالی بودن این فایل رو تضمین می کنیم.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل می باشد و در فایل اصلی پاورپوینت کامل درس طراحی الگوریتم ها (روش تقسیم و حل) ۴۸ اسلاید در PowerPoint،به هیچ وجه بهم ریختگی وجود ندارد

بخشی از مطالب داخلی اسلاید ها

پاورپوینت کامل درس طراحی الگوریتم ها (روش تقسیم و حل) ۴۸ اسلاید در PowerPoint

اسلاید ۴: هنگام پی ریزی یک الگوریتم بازگشتی ، باید:۱- راهی برای به دست آوردن حل یک نمونه از روی حل یک نمونه ازروی حل یک یا چند نمونه کوچک تر طراحی کنیم.۲- شرط(شرایط ) نهایی نزدیک شدن به نمونه(های) کوچک تر را تعیین کنیم.۳- حل را در حالت شرط (شرایط)نهایی تعیین کنیم.

اسلاید ۵: الگوریتم۱-۲: جست و جوی دودویی (بازگشتی) index location ( index low, index high ){ index mid; if (low > high ) return 0; else { mid = (low + high) /2; if (x = = S [mid]) return mid; else if ( x < S [mid]) return location (low , mid – ۱); else return location (mid + 1, high); } } فراخوانی اولیه: location(1, n)

اسلاید ۶: تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم جست و جوی دودویی بازگشتی عمل اصلی: مقایسه x با S [mid]. اندازه ورودی: n ، تعداد عناصر آرایه.W (n) = W (n / 2) + 1 برای n >1 ، n توانی از ۲ است W (n) = W (n / 2) + 1 W (1) = 1 W (n) = lg n + 1 (lg n)

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

اسلاید ۸: مرتب سازی ادغامی شامل مراحل زیر می شود:۱- تقسیم آرایه به دو زیر آرایه، هر یک با n/2 عنصر.۲- حل هر زیر آرایه با مرتب سازی آن.۳- ترکیب حل های زیر آرایه ها از طریق ادغام آن ها در یک آرایه مرتب.

اسلاید ۹: مراحل انجام شده توسط انسان در هنگام مرتب سازی ادغامی

اسلاید ۱۰: الگوریتم۲-۲: مرتب سازی ادغامی void mergsort (int n , keytype S [ ]) { const int h = n/2 , m = n – h; keytype U [1…h],V [1..m]; if (n >1) { copy S[1] through S[h] to U[h]; copy S [h + 1] through S[h] to V[1] through V[m]; mergesort(h, U); mergesort(m,V); merge (h , m , U,V,S); } }

اسلاید ۱۱: الگوریتم۳-۲: ادغام void merg ( int h , int m, const keytype U[ ], const keytype V[ ], keytype S[ ] ) { index i , j , k; i = 1; j = 1 ; k = 1; while (i <= h && j <= m) { if (U [i] < V [j]) { S [k] = U [i] i+ + ;

اسلاید ۱۲: } else { S [k] = V [j]; j+ +; } k+ +; } if ( i > h) copy V [j] through V [m] to S [k] through S [ h + m ] else copy U [i] through U [h] to S [k] through S [ h + m ] }

اسلاید ۱۳: تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم ۳-۲(ادغام) عمل اصلی: مقایسهU [i] با . V[j] اندازه ورودی:h وm ،تعداد عناصر موجود در هر یک از دو آرایه ورودی.W ( h , m) = h + m – 1

اسلاید ۱۴: تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم ۲-۲( مرتب سازی ادغامی)عمل اصلی: مقایسه ای که درادغام صورت می پذیرد. اندازه ورودی: n ، تعداد عناصر آرایه S. W (n) = W (h) + W ( m) + h + m – ۱ زمان لازم برای ادغام زمان لازم برای مرتب سازی V زمان لازم برای مرتب سازی U برای n >1 که n توانی از ۲ است W (n) = 2 W( n / 2) + n -1 W (1) = 0W( n ) ( n lg n)

اسلاید ۱۵: مرتب سازی درجا: روشی که از فضایی بیشتر از آنچه مورد نیاز ورودی است استفاده نمی کند.الگوریتم گفته شده درجا نیست زیرا از آرایه U و V به همرا آرایه ورودی S استفاده می کند.میزان حافظه اضافی:n +n/2 +n/4+ …2nکاهش مقدار حافظه اضافی به n ؟

اسلاید ۱۶: الگوریتم۴-۲: مرتب سازی ادغامی ۲(mergesort 2 )void mergesort2 (index low, index high) { index mid; if (low < high) { mid = ( low + high) / 2 ; mergesort 2 (low, mid); mergesort 2 (mid +1, high); merge2(low,mid,high) } }

اسلاید ۱۷: الگوریتم۵-۲:ادغام۲ مسئله: ادغام دو آرایه ی مرتب S که درmergesort ایجاد شده اند. void mrge2 (index low, index mid, index high) { index i, j , k; keytype U [ low..high] i = low; j = mid +1 ; k = low; while ( i <= mid && j <= hig