ریاضیات گسسته چیست و چرا دانشجویان رشته نرم‌افزار باید آن‌را جدی بگیرند؟

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

سرفصل‌هایی از ریاضیات گسسته که نیازمند توجه بیشتر هستند

منطق – مطالعه استدلال- مَنطِق مطالعه‌ی روشمند قاعده استنتاج مجاز مانند روابطی که منجر به پذیرش گزاره (تالی) بر پایه‌ی مجموعه دیگر گزاره‌ها (پیش‌فرض‌ها) می‌شود، است.

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

نظریه اعداد –شاخه ای از ریاضیات محض است که خود را عمدتاً وقف مطالعه اعداد صحیح نموده‌است. ریاضیدان آلمانی، کارل فردریش گاوس (۱۷۷۷–۱۸۵۵) گفت: «ریاضیات ملکه علوم است، و نظریه اعداد ملکه ریاضیات.» نظریه اعداد دانان به مطالعه اعداد اول و همچنین خواص اشیائی که از اعداد ساخته می‌شوند می پردازند (به عنوان مثال اعداد گویا) یا تعمیم‌هایی از اعداد تعریف می‌کنند (مثل اعداد صحیح جبری).

ترکیبیات (مطالعه شمارش)- شاخه‌ای از ریاضیات است که به بررسی ساختارهای متناهی و شمارا می‌پردازد.

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

هندسه دیجیتال و توپولوژی دیجیتال- هندسه دیجیتال با مجموعه‌های گسسته (عموماً مجموعه‌های نقاط گسسته) سر و کار دارد که مدل‌ها یا تصاویر دیجیتال اشیای دو بعدی و سه بعدی فضای اقلیدسی در نظر گرفته می‌شوند. با ارقام نشان دادن جایگزینی یک شئ با یک مجموعه گسسته از نقاطش است. تصاویری که روی صفحه تلویزیون یا در روزنامه‌ها می‌بینیم در حقیقت تصاویر دیجیتال هستند. کاربردهای اصلی هندسه دیجیتال در زمینه‌های گرافیک کامپیوتر و آنالیز تصاویر است.

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

نظریه اطلاعات - به مقداردهی (Quantification)، ذخیره و انتقال اطلاعات می‌پردازد. این نظریه، مدلی ریاضی از شرایط و عوامل مؤثر در پردازش و انتقال اطلاعات (داده‌ها) به‌دست می‌دهد. تمرکز این نظریه بر محدودیت‌های بنیادین ارسال و پردازش اطلاعات است، و کمتر به چگونگی عملکرد و پیاده‌سازی روش‌های انتقال و پردازش اطلاعات می‌پردازد. پیدایش این نظریه در پی کارهای کلود شانون در ۱۹۴۸ بوده‌است.

نظریه محاسبه‌پذیری و پیچیدگی (بررسی محدودیت‌های نظری و عملی الگوریتم‌ها)- محاسبه‌پذیری توانایی حل یک مسئله به روشی مؤثر است؛ که یک موضوع کلیدی در زمینه نظریه محاسبه پذیری در منطق ریاضی و نظریه محاسبات در علوم کامپیوتر است. محاسبه‌پذیری یک مسئله ارتباط نزدیکی با وجود یک الگوریتم برای حل مسئله دارد. گسترده‌ترین مدل‌های مورد مطالعه از محاسبات توابع تورینگ-محاسبه پذیر، μ-بازگشتی و حساب لامبدا هستند، که تمامی آن‌ها دارای قدرت محاسباتی معادل هستند. از انواع دیگر مطالعه محاسبه پذیری، همچنین: مفاهیم محاسبه‌پذیری ضعیف تر از ماشین‌های تورینگ که در نظریه اتوماتا مطالعه می‌شود و مفاهیم محاسبه‌پذیری قوی تر از ماشین تورینگ که در زمینه hypercomputation مطالعه می‌شود را می‌توان نام برد.

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

جبر خطی (مطالعه معادلات خطی مرتبط)- جبر خطّی شاخه‌ای از ریاضیات است که به بررسی و مطالعهٔ ماتریسها، بردارها، فضاهای برداری (فضاهای خطّی)، تبدیلات خطی، و دستگاه‌های معادلات خطی می‌پردازد.

تابع – تابع در ریاضیات یک رابطه دوتایی روی دو مجموعه است که هر عنصر در مجموعه اول را دقیقاً به یک عنصر در مجموعه دوم مرتبط می‌کند. مثال‌های معمول در این زمینه، توابعی از اعداد صحیح به اعداد صحیح یا از اعداد حقیقی به اعداد حقیقی است.

مجموعه جزئاً مرتب - مجموعه جزئی ‌مرتب (partially ordered set) در ریاضیات و مخصوصاً نظریه ترتیب، «مفهوم شهودی یک ترتیب، پیاپی‌سازی، یا چینش عناصر یک مجموعه» را صوری‌سازی می‌کند و تعمیم می‌دهد. به مجموعه جزئی‌مرتب به صورت مخفف، پوسِت (به انگلیسی: poset) هم می‌گویند. یک پوسِت شامل یک «مجموعه» همراه با یک «رابطه دوتایی» است، که این رابطه بیانگر آن است که برای جفت عنصرهای خاصی در آن مجموعه، یکی از آن عناصر از نظر ترتیبی قبل از دیگری قرار دارد. به چنین رابطه‌ای، «رابطه جزئی‌مرتب» می‌گویند.

