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

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

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

ماتریس

»

مسئله

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