آموزش ساختمان داده قسمت چهارم

سعید ضیادید 1395/1/23 1363

آموزش ساختمان داده  قسمت چهارم

به نام خدا

سلام عرض میکنم  خدمت همه ی شما دوستان عزیز

با جلسه ی چهارم از سری آموزش های ساختمان داده در خدمت شما هستم.

در این جلسه قصد داریم درباره ی درباره ی ماتریس ها و ارتباط اونها با آرایه ها صحبت کنیم ، همچنین نکاتی رو درباره ی آرایه ها و رشته ها بیان خواهیم کرد .

ماتریس ها اشیای مهمی در ریاضیات محسوب میشن که در بسیاری از مسائل کاربرد دارند . ماتریس ها رو میشه به صورت آرایه های دو بعدی mدرn یا جدولی باm سطر و n ستون تعریف کرد .به هر عنصر یک ماتریس ، یک درایه میگن و واضح هست که تعداد درایه های یک ماتریس MxN برابر با MN خواهد بود . برخی از ماتریس های مهم عبارت هستند از : ماتریس های مربعی ، ماتریس های مثلثی و ماتریس های قطری .

اعمال مختلفی هم روی ماتریس ها انجام میشه مثل جمع و تفریق و ضرب و ... . که یکی از مهمترین اعمال هم همین ضرب ماتریس هاست . برای اینکه بخوایم دو ماتریس A و B رو در هم ضرب کنیم ، باید تعداد ستون های ماتریس A با تعداد سطر های ماتریس B برابر باشه . مثلا میشه یک ماتریس MxN رو در یک ماتریس NxK ضرب کرد که ماتریس حاصلضرب یک ماتریس MxK خواهد بود . ضرب ماتریس دارای خاصیت "شرکت پذیری " و فاقد خاصیت "جابه جایی" هست .

تعداد حالات شرکت پذیری ضرب n+1 ماتریس برابر هست با :

ترکیب  n از 2n تقسیم بر n+1

مثلا تعداد حالات شرکت پذیری ضرب 4 ماتریس برابر هست با 5 .

 

حالا اون ماتریس هایی که به عنوان ماتریس های مهم خدمتتون معرفی کردم ، دارای یک خاصیت هایی هستن در ضرب . مثلا حاصلضرب دو تا ماتریس بالا مثلثی ، یک ماتریس بالا مثلثیه و به همین ترتیب حاصلضرب دوتا ماتریس پایین مثلثی یک ماتریس پایین مثلثیه .

در جلسه ی قبلی درباره ی چند جمله ای های اسپارس با هم صحبت کردیم . بنابراین تا حدی با مفهوم " اسپارس" آشنا هستیم . پس الان میتونیم مطالبی رو درباره ی ماتریس های اسپارس بگیم . ماتریس اسپارس یا پراکنده ، به ماتریسی میگن که تعداد قابل توجهی از درایه هاش عدد صفر باشن . مثلا فرض کنید یک ماتریس 5 در 5 داشته باشیم که فقط 4 تا درایه ی غیر صفر داشته باشه . خب مشخصه که این ماتریس ، یک ماتریس خلوت به حساب میاد . در تصویر زیر نوع داده ی انتزاعی ماتریس اسپارس رو مشاهده میکنید .

توابع جمع و ضرب و ترانهاده هم در این ADT لحاظ شده اند.

اما اول از هرچیز باید بتونیم یک نوع نمایش خوب برای ماتریس ها پیدا کنیم . خب یک راه معمول برای نمایش ماتریس ها ، استفاده از آرایه های 2 بعدی هست . خب برای این نوع نمایش ما تک تک درایه ها و عناصر رو داریم ذخیره میکنیم . مثلا فرض کنید برای یک ماتریس 5 در 5 باید تمام 25 عنصر رو نمایش بدیم و ذخیره کنیم . همچننین مثلا اسم آرایه اگه باشه A عنصر A[2][3]

 نشان دهنده ی درایه ای هست که توی سطر سوم و ستون چهارم ماتریس باشه . ( خونه های آرایه رو از صفر شروع کردیم ولی ماتریس رو از یک درنظر گرفتیم . ) . حالا فرض کنید یک ماتریس 2000 در 2000 داریم . خب معلومه که این ماتریس 4 میلیون درایه داره . حالا اگه فقط 500 تا از این درایه ها غیر صفر باشن و به نوعی اسپارس به حساب بیان ، آیا لازمه همه ی درایه نشون داده بشن ؟ خب کلی درایه ی صفر داریم . پس به نظر میاد اگه مکانیزمی باشه که ما فقط عناصر غیر صفر رو ذخیره کنیم و نمایش بدیم ، خیلی بهتر خواهد بود .

