X
تبلیغات
آموزش کامپیوتر - طراحی و تحلیل الگوریتم

آموزش کامپیوتر

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

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

 

برنامه نویسی به روش تقسیم و حل:

در برنامه نویسی به روش تقسیم و حل (divide and conqure) مسأله مفروض به قسمت های کوچک تقسیم می شود. در صورتی که این قسمت های کوچک قابل تجزیه شدن نباشند پاسخ آنها با هم ترکیب می شود، و در نهایت جواب مسأله از ترکیب پاسخ مراحل مختلف به دست می آید. تقسیم و حل در برخورد با محاسبات تکراری بارها آنها را انجام می دهد. در واقع می توان گفت تقسیم و حل برای پاسخ دهی به مسأله درخت ترسیم می کند. برنامه نویسی به روش تقسیم و حل برای مسأله هایی که نیاز به محاسبات تکراری دارند مناسب نیست. برای این سری از مسأله ها روش برنامه نویسی پویا توصیه می شود.

 

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

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

 

در ادامه با ارائه مثالی به بررسی اجمالی این دو روش می پردازیم: برنامه محاسبه ضرایب بسط دو جمله ای نیوتن.

اگر عبارت زیر را داشته باشیم محاسبه ضریب جمله سوم وقتی توان 2 است به راحتی قابل مشاهده و محاسبه است:

 

(a + b)² = a² + 2ab + b²

 

اما اگر توان عبارت بالا n باشد، و n را عددی مانند 10 فرض کنیم، بدست آوردن ضریب جمله jام کار مشکلی خواهد بود. همانطور که می دانید ضریب جمله jام بسط نیوتن برابر است با:

 

C(n , j) = n! / ( j! (n - j)! )

 

پس از دیدگاه ریاضی هدف ما بدست آوردن مقدار ترکیب j روی n است. اما برای اینکار از ضابطه فوق استفاده نمی کنیم، بلکه از رابطه بازگشتی زیر بهره می بریم:

 

C(n , r) = C(n - 1 , r) + C(n - 1 , r - 1)

 

با این شرط که

اگر r = 0 یا r = n آنگاه C(n , r) = 1

 

برای این محاسبه از تابع C با دو ورودی استفاده می کنیم. ورودی اول مقدار n و ورودی دوم مقدار r.

 

به روش تقسیم و حل:

int C( int n , int r )

{

 if ( r == 0 || r == n )

  return 1 ;

 else

  return C( n - 1 , r - 1 ) + C( n - 1 , r ) ;

}

 

با یک محاسبه ساده مشخص می شود که مرتبه (order) به روش این روش (تقسیم و حل) از جنس فاکتوریل است!!!

 

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

int C( int n , int r )

{

 int arr[10][10] , i , j ;

 for ( i = 0 ; i <= n ; i++ )

  for ( j = 0 ; j <= min( i , r ) ; j++)

   if ( j == 0 || j == i )

    arr[i][j] = 1 ;

   else

    arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j] ;

 return arr[n][r] ;

}

در این قطعه کد تابع فرعی min کوچکترین مقدار در بین ورودی های خود را بازمی گرداند، که می تواند به صورت زیر پیاده سازی شود:

 

int min ( int a , int b )

{

 return ( a < b ? a : b ) ;

}

 

با استفاده از این روش مرتبه از جنس فاکتوریل خارج شده و به فرم n*k در می آید! اما . . .

در برنامه ضریب دوجمله ای به روش برنامه نویسی پویا همواره یک ماتریس 10 در 10 در حافظه مقیم است. در این حالت مرتبه زمانی نسبت به روش تقسیم و حل بهبود پیدا کرده، اما باید فکری به حال مرتبه مکانی هم کرد. در واقع حافظه زیادی در روش ارائه شده بی مصرف باقی می ماند. علاوه بر این تنها قادر به محاسبات برای حداکثر n = 10 هستیم. پیشنهاد شما برای رفع این مشکل چیست؟

+ نوشته شده در  هفدهم آذر 1386ساعت 18:12  توسط طاهر  | 

