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

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

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

ماتریس

»

مسئله

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