ماتریس در ساختمان داده⚡️معرفی انواع ماتریس (خلوت،قطری)

Q: منظور از ماتریس چیست و انواع آن کدام است؟

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

Q: آیا میتوان گفت که یک ماتریس صفر معکوسپذیر است؟

خیر، ماتریس صفر معکوسپذیر نیست. این به این دلیل است که دترمینان آن صفر است.

به مجموعه‌ای از داده‌های پشت سر هم حافظهحافظه در کامپیوتر، همه چیز در مورد حافظه در معماری کامپیوتردر این مقاله به بررسی کامل حافظه در کامپیوتر، انواع حافظه در کامپیوتر، کش، روش‌های آدرس دهی کش، نگاشت آدرس و موارد دیگر می‌پردازیم که همگی از یک نوع بوده و از آدرس مشخصی شروع می‌شوند، آرایه گفته می‌شود. آرایهآموزش آرایه در ساختمان داده به زبان ساده و از 0 تا 100در این مقاله موارد زیر بررسی شده است : 1- آرایه چیست 2- انواع اندیس گذاری در آرایه 3- انواع آرایه 4- محاسبه آدرس در آرایه 5- محاسبه شماره در آرایه 6- آرایه در برنامه نویسی 7- مزایای استفاده از آرایه ساده‌ترین ساختمان دادهآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است است که در آن می‌توان به هر داده مستقیماً تنها با استفاده از شماره اندیس آن دسترسی داشت. به هر آرایه دو بعدی n×n یک ماتریس یا جدول با m سطر و n ستون گفته می‌شود که تعداد mn خانه در آن وجود دارد. در ادامه بیشتر با ماتریس و انواع آن آشنا خواهیم شد.

$در سمت راست تصویر یک ماتریس قرار گرفته و در سمت چپ عنوان"ماتریس چیست؟" نمایش داده شده است$

ماتریس مربعی

به هر ماتریس n×n با n² خانه ماتریس مربع گفته می‌شود. در هر ماتریس مربع n×n مانند A روابط زیر برای اندیس خانه A[i, j] وجود دارد:

A[i, j] بالای قطر فرعی است
A[i, j] روی قطر فرعی است
A[i, j] پایین قطر فرعی است