مرتب سازی سریع - ارائه شده توسط ابوذر میرزایی

مرتب سازی سریع (Quick Sort) از جمله روشهای محبوب و با سرعت بالا برای مرتب کردن داده ها محسوب می شه. این روش هم مثل روش ادغام از تقسیم و حل (Divide and Conqure) برای مرتب کردن داده ها استفاده می کنه. به این ترتیب که داده ها رو به دو قسمت مجزا تقسیم، و با مرتب کردن اونها کل داده ها رو مرتب می کنه. برای اینکار یکی از داده ها (مثلا داده اول) به عنوان محور انتخاب می شه. داده ها بر اساس محور طوری چینش می شن که همه داده های کوچکتر از محور سمت چپ و داده های بزرگتر یا مساوی اون سمت راستش قرار می گیرن. با مرتب کردن دو قسمت به دست اومده کل داده ها مرتب می شن. در این حالت مثل روش ادغام نیازی به ادغام کردن داده ها نیست. چرا که قسمت سمت راست همگی از قسمت سمت چپ کوچکتر هستن و بالعکس. مثلا اعداد صحیح زیر رو در نظر بگیرید:


5  6  1  9  -2  4  5  15  3  1  4  10


عدد 5 رو به عنوان محور در نظر می گیریم. داده ها به این صورت بازچینی می شن:


1  -2  4  3  1  4  5  6  9  5  15  10


همونطور که مشاهده می کنید اعداد سمت چپ عدد 5 زیر خط دار همگی از ۵ کوچیکتر و  اعداد سمت راست بزرگتر یا مساوی اون هستن.

تابع partition با دریافت آرایه و حد بالا و پایین تکه ای که باید تقسیم بشه عملیات لازم رو انجام می ده، و اندیس محل تفکیک رو (محل عدد ۵ در مثال بالا) به عنوان نتیجه بر می گردونه.

 

int partition ( int arr[ ] , int low , int high )

{

 int lb = low + 1 , rb = high , temp , pivot = arr[ low ] , p ;

 while ( lb <= rb )

 {

  while ( arr[ lb ] <= pivot && lb <= rb )

   lb ++ ;

  while ( arr[ rb ] > pivot && lb <= rb )

   rb -- ;

  if ( lb < rb )

  {

   temp = arr[ lb ] ;

   arr[ lb ] = arr[ rb ] ;

   arr[ rb ] = temp ;

  }

 }

 if ( rb == high )

  p = high ;

 else if( rb == low )

  p = low ;

 else

  p = lb - 1 ;

 arr[ low ] = arr[ p ] ;

 arr[ p ] = pivot ;

 return p ;

}

 

اگه این تابع رو برای مثال بالا استفاده کنیم مقدار ۶ (اندیس ۵ زیرخط دار) برگشت داده می شه. با تکرار کردن این عملیات برای دو قسمت به دست اومده (در مثال بالا از اندیس صفر تا ۵ و از اندیس ۷ تا ۱۱) داده ها به صورت کامل مرتب می شن.

بر اساس گفته های بالا تابع مرتب سازی به این صورت خواهد بود:

 

void quick_sort ( int arr[ ] , int low , int high )

{

 if ( low < high )

 {

  int p = partition( arr , low , high ) ;

  quick_sort( arr , low , p - 1 ) ;

  quick_sort( arr , p + 1 , high ) ;

 }

}

 

همونطور که مشاهده می کنید این تابع بصورت بازگشتی نوشته شده. در صورتی که بخواید به صورت غیر بازگشتی بنویسید باید از پشته به صورت زیر استفاده کنید:

 

void quick_sort ( int arr[ ] ,int n )

{

 stack st ;

 st.push( 0 ) ;

 st.push( n - 1 ) ;

 int low , p , high ;

 while( ! st.isempty( ) )

 {

  high = st.pop( ) ;

  low = st.pop( ) ;

  p = partition( arr , low , high ) ;

  if ( p > low )

  {

   st.push( low ) ;

   st.push( p - 1 ) ;

  }

  if ( p < high )

  {

   st.push( p + 1 ) ;

   st.push( high ) ;

  }

 }

}

 

