ساختارهای گسسته؛ از منطق و اثبات ریاضی تا ترکیبیات، احتمال و نظریه گراف

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

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

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

در پایان این درس چه توانایی‌هایی کسب می‌کنید؟

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

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

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

• منطق (۲ جلسه)
  • اصول استنتاج
  • روش‌های اثبات
• استقرا (۱.۵ جلسه)
  • استقرای ریاضی، استقراء قوی
  • استقرای ساختاری
• نظریه‌ی اعداد (۲.۵ جلسه)
  • بخش‌پذیری، ب.م.م، ک.م.م، اعداد اول
  • همنهشتی، قضیه اویلر، کاربرد در رمزنگاری
• شمارش (۴ جلسه)
  • اصول اولیه‌ی شمارش، جایگشت و ترکیب، ضرایب دوجمله‌ای
  • جایگشت‌ها و ترکیب‌های باتکرار، اصل طرد و شمول
  • توزیع اشیا درون جعبه‌ها، اصل لانه‌کبوتری
  • روابط بازگشتی و حل روابط بازگشتی همگن
• احتمالات گسسته (۲ جلسه)
  • نظریه‌ی احتمالات، تابع توزیع احتمال، رویدادهای مستقل، احتمالات شرطی
  • متغیرهای تصادفی، امید ریاضی و واریانس
• گراف‌ها (۴ جلسه)
  • تعاریف اولیه، گراف‌های خاص، گراف‌های دوبخشی، نمایش گراف‌ها
  • مسیرها و همبندی، مسیرهای اویلری، مسیرهامیلتونی
  • گراف‌های مسطح، قضیه‌ی اویلر
  • درخت‌ها و جنگل‌ها، درخت‌های ریشه‌دار

• تحویل تمرین‌هاا: ۳ نمره
• کوییز از تمرین‌ها: ۵ نمره
• آزمون‌‌ها پایان‌دوره: ۱۲ نمره