\[\left\{ \begin{array}{c} \mathrm{i\ +\ j\ \lt\ n\ +\ 1} \\ \mathrm{i\ +\ j \ = \ n\ +\ 1} \\ \mathrm{i\ +\ j\ \gt \ n\ +\ 1} \end{array} \right.\]

A[i, j] بالای قطر اصلی است
A[i, j] روی قطر اصلی است
A[i, j] پایین قطر اصلی است

\[\left\{ \begin{array}{c} \mathrm{i\ \lt \ j} \\ \mathrm{i\ = \ j} \\ \mathrm{i\ \gt\ j} \end{array} \right.\]

تصویر یک ماتریس مربعی به همراه نمایش قطرهای اصلی و فرعی

ماتریس بالا مثلثی و پایین مثلثی

در هر ماتریس مربع n×n اگر عناصر زیر قطر اصلی 0 باشند ماتریس بالا مثلثی و اگر عناصر بالای قطر اصلی 0 باشند ماتریس پایین مثلثی است.

\[\left[ \begin{array}{ccccc} \mathrm{X} & \mathrm{X} & \mathrm{X} & \mathrm{\dots } & \mathrm{X} \\ \circ & \mathrm{X} & \mathrm{X} & \mathrm{\dots } & \mathrm{X} \\ \circ & \circ & \mathrm{X} & \mathrm{\dots } & \mathrm{X} \\ \mathrm{\vdots } & \mathrm{\vdots } & \mathrm{\vdots } & \mathrm{\dots } & \mathrm{\vdots } \\ \circ & \circ & \circ & \mathrm{\dots } & \mathrm{X} \end{array} \right]\] (ب) بالا مثلثی

\[\left[ \begin{array}{ccccc} \mathrm{X} & \circ & \circ & \mathrm{\dots } & \circ \\ \mathrm{X} & \mathrm{X} & \circ & \mathrm{\dots } & \circ \\ \mathrm{X} & \mathrm{X} & \mathrm{X} & \mathrm{\dots } & \circ \\ \mathrm{\vdots } & \mathrm{\vdots } & \mathrm{\vdots } & \mathrm{\dots } & \mathrm{\vdots } \\ \mathrm{X} & \mathrm{X} & \mathrm{X} & \mathrm{\dots } & \mathrm{X} \end{array} \right]\](الف) پایین مثلثی

ماتریس‌های بالا مثلثی و پایین مثلثی

در هر ماتریس بالا مثلث یا پایین مثلث:

\[{\left[ \begin{array}{ccccc} \times & \times & \cdots & \times & \times \\ 0 & \times & \cdots & \times & \times \\ 0 & 0 & \times & \times & \times \\ 0 & 0 & 0 & \times & \times \\ 0 & 0 & 0 & 0 & \times \end{array} \right]}_{\left(n\times n\right)}\]

$ \begin{array}{c} \mathrm{n} \\ \mathrm{+\ n}\mathrm{-}\mathrm{1} \\ \begin{array}{c} \mathrm{+}\ \mathrm{n}\mathrm{-}\mathrm{2} \\ \mathrm{+}\ \ \ \ \vdots \ \ \ \ \\ \begin{array}{c} \underline{\ \ \ \ \ \ \ \ \ \mathrm{1}\mathrm{\ \ \ \ \ }} \\ \frac{\mathrm{n(n\ +\ }\mathrm{1}\mathrm{)}}{\mathrm{2}} \\ \ \end{array} \end{array} \end{array} $
(تعداد خانه‌های مخالف صفر)

${\mathrm{n}}^{\mathrm{2}}$ = تعداد کل خانه‌ها $\frac{\mathrm{n(n\ +\ }\mathrm{1}\mathrm{)}}{\mathrm{2}}$ = تعداد خانه‌های مخالف صفر $\frac{\mathrm{n(n\ -\ }\mathrm{1}\mathrm{)}}{\mathrm{2}}$ = تعداد خانه‌های صفر

حتما بخوانید :

گراف چیست،‌ آموزش تمامی مطالب گراف

ماتریس قطری

هر ماتریس $n×n$ که در آن L قطر آن که قطر اصلی نیز شامل آن است مخالف صفر باشد، ماتریس L قطری می‌گویند.

ماتریس L قطری فقط برای L های فرد تعریف می‌شود.

ماتریس	تعداد خانه مخالف صفر	نمایش
ماتریس 1 قطری = ماتریس قطری	\[N\]	\[{\left[ \begin{array}{ccc} \mathrm{x} & 0 & 0 \\ 0 & \mathrm{x} & 0 \\ 0 & 0 & \mathrm{x} \end{array} \right]}_{\mathrm{n\times n}}\]
ماتریس 3 قطری	\[3n-2\]	\[{\left[ \begin{array}{ccc} \mathrm{x} & \mathrm{x} & 0 \\ \mathrm{x} & \mathrm{x} & \mathrm{x} \\ 0 & \mathrm{x} & \mathrm{x} \end{array} \right]}_{\mathrm{n\times n}}\]
\[\vdots \]	\[\vdots \]	\[\vdots \]
ماتریس L قطری	\[\mathrm{nL}\mathrm{-}\frac{{\mathrm{L}}^{\mathrm{2}}-\mathrm{1}}{\mathrm{4}}\simeq \mathrm{nL}\]

مثال: در یک آرایه (Array) دو بعدی 5 × 5 مقادیر خانه‌های سطر اول همگی یک می‌باشد. اگر محتوای بقیه خانه‌های ستون‌های 1 و 5 برابر با صفر بوده و داشته باشیم: (کارشناسی ارشد - آزاد 71 و آزاد 72)

برای I از 2 تا 5 و J از 2 تا 4:

$\mathrm{A}\left(\mathrm{I\ ,\ J}\right)=\frac{\mathrm{1}}{\mathrm{2}}\left(\mathrm{A}\left(\mathrm{I}\mathrm{-}\mathrm{1}\mathrm{\ ,\ J}\mathrm{-}\mathrm{1}\right)+\mathrm{A}\left(\mathrm{I}\mathrm{-}\mathrm{1}\mathrm{\ ,\ J+}\mathrm{1}\right)\right)$

محتوای خانه‌های سطر سوم این آرایه چه خواهد بود؟

1) $\mathrm{\ \ \ \ \ }0\mathrm{\ \ \ \ \ }\mathrm{1}\mathrm{\ \ \ \ \ }\mathrm{1}\mathrm{\ \ \ \ \ }\mathrm{1}\mathrm{\ \ \ \ \ }0$

2) $\mathrm{\ \ \ \ \ } 0\mathrm{\ \ \ \ \ }\frac{\mathrm{1}}{\mathrm{2}}\ \ \ \ \ \frac{\mathrm{1}}{\mathrm{2}}\ \ \ \ \ \frac{\mathrm{1}}{\mathrm{4}}\ \ \ \ \ 0$

3) $\mathrm{\ \ \ \ \ }0\mathrm{\ \ \ \ \ }\frac{\mathrm{1}}{\mathrm{2}}\ \ \ \ \ \mathrm{1}\ \ \ \ \ \frac{\mathrm{1}}{\mathrm{2}}\ \ \ \ \ 0$

4) $\mathrm{\ \ \ \ \ }0\mathrm{\ \ \ \ \ }\frac{\mathrm{1}}{\mathrm{4}}\ \ \ \ \ \frac{\mathrm{1}}{\mathrm{2}}\ \ \ \ \ \mathrm{1}\ \ \ \ \ 0$

حل: گزینه 3 درست است.

با توجه به توضیحات مربوط به ماتریس مورد بررسی در سؤال، آرایه دو بعدی فوق به صورت زیر شبیه‌سازی می‌شود.

$\mathrm{A\ \ \ }\mathrm{\ \ } \begin{array}{c} \mathrm{\ } \\ \mathrm{1} \\ \mathrm{2} \\ \mathrm{3} \\ \mathrm{4} \\ \mathrm{5} \end{array} \begin{array}{c} \begin{array}{cccccccc} \mathrm{\ } & \mathrm{1} & \mathrm{2} & \mathrm{3} & \mathrm{4} & \mathrm{5} & \ & \mathrm{\ \ \ } \end{array} \\ {\left[ \begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & {{\frac{1}{2}}} & 1 & {{\frac{1}{2}}} & 0 \\ 0 & \mathrm{\ } & \mathrm{\ } & \mathrm{\ } & 0 \\ 0 & \mathrm{\ } & \mathrm{\ } & \mathrm{\ } & 0 \end{array} \right]}_{\mathrm{5}\mathrm{\times }\mathrm{5}} \end{array} $

