صفحه اصلی

صفحه شخصی مسعود اقدسی‌فام
الگوریتمستان - آموخته‌های من از دنیای برنامه‌نویسی و طراحی الگوریتم
● وب‌سایت آرشیو سوالات منطقه‌ای و جهانی مسابقات برنامه‌نویسی ACM-ICPC، با امکان ارسال پاسخ و بررسی جواب.
● علاقمندان به شرکت در مسابقات برنامه‌نویسی و حل سوالات الگوریتمی می‌توانند از این وب‌سایت معتبر به همراه کتاب معرفی شده جهت تمرین و آمادگی بیشتر استفاده کنند.

الگوریتمستان
آشنایی با توابع دوست کلاس در زبان برنامه‌نویسی ++C و کاربرد آنها در سربارگذاری عملگرها
الگوریتمستان
آشنایی با قالب‌ها به عنوان یکی از امکانات متمایز ++C از C
الگوریتمستان
بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه آن با روش تقسیم و حل و روش برنامه‌نویسی پویا
الگوریتمستان
آشنایی با آرایه پویای یک بعدی و کاربردهای آن در زبان برنامه‌نویسی ++C
الگوریتمستان
بررسی معمای هشت وزیر یا n وزیر و راهبرد عقبگرد برای حل مساله
الگوریتمستان
آشنایی با درخت Heap (هیپ، هرم یا کپه) به عنوان یکی از ساختمان های داده پرکاربرد و بررسی روش ساخت، درج گره و حذف گره و ارائه کد نمونه به زبان برنامه‌نویسی ++C
الگوریتمستان
آشنایی با حلقه‌های تکرار در زبان برنامه‌نویسی ++C و دستورات کنترلی مورد استفاده در آن
الگوریتمستان
معرفی متغیرهای مرجع در زبان برنامه‌نویسی ++C و آشنایی با مهمترین کاربردهای آنها
الگوریتمستان
آشنایی با مفهوم و عملکرد اشاره‌گرها در زبان برنامه‌نویسی ++C و ارائه مثالهایی از کاربرد آن
الگوریتمستان
بررسی مساله برج هانوی و روش‌های حل بازگشتی و غیربازگشتی آن
الگوریتمستان
آشنایی با روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا - Dynamic Programming) به عنوان یکی از روش‌های پر کاربرد طراحی الگوریتم و یافتن راه حل بهینه مسائل، و روش محاسبه دنباله فیبوناچی
الگوریتمستان
آشنایی با روش مرتب‌سازی ادغامی با قطعه کدهایی به زبان برنامه‌نویسی ++C
الگوریتمستان
بررسی روش‌های مختلف محاسبه ضرایب دوجمله‌ای نیوتن یا ترکیب دو عدد با قطعه کد به زبان برنامه‌نویسی ++C
الگوریتمستان
بررسی مساله مربی ناامید، از سوالات مسابقات برنامه‌نویسی ACM

»   ضرب استراسن چهارشنبه، 4 شهریور ماه 1388، ساعت 14:51

مطلبی که می‌خوانید، ویراست دوم مطلبی است که نسخه اولیه آن با عنوان "ضرب استراسن" از طریق وب‌سایت برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وب‌سایت الگوریتمستان) منتشر شده بود.

همه ما با تعریف ضرب ماتریس‌های مربعی آشنایی داریم. حاصلضرب ماتریس‌های مربعی A و B به صورت زیر تعریف می‌شود:

 

ضرب استراسن

 

یه عنوان مثال، در حالت n = 2 داریم:

 

ضرب استراسن

 

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

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

 

ضرب استراسن

 

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

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

 

ضرب استراسن

 

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

 

ضرب استراسن

 

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

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

 

ضرب استراسن

 

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

 

ضرب استراسن

 

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

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

 

ضرب استراسن

 

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

 

ضرب استراسن

 

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

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

 

ضرب استراسن

 

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

 

ضرب استراسن

 

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

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