در این جالت نیازی به ارسال حد بالا و پایین آرایه به تابع نیست. به جای اون تعداد داده ها به تابع ارسال می شه.

تابع quick_sort دادهای مثال بالا رو به این ترتیب مرتب می کنه:

5  6  1  9  -2  4  5  15  3  1  4  10

1  -2  4  3  1  4  5  6  9  5  15  10

-2  1  4  3  1  4  5  5  6  9  15  10

-2  1  3  1  4  4  5  5  6  9  15  10

-2  1  1  3  4  4  5  5  6  9  10  15

-2  1  1  3  4  4  5  5  6  9  10  15

انتخاب عنصر محور نقش مهمی رو در سرعت مرتب سازی ایفا می کنه. داده های زیر رو در نظر بگیرید:

5 4 3 2 1

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

+ نوشته شده در  هفدهم آذر 1386ساعت 18:7  توسط طاهر  | 

مرتب سازی انتخابی

معمولا اطلاعات و داده های خامی که در اختیار برنامه نویس قرار داره بصورت نامرتب هستن. مواقعی پیش می یاد که لازمه این داده ها بر حسب فیلد خاصی مرتب بشن؛ مثل لیست دانش آموزان بر حسب معدل ، لیست کارمندان بر حسب شماره پرسنلی ، لیست دفترچه تلفن بر حسب نام خانوادگی و ... روشهای متعددی برای مرتب سازی وجود داره که من قصد دارم تا حد امکان شما رو با این روشها آشنا کنم. برای شروع روش مرتب سازی انتخابی (Selection Sort) رو توضیح می دم.

روش انتخابی اولین روشیه که به ذهن می رسه: بزرگترین رکورد بین رکوردهای لیست رو پیدا می کنیم و به انتهای لیست انتقال می دیم. از بقیه رکوردها بزرگترین رو انتخاب می کنیم و انتهای لیست - کنار رکورد قبلی - قرار می دیم و ... مثلا:

 

0:  9 1 6 4 7 3 5

1:  5 1 6 4 7 3 9

2:  5 1 6 4 3 7 9

3:  5 1 3 4 6 7 9

4:  4 1 3 5 6 7 9

5:  3 1 4 5 6 7 9

6:  1 3 4 5 6 7 9

 

برای مرتب سازی آرایه ای از اعداد صحیح با این روش از کد پایین استفاده می شه:

 

void selection_sort ( int arr[] , int n )

{

  register int i , j ;

  int max , temp ;

  for ( i = n - 1 ; i > 0 ; i -- )

  {

    max = 0 ;

    for ( j = 1 ; j <= i ; j ++ )

      if ( arr[ max ] < arr[ j ] )

        max = j ;

    temp = arr[ i ] ;

    arr[ i ] = arr[ max ] ;

    arr[ max ] = temp ;

  }

}

 

procedure selection_sort ( var arr : array of integer ) ;

var

    i , j , max , temp : integer ;

begin

    for i := High ( arr ) downto  1 do

    begin

        max := 0 ;

        for j :=  1 to i do

            if arr[ max ] < arr [ j ] then

                max := j ;

        temp := arr[ i ] ;

        arr[ i ] := arr[ max ] ;

        arr[ max ] := temp ;

    end ;

end ;

 

اگه تعداد رکوردها برابر n باشه ، n - 1 مرحله لازمه تا تمام داده ها مرتب بشن. مرحله اول n - 1 مقایسه ، مرحله دوم n - 2 مقایسه ، ... و مرحله آخر 1 مقایسه انجام می گیره. پس روی هم رفته برای مرتب کردن n رکورد به n ( n - 1 ) / 2 مقایسه نیاز داریم ، که نشون می ده این روش چندان مناسب نیست.

اولین عیب این روش ثابت بودن تعداد مقایسه ها بدون در نظر گرفتن شیوه چینش رکوردهاست. مثلا حالتی که رکوردها به طور کاملا معکوس باشن (یعنی رکورد اول بزرگترین رکورد و لیست نزولی باشه) با حالتی که لیست کاملا مرتب باشه هیچ تفاوتی نداره ، و همیشه n ( n - 1 ) / 2 مقایسه باید انجام بگیره!!!

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

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