شرایط گفته شده در صورت ‌سؤال به این صورت است که به ازای I از 2 تا 5 و J از 2 تا 4:

بنابراین محتوای خانه‌های دیگر ماتریس را با استفاده از این رابطه به‌دست می‌آوریم:

$\mathrm{A}\left(\mathrm{2}\mathrm{\ ,\ }\mathrm{2}\right)=\frac{\mathrm{1}}{\mathrm{2}}\left(\mathrm{A}\left(\mathrm{2}\mathrm{-}\mathrm{1}\mathrm{\ ,\ }\mathrm{2}\mathrm{-}\mathrm{1}\right)+\mathrm{A}\left(\mathrm{2}\mathrm{-}\mathrm{1}\mathrm{\ ,\ }\mathrm{2}\mathrm{\ +\ }\mathrm{1}\right)\right)=\frac{\mathrm{1}}{\mathrm{2}}\left(\mathrm{A}\left(\mathrm{1}\mathrm{\ ,}\mathrm{\ 1}\right)+\mathrm{A}\left(\mathrm{1}\mathrm{\ ,\ }\mathrm{3}\right)\right)=\frac{\mathrm{1}}{\mathrm{2}}\left(\mathrm{1}\mathrm{+}\mathrm{1}\right)=\mathrm{1}$

$\mathrm{A}\left(\mathrm{2}\mathrm{\ ,\ }\mathrm{3}\right)=\frac{\mathrm{1}}{\mathrm{2}}\left(\mathrm{A}\left(\mathrm{1}\mathrm{\ ,\ }\mathrm{2}\right)+\mathrm{A}\left(\mathrm{1}\mathrm{\ ,\ }\mathrm{4}\right)\right)=\frac{\mathrm{1}}{\mathrm{2}}\left(\mathrm{1}\mathrm{\ +\ }\mathrm{1}\right)=\mathrm{1}$

$\mathrm{A}\left(\mathrm{2}\mathrm{\ ,\ }\mathrm{4}\right)=\frac{\mathrm{1}}{\mathrm{2}}\left(\mathrm{A}\left(\mathrm{1}\mathrm{\ ,\ }\mathrm{3}\right)+\mathrm{A}\left(\mathrm{1}\mathrm{\ ,\ }\mathrm{5}\right)\right)=\frac{\mathrm{1}}{\mathrm{2}}\left(\mathrm{1}\mathrm{\ +\ }\mathrm{1}\right)=\mathrm{1}$

$\mathrm{A}\left(\mathrm{3}\mathrm{\ ,\ }\mathrm{2}\right)=\frac{\mathrm{1}}{\mathrm{2}}\left(\mathrm{A}\left(\mathrm{2}\mathrm{\ ,\ }\mathrm{1}\right)+\mathrm{A}\left(\mathrm{2}\mathrm{\ ,\ }\mathrm{3}\right)\right)=\frac{\mathrm{1}}{\mathrm{2}}\left(0\mathrm{\ +\ }\mathrm{1}\right)=\frac{1}{\mathrm{2}}$

$\mathrm{A}\left(\mathrm{3}\mathrm{\ ,\ }\mathrm{3}\right)=\frac{\mathrm{1}}{\mathrm{2}}\left(\mathrm{A}\left(\mathrm{2}\mathrm{\ ,\ }\mathrm{2}\right)+\mathrm{A}\left(\mathrm{2}\mathrm{\ ,\ }\mathrm{4}\right)\right)=\frac{\mathrm{1}}{\mathrm{2}}\left(\mathrm{1}\mathrm{\ +\ }\mathrm{1}\right)=\mathrm{1}$

$\mathrm{A}\left(\mathrm{3}\mathrm{\ ,\ }\mathrm{4}\right)=\frac{\mathrm{1}}{\mathrm{2}}\left(\mathrm{A}\left(\mathrm{2}\mathrm{\ ,\ }\mathrm{3}\right)+\mathrm{A}\left(\mathrm{2}\mathrm{\ ,\ }\mathrm{5}\right)\right)=\frac{\mathrm{1}}{\mathrm{2}}\left(\mathrm{1}\mathrm{\ +\ }0\right)=\frac{1}{\mathrm{2}}$

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

$0 , \frac{\mathrm{1}}{\mathrm{2}}, \mathrm{1}, \frac{\mathrm{1}}{\mathrm{2}}, 0$ : سطر سوم

مثال: فرض کنید (i , j) و (K , L) دو عنصر در یک صفحه 8 × 8 باشند (مانند صفحه شطرنج) کدام‌یک از گزینه‌های زیر هم‌قطر بودن آن‌ها را تعیین می‌کند؟ (تهدید دو مهره فیل) (کارشناسی ارشد - علوم کامپیوتر 79)

1) $ \mathrm{if\ (i\ =\ K)\ or\ (j\ =\ L)\ then}$

