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

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

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

ماتریس

»

مسئله

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