+ نوشته شده در  هفدهم آذر 1386ساعت 8:40  توسط طاهر  | 

بازگشتی یا غیر بازگشتی؟

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

مثال اول: دنباله فیبوناتچی

اکثر شما با دنباله فیبوناتچی آشنا هستین. این دنباله به صورت زیر تعریف می شه:

F( n ) = F( n - 1 ) + F( n - 2 )               n > 2              ,                  F( 1 ) = F( 2 ) = 1

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

unsigned fibo (unsigned n)

{

   if ( n == 1 || n == 2 )

      return 1 ;

   return fibo ( n - 1 ) + fibo ( n - 2 ) ;

}

اما آیا این روش بهترین راه حل رو ارائه می ده؟

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

#include

long double count = 0 ;

unsigned fibo (unsigned n)

{

  count ++ ;

  if ( n == 1 || n == 2 )

     return 1 ;

  return ( fibo ( n - 1 ) + fibo ( n - 2 ) ) ;

}

 void main ( )

{

  unsigned n ;

  cout << "Enter n :" ;

  cin >> n ;

  cout << "F(" << n << ") = " << fibo(n) << endl ;

  cout << "count = " << count ;

  getch ( ) ;

}

متغیر عمومی count تعداد بارهایی رو که تابع fibo فراخوانی می شه ، نگه می داره. برنامه رو اجرا کنید و مقدار n رو 40 بدید. خروجی باید چیزی شبیه عبارات زیر باشه:

Enter n : 40

F(40) = 32459

count = 2.046683e+08

یعنی جمله 40 ام دنباله فیبوناتچی 32459 هستش که برای محاسبه اون تابع fibo حدود 204 میلیون بار فراخوانی شده!!! حالا اگه هوس کنید مقدار n رو عدد نه چندان بزرگی مثل 1000 بدید ، کامپیوتر به احتمال قوی قفل می کنه. چرا که حدود 8.693312e+۲۰۸ (تقریبا یه 9 با 208 تا صفر جلوش) بار باید تابع fibo فراخوانی بشه. در ضمن این رو هم در نظر بگیرید که هر بار فراخوانی تو در توی بازگشتی یه تابع ، مقادیری رو به پشته اضافه می کنه. بنابراین حافظه مصرفی این روش فوق العاده بالاست. در کل تعداد فراخوانیهای تو در توی تابع fibo برای محاسبه جمله n ام دنباله فیبوناتچی از رابطه زیر محاسبه می شه:

تعداد فراخوانیهای فیبوناتچی

از همه این بحث ها می شه نتیجه گرفت که این روش چندان مناسب نیست. اما آیا روش دیگه ای هم وجود داره؟ بله ، وجود داره : روش غبر بازگشتی. به تعریف جدید تابع fibo توجه کنید:

unsigned fibo ( unsigned n )

{

  unsigned t1 = 1 , t2 = 1 , t3 = 1 ;

  register int i ;

  for ( i = 3 ; i <= n ; i ++ )

  {

    t3 = t2 + t1 ;

    t1 = t2 ;

    t2 = t3 ;

   }

   return t3 ;

}

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

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

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

مثال دوم: پیمایش درخت دودویی

