درس ریاضی گسسته یکی از دروس پایه‌ای و مقدماتی دانشکده‌های ریاضی و علوم کامپیوتره. توی این درس با دنیایی از مفاهیم آشنا می‌شی که شاید اسمشون به گوشت خورده باشه ولی هیچ‌وقت جدی نگرفتیشون: منطق ریاضی، نظریه مجموعه‌ها، آنالیز شمارشی، روابط بازگشتی، توابع مولد و نظریه...
ریاضیات گسسته؛ از منطق تا گراف 🎓
درس ریاضی گسسته یکی از دروس پایه‌ای و مقدماتی دانشکده‌های ریاضی و علوم کامپیوتره. توی این درس با دنیایی از مفاهیم آشنا می‌شی که شاید اسمشون به گوشت خورده باشه ولی هیچ‌وقت جدی نگرفتیشون: منطق ریاضی، نظریه مجموعه‌ها، آنالیز شمارشی، روابط بازگشتی، توابع مولد و نظریه گراف. دوره آموزش ریاضیات گسسته‌ای که اینجا معرفی می‌کنیم، مربوط به نیمسال دوم سال تحصیلی ۱۳۹۱ در دانشکده ریاضیات دانشگاه صنعتی شریفه و به‌صورت رایگان در اختیار علاقه‌مندان قرار گرفته.
📋 مشخصات کلی دوره
ویژگی
جزئیات
عنوان دوره
ریاضیات گسسته
مدرس
دکتر میر امید حاجی میرصادقی
دانشگاه
صنعتی شریف
تعداد جلسات
۲۷ جلسه
مدت زمان
حدود ۳۷ ساعت
سطح
مقدماتی تا متوسط
هزینه
رایگان
این دوره برای چه کسانی مناسبه؟
خب، ببینیم این دوره به درد کی می‌خوره. اگه دانشجوی مهندسی کامپیوتر یا علوم کامپیوتری، این درس برات حکم نون شب رو داره؛ چون تقریباً همه‌جای برنامه‌نویسی و الگوریتم بهش گره خورده. ولی فقط این دو رشته نیستن. دانشجوهای مهندسی صنایع هم از مباحث ریاضی گسسته استفاده زیادی می‌برن، مخصوصاً توی بهینه‌سازی و تحقیق در عملیات. حتی اگه دانش‌آموز پیش‌دانشگاهی باشی و بخوای برای المپیاد کامپیوتر یا المپیاد ریاضی آماده شی، این دوره رایگان می‌تونه یه نقطه شروع خیلی خوب باشه.
پیش‌نیازها و مسیر یادگیری
قبل از اینکه بپری وسط درس، یه پیشنهاد دارم. بهتره اول یه نگاهی به دوره آمار و احتمال مهندسی دانشگاه شریف که دکتر علی شریفی زارچی تدریس کرده بندازی. اینطوری پایه‌ی ذهنیت ریاضیت قوی‌تر می‌شه و مفاهیم گسسته راحت‌تر جا می‌افتن. بعد از تموم کردن این دوره هم اگه دوست داشتی عمیق‌تر بری، می‌تونی سراغ دوره منطق ریاضی دانشگاه تهران با تدریس دکتر مجید علیزاده یا دوره فلسفه ریاضی دانشگاه شریف با تدریس دکتر سیاوش شهشهانی بری.
سرفصل‌های دوره ریاضیات گسسته
سرفصل‌های این دوره رو به ترتیب مرور می‌کنیم:
فصل اول – حساب گزاره‌ها: گزاره و انواعش، عملگرهای منطقی، شرطی و دوشرطی، هم‌ارزی‌های منطقی، قوانین دمورگان و تابع ارزش
فصل دوم – استلزام منطقی: قاعده‌های استنتاج، قیاس تعدی، استثنایی و عکس، ترکیب عطفی، بسط فصلی رزولوشن و سازگاری
فصل سوم – سورها: گزاره‌نما، متغیرهای آزاد و مقید، کاربرد سورها در علم کامپیوتر، نقیض سورها، سورهای تو در تو و ترتیب سورها
فصل چهارم – مجموعه‌ها: نمودار ون، زیرمجموعه، عملیات روی مجموعه‌ها، حاصل‌ضرب دکارتی و قانون‌های نظریه مجموعه‌ها
فصل پنجم – رابطه و تابع: تعریف رابطه، تعداد رابطه‌های تعریف‌شده روی مجموعه، خواص رابطه‌ها، تشخیص خواص با گراف جهت‌دار و ماتریس
فصل ششم – رابطه هم‌ارزی: رابطه هم‌ارزی، کلاس هم‌ارزی، افراز و بستار روابط
فصل هفتم – ترتیب جزئی، لاتیس و جبر بول: عناصر مقایسه‌پذیر، ترتیب کامل، نمودار هاس، عضو ماکسیمال و مینیمال، ماکسیمم و مینیمم
فصل هشتم – ساختارهای جبری: عملیات n تایی، خواص، دستگاه جبری و همومورفیسم‌ها
فصل نهم – شمارش: اصل جمع، اصل ضرب، جایگشت، جایگشت با تکرار و ترکیب
فصل دهم – روابط بازگشتی: تعریف رابطه بازگشتی، برج هانوی، زادوولد خرگوش‌ها و دنباله فیبوناچی، تابع مولد نمایی و حل روابط بازگشتی
فصل یازدهم – گراف: تعریف گراف، نمایش گراف، رنگ‌آمیزی گراف و چندجمله‌ای فامی
فصل دوازدهم – درخت‌ها: تعریف درخت، جنگل، درخت ریشه‌دار، پدر، فرزند، همزاد، جد، نوه، برگ و راس داخلی
کتاب مرجع این درس هم Introductory Discrete Mathematics نوشته V. K. Balakrishnan هست.
ریاضیات گسسته دقیقاً چیه و چرا باید بخونیمش؟ 🤔
بیایید یه کم ساده‌تر بگیم. علم ریاضی رو می‌شه به دو بخش گسسته و پیوسته تقسیم کرد. ریاضیات گسسته فقط با عناصر گسسته سر و کار داره؛ یعنی چیزهایی که توی فضای پیوسته معنی پیدا می‌کنن، اینجا جایی ندارن. مثلاً اصل ضرب و توزیع پواسون بخشی از ریاضیات گسسته‌ان، ولی توزیع نرمال می‌ره توی دسته ریاضیات پیوسته.
یه نکته جالب: شاید قدیمی‌ترین بخش ریاضیات، همین ریاضیات گسسته باشه. تا قبل از قرن ۱۷ میلادی که مفاهیمی مثل اعداد حقیقی، انتگرال و مشتق مطرح بشن، تقریباً همه ریاضیات همون بخش گسسته بود. بعدها که این مباحث جدید اومدن، اسم بخش قدیمی‌تر شد ریاضیات گسسته. ولی این به معنی قدیمی شدنش نیست؛ اتفاقاً با رشد علوم کامپیوتر، اهمیتش چند برابر هم شده.
چرا این دوره به کارت میاد؟
اگه یه بار توی زندگی برنامه‌نویسی کرده باشی یا حتی یه الگوریتم ساده نوشته باشی، حتماً به این برخوردی که خیلی از تصمیم‌گیری‌های الگوریتمی ریشه‌شون توی ریاضیات گسسته‌ست. بذار یه مثال ملموس بزنم: فرض کن می‌خوای یه الگوریتم برای پیدا کردن کوتاه‌ترین مسیر بین دو نقطه توی یه شبکه بنویسی. اینجا دقیقاً همون جاییه که نظریه گراف به دادت می‌رسه. یا فرض کن می‌خوای تعداد حالات ممکن برای چیدن چند شیء رو حساب کنی؛ این می‌شه بحث شمارش.
چند تا از مهم‌ترین کاربردهای ریاضیات گسسته:
رمزنگاری: امنیت اطلاعات و ساختارهای رمز، بر پایه مفاهیم گسسته بنا شده
الگوریتم‌های کامپیوتری: طراحی الگوریتم‌ها بدون منطق ریاضی تقریباً غیرممکنه
پایگاه داده رابطه‌ای: ساختار جدول‌ها و کوئری‌ها از نظریه مجموعه‌ها میاد
لجستیک و زنجیره تأمین: بهینه‌سازی مسیرها و تخصیص منابع
