مبانی ترکیبیات
Foundations of Combinatorics
| نام درس: | مبانی ترکیبیات | مقطع: | کارشناسی |
|---|---|---|---|
| پیش‌نیاز: | مبانی علوم ریاضی | گروه درس: | تخصصی الزامی |
| هم‌نیاز: | ندارد | نوع درس: | نظری |
| تعداد واحد: | 3 | تعداد ساعت: | 48 |
| حل تمرین: | دارد |
سرفصل درس:
دوره سریع مفاهیم مجموعه‌ها، توابع، الگوریتم و منطق گزاره ها و جبر بول، شمارش شامل: مفاهیم اصلی، اصل لانه کبوتری، تبدیلها و ترکیب ها و ضرایب دوجمله ای، اصل شمول وعدم شمول، روابط بازگشتی،توابع مولد. روابط و انواع آنها: روابط و نمایش آنها، روابط هم ارزی و افزارها، روابط ترتیب جزئی و ترتیب کامل، بستار یک رابطه نسبت به خواص مختلف (این بخش با هماهنگی با درس " مبانی علوم ریاضی" ارائه می شود به نحوی که تکرار صورت نپذیرد). ماتریس ها: ماتریس ها از دیدگاه ترکیباتی، بالاخص برخی خواص مهم ماتریس های صفر و یک (آماده سازی برای بخش مربع های لاتین و گراف ها)، آشنایی با ماتریس های آدامار و برخی نتایج در این مورد. گراف ها و مدل های مبتنی بر آنها: معرفی مفهوم گراف با تاکید بر کاربردهای آن در مدلسازی (با چند مثال با نظر استاد)، آشنایی با مفاهیم اصلی نظریه گراف نظیر دور، مسیر، درجه، دنباله درجه ای، انواع اصلی گراف نظیر گراف های کامل، درخت ها، گراف های دوبخشی، گراف های اویلری و هامیلتونی و گراف های جهت دار و تورنمنت ها (با تاکید بر مثال و کاربردها)، تطابق های کامل و ماکزیمم (طرح الگوریتم و کاربردها)، رنگ آمیزی گراف ها و چند جمله ای رنگی (با ارائه مثال و الگوریتم). مربع های لاتین، طرح ها و هندسه های متناهی: آشنایی با تعریف و مفاهیم اصلی با تاکید بر ارتباط این مفاهیم (با ارائه مثال) و همچنین تاکید بر ارتباط این مفاهیم با مفاهیم قبلی طرح شده در درس نظیر گراف ها و همچنین ارائه چند مورد در این خصوص، ارائه مفهوم سیستمهای نمایندگی متمایز و همچنین طرح صورت قضیه فیلیپ هال و ارائه مثال و کاربرد در مربعها لاتین و چند کاربرد عملی (با نظر استاد).
منابع:
-
گریمالدی، ر. پ. (۱۳۷۷). ریاضیات گسسته و ترکیبیاتی، ترجمه محمدعلی رضوانی و بیژن شمس، انتشارات فاطمی.
-
Stein, C., Drysdale, R. L., & Bogart, K. (2011). Discrete Mathematics for Computer Scientists, Addison-Wesley, url: http://cslabcms.nju.edu.cn/problem_solving/images/1/1f/Discrete_Mathematics_for_Computer_Scientists.pdf
-
Haggard, G., Schlipf, J. S., & Whinston, A. B. (2006). Discrete Mathematics for Computer Scientists. Brooks/Cole Publishing. url: https://www2.cs.uh.edu/~arjun/courses/ds/DiscMaths4CompSc.pdf
-
Anderson, I. (1989). A first course in combinatorial mathematics. Clarendon Press.
-
Grimaldi, R. P. (2006). Discrete and Combinatorial Mathematics (5th ed.). Pearson Education India.
-
Harris, J. M., Hirst, J. L., & Mossinghoff, M. J. (2008). Combinatorics and Graph Theory. Springer. PDF: http://mezbanhabibi.ir/wp-content/uploads/2020/01/Combinatorics-and-Graph-theory.pdf
-
Cameron, P. J. (1996). Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press. Retrieved from https://webspace.maths.qmul.ac.uk/p.j.cameron/comb/
-
Brualdi, R. A. (2009), Introductory Combinatorics (5th Edition), Pearson Education. https://newsite.kashanu.ac.ir/Files/IntroductoryCombinatorics.pdf
-
Tucker, A. (2012). Applied Combinatorics. Wiley. url: https://www.wiley.com/en-sg/Applied+Combinatorics,+6th+Edition-p-9780470458389