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

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

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

ماتریس

»

مسئله

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