2) $\mathrm{if\ (i}\mathrm{-}\mathrm{K\ =\ j}\mathrm{-}\mathrm{L)\ or\ (i}\mathrm{-}\mathrm{K\ =\ L}\mathrm{-}\mathrm{j)\ then}$

3) $\mathrm{if\ (i}\mathrm{-}\mathrm{K\ =\ j}\mathrm{-}\mathrm{L)\ then}$

4) $\mathrm{if\ (i}\mathrm{-}\mathrm{K\ =\ j}\mathrm{-}\mathrm{L)\ or\ (i}\mathrm{-}\mathrm{K\ =\ L\ +\ }\mathrm{8}\mathrm{-}\mathrm{j)\ then}$

حل: گزینه 2 درست است.

برای حل این سؤال با آوردن مثال برای یک ماتریس 8 × 8 و در نظر گرفتن وضعیت مهره‌های فیل جواب را به دست می‌آوریم:

$\left(\mathrm{i\ ,\ j}\right)\mathrm{\ \ \ \ }↔\mathrm{\ }\mathrm{\ \ \ \ }\left(\mathrm{K\ ,\ L}\right)$ $\left(\mathrm{1}\mathrm{\ ,\ }\mathrm{3}\right)\mathrm{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\left(\mathrm{3}\mathrm{\ ,\ }\mathrm{1}\right)$ $\left(\mathrm{1}\mathrm{\ ,\ }\mathrm{3}\right)\mathrm{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\left(\mathrm{6}\mathrm{\ ,\ }\mathrm{8}\right)$

حتما بخوانید :

ساختمان داده پشته ⚡️ پشته چیست؟ کاربرد پشته در ساختمان داده

ماتریس اسپارس (تُنک، پراکنده، خلوت، Sparse)

بنابر تعریف به هر ماتریس m × n که تعداد خانه‌های صفر و بی‌ارزش (Nonvalue) در آن بیش‌تر از تعداد خانه‌های مخالف صفر باشد، ماتریس اسپارس می‌گویند.

حاصل‌ضرب، جمع و تفریق ماتریس‌های Sparse ممکن است Sparse نباشد.

جمع :

\[\left[ \begin{array}{cc} \mathrm{1} & 0 \\ 0 & 0 \end{array} \right]+\left[ \begin{array}{cc} 0 & \mathrm{1} \\ 0 & 0 \end{array} \right]=\left[ \begin{array}{cc} \mathrm{1} & \mathrm{1} \\ 0 & 0 \end{array} \right]\]

(اسپارس نیست)

تفریق :

\[\left[ \begin{array}{cc} \mathrm{1} & 0 \\ 0 & 0 \end{array} \right]-\left[ \begin{array}{cc} 0 & \mathrm{1} \\ 0 & 0 \end{array} \right]=\left[ \begin{array}{cc} \mathrm{1} & \mathrm{-}\mathrm{1} \\ 0 & \mathrm{\ \ \ }0 \end{array} \right]\]

(اسپارس نیست)

ضرب :

\[\left[ \begin{array}{ccc} \mathrm{1} & 0 & 0 \\ \mathrm{1} & 0 & 0 \\ 0 & 0 & 0 \end{array} \right]\times \left[ \begin{array}{ccc} \mathrm{1} & \mathrm{1} & \mathrm{1} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array} \right]=\left[ \begin{array}{ccc} \mathrm{1} & \mathrm{1} & \mathrm{1} \\ \mathrm{1} & \mathrm{1} & \mathrm{1} \\ 0 & 0 & 0 \end{array} \right]\]

(اسپارس نیست)

روش های ذخیره سازی ماتریس ‌های اسپارس

آرایه دو بعدی و ذخیره مختصات خانه‌های مخالف صفر (روش عمومی)
آرایه یک بعدی برای نگه‌داری مقادیر مخالف صفر به کمک فرمول (رابطه) در ماتریس‌های بالا مثلث، پایین مثلث، سه قطری و...

آرایه دو بعدی و ذخیره مختصات خانه‌های مخالف صفر (روش عمومی)

در صورتی که ماتریس اسپارس m × n با r خانه مخالف صفر وجود داشته باشد، برای ذخیره آن از یک آرایه دو بعدی با 1 + r سطر و 3 ستون به‌شرح زیر استفاده می‌شود:

$\mathrm{S}\mathrm{parse}\left[\mathrm{1}\mathrm{\ ..\ r}\mathrm{\ }\mathrm{+}\mathrm{\ }\mathrm{1}\mathrm{\ ,\ }\mathrm{1}\mathrm{\ ..\ }\mathrm{3}\right]$

در سطر اول به‌ترتیب: تعداد سطرها (m)، تعداد ستون‌ها (n) و تعداد خانه‌های مخالف صفر (r) ماتریس اسپارس قرار داده می‌شود.
از سطر دوم به بعد، هر سطر شامل سه مؤلفه است که همان مختصات و مقدار خانه‌های مخالف صفر است:$\left(\mathrm{i\ ,\ j\ ,\ A}\left[\mathrm{i\ ,\ j}\right]\neq 0\right)$

تعداد مقادیر مخالف0 تعداد ستون‌ها تعداد سطرها

مشخصات کلی $\leftarrow $

$\left. \begin{array}{c} \mathrm{\ } \\ \mathrm{\ } \\ \mathrm{\ } \\ \mathrm{\ } \end{array} \right\}\mathrm{\ }\mathrm{\leftarrow }\mathrm{\ }\left(\mathrm{i\ ,\ j\ ,\ A}\left[\mathrm{i\ ,\ j}\right]\neq 0\right)$

