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

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

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

ماتریس

»

مسئله

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