الگوریتمستان - برنامه‌نویسی، طراحی الگوریتم و آمادگی مسابقات برنامه‌نویسی
الگوریتمستان
کاربران حاضر در وب‌گاه: ۱ کاربر - عنوان‌ و توضیح تمامی نوشته‌های وب‌گاه را در نقشه‌ی وب‌گاه ببینید.
جستجو در نوشته‌های وب‌گاه:   
تعداد:  ۴۰

میانگین:  ۴.۰۰  از  ۵.۰۰
امروز:  ۴ بازدید

۲۴ ساعت گذشته:  ۱۱ بازدید

۷ روز گذشته:  ۹۴ بازدید

۳۰ روز گذشته:  ۳۷۳ بازدید
الگوریتمستان در تلگرام

Google Plus           Twitter

Cloob           FaceBook
بررسی مسأله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
معرفی الگوریتم جستجوی اول عمق (DFS) برای پیمایش گراف و کاربردهای آن به همراه قطعه کد به زبان برنامه‌نویسی ++C
آشنایی با الگوریتم دایکسترا برای یافتن کوتاهترین مسیر تک‌مبدأ در گراف وزن‌دار بدون یال منفی با قطعه کد به زبان ++C
عناوین بخشی از مباحث پرکاربرد در سوالات مسابقات برنامه‌نویسی
بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه‌ی آن با روش تقسیم و حل و روش برنامه‌نویسی پویا
آشنایی با الگوریتم استراسن برای محاسبه‌‌ی حاصلضرب ماتریس‌ها
آشنایی با کلاس‌های حافظه و کاربرد آنها در زبان ++C
نوشته‌های محبوب بازدیدکنندگان
بررسی الگوریتم‌های محاسبه‌ی دنباله‌ی اعداد فیبوناچی و کارایی آنها
بررسی مسأله‌ی Simple Addition از سوالات آمادگی مسابقات برنامه‌نویسی
آشنایی با الگوریتم دایکسترا برای یافتن کوتاهترین مسیر تک‌مبدأ در گراف وزن‌دار بدون یال منفی با قطعه کد به زبان ++C
معرفی متغیرهای مرجع در زبان برنامه‌نویسی ++C و آشنایی با مهمترین کاربردهای آنها
آشنایی با روش حریصانه و کاربردهای آن مانند مسأله‌ی خرد کردن پول
معرفی کتاب Art of Programming Contest برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود نسخه‌ی الکترونیکی
بحث در مورد مسأله‌ی کاشیکاری یا فرش کردن زمین با موزاییک به روش تقسیم و حل
نوشته‌ها از این دسته
بررسی مسأله‌ی تاریخچه‌ی جدول (Grid History)، از سوالات مسابقات برنامه‌نویسی بیان
آشنایی با روش مرتب‌سازی حبابی و بحث در مورد عملکرد آن، با قطعه کد به زبان برنامه‌نویسی ++C
بررسی مسأله‌ی Simple Addition از سوالات آمادگی مسابقات برنامه‌نویسی
آشنایی با الگوریتم فلوید-وارشال برای یافتن کوتاهترین مسیرهای گراف با قطعه کد نمونه به زبان برنامه‌نویسی ++C
بررسی مسأله‌ی آسانسورها (Elevators)، از سوالات مسابقات برنامه‌نویسی ACM
معرفی کتاب Art of Programming Contest برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود نسخه‌ی الکترونیکی
معرفی الگوریتم جستجوی اول عمق (DFS) برای پیمایش گراف و کاربردهای آن به همراه قطعه کد به زبان برنامه‌نویسی ++C

ضرب استراسن - الگوریتمستان
الگوریتمستان
4014.005.00
  »  


       

آشنایی با الگوریتم استراسن برای محاسبه‌‌ی حاصلضرب ماتریس‌ها

http://www.aachp.ir
آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «ضرب استراسن» آبان ماه 1386 از طریق وب‌گاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وب‌گاه الگوریتمستان) منتشر شده بود.