یک راه دیگه هم برای نمایش اینه که ما بیایم از 3 تایی <مقدار،ستون، سطر> استفاده کنیم . یعنی از آرایه های 3 گانه استفاده کنیم که یک نوع نمایش مناسب برای ماتریس های اسپارس به حساب میاد . اولویت اول ما هم بر اساس ترتیب سطری و سپس ستونی خواهد بود . با تمام مطالبی که گفتیم میتونیم مطلب زیر رو داشته باشیم .

حالا بیایم یک مثال از این نوع نمایش رو با هم ببینیم .

شکل زیر هم یک برنامه ی مناسب و سریع برای محاسبه ی ترانهاده ی یک ماتریس هست :

یک نکته هم درباره ی ضرب ماتریس ها بگیم . اونم اینه که حتما میدونید برای ضرب 2 ماتریس به 3 حلقه ی تکرار نیاز داریم . تعداد ضرب های لازم برای اینکار برابر با تعداد تکرار این حلقه هاست . یعنی اگه دو ماتریس A و B بخوان در هم ضرب بشن و به ترتیب MxN و NxK باشن ، به تعداد MNK ضرب نیاز داریم .یک مثال مفید رو هم ببینیم :

مثال : فرض کنید ماتریس A یک ماتریس 3در 10 ماتریس B یک ماتریس 10 در 5 و ماتریس C یک ماتریس 5در 4 باشه . باتوجه به حالت های مختلف شرکت پذیری ، ضرب های حاصلضرب این 3 ماتریس ، چنتا هست ؟

A(BC)=(3.10.4)+(10.5.4)=120+200=320

(AB)C=(3.10.5)+(3.5.4)=150+60=210

از مثال بالا متوجه میشیم که حالت های مختلف شرکت پذیری ، باعث ایجاد تفاوت در تعداد ضرب های لازم میشه . پس میشه درباره ی بهینگی هم حرف زد چون تعداد ضرب کمتر ، یعنی زمان اجرای کمتر و برنامه ی سریعتر . (البته ممکنه در تابع پیچیدگی زمانی تاثیر چندانی نذاره ولی به هرحال تاحدی تفاوت ایجاد میکنه در زمان اجرا )

حالا بیایم یکسری نکات دیگه درباره ی آرایه ها بگیم . ببینید دوستان ، آرایه ی A رو میشه به شکل های زیر نشون داد :

برای محاسبه ی فضای یک آرایه هم کافیه تعداد عناصر آرایه رو در فضای نوع عناصر آرایه ضرب کنیم .

مثلا فرض کنید آرایه ی مقابل رو داریم :

[5...2    3....1-[ و همه ی عناصر اونهم اعداد صحیح هستن . مشخصه تعداد عناصر این آرایه 20 تا هستن و از اونجایی که هر فضای هر عدد صحیح 2 بایت هست ، پس فضای کل آرایه ، 40 بایت خواهد بود .

خب حالا یه توضیح کوتاه هم درباره ی نوع داده ی انتزاعی رشته میدیم . رشته رو میشه به صورت S=a1a2....an نشون داد که هر کدوم از a ها کاراکتری از مجموعه کاراکتر های زبان برنامه نویسی هستن . n طول رشته هست و اگه n=0 باشه ، رشته تهی خواهد بود . چندین عمل هم میشه برای رشته ها تعریف کرد . مثل ایجاد یک رشته ، کپی کردن ، الحاق و خواندن و چاپ و ...... در تصویر زیر ADT مربوط به رشته رو میبینید :

 

خب برای این جلسه کافیه .. ان شاءالله در جلسه ی بعد با ساختار های داده ای "پشته و صف " در خدمت شما خواهیم بود . خدانگهدار

قسمت بعدی قسمت قبلی