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

مدرس: محمدعلی آبام، محمد ایزدی گواهی: رسمی دوزبانه
ترم: پاییز ۱۴۰۳ پیش‌نیاز: –
زمان ارائه: شنبه و دوشنبه ۱۴:۰۰ تا ۱۵:۳۰ محل برگزاری: کلاس مجازی

هدف کلی

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

سرفصل‌ها

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

ارزیابی

  • آزمونک‌ها: ۶ نمره
  • آزمون‌‌ها پایان‌دوره: ۱۴ نمره

منابع

  1. K. H. Rosen. Discrete Mathematics and Its Applications. 8th Edition, McGraw Hill, 2018.
  2. R. P. Grimaldi. Discrete and Combinatorial Mathematics: An Applied Introduction. 5th Edition, Pearson Addison Wesley, 2004.
  3. A. Engel. Problem-Solving Strategies. Springer, 1998.