عزیزانی که با مبحث ساختمان داده ها و بالاخص درختهای دودویی سر و کار داشتن یا دارن ، تعریف بازگشتی پیمایشهای مختلف یه درخت دودویی رو می دونن. این تعاریف رو به صورت غیر بازگشتی هم می شه پیاده سازی کرد. اما بسته به اینکه درخت دودویی چطور گسترش پیدا کرده باشه ، بهینگی روشها عوض می شه. همونطور که اطلاع دارید اگر یه درختی شامل n داده باشه ، شماره آخرین سطحش حداکثر برابر n - 1 و حداقل جزء صحیح لگاریتم مبنای دوی n خواهد بود. یعنی مثلا اگه 10000 تا داده داشته باشیم ، ممکنه بین 14 الی 10000 سطح توی درختمون موجود باشه (هرچقدر درخت متقارنتر باشه ، تعداد سطوح می یاد پایین). حالا اگه قرار باشه همچین درختی رو با روش بازگشتی پیمایش کنیم ، سقف تعداد فراخوانیهای تودرتوی تابع ، عددی بین 14 تا 10000 خواهد بود. پس هرچقدر درخت متقارنتر باشه ، روش بازگشتی صرفه بیشتری داره (توجه داشته باشید که تعداد فراخوانیهای تو در تو خیلی خیلی مهمتر از تعداد کل فراخوانیهاست. چون فراخوانیهای تودرتو هستن که باعث بالارفتن حافظه مصرفی می شن). دقیقا به همین خاطر و البته بعضی مسایل دیگه ، درختهای قرمز - مشکی ابداع شدن ، تا درخت رو تا حد امکان متقارن بکنن.

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

+ نوشته شده در  هفدهم آذر 1386ساعت 8:16  توسط طاهر  | 

مقایسه روشهای محاسبه دترمینان

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

برنامه های مربوط به این دو روش رو - که با زبان ++C نوشته شده - می تونید ازاینجادانلود کنید. فایل det1.cpp برای روش بسط لاپلاس ( یا همون تعریف دبیرستانی دترمینان ) و فایل det2.cpp برای روش گاوس - جردن نوشته شده. هر دوی این برنامه ها ماتریس رو از فایل matrix.txt می خونن. سطر اول این فایل رو عدد n و سطرهای بعدی رو سطرهای ماتریس تشکیل می دن. اگه این برنامه ها رو با ماتریس از مرتبه 4 یا 5 امتحان کنید ، تفاوت زیادی احساس نمی کنید. اما اگه n برابر 10 باشه تفاوت محسوس می شه.

قبلا ثابت کردم که برای محاسبه دترمینان یه ماتریس مرتبه 20 به روش بسط لاپلاس ، تابع دترمینان باید حدود 1.7 میلیارد میلیارد بار خودش رو فراخوانی کنه! اگه برنامه مربوط به این بسط رو با ماتریس مرتبه 20 امتحان کنید با اتفاق عجیبی روبرو می شید. تقریبا می تونید مطمئن باشید که عمر شما کفاف گرفتن جواب رو نمی ده. محاسبه دترمینان ماتریس مرتبه 20 به روش بسط لاپلاس حداقل 670 میلیارد برابر ماتریس مرتبه 10 وقت می بره. پس اگه کامپیوتر شما دترمینان ماتریس مرتبه 10 رو در یک ثانیه حساب کنه ، حدود 22 هزار سال طول می کشه تا دترمینان ماتریس مرتبه 20 رو محاسبه کنه!!! مگر اینکه از ابر کامپیوتر استفاده کنید.

اما روش گاوس - جردن چطور؟ این روش چقدر وقت می بره؟ این روش نه تنها دترمینان ماتریس مرتبه 20 که حتی دترمینان ماتریس مرتبه 100 رو در کمتر از یک ثانیه محاسبه می کنه! به همین دلیل محبوبیت وحشتناکی داره! البته همونطور که قبلا هم اشاره کردم روش سومی هم وجود داره ، که به هیچ وجه به پای روش گاوس - جردن نمی رسه ، اما به مراتب بهتر از روش بسط لاپلاس نتیجه می ده.

+ نوشته شده در  پانزدهم آذر 1386ساعت 8:23  توسط طاهر  | 

روشهای محاسبه دترمینان

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

دترمینان ماتریس

یا

دترمینان ماتریس

که دترمینان ماتریس مربعی مرتبه n رو به دترمینان n تا ماتریس از مرتبه n - 1 تبدیل می کنه و البته برای مرتبه 2 داریم:

دترمینان 2 در 2

حالا فرض کنید تابعی نوشتیم که دترمینان یک ماتریس مربعی مرتبه n رو به روش خودفراخوانی (بازگشتی) محاسبه می کنه. فکر می کنید اگه n=20 باشه ، این تابع چند بار باید خودش را فرابخونه تا بتونه دترمینان رو حساب کنه؟ مرحله توقف تابع بازگشتی رو هم n = 2 در نظر بگیرید یعنی برای n = 2 تابع مستقیما دترمینان رو محاسبه می کنه.

فکر می کنید این عدد چقدر بزرگ باشه؟ حساب می کنیم:

فرض کنیم ( T( n تعداد فراخوانیها برای حساب کردن دترمینان ماتریس مرتبه n باشه. واضحه که T ( 2 ) = 1 ، و همینطور:

T( 3 ) = 3 T( 2 ) + 1 = 4

T( 4 ) = 4 T( 3 ) + 1 = 17

برای حساب کردن دترمینان ماتریس 3 در 3 یه بار تابع رو با n = 3 فراخوانی می کنیم . اون هم خودش سه بار تابع رو برای n = 2 فراخوانی می کنه. پس رو هم 4 بار تابع فراخوانی می شه و ...

با یه حساب سر انگشتی می تونید به این نتیجه برسید که اگه n به اندازه کافی بزرگ باشه (مثلا n > 10) می شه گفت:

T( n ) = n! ( e - 2 )

(e عدد نپر و !n برای فاکتوریل n)

یعنی مثلا برای n = 20 تابع باید بیشتر از 1.7 میلیارد میلیارد بار (یه 17 با 17 تا صفر جلوش!!) خودش رو فراخوانی کنه تا بتونه دترمینان رو حساب کنه!!!!!! تازه اینها فقط تعداد فراخوانیها رو نشون میده. اینکه هر بار محاسبات تابع چقدر طول می کشه و چقدر حافظه نیاز هست بماند ، که اگه بخوایم اونها رو هم حساب کنیم عددمون سر به فلک می کشه!!!

خوب حالا فکر می کنید کامپیوتر چطور دستگاههای بزرگ معادلات رو حل می کنه؟ محض اطلاع اون عزیزانی که اطلاع ندارن بگم توی مباحثی مثل تحقیق در عملیات و برنامه ریزی خطی ممکنه یه دستگاه معادلات 100 مجهوله داشته باشیم که اگه قرار باشه از روش بالا برای پیدا کردن جواب استفاده کنیم چند هزار سال با قویترین کامپیوتر ها طول می کشه!

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

اما آیا روش دیگه ای وجود داره؟

اگه بخش ضمیمه کتاب «حساب دیفرانسیل و انتگرال و هندسه تحلیلی» نوشته «جرج بی. توماس و ...» رو که تو هر دانشگاه و کتابخونه ای پیدا می شه بخونید ، یه روش خیلی جالب برای محاسبه دترمینان ارائه شده که دترمینان ماتریس مرتبه n رو فقط به یه دترمینان از مرتبه n - 1 تبدیل می کنه. روش جدید به این شکله:

 

دترمینان به روش سوم

البته باید توجه کنید که تو هر مرحله درایه سطر و ستون اول باید غیر صفر باشه که اگه نبود می شه سطرها رو جابه جا کرد. اگه جابه جایی سطرها هم اثر نداشت به این معنی که یه ستون با درایه های صفر داریم. پس دترمینان صفر می شه.

حالا اگه ( T ( n رو واسه این روش حساب کنیم (خودتون زحمتش رو بکشین) به دست می یاد:

T( n ) = ( 2 n3- 3 n2 + 7 n -12 ) / 6

اگه n = 20 باشه: T( 20 ) = 14928 که نشون میده این روش نسبت به روش اول فوق العاده کاراتره (15هزار کجا و 1.7 میلیارد میلیارد کجا !!!!) در ضمن محاسباتش هم نسبت به روش اول خیلی خیلی کمتره. ولی به پای روش گاوس – جردن نمی رسه.

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

+ نوشته شده در  پانزدهم آذر 1386ساعت 8:21  توسط طاهر  | 

 


طراحی سایت و بهینه سازی سایت توسط : گروه طراحان نگاه تازه