الگوریتمستان

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
نوشته‌ها با برچسب ماتریس نوشته‌ها با برچسب ماتریس - الگوریتمستان الگوریتمستان الگوریتمستان
نوشته‌ها با برچسب «

ماتریس

»

مسئله

ماتریس مربعی با ابعاد $N$ در $N$ و درایه‌هایی از اعداد صحیح موجود است. منظور از زیرماتریس بیشینه، زیرماتریسی از ماتریس مفروض است که مجموع عناصر آن بزرگتر یا مساوی مجموع عناصر هر زیرماتریس دیگر آن است.

به عنوان مثال، برای ماتریس زیر:

  

\[ \begin{matrix} 0 & -2 & -7 & 0 \\ 9 & 2 & -6 & 2 \\ -4 & 1 & -4 & 1 \\ -1 & 8 & 0 & -2 \end{matrix} \]

  

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

ادامه ...

دترمینان ماتریس مربعی - که به صورت $ \vert A \vert $ یا $ det( A ) $ نمایش داده می‌شود - یکی از مفاهیم مشهور جبر خطی است که کاربردهای بسیاری در علوم مختلف دارد. امکان محاسبه‌ی سریع دترمینان یک ماتریس با ابعاد بزرگ بحث مهمی است که در ادامه سه روش محاسباتی رایج و پيچيدگي زمانی آنها مرور خواهند شد.

طبق تعریف دترمینان اگر اندازه‌ی ابعاد ماتریس مربعی یک باشد ($n = 1$)، دترمینان همان مقدار تک‌عضو آن است. یعنی:

  

ادامه ...

همه‌ی ما با تعریف ضرب ماتریس‌های مربعی آشنایی داریم. حاصلضرب ماتریس‌های مربعی A و B به صورت زیر تعریف می‌شود:

  

\[ A=(a_{ij})_{n \times n} = \qquad , \qquad B=(b_{ij})_{n \times n} \] \[ C = A \times B = (c_{ij})_{n \times n} \qquad ; \qquad c_{ij}= \sum_{k=1}^{n} a_{ik} \; b{kj} \]

  

به عنوان مثال در حالت $n = 2$ داریم:

  

\[ \begin{pmatrix} a_{11} & a_{12}\\ a_{21} & a_{22} \end{pmatrix} \times \begin{pmatrix} b_{11} & b_{12}\\ b_{21} & b_{22} \end{pmatrix} = \begin{pmatrix} a_{11}b_{11}+a_{12}b_{21} & a_{11}b_{12}+a_{12}b_{22}\\ a_{21}b_{11}+a_{22}b_{21} & a_{21}b_{12}+a_{22}b_{22} \end{pmatrix} \]

ادامه ...

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

فرض کنید قصد داریم حاصلضرب عبارت ماتریسی $ A_{3 \times 7} \times B_{7 \times 8 } \times C_{8 \times 4} $ را محاسبه کنیم. می‌دانیم که ضرب ماتریس‌ها خاصیت شرکت‌پذیری داشته، اما خاصیت جابجایی ندارد. بنابراین رعایت ترتیب ضرب آنها مهم است. پرانتزبندی‌های مختلف ضرب ماتریس‌ها حالت‌های مختلف محاسبه آن را به ما می‌دهند:

  

\[1: A \times (B \times C) \]

ادامه ...

الگوریتمستان در تلگرام

   

 

پیوند کوتاه:
برچسب‌ها
#درخت پوشا #ترجمه‌ی فارسی سوالات برنامه‌نویسی #الگوریتم فلوید-وارشال #مسئله‌ی کوله‌پشتی #سوالات مسابقات برنامه‌نویسی بیان #مسئله‌های الگوریتمی #حل سوالات مسابقات برنامه‌نویسی #تمرین المپیاد کامپیوتر #سوالات مسابقات ACM-ICPC #ترجمه فارسی سوالات کتاب Programming Challenges #کتاب الکترونیکی #مسأله‌های الگوریتمی #مسأله‌های برنامه‌نویسی #الگوریتم دایکسترا #صف #آمادگی مسابقه ACM #الگوریتم‌های تقسیم و غلبه #برنامه‌نویسی ++C #درخت‌ها #الگوریتم‌های برنامه‌نویسی پویا #الگوریتم #برنامه‌نویسی #ویدئوی آموزشی #مسئله‌های برنامه‌نویسی #پیمایش گراف #حل سوالات UVa Online Judge #معرفی وب‌سایت #آموزش ساختمان داده‌ها #حل مسئله‌‌ی الگوریتمی #حل سوالات ACM-ICPC #الگوریتم‌های گراف #نمونه سوال فارسی مسابقه‌ی ACM #حل سوالات Timus Online Judge #نمونه سوال مسابقه ACM #الگوریتم‌های مسیریابی #جستجوی اول عمق #آمادگی مسابقه برنامه‌نویسی #آموزش الگوریتم #سوالات UVa Online Judge #الگوریتم‌های کوتاهترین مسیر #کتابخانه قالب استاندارد ++C #دانلود کتاب #کتاب مسابقات برنامه‌نویسی #تکنیک‌های طراحی الگوریتم #ترجمه‌ی فارسی سوالات UVa Online Judge #سوالات چالشی برنامه‌نویسی #گراف #الگوریتم‌های مرتب‌سازی #مسابقه برنامه نویسی #منبع آموزشی #مسابقات برنامه‌نویسی #مسابقه برنامه‌نویسی #نمونه سوال فارسی مسابقات برنامه‌نویسی #الگوریتم‌های حریصانه #الگوریتم‌های بازگشتی #کتاب الگوریتم #ساختمان داده #آمادگی المپیاد کامپیوتر #مسابقات برنامه‌نویسی ACM #محاسبات ریاضی #ترجمه‌ی فارسی سوالات ACM #نمونه سوالات مسابقه برنامه‌نویسی #الگوریتم‌های عقبگرد #وبلاگ #نکات برنامه‌نویسی #تمرین مسابقه‌ی برنامه‌نویسی ای‌سی‌ام #ماتریس #آموزش برنامه‌نویسی ++C #تمرین طراحی الگوریتم #نمونه سوال فارسی مسابقات ACM #جستجوی اول سطح #تمرین مسابقه برنامه‌نویسی #آموزش طراحی الگوریتم #سوالات برنامه‌نویسی