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

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

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

ماتریس

»

مسئله

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