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

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

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

ماتریس

»

مسئله

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