همه‌ی ما با تعریف ضرب ماتریس‌های مربعی آشنایی داریم. حاصلضرب ماتریس‌های مربعی 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} \]

      

    همانگونه که از تعریف پیداست، برای محاسبه‌ی هر درایه نیاز به n عمل ضرب داریم. بنابراین برای محاسبه‌ی تمامی n2 درایه‌ی ماتریس C به n3 عمل ضرب نیاز خواهیم داشت. یعنی الگوریتم ضرب ماتریس‌ها با تعریف اصلی آن از مرتبه‌ی ( O( n3 است.

    قبل از ادامه‌ی بحث به مثال زیر توجه کنید:

      

\[ A = \begin{pmatrix} 1 & 2 & 0 \\ 5 & 1 & 9 \\ -2 & 2 & 4 \end{pmatrix} \; \leftrightarrow \; A^\prime \begin{pmatrix} 1 & 2 & 0 & 0 \\ 5 & 1 & 9 & 0 \\ -2 & 2 & 4 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} \] \[ B = \begin{pmatrix} -1 & 2 & 3 \\ 0 & 6 & 5 \\ 10 & 3 & 1 \end{pmatrix} \; \leftrightarrow \; B^\prime \begin{pmatrix} -1 & 2 & 3 & 0 \\ 0 & 6 & 5 & 0 \\ 10 & 3 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} \] \[ C = A \times B = \begin{pmatrix} -1 & 14 & 13 \\ 85 & 43 & 29 \\ 42 & 20 & 8 \end{pmatrix} \; \leftrightarrow \; C^\prime = A^\prime \times B^\prime = \begin{pmatrix} -1 & 14 & 13 & 0 \\ 85 & 43 & 29 & 0 \\ 42 & 20 & 8 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} \]

      

    این مثال نشان می‌دهد که اضافه کردن سطرها و ستون‌های صفر به ماتریس، تاثیری در جواب نهایی حاصلضرب ندارد. این مطلب را به صورت منطقی و عبارات ریاضی هم می‌توان ثابت کرد.

    حال فرض کنید n توانی از عدد دو باشد. اگر اینطور نبود با اضافه کردن تعداد مناسبی از سطرها و ستون‌های صفر مرتبه‌ی ماتریس‌ها را به توانی از عدد 2 می‌رسانیم. سپس هر کدام از ماتریس‌های A و B را به چهار زیر ماتریس به فرم زیر تقسیم می‌کنیم:

      

\[ \begin{pmatrix} A_{11} & A_{12}\\ A_{21} & A_{22} \end{pmatrix} \qquad , \qquad \begin{pmatrix} B_{11} & B_{12}\\ B_{21} & B_{22} \end{pmatrix} \]

      

    به راحتی می‌توان ثابت کرد:

      