\[{ \begin{array}{c} \ \ \ \ \ \ \ \ \ \begin{array}{ccc} \searrow \ & \ \downarrow \ \ \ & \swarrow \end{array} \\ \begin{array}{cc} \to & \ \end{array} \left[ \begin{array}{ccc} 3 & 6 & 4 \\ 1 & 2 & 13 \\ 1 & 6 & 14 \\ 2 & 1& 16 \\ 3 & 6 & 15 \end{array} \right] \end{array} }_{5\times 3}\] نمایش ماتریس اسپارس

\[{\left[ \begin{array}{cccccc} 0 & 13 & 0 & 0 & 0 & 14 \\ 16 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 15 \end{array} \right]}_{3\times 6}\] ماتریس اسپارس

چون خانه‌های مخالف 0، 4 تا است، بنابراین ماتریس اسپارس شامل 5 سطر و 3 ستون خواهد بود.

مقرون به‌صرفه بودن

روش مطرح شده در بالا در شرایطی مقرون به صرفه است که تعداد خانه‌های ماتریس نگه‌دارنده Sparse[1 .. r+1, 1 .. 3] از تعداد خانه‌های ماتریس اسپارس m × n به مراتب کم‌تر باشد:

\[\mathrm{3}\left(\mathrm{r\ +\ }\mathrm{1}\right)\mathrm{\ \lt\ \ mn}{{\stackrel{\mathrm{\ \ \ \ \ \ }\mathrm{3}\left(\mathrm{r\ +\ }\mathrm{1}\right)\ =\ \mathrm{3}\mathrm{r}\ \ \ \ \ \ }{\longrightarrow}}}\mathrm{r\ \ \lt\ \ }\frac{\mathrm{mn}}{\mathrm{3}}\]

به‌عبارت بهتر تعداد خانه‌های مخالف صفر r کم‌تر از 1/3 (یک سوم) خانه‌های ماتریس اسپارس باشد.

مثال: می‌توان هر ماتریس تنک (Sparse) را به صورت یک آرایه دو بعدی نمایش داد. برای این کار سطر، ستون و مقدار درایه‌های غیرصفر ماتریس را در آرایه ذخیره می‌کنند. یک ماتریس L قطری با n سطر و n ستون داده شده است. برای مقرون به صرفه بودن این نمایش تنک، بزرگ‌ترین L ممکن برابر است با ... (علوم کامپیوتر - کارشناسی ارشد - 79)

1) $\mathrm{L\ \lt\ }\left\lfloor \ \frac{\mathrm{n}}{\mathrm{3}}\ \right\rfloor $

2) $\mathrm{\ }\mathrm{L\ \lt\ }\left\lfloor \ \frac{\mathrm{n}}{\mathrm{2}}\ \right\rfloor $

3) $\mathrm{L\ \lt\ }\left\lfloor \sqrt{\mathrm{n}}\right\rfloor $

4) $\mathrm{L\ \lt\ }\left\lfloor \ \frac{\mathrm{n}}{\mathrm{4}}\ \right\rfloor $

حل: گزینه 1 درست است.

تعداد خانه‌های مخالف صفر در یک ماتریس n × n به صورت L قطری برابر می‌شود با:$\mathrm{r\ =\ nL}\mathrm{-}\frac{{\mathrm{L}}^{\mathrm{2}}-\mathrm{1}}{\mathrm{4}}\simeq \mathrm{nL}$بنابراین باید:

$\mathrm{r\ \lt\ }\frac{\mathrm{mn}}{\mathrm{3}}{{\mathop{{{\stackrel{\mathrm{\ \ \ \ }\mathrm{\ m\ =\ n\ \ \ \ \ }}{\longrightarrow}}}}_{\mathrm{r = nl}}}}\mathrm{nL\ \lt\ }\frac{\mathrm{n\ \times \ n}}{\mathrm{3}}\to \mathrm{L\ \lt\ }\frac{\mathrm{n}}{\mathrm{3}}$

ترانهاده کردن (Transpose) ماتریس اسپارس

برای ترانهاده کردن ماتریس Sparse به این شکل عمل می‌کنیم که ابتدا در سطر اول، جای سطر و ستون را عوض کرده و به همراه تعداد خانه‌های مخالف صفر در ماتریس ترانهاده قرار می‌دهیم. سپس از سطر دوم به بعد روی ستون دوم به ترتیب از بالا به پایین کوچک‌ترین عنصر را پیدا کرده، جای سطر و ستون آن‌ها را عوض کرده و به همراه مقدارشان در ماتریس ترانهاده قرار می‌دهیم.

\[\left[ \begin{array}{ccc} 6 & 3 & 4 \\ 1 & 2 & 16 \\ 2 & 1 & 13 \\ 6 & 1 & 14 \\ 6 & 3 & 15 \end{array} \right]\]

ترانهاده

\[\longrightarrow \]

\[\left[ \begin{array}{ccc} 3 & 6 & 4 \\ 1 & 2 & 13 \\ 1 & 6 & 14 \\ 2 & 1 & 16 \\ 3 & 6 & 15 \end{array} \right]\]

