پاورپوینت Algurithm Design

بخشی از پاورپوینت

اسلاید 1 :

Algurithm Design

اسلاید 2 :

مباحث پایان ترم طراحی الگوریتم
روش برنامه نویسی پویا
روش عقبگرد
روش انشعاب و تحدید
قسمتی از گراف

اسلاید 3 :

روش برنامه نویسی پویا Dynamic Programming
مباحث پایان ترم طراحی الگوریتم

اسلاید 4 :

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

اسلاید 5 :

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

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

اسلاید 6 :

روش برنامه نویسی پویا
گام اول : ایجاد یک ساختار آرایه ای جهت ذخیره سازی
گام دوم : پر کردن بخشی از آرایه با کمک اطلاعات داده شده در صورت سوال
گام سوم : پیدا کردن یک روش بازگشتی (که از خانه های آرایه ای که قبلا پرشده استفاده کند.)
گام آخر : خلاقیت!

اسلاید 7 :

برنامه نویسی پویا :
مسئله فیبوناچی
So starting from
x(0) = 0
x(1) = 1
the series progresses infinitely as: 0,1,1,2,3,5,8,13.

Problem : finding the nth Fibonacci number?
مقادیر اولیه به صورت مقابل هستند:

نمونه دنباله آن بصورت روبرو :

هدف : پیداکردن n امین جمله.

اسلاید 8 :

برنامه نویسی پویا :
مسئله فیبوناچی
Fib(n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
else
return Fib(n-1) + Fib(n-2);
}
int fib(int n)
{
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
{
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
Time Complexity: O(n)Extra Space: O(n)
Solution 1
D and C
Devide and Conquer
Dynamic Programming

اسلاید 9 :

برنامه نویسی پویا :
مسئله فیبوناچی
Fib(n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
else
return Fib(n-1) + Fib(n-2);
}
B[n] ={0,1-1,-1,-1, ….}
DyFib(n) {
if (B[n] >= 0)
return B[n];
else {
B[n]=DyFib (n-1) + DyFib (n-2);
return B[n];
}
}
Solution 2
D and C
Dynamic Programming
Devide and Conquer

اسلاید 10 :

برنامه نویسی پویا :
مسئله برش چوب
فرض کنید صاحب یک کارگاه نجاری هستید
یک الوار چوبی به طول n در کارگاه دارید
مشتری های متفاوتی برای خرید قطعات کوچک با اندازه های متفاوت هست.
اما قیمت قطعات کوچک بر اساس تقاضای بازار باتوجه به قطعه فرق میکند!
فرض تمام طول قطعات اعداد صحیح هستند
چون ما هرجای چوب را میتوانیم ببریم یا نبریم => 2n-1 حالت برای برش پدید می آید
قیمت قطعات در آرایه P[1…n] هست..
منظور از p[i] این است که : قطعه چوب به طول i قیمتش به اندازه مقدار p[i] است!

هدف : برش این الوار بگونه ای که در نهایت بیشترین سود حاصل شود

اسلاید 11 :

برنامه نویسی پویا :
مسئله برش چوب
اگر فرض کنید طول چوب فعلی ما ۴ است.
در نتیجه ما 2n-1 = 23 = 8 راه برای برش داریم!

اسلاید 12 :

برنامه نویسی پویا :
مسئله برش چوب

اسلاید 13 :

برنامه نویسی پویا :
مسئله برش چوب
CUT-ROD(p,n)
if n==0
return 0
q = -∞
for i=1 to n
q=max{q,p[i]+CUT-ROAD(p,n-i)}
return q

اسلاید 14 :

برنامه نویسی پویا :
مسئله برش چوب
DP-CUT-ROD(p,n)
let r[0..n], s[0..n] be new arrays
r[0]=0
for j=1 to n
q=-∞
for i=1 to j
if q < p[i]+r[j-i]
s[j]=i;
q= p[i]+r[j-i]
r[j]=q
return r and s

اسلاید 15 :

برنامه نویسی پویا :
ضریب چند جمله ای

اسلاید 16 :

برنامه نویسی پویا :
ضریب چند جمله ای
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
// Base Cases
if (k==0 || k==n)
return 1;

// Recur
return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}

اسلاید 17 :

برنامه نویسی پویا :
ضریب چند جمله ای
int binomialCoeff(int n, int k) // Returns value of Binomial Coefficient C(n, k)
{
int C[n+1][k+1];
int i, j;
for (i = 0; i <= n; i++) // Caculate value of Binomial Coefficient in bottom up manner
{
for (j = 0; j <= min(i, k); j++) //why use minimum? => for fill bottom triangle!
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;

// Calculate value using previosly stored values
else
C[i][j] = C[i-1][j-1] + C[i-1][j]; //use khayam pascal triangle method!
}
}

return C[n][k];
}

اسلاید 18 :

برنامه نویسی پویا :
مسئله خردکردن پول

اسلاید 19 :

برنامه نویسی پویا :
مسئله یافتن کوتاهترین مسیر بین جفت رئوس (الگوریتم فلوید)
void floyd ( int n,const number W [][], number D [][])
{
index i , j , k ;
D = W ;
for ( k = 1 ; k ≤ n ; k ++)
for ( i = 1; i ≤ n ; i++)
for ( j = 1 ; j ≤ n ; j ++)
D [i] [j] = minimum ( D [i][j], D[i][k] + D[k][j]);
}

اسلاید 20 :

برنامه نویسی پویا :
مسئله یافتن کوتاهترین مسیر بین جفت رئوس (الگوریتم فلوید)
void floyd2 ( int n, const number W [][], number D [][], index P [][])
{
index i , j , k ;
for ( i = 1 ; i ≤ n ; i ++)
for ( j = 1 ; j ≤ n ; j++)
P [i] [j] = 0;
D = W;
for ( k = 1 ; k <= n ; k ++)
for ( i = 1 ; i <= n ; i ++)
for ( j = 1 ; j <= n ; j ++)
if ( D [i] [k] + D [k] [j] < D [i] [j] ) {
P [i] [j] = k;
D [i] [j] = D [i] [k] + D [k] [j];
}
}