کتاب ارشد درس و کنکور ساختمان گسسته | گسترش علوم پایه

درباره‌ی کتاب درس و کنکور ساختمان گسسته حمیدرضا مقسمی

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

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

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

بخشی از کتاب درس و کنکور ساختمان گسسته حمیدرضا مقسمی

مثال6

ماتریس های مجاورتی برای گرافی بدون جهت و جهتدار را در زیر نوشته ایم: در واقع ماتریس مجاورت مشخص می سازد آیا بین دو گره دلخواه مسیر مستقیمی وجود دارد یا خیر.  در ماتریس گراف وزن دار، وزن هر لبه به عنوان درایه ماتریس گراف در نظر گرفته می شود.

نکته 1: همان طور که در مثال بالا مشاهده می کنید، ماتریس مجاورتی برا یک گراف بدون جهت همواره متقارن است ولی ماتریس مجاورتی یک گراف جهت دار ممکن است متقارن نباشد. در گراف ساده که طرقه ندارد، درایه های قطر اصلی همگی صفر هستند.

نکته 2: برای گراف بدون جهت درجه هر رأس مانند i، مجموع عناصر سطحی آن است و برای یک گراف جهت دار، مجموع سطری، درجه خارجی و مجموع ستونی درجه وارده خواهد بود.

نکته 3: تعداد "1" ها در ماتریس مجاورتی گراف بدون جهت دو برابر تعداد یال ها و در گراف جهت دار برابر تعداد یال ها می باشد. نکته 4: اگر  A ماتریس مجاورتی یک گراف ساده باشد، درایه های قطر اصلی ماتریس A2 = A x A مساوی درجه رئوس آن گراف خواهند بود. تذکر: برای نمایش یک گراف میتوان از ماتریس یرخورد یا تلاقی (incidence) نیز استفاده کرد. در این روش گره ها در سطرها و لبه ها در ستون ای ماتریس قرار می گیرند. اگر رأس i لبه j را تلاقی کند آنگاه M [I , j] =1 خواهد بود.

مثال 7

در شکل زیر ماتریس تلاقی گراف را نوشته ایم: بدیهی است در ماتریس فوق در هر ستون دقیقاً دو عنصر 1 وجود دارد و تعداد یک های هر سطر نیز برابر درجه آن رأس است.

تمرین اول: تست ها با عنوان « تعاریف اولیه و نمایش گراف» را حل کنید. مسیر: هر دنباله از لبه های یک گراف (جهت دار یا غیر جهت دار) که گره پایانی هر لبه، گره آغازی لبه بعدی باشد، یک «مسیر» خوانده می شود. تعداد یال های مسیر را «طول مسیر» می گوییم.

کتاب درس و کنکور ساختمان گسسته (کارشناسی ارشد) تألیف حمیدرضا مقسّمی توسط انتشارات گسترش علوم پایه به چاپ رسیده است.

فهرست

• تمامــی گــرایش هــای کامپیــوتر
• نویسنده: حمیدرضا مقسّمی
• انتشارات: گسترش علوم پایه