تحلیل الگوریتم ترانهاده

برای ترانهاده کردن ماتریس A _Rows_×_Columns در ماتریس B _Columns_{× R}_ows می‌توان از الگوریتم زیر در زمان (Columns × Rows)O استفاده کرد:

for i := 1 to columns do
for j := 1 to rows do
B[j][i] := A[i][j];

for i := 1 to columns do
for j := 1 to rows do
B[j][i] := A[i][j];

در صورتی که ماتریس اسپارس Rows × Columns با Element خانه مخالف صفر وجود داشته باشد و برای ذخیره آن از یک آرایه دو بعدی با 1 + Rows سطر و 3 ستون استفاده کنیم، زمان ترانهاده کردن ماتریس (Columns × Elements)O خواهد شد.

ترانهاده سریع ماتریس اسپارس

با استفاده از یک الگوریتم کاراتر و سریع‌تر می‌توان در زمان (Columns + Elements)O ترانهاده یک ماتریس اسپارس را به‌دست آورد. (برای کسب اطلاعات بیش‌تر به فصل دوم از کتاب ساختمان داده هورویتز مراجعه شود)

مثال: ماتریس خلوت ماتریسی است دو بعدی مانند A[1 .. m, 1 .. n] که اکثر عناصر آن صفر می‌باشد. برای صرفه‌جویی در حافظه فقط عناصر غیر صفر را به همراه شماره سطر و شماره ستون و مقدار عنصر در آرایه‌ای با تعریف زیر ذخیره می‌نماییم. (به ترتیب سطری)

$\mathrm{type\ sparse\ matrix\ =\ arry}\left[0\ ..\ \mathrm{max\ terms\ ,\ }\mathrm{1}\mathrm{\ }\mathrm{..\ }\mathrm{3}\right]\mathrm{\ of\ integer}\mathrm{;}$

مثال: کدام‌یک از گزینه‌های زیر صحیح می‌باشد؟ (t تعداد عناصر غیر صفر می‌باشد)

1) سریع‌ترین زمان برای به دست آوردن ترانهاده ماتریس خلوت به ترتیب سطری O(n + t) است.

2) حاصل‌ضرب دو ماتریس خلوت الزاماً یک ماتریس خلوت است.

3) سریع‌ترین زمان برای به دست آوردن ترانهاده ماتریس خلوت به ترتیب سطری O(m + t) است.

4) سریع‌ترین زمان برای به دست آوردن ترانهاده ماتریس خلوت به ترتیب سطری θ(nt) است.

حل: گزینه 1 درست است.

\[\mathrm{O}\left(\mathrm{C}\mathrm{olumns\ +\ }\mathrm{E}\mathrm{lements}\right){{\stackrel{\mathrm{\ \ \ \ \ \ }\mathrm{C}\mathrm{olumns\ =\ n\ ,\ }\mathrm{E}\mathrm{lements\ =\ t\ \ \ \ \ \ }}{\longrightarrow}}}\mathrm{O}\left(\mathrm{n\ +\ t}\right)\]

حتما بخوانید :

آرایه (Array) در ساختمان داده

آرایه یک بعدی برای نگهداری مقادیر مخالف صفر به کمک فرمول (رابطه) در ماتریس های بالا مثلث، پایین مثلث، سه قطری و...

بعضی ماتریس‌ها مانند: بالا مثلث، پایین مثلث و ... اسپارس نیستند، اما زمانی که تعداد عناصر در آن‌ها زیاد می‌شود، تعداد صفرهای ماتریس قابل توجه خواهد شد در این وضعیت بهتر است مقادیر مخالف صفر ماتریس به صورت زیر ذخیره شود:

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

مثال: ماتریس پایین مثلثی A[1 .. n, 1 .. n] را در نظر بگیرید که عناصر مخالف صفر آن را به صورت سطری در یک آرایه یک بعدی نگه‌داری کرده‌ایم، در این وضعیت:

در ماتریس $\mathrm{S\ =\ }\frac{\mathrm{n}\left(\mathrm{n\ +\ }\mathrm{1}\right)}{\mathrm{2}}$ خانه‌ی مخالف صفر وجود دارد. برای همین به یک آرایه یک بعدی (B[1 .. S]) نیاز داریم.
هر خانه A[i, j] ≠ 0 در ماتریس پایین مثلث با رابطه (فرمول سطری) زیر محل خود را در آرایه یک بعدی (B[k]) مشخص می‌کند.