احتمالات - احتمال معمولاً مورد استفاده برای توصیف نگرش ذهن نسبت به گزاره‌هایی است که ما از حقیقت آن‌ها مطمئن نیستیم. گزاره‌های مورد نظر معمولاً از فرم "آیا یک رویداد خاص رخ می‌دهد؟" و نگرش ذهن ما از فرم "چقدر اطمینان داریم که این رویداد رخ خواهد داد؟" است. میزان اطمینان ما، قابل توصیف به صورت عددی می‌باشد که این عدد مقداری بین ۰ و ۱ را گرفته و آن را احتمال می نامیم. هر چه احتمال یک رویداد بیشتر باشد، ما مطمئن تر خواهیم بود که آن رویداد رخ خواهد داد. در واقع میزان اطمینان ما از اینکه یک واقعه (تصادفی) اتفاق خواهد افتاد.

برهان (ریاضی) -برهان یا اثبات استدلالی متقاعدکننده است که نشان می‌دهد یک گزاره ریاضی (با توجه به استانداردهای مربوط)، الزاماً صحیح است. برهان، یک استدلال استنتاجی است و نه استدلالی استقرایی، به این معنا که برهان باید نشان دهد که یک گزاره در تمامی شرایط و بدون هیچ استثنایی، همواره صحیح است.

شمارش - شمارش روال تخصیص یک‌به‌یک شماره به هریک از اعضای یک مجموعه برای پی بردن به اندازهٔ مجموعه است. شمارش و اندازه‌گیری از مهم‌ترین روال‌های ریاضیات هستند.

رابطه دوتایی - در ریاضیات یک رابطه دوتایی روی مجموعه A است که با A2 نمایش داده می‌شود. مفهوم کلی‌تر: رابطه دوتایی بین دو مجموعه A و B می‌شود زیرمجموعه‌ای از A*B.

کاربرد ریاضیات گسسته در رمزنگاری

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

پایگاه داده‌های رابطه

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

استفاده به عنوان تدارکات

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

الگوریتم‌های کامپیوتری

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

کاربردهای همنهشتی

همنهشتی‌ها کاربردهای زیادی در ریاضیات گسسته ،علوم کامپیوتر، و بسیاری از رشته‌های دیگر دارد. در این مقاله سه کاربرد آن را معرفی می‌کنی.

استفاده در تخصیص مکان‌های حافظه به فایل‌های کامپیوتری

فرض کنید یک شماره شناسایی مشتری به طول ده رقم است. برای بازیابی سریع فایل‌های مشتری، نمی‌خواهیم با استفاده از رکورد مشتری، یک خانه حافظه اختصاص دهیم. در عوض، می‌خواهیم از یک عدد صحیح کوچکتر مربوط به شماره شناسایی استفاده کنیم. اینکار را می‌توان با تابع درهم‌ساز (hashing function) معروف است انجام داد.

تولید اعداد تصادفی

ساختن دنباله‌ای از اعداد تصادفی برای الگوریتم‌های تصادفی، برای شبیه‌سازی‌ها، و نیز برای بسیاری از اهداف دیگر مهم هستند. ساختن یک دنباله از اعداد تصادفی واقعی خیلی دشوار است یا احتمالاً غیرممکن.

با استفاده از همنهشتی می‌توان دنباله‌ای از اعداد شبه تصادفی تولید کرد. این اعداد تصادفی دارای این مزیت هستند که خیلی سریع ساخته می‌شوند و عیب آن در ای ن است که در استفاده از این دنباله‌ها در کارهای مختلف باید پیشگویی‌های زیادی داشته باشیم.

رقم‌های کنترلی

از همنهشتی‌ها می‌توان در برای تولید رقم‌های کنترلی (check digit) شماره‌های شناسایی از انواع مختلف نظیر شماره‌های کد ورد استفاده در محصولات خرده فروشی، شماره‌های مورد استفاده در کتاب‌ها، شماره‌های بلیط هواپیمایی، و… استفاده کرد.

تابع درهم‌ساز

در عمل، تابع‌ها ی در هم ساز مختلفی وجود دارد اما یکی از متداول‌ترین آن‌ها به شکل h(k)=k mod m است که در آن m تعداد خانه‌های حافظه موجود است. تابع‌های در هم ساز به راحتی ارزیابی می‌شوند طوری‌که مکان فایل‌ها را به سرعت می‌توان مشخص کرد. تابع در هم ساز h(k) ای نیاز را برطرف می‌کند. برای یافتن h(k) لازم است باقی‌مانده تقسیم k بر m را بدست آوریم. همچینی این تابع پوشا نیز هست.

روش همنهشتی خطی

معمول‌ترین روش استفاده شده برای تولید اعداد شبه تصادفی این روش همنهشتی خطی (liner consequential method) است.

رقم‌های کنترلی

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