You are not allowed to perform this action

ساختمان‌های گسسته

Discrete Structures

شماره درس: ۴۰۱۱۵ تعداد واحد: ۳
مقطع: کارشناسی نوع درس: نظری
پیش‌نیاز: – هم‌نیاز: –

اهداف درس

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

ریز مواد

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

ارزیابی

  • تمرین نظری: ۱۵٪ نمره
  • آزمون‌‌ها (میان‌ترم، پایان‌ترم و آزمونک‌ها): ۸۵٪ نمره

مراجع

  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.