$\mathrm{k\ =\ }\frac{\mathrm{i}\left(\mathrm{i}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}+\mathrm{j}$

\[\left(\mathrm{B}\left[\mathrm{k}\right]\right)\]\[\left[ \begin{array}{ccccc} \mathrm{1} & \mathrm{2} & . & . & . \end{array} \right] \begin{array}{cc} \mathrm{\ } & \mathrm{S} \end{array} \] \[\mathrm{S\ =\ }\frac{\mathrm{n}\left(\mathrm{n\ +\ }\mathrm{1}\right)}{\mathrm{2}}\]

\[\longrightarrow \]

\[\mathrm{A}\left[\mathrm{i\ ,\ j}\right]\neq 0\]\[\left[ \begin{array}{cccc} \times & 0 & 0 & 0 \\ \times & \times & 0 & 0 \\ \times & \dots & \times & 0 \\ \times & \times & \times & \times \end{array} \right]\]

\[\left(\mathrm{B}\left[\mathrm{k}\right]\right)\]\[ \begin{array}{c} \begin{array}{cccccc} \ \ 1\ & \ \ 2\ & \ \ 3\ & \ \ 4\ \ & 5\ \ \ & 6\ \ \ \end{array} \\ \left[ \begin{array}{cccccc} 10 & 20 & 30 & 40 & 50 & 60 \end{array} \right] \end{array} \]

\[\longrightarrow \]

\[\mathrm{A}\left[\mathrm{i\ ,\ j}\right]\]\[\left[ \begin{array}{ccc} 10 & 0 & 0 \\ 20 & 30 & 0 \\ 40 & 50 & 60 \end{array} \right]\]

به‌طور مثال موقعیت خانه‌ی $A[3, 2] = 50$ در آرایه یک بعدی B[5] است. رابطه بین $(i=3, j=2)$ در ماتریس و $(k=5)$ در آرایه یک بعدی توسط فرمول زیر تعیین می‌شود:

$\mathrm{k\ =\ }\frac{\mathrm{i}\left(\mathrm{i}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}+\mathrm{j}$

که در این‌جا داریم:

$\underbrace{\mathrm{A}\left[\mathrm{3}\mathrm{\ ,\ }\mathrm{2}\right]}_{\left[\mathrm{i\ ,\ j}\right]}\underbrace{\mathop{{{\stackrel{\mathrm{\ \ \ \ i\ =\ }\mathrm{3}\mathrm{\ \ \ \ }}{\longrightarrow}}}}_{\mathrm{j\ =\ }\mathrm{2}}\mathrm{k\ =\ }\frac{\mathrm{3}\left(\mathrm{3}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}+\mathrm{2}\mathrm{\ =\ }\mathrm{5}}_{\frac{\mathrm{i}\left(\mathrm{i}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}+\mathrm{j}}\mathrm{\longrightarrow }\underbrace{\mathrm{B}\left[\mathrm{5}\right]}_{\mathrm{B}\left[\mathrm{k}\right]}$

مثال: برای هر خانه مخالف صفر $A[i, j]$ درماتریس بالا مثلثی n × n، رابطه زیر محل آن خانه را در آرایه یک بعدی B مشخص می‌کند. $(B[k])$

$\mathrm{k\ =\ }\left(\mathrm{i}\mathrm{-}\mathrm{1}\right)\left(\mathrm{n}\mathrm{-}\frac{\mathrm{i}}{\mathrm{2}}\right)+\mathrm{j}$

فرمول ستونی	فرمول سطری	تعداد خانه مورد نیاز برای ذخیره مقادیر مخالف صفر در آرایه یک بعدی	ماتریس
\[\mathrm{k\ =\ }\left(\mathrm{j}\mathrm{-}\mathrm{1}\right)\left(\mathrm{n}\mathrm{-}\frac{\mathrm{j}}{\mathrm{2}}\right)+\mathrm{i}\]	\[\mathrm{k\ =\ }\frac{\mathrm{i}\left(\mathrm{i}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}+\mathrm{j}\]	\[\frac{\mathrm{n}\left(\mathrm{n\ +}\mathrm{\ }\mathrm{1}\right)}{\mathrm{2}}\]	پایین مثلث
\[\mathrm{k\ =\ }\frac{\mathrm{j}\left(\mathrm{j}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}+\mathrm{i}\]	\[\mathrm{k\ =\ }\left(\mathrm{i}\mathrm{-}\mathrm{1}\right)\left(\mathrm{n}\mathrm{-}\frac{\mathrm{i}}{\mathrm{2}}\right)+\mathrm{j}\]	\[\frac{\mathrm{n}\left(\mathrm{n\ +}\mathrm{\ }\mathrm{1}\right)}{\mathrm{2}}\]	بالا مثلث
\[\mathrm{2}\mathrm{j}\mathrm{\ +\ }\mathrm{i}\mathrm{-}\mathrm{2}\]	\[\mathrm{2}\mathrm{i\ +\ j}\mathrm{-}\mathrm{2}\]	\[\mathrm{3}\mathrm{n}\mathrm{-}\mathrm{2}\]	سه قطری

نتیجه‌گیری

بین دو روش بیان شده یعنی:

روش عمومی نمایش ماتریس اسپارس (نگه‌داری مختصات مقادیر مخالف صفر با استفاده از آرایه 2 بعدی)
نگه‌داری مقادیر مخالف صفر در آرایه یک بعدی که تعداد عناصر آن به تعداد خانه‌های مخالف 0 است.

روش دوم از نظر حافظه مقرون به صرفه‌تر است البته به شرط آن که بتوان رابطه یا فرمولی بین اندیس‌های آرایه B[k] و اندیس‌های مقادیر مخالف صفر A[i, j] پیدا کرد.

مثال: ماتریس دو بعدی با ابعاد N × N به نام MAT2 یک ماتریس تنک یا خلوت (Sparse) است که در آن هر سطر فقط عنصر روی قطر، یک عنصر بالای قطر و یک عنصر زیر قطر دارای اطلاع بوده و بقیه عناصر همه صفر می‌باشند. می‌خواهیم جهت جلوگیری از هدر رفتن فضا اطلاعات را به‌جای این که از ماتریس دو بعدی MAT2 ذخیره نماییم در ماتریس یک بعدی MAT1 به صورت زیر ذخیره کنیم.

$\mathrm{MAT}\mathrm{2}\left[ \begin{array}{c} {\mathrm{a}}_{\mathrm{11}}\ \ \ \ \ {\mathrm{a}}_{\mathrm{1}\mathrm{2}}\ \ \ \ \ 0\mathrm{\ }\mathrm{\ }\mathrm{\ \ \ \ \ \ }0 \\ {\mathrm{a}}_{\mathrm{21}}\ \ \ \ \ {\mathrm{a}}_{\mathrm{22}}\ \ \ \ \ {\mathrm{a}}_{\mathrm{23}}\ \ \ \ \ \ \\ \begin{array}{c} 0\ \ \ \ \ \mathrm{\ }\ \ \ {\mathrm{a}}_{\mathrm{32}}\ \ \ \ \ {\mathrm{a}}_{\mathrm{33}}\ \ \ \ \ \ \\ \mathrm{0\ }\ \ \ \ \ \ \mathrm{\ }\ 0\ \ \ \ \ \ \ \ {\mathrm{a}}_{\mathrm{43}}\ \ \ \ \ \ \\ 0\mathrm{\ }\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ddots \end{array} \end{array} \right]$

$ \begin{array}{cc} \ & \begin{array}{ccccccc} \ \ \ \ 1\ & \ \ \ \ 2\ \ & \ \ 3\ \ \ & \ 4\ \ \ \ & 5\ \ \ \ & 6\ \ \ \ \ & \ \end{array} \ \ \ \ \\ \mathrm{MAT1} & \left[ \begin{array}{ccccccc} {\mathrm{a}}_{\mathrm{11}} & {\mathrm{a}}_{\mathrm{1}\mathrm{2}} & {\mathrm{a}}_{\mathrm{21}} & {\mathrm{a}}_{\mathrm{22}} & {\mathrm{a}}_{\mathrm{23}} & {\mathrm{a}}_{\mathrm{32}} & \cdots \end{array} \right] \end{array} $

عنصر MAT2[i, j]، (i, j ≤ n) در چه خانه‌ای (اندیس) از ماتریس MAT1 ذخیره خواهد شد؟

1) $\frac{\mathrm{I\ \times \ }\left(\mathrm{I}\mathrm{\ -\ }\mathrm{1}\right)}{\mathrm{2}}\mathrm{+}\mathrm{J}$

2) $\mathrm{2}\mathrm{I\ +\ J}\mathrm{-}\mathrm{2} $

3) $\mathrm{3}\mathrm{\ \times \ }\left(\mathrm{I\ +\ J}\right) $

4) $\mathrm{3}\mathrm{\ \times }\left(\mathrm{I\ +\ J}\right)-\mathrm{2} $

حل: گزینه 2 درست است.

برای به دست آوردن رابطه‌ای که هر خانه مخالف صفرA[i, j] در ماتریس سه قطری MAT2 را در آرایه‌ی یک بعدی MAT1 ذخیره کند از این روش استفاده می‌کنیم که چند عنصر به صورت تصادفی از آرایه دو بعدی انتخاب کرده و i، j آن را در روابط گزینه‌ها قرار می‌دهیم تا ببینیم اندیس به دست آمده از روابط با اندیس خانه‌ها در آرایه یک بعدی همخوانی دارد یا نه.

${\mathrm{a}}_{\mathrm{23}}=\mathrm{5}\mathrm{\ }\mathrm{\longrightarrow }$ $\;\; \; \text{ گزینه 1 : } \;\;$$ \frac{\mathrm{2}\mathrm{\ \times \ }\left(\mathrm{2}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}+\mathrm{3}\mathrm{\ =\ }\mathrm{4}\mathrm{\ }\mathrm{\neq }\mathrm{\ }\mathrm{5} \;\; \mathbf{\times}$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{ گزینه 2 :}\;\;$$ \mathrm{2}\left(\mathrm{2}\right)+\left(\mathrm{3}\right)-\mathrm{2}\mathrm{\ =\ }\mathrm{5\ }\mathrm{=\ }\mathrm{5} \;\; \checkmark$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{ گزینه 3 :}\;\;$$ \mathrm{3}\mathrm{\ \times }\left(\mathrm{2}\mathrm{\ +\ }\mathrm{3}\right)=\mathrm{15}\mathrm{\ }\mathrm{\neq }\mathrm{\ }\mathrm{5} \;\; \mathbf{\times}$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{ گزینه 4 :}\;\;$$ \mathrm{3}\mathrm{\ \times }\left(\mathrm{2}\mathrm{\ +\ }\mathrm{3}\right)-\mathrm{2}\mathrm{\ =\ }\mathrm{13}\mathrm{\ }\mathrm{\neq }\mathrm{\ }\mathrm{5} \;\; \mathbf{\times}$

حتما بخوانید :

کاربرد ساختمان داده ⚡️ کاربرد ساختمان داده در کامپیوتر

جمع‌بندی

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

منظور از ماتریس چیست و انواع آن کدام است؟

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