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

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

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

ماتریس

»

مسئله

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

ادامه ...

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

   

 

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