\[ C = A \times B = \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} \]

      

    اما آیا این تقسیم‌بندی تاثیری در بهینه شدن تعداد محاسبات دارد؟

    فرض کنیم ( T( n تعداد ضربهای لازم برای محاسبه‌ی حاصلضرب این دو ماتریس - با استفاده از زیرماتریس‌ها - باشد. پس داریم:

      

\[ T(n) = 8 \; T \Big( \frac{n}{2} \Big) \qquad , \qquad T(1) = 1 \]

      

    با حل این رابطه‌ی بازگشتی به نتیجه‌ی زیر می‌رسیم:

      

\[ T(n) =  8 \; T \Big( \frac{n}{2} \Big) =  8^2 \; T \Big( \frac{n}{2^2} \Big) = \cdots =  8^k \; T \Big( \frac{n}{2^k} \Big) \] \[ n = 2 ^ k \; \Rightarrow \; T(n) = 8 ^ k \; T( \frac{n}{n} ) = {(2^3)}^k \; T(1) = {(2^k)}^3 \times 1 = n ^ 3 \]

      

    که نشان می‌دهد همچنان n3 عمل ضرب برای محاسبه‌ی حاصلضرب نیاز است.

    ولکر استراسن با بررسی‌هایی که انجام داد، الگوریتم تقسیم و غلبه‌ای برای ضرب ماتریس‌ها با استفاده از تقسیم‌بندی ارائه داد که به جای هشت عمل ضرب در هر مرحله، هفت عمل نیاز دارد. به این ترتیب:

      

\[ T^\prime(n) =  7 \; T^\prime \Big( \frac{n}{2} \Big) =  7^2 \; T^\prime \Big( \frac{n}{2^2} \Big) = \cdots =  7^k \; T^\prime \Big( \frac{n}{2^k} \Big) \] \[ n = 2 ^ k \; \Rightarrow \; T^\prime(n) = 7 ^ k \; T^\prime( \frac{n}{n} ) = {(2^{log_27})}^k \; T^\prime(1) = {(2^k)}^{log_27} \times 1 = n ^ {log_27} \]

      

    در نتیجه مرتبه‌ی اجرای الگوریتم به ( O( n2.81 تبدیل می‌شود. به عنوان مثال اگر n برابر 1024 باشد:

      

\[ n = 1024 = 2^{10} \Rightarrow k = 10 \] \[ T(1024) = 8 ^{10} = 1073741824 \] \[ T^\prime(1024) = 7 ^{10} = 282475249 \] \[ \frac{T(1024)}{T^\prime(1024)} \simeq 3.8 \]

      

    یعنی در این حالت زمان محاسبه‌ی حاصلضرب به روش استراسن نسبت به حالت عادی نزدیک به چهار برابر کمتر می‌شود.

    در روش استراسن ماتریس‌های زیر که همه از مرتبه‌ی n / 2 هستند از روی زیرماتریس‌های ماتریس‌های A و B ساخته می‌شوند:

      

\[ P=(A_{11}+A_{22})(B_{11}+B_{22}) \] \[ Q=(A_{21}+A_{22})B_{11} \] \[ R=A_{11}(B_{12}-B_{22}) \] \[ S=A_{22}(B_{21}-B_{11}) \] \[ T=(A_{11}+A_{12})B_{22} \] \[ U=(A_{21}-A_{11})(B_{11}+B_{12}) \] \[ V=(A_{12}-A_{22})(B_{21}+B_{22}) \]

      

    که تنها هفت عمل ضرب برای محاسبه نیاز دارند. استراسن ثابت کرد زیرماتریس‌های متناظر ماتریس حاصلضرب از رابطه‌های زیر به دست می‌آید:

      

\[ C_{11}=P+S-T+V \] \[ C_{12}=R+T \] \[ C_{21}=Q+S \] \[ C_{22}=P-Q+R+U \]

      

    تقسیم کردن ماتریس‌ها به چهار بخش - برای محاسبه به روش استراسن - تا زمانی ادامه پیدا می‌کند که مرتبه‌ی ماتریس‌ها به 2 برسند. وقتی به این مرحله رسیدیم، با تعریف اصلی ضرب ماتریس‌ها حاصلضرب را محاسبه می‌کنیم.

    نکته: علت اینکه چرا تنها عمل ضرب را بررسی کردیم این بود که عمل ضرب هزینه‌ی زمانی بیشتری نسبت به عمل جمع و تفریق دارد. اگرچه می‌توان ثابت کرد که این روش به ازای مقادیر بزرگ n از نظر میزان عمل جمع و تفریق هم کاراتر است.


این نوشته آخرین بار در تاریخ مورد بازنویسی علمی قرار گرفته است.
امتیاز نوشته
1 2 3 4 5
نوشته‌های مرتبط
بررسی مسأله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
بررسی الگوریتم‌های محاسبه‌ی دنباله‌ی اعداد فیبوناچی و کارایی آنها
بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه‌ی آن با روش تقسیم و حل و روش برنامه‌نویسی پویا
بررسی روش‌های بسط لاپلاس، گاوس، فرمول تحویل و ساروس، برای محاسبه‌ی دترمینان ماتریس مربعی و پیچیده‌گی زمانی آنها
آشنایی با روش مرتب‌سازی ادغامی با قطعه کدهایی به زبان برنامه‌نویسی ++C
آشنایی با روش مرتب‌سازی سریع، همراه با قطعه کدهای نمونه به زبان برنامه‌نویسی ++C
آشنایی با دنباله‌ی عددی کاتالان، کاربردها و روش پیاده‌سازی آن به زبان برنامه‌نویسی ++C
بررسی روش‌های مختلف محاسبه‌ی ضرایب دوجمله‌ای نیوتن یا ترکیب دو عدد با قطعه کد به زبان برنامه‌نویسی ++C
بررسی مسأله‌ی برج هانوی و روش‌های حل بازگشتی و غیربازگشتی آن
بحث در مورد مسأله‌ی کاشیکاری یا فرش کردن زمین با موزاییک به روش تقسیم و حل
آشنایی با درخت جستجوی دودویی (Binary Search Tree) و عملیات جستجو و درج و حذف گره
آشنایی با روش Divide and Conquer (تقسیم و حل / تقسیم و غلبه) و کاربردهای آن در مرتب‌سازی، جستجو و حل مسائل الگوریتمی دیگر
پیوند کوتاه صفحه تأیید و پیشنهاد نوشته
به اشتراک‌گذاری نوشته
اشتراک‌گذاری در LinkedIn         ارسال با Telegram         اشتراک‌گذاری در Twitter         اشتراک‌گذاری در Facebook         Google Plus

اشتراک‌گذاری در فیس‌نما         ارسال با پست الکترونیک         اشتراک‌گذاری در Digg         Cloob         اشتراک‌گذاری در StumbleUpon
QR-Code صفحه
دسته‌بندی چاپ نوشته
‌برچسب‌ها
ارسال پیام
» acm

پنجشنبه، ۱۹ شهریور ماه ۱۳۸۸، ساعت ۱۰:۵۵
سلام رفیق برا چی وقتی باهنر قبول شدی نرفتی


شنبه، ۲۱ شهریور ماه ۱۳۸۸، ساعت ۱۸:۲۶
مسعود اقدسی‌فام:
سلام رفيق
خدمت سربازي اجازه ادامه تحصيل بهم نداد. تا تموم شدن اين دوره حق ادامه تحصيل ندارم.
ممنون كه به يادم بودي. [«06»]

» پرستو

سه‌شنبه، ۲۱ مهر ماه ۱۳۸۸، ساعت ۱۳:۵۰
به که با این کارت لطفی بزرگ به من و بشریت می کنی . خیلی بخشنده ای که علمتو در اختیار دیگران بدون هیچ چشم داشتی میگذاری واقعا خسته نباشید . یه روز جواب این همه مهربونی هاتو از خدا می گیری. چون مشکل منو حل کردی .

» راضیه

سه‌شنبه، ۵ آبان ماه ۱۳۸۸، ساعت ۱۹:۱۸
سلام ببخشید من برنامه ضرب اعداد بزرگ را به روش تقسیم وحل میخوام اگه دارین ممنون میشیم تا 5 شنبه برام بزارین10


دوشنبه، ۱۱ آبان ماه ۱۳۸۸، ساعت ۱۹:۱۲
مسعود اقدسی‌فام:
سلام
اگر قوانین ارسال پیام رو مطالعه کرده بودید متوجه می شدید که به درخواست برنامه آماده پاسخی داده نمی شه.
ممنون از حضورتون.

» zebel

جمعه، ۱۶ بهمن ماه ۱۳۸۸، ساعت ۲۱:۴۷
سلام
میشه الگوریتم ضرب دو ماتریس به روش استراسن رو پیاده سازی کنید؟
یا الگوریتم ضرب اعداد صحیح بسیار بزرگ را (به روش تقسیم و غلبه) پیاده سازی کنید.
اینا پروژه دانشگاهمه
متشکرم

» goli

دوشنبه، ۱۷ اسفند ماه ۱۳۸۸، ساعت ۱۱:۰۰
04خیلی چرت بود

» همتا

سه‌شنبه، ۱۷ فروردین ماه ۱۳۸۹، ساعت ۱۵:۱۶
سلام دوست عزیز
راه حلی به نظرتون میرسه که طول آرایه رو بشه تو پشته نگهداری کرد؟

» رضا

سه‌شنبه، ۶ مهر ماه ۱۳۸۹، ساعت ۱۳:۲۵
احسن   جالب بود

» سحر

دوشنبه، ۸ اسفند ماه ۱۳۹۰، ساعت ۰۱:۰۳
salam, merc az matalebe por mohtavatoon, mikhastam khahesh konam algoritme zarbe matris ro ham be zabane ++c benevisin, man kheyli gashtam vali peyda nakardam , mamnoon

» lili

یکشنبه، ۱۴ آبان ماه ۱۳۹۱، ساعت ۱۰:۵۴
سلام.
ممنون میشم اگه سوالما تا 3شنبه جواب بدین اخرین وقتشه.
ضرب دو ماتریس 3*3 به روش استراسنوساده وتعداد جمع ها وضربهادر هر یک کدام روش بهتر است؟؟؟؟06

» 1

شنبه، ۱۸ آبان ماه ۱۳۹۲، ساعت ۱۷:۴۲
0505050505050505

» سعید

سه‌شنبه، ۵ خرداد ماه ۱۳۹۴، ساعت ۱۶:۴۸
خیلی بد بود چی بود این؟ضرب اترایست فقط همینه داداشه من؟ 10 10 11 11

» فاطمه

دوشنبه، ۱۱ آبان ماه ۱۳۹۴، ساعت ۲۱:۳۰
خیلی عالی توضیح دادین. مختصر و مفید. خیلی ممنون 12



دوست عزیزم، لطفا پیش از ارسال پیام به موارد زیر توجه داشته باشید:

۱- تا حد ممکن از حروف فارسی برای نگارش پیام فارسی استفاده کنید. امکان ارسال پیام لاتین و کدهای برنامه‌نویسی با چیدمان چپ به راست نیز وجود دارد.
۲- به درخواست پروژه‌های آماده و موارد مشابه پاسخ داده نخواهد شد.
۳- از قرار دادن هرگونه نشانی یا شماره تماس در متن پیام خودداری کنید.
۴- از ارسال پیام‌های تبلیغاتی خودداری کنید.
۵- از ارسال سوال و پیام غیرمرتبط با این نوشته خودداری کنید.
۶- لطفا نظر خود را در مورد این نوشته با ثبت امتیاز مشخص نمایید.

پیشاپیش از همکاری شما سپاسگزارم.


نام:  
پست الکترونیک
وب‌گاه:
امتیاز:  
متن پیام: right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left  
پیوندهای مرتبط
تمامی نوشته‌های وب‌گاه الگوریتمستان تحت قرارداد باز Creative Commons Attribution-ShareAlike v4.0 هستند.