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

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

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

ماتریس

»

مسئله

ماتریس مربعی با ابعاد $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) \]

ادامه ...

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

   

 

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