<div dir="rtl">

# مبانی ترکیبیات

</div>

## Foundation of Combinatorics

<div dir="rtl">

| <div style="width:80px">مقطع:</div> | <div style="width:80px">کارشناسی</div> | <div style="width:80px">نوع درس:</div> | <div style="width:80px">نظری </div> |
| :---------------------------------- | --------------------------------------- | :------------------------------------- | -------------------------------------- |
| تعداد واحد: | ۳ | تعداد ساعت: | ۴۸ |
| پیش‌نیاز: | مبانی علوم ریاضی | هم‌نیاز: | - |
| حل تمرین: | دارد | آموزش تکمیلی: | سفر علمی آزمایشگاه نرم افزار سمینار کارگاه موارد دیگر: .............. |

**اهداف کلی :**
آشنایی با ساختارهای مختلف گسسته مانند ماتریس ها، گراف ها، مربع های لاتین، آشنایی با تفکر الگوریتمیک و مدل های محاسباتی ساده

**اهداف ویژه:**
دانشجو باید بتواند با مفاهیم و تکنیکهای اساسی ترکیبیاتی کار کند.

**سر فصل یا رئوس مطالب:**

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

` `

**فهرست منابع پیشنهادی**:

</div>

* ر . پ. گریمالدی، ریاضیات گسسته و ترکیبیاتی، ترجمه محمدعلی رضوانی و بیژن شمس، انتشارات فاطمی، 1377

<div dir="ltr">

* Anderson, Ian. A first course in combinatorial mathematics. Clarendon Press, 1989.
* Grimaldi, Ralph P. Discrete and Combinatorial Mathematics, 5/e. Pearson Education, India, 2006.

</div>