‌چاپ مطلب
نسخه قابل چاپ مشاهده نسخه قابل چاپ و ارسال به چاپگر
آمار
تعداد امتیازهای ثبت شده:  33 ،  میانگین امتیازهای ثبت شده:  3.94 از 5.00
امتیاز مطلب
1 2 3 4 5
ارسال پیام
» acm

پنجشنبه، 19 شهریور ماه 1388، ساعت 10:55
سلام رفیق برا چی وقتی باهنر قبول شدی نرفتی

» مسعود اقدسی‌فام

شنبه، 21 شهریور ماه 1388، ساعت 18:26
سلام رفيق
خدمت سربازي اجازه ادامه تحصيل بهم نداد. تا تموم شدن اين دوره حق ادامه تحصيل ندارم.
ممنون كه به يادم بودي.

» پرستو

سه‌شنبه، 21 مهر ماه 1388، ساعت 13:50
به که با این کارت لطفی بزرگ به من و بشریت می کنی . خیلی بخشنده ای که علمتو در اختیار دیگران بدون هیچ چشم داشتی میگذاری واقعا خسته نباشید . یه روز جواب این همه مهربونی هاتو از خدا می گیری. چون مشکل منو حل کردی .

» مسعود اقدسی‌فام

چهارشنبه، 22 مهر ماه 1388، ساعت 12:48
ممنون پرستو جان، لطف داری. خوشحالم که تونستم کمکی بکنم.

» راضیه

سه‌شنبه، 5 آبان ماه 1388، ساعت 19:18
سلام ببخشید من برنامه ضرب اعداد بزرگ را به روش تقسیم وحل میخوام اگه دارین ممنون میشیم تا 5 شنبه برام بزارین

» مسعود اقدسی‌فام

دوشنبه، 11 آبان ماه 1388، ساعت 19:12
سلام
اگر قوانین ارسال پیام رو مطالعه کرده بودید متوجه می شدید که به درخواست برنامه آماده پاسخی داده نمی شه.
ممنون از حضورتون.

» zebel

جمعه، 16 بهمن ماه 1388، ساعت 21:47
سلام
میشه الگوریتم ضرب دو ماتریس به روش استراسن رو پیاده سازی کنید؟
یا الگوریتم ضرب اعداد صحیح بسیار بزرگ را (به روش تقسیم و غلبه) پیاده سازی کنید.
اینا پروژه دانشگاهمه
متشکرم

» goli

دوشنبه، 17 اسفند ماه 1388، ساعت 11:00
خیلی چرت بود

» همتا

سه‌شنبه، 17 فروردین ماه 1389، ساعت 15:16
سلام دوست عزیز
راه حلی به نظرتون میرسه که طول آرایه رو بشه تو پشته نگهداری کرد؟

» رضا

سه‌شنبه، 6 مهر ماه 1389، ساعت 13:25
احسن   جالب بود

» سحر

دوشنبه، 8 اسفند ماه 1390، ساعت 01:03
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

یکشنبه، 14 آبان ماه 1391، ساعت 10:54
سلام.
ممنون میشم اگه سوالما تا 3شنبه جواب بدین اخرین وقتشه.
ضرب دو ماتریس 3*3 به روش استراسنوساده وتعداد جمع ها وضربهادر هر یک کدام روش بهتر است؟؟؟؟

» 1

شنبه، 18 آبان ماه 1392، ساعت 17:42



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

1- تا حد ممکن از حروف فارسی برای نگارش پیام خود استفاده کنید. امکان ارسال پیام لاتین و کدهای برنامه‌نویسی با چیدمان چپ به راست نیز وجود دارد.
2- به درخواست پروژه‌های آماده و موارد مشابه پاسخ داده نخواهد شد.
3- از قرار دادن هرگونه نشانی یا شماره تماس در متن پیام خودداری کنید.
4- از ارسال پیام‌های تبلیغاتی خودداری کنید.
5- از ارسال سوال و پیام غیرمرتبط با مطلب ارائه شده خودداری کنید.
6- لطفا نظر خود را در مورد مطلب ارائه شده، با ثبت امتیاز مشخص نمایید.

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


نام:  
پست الکترونیک
وب‌سایت:
متن پیام: