ساختارهای گسسته

کلیات

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

ریز مواد

شمارش (۳ جلسه)
- اصول اولیه‌ی شمارش، جایگشت‌ها و ترکیب‌ها
- ضرایب دوجمله‌ای، جایگشت‌ها و ترکیب‌های باتکرار
- اصل طرد و شمول، توزیع اشیا درون جعبه‌ها
منطق (۲ جلسه)
- منطق گزاره‌ها، گزاره‌های هم‌ارز، گزاره‌نماها، سورها
- اصول استنتاج، روش‌های اثبات
استقرای ریاضی (۲ جلسه)
- مراحل استقرا، قوی کردن فرض استقرا
- استقرای قوی، استقرای ساختاری، اصل خوش‌ترتیبی
مجموعه‌ها و توابع (۲ جلسه)
- عملگرهای مجموعه‌ای، مجموعه‌های شمارا و ناشمارا
- انواع توابع، ترکیب توابع، کاردینالیتی، قضیه‌ی شرودر-برنشتین
نظریه‌ی اعداد (۲ جلسه)
- بخش‌پذیری، لم بزو، الگوریتم اقلیدس، اعداد اول
- محاسبات پیمانه‌ای، تابع اویلر، قضیه‌ی فرما، رمزنگاری
اصل لانه‌ کبوتری (۱ جلسه)
- اثبات وجودی، مسائل عددی، مسائل هندسی
روابط بازگشتی (۳ جلسه)
- کاربردهای روابط بازگشتی، مسائل بازگشتی
- حل روابط بازگشتی (همگن و غیر همگن)
- توابع مولد، کاربرد در مسائل شمارشی و حل روابط بازگشتی
رابطه‌ها و ترتیب جزئی (۲ جلسه)
- رابطه‌ها و خواص آن‌ها، نمایش روابط، بستار رابطه‌ها
- مجموعه‌های مرتب جزئی، نمودار هاس، ترتیب توپولوژیکی
- مشبکه‌ها، جبر بول، خواص جبر بول
نظریه‌ی گراف‌ها (۵ جلسه)
- تعاریف اولیه، نمایش گراف‌ها، یک‌ریختی گراف‌ها
- مسیرها و همبندی، مسیرهای اویلری، قضیه‌ی اویلر
- دور همیلتنی، قضیه‌ی دیراک، رنگ‌آمیزی گراف‌ها
- گراف‌های مسطح، فرمول اویلر، رنگ‌آمیزی گراف‌های مسطح
- درخت‌ها و جنگل‌ها، درخت‌های فراگیر، درخت‌های فراگیر کمینه
مدل‌سازی محاسبات (۲ جلسه)
- زبان‌ها و ماشین‌ها، ماشین‌های با حالات متناهی، زبان‌های منظم
- ماشین تورینگ، تصمیم‌پذیری، تز چرچ-تورینگ

ارزیابی

ده سری تمرین نظری (بدون تحویل)
سه آزمون‌ (هر یک ۷ نمره)

مرجع اصلی

K. H. Rosen. Discrete Mathematics and Its Applications. 8th Edition, McGraw Hill, 2018.

مراجع کمکی

R. P. Grimaldi. Discrete and Combinatorial Mathematics: An Applied Introduction. 5th Edition, Pearson Addison Wesley, 2004.
A. Engel. Problem-Solving Strategies. Springer, 1998.