تماس درباره   صفحه اصلی
  ساختمان داده > آرايه > ماتريس  
 
 

ماتريس


ماتريس ها معادل آرايه هاي دو بعدي هستند.

تعاريف ماتريس
عمليات روس ماتريس ها
ماتريس خلوت


تعاريف ماتريس

ماتريس ها معادل آرايه هاي دو بعدي هستند. A‌ يك ماتريس m×n است شامل m×n عدد قرار گرفته در m سطر و n‌ ستون به شكل:

A11 A12 … A1n
A21 A22 … A2n
………………
Am1 Am2 … Amn

يك ماتريس با تعداد سطر و ستون برابر را ماتريس مربعي (square matrix) مي نامند.

قطر اصلي يك ماتريس مربعي شامل عناصر A11,A22,…,Ann است. يعنی اگر i=j باشد Aij روی قطر اصلی است.

يك ماتريس پائين مثلثي (lower triangle matrix) ماتريس مربعي است كه عناصر بالای قطراصلی آن همگی صفر باشند. يعنی اگر i<j باشد Aij=0 است

در ماتريس بالا مثلثی (upper triangle matrix) کليه عناصر زير قطراصلی صفر هستند. يعنی اگر i>j باشد Aij=0 است

يك ماتريس قطري، ماتريس مربعي است كه عناصر غير صفر آن روي قطر اصلي قرار دارند.

ماتريس مربعي A را متقارن مي نامند اگر براي همه i و j ها A[j,i] =A[i,j].


عمليات روي ماتريس ها

جمع دو ماتريس

فرض كنيد A‌ و B‌ ماتريس‌هاي هم اندازه M×N باشد. حاصل جمع B+A در ماتريس C به ابعاد M×N ذخيره مي شود. الگوريتم جمع اين دو ماتريس به صورت زير است:

for (i := 1 to M)
   for (j:= 1 to N)
     C[i,j] := A[i,j]+B[i,j]
   end for
end for
end

پيچيدگي الگوريتم فوق O(m×n) است. اگر ماتريس‌ها مربعي باشند پيچيدگي الگوريتم O(n2) مي‌شود.

ضرب دو ماتريس

فرض كنيد A‌ يك ماتريس M‌×P و B‌ يك ماتريس P×N باشد. حاصل ضرب A×B در ماتريس C به ابعاد M×N ذخيره مي شود. الگوريتم زير حاصل ضرب دو ماتريس را محاسبه می کند:

for (i := 1 to M )
   for (j:= 1 to N )
     C[i,j] :=0
     for (k:=1 to P)
       C[i,j] := C[i,j] + A[i,k]*B[k,j]
     end for
   end for
end for
end

پيچيدگي الگوريتم فوق O(m.n.p) است. اگر ماتريس‌ها مربعي باشند پيچيدگي الگوريتم O(n3) مي‌شود.


ماتريس خلوت

ماتريس‌ی كه عناصر صفر آنها زياد است و نسبتا تعداد کمی عنصر غير صفر دارد را ماتريس خلوت يا اسپارس (sparse matrix) مي نامند.
ماتريس هاي قطري و مثلثي نمونه‌هايي از ماتريس‌هاي خلوت هستند.

روش طبيعي نمايش ماتريس ها در حافظه به صورت يک آرايه‌هاي دوبعدي براي اين گونه ماتريس ها مناسب نيست. براي جلوگيري از اتلاف حافظه مي توان تنها عناصر غير صفر را ذخيره كرد. آرايه حاصل داراي سه ستون است که براي ذخيره مختصات سطر و ستون و مقدارعنصر غير صفر بکار می روند و تعداد سطرهای آن به تعداد عناصر غير صفراست. اين روش ذخيره ماتريس خلوت را point access method می نامند


نكته. تعداد عناصر غيرصفر ماتريس مثلثي n بعدي برابر است با: 1+2+3+…+n=n(n+1)/2 و تعداد عناصر صفر آن برابر است با: n2 – n(n+1)/2 = n(n-1)/2.

نكته. حاصلضرب دو ماتريس اسپارس ديگر اسپارس نيست.


 


 


صفحه اصلی| PDF| درباره| تماس