نویسنده : ساجده فدائی - دانشجو ارشد کامپیوتر صنعتی شریف اغلب در زندگی برای همه ما این سوال ایجاد می‌شود که واقعا ریاضیات چه کاربردی در زندگی روزمره خواهند داشت؟ بسیاری از ما در تمام طول تحصیل زمانیکه با فرمول‌های پیچیده ریاضیات مواجه می‌شدیم، حس خشم عجیبی درونمان ایجاد می‌شد و با عصبانیت تمام از خودمان می‌پرسیدیم چرا من باید اینها را یاد بگیرم؟!
خواندن این مقاله به شما کمک خواهد کرد که پاسخ خیلی از این سوال‌ها را پیدا کنید.
ریاضی گسسته چیست؟
اغب گفته می‌شود ریاضیات گسسته پایه و اساس نیمی از مسائل ریاضی و تحقیقات علمی است و هرچه جهان به سمت جلو حرکت می‌کند کاربرد ریاضی گسسته چه در زمینه آکادمیک و چه در صنعت بیشتر می‌شود. ریاضیات گسستهجامع ترین آموزش درس ریاضی گسسته
درس ریاضیات گسسته به معرفی مباحثی نظیر شمارش و احتمال، استدلال و برهان خلف، نظریه اعداد، منطق ریاضی، روابط بازگشتی، روابط و نظریه گراف می‌پردازد. از آن رو که در عصر کنونی ریاضی گسسته بطور گسترده در رشته کامپیوتر و برنامه نویسی استفاده می‌شود در این صفحه به معرفی و بررسی درس ریاضی گسسته پرداخته شده است شاخه‌ای از علوم ریاضی است که به مطالعه و بررسی بر روی عناصر قابل شمارش و مجزا از یکدیگر می‌پردازد مانند: نظریه گراف‌ها، نظریه اعداد، محاسبات، احتمالات و ترکیبیات.
امروزه برنامه‌های کاربردی و نرم افزارهای زیادی در جهان وجود دارند که اساس طراحی و ساخت آنها بر پایه علمِ ریاضی گسسته است، اکنون قصد داریم چند نمونه از موارد پرکاربردی که هم افراد عادی و هم افراد متخصص از آنها استفاده می‌کنند را معرفی کنیم، مطمئنا کمتر کسی از این موضوع اطلاع دارد که درون این برنامه‌ها از ریاضیات گسسته استفاده شده است!
کاربردهای ملموس ریاضی گسسته در زندگی
Google Maps
برنامه ریزی خطوط راه آهن (Railway Planning)
سیستم رأی گیری (Voting System)
پیاده سازی تست ویروس کرونا (Scaling COVID-19 testing)
نقشه گوگل (Google Maps)
در یک زمان نه چندان دور وقتی که به دنبال پیداکردن مکانی در نقشه بودیم، مجبور بودیم یک برگه بزرگ تاشده کاغذی را باز کنیم و مکان فعلی خودمان و مسیری که به سمت مقصدمان منتهی می‌شد را بر روی نقشه بیابیم. و باید خیلی خوش شانس می‌بودیم که مسیر مشخص شده و یا مکانی که به دنبال آن بودیم مثل هتل‌ها، تعطیل نشده باشند و یا اینکه مسیر تعیین شده مسدود و یا تخریب نشده باشد.
اما در سال‌های گذشته با پیدایش Google Map تقریبا تمام نقشه‌های کاغذی از بین رفت و ما مجهز به یک نقشه هوشمند شدیم که در هر لحظه می‌توانیم به مقصد دلخواه خود دسترسی داشته و در سریعترین زمان ممکن به آن برسیم. اما این سوال پیش می‌آید که واقعا این تکنولوژی پیشرفته و هوشمند چطور کار می‌کند؟ چطور این همه اطلاعات گرافیکی و جغرافیایی را می‌توان تهیه، گردآوری و سازماندهی کرد و در اختیار مردم قرار داد؟
یک جواب ساده به پاسخ به این پرسش وجود دارد؛ این اطلاعات توسط ماهواره‌ها، مراکز دولتی، کارمندان گوگل و یا حتی خود شما تهیه و پردازش می‌شود.
شاید 20 سال پیش به ذهن هیچ شخصی خطور نمی‌کرد که در آینده برنامه‌ای به وجود خواهد آمد که حتی می‌تواند ترافیک یک مسیر را در ساعت‌های مختلف شبانه روز مشخص کند، در حال حاضر Google Map این کار را انجام می‌دهد، گوگل مپ برای این کار ترکیبی از داده‌های مختلف را که شامل داده‌های مکانی و الگوهای ترافیکی و تعامل با کاربران است را با استفاده از علم یادگیری ماشین تحلیل و ترافیک را پیشبینی می‌کند.
شاید غیرقابل تصور باشد که Google Map تمام این کارها را برپایه یک الگوریتمآموزش طراحی الگوریتم به زبان ساده
درس طراحی الگوریتم یکی از مهم‌ترین و بنیادیترین دروس رشته کامپیوتر است. هدف از این درس، معرفی روشهای مختلف طراحی الگوریتم‌ها برای حل مسائل گوناگون است، در این صفحه به معرفی و آموزش طراحی الگوریتم پرداخته شده است. بسیار ساده، اما بطور باورنکردنی موثر بنام الگوریتم دایجسترا (Dijkstra) انجام می‌دهد. نام این الگوریتم برگرفته از نام آقای Dijkstra است که بعنوان برنامه نویس در ساختمان مرکز ریاضی آمستردام هلند مشغول به کار بود (مرکز ریاضی آمستردام یک مرکز تحقیقاتی در زمینه ریاضیات و علوم کامپیوتر نظری است و بخشی از سازمان تحقیقات علمی هلند (NWO) بوده و در پارک علمی آمستردام واقع شده است). او در سال 1956 مدعی شد برنامه‌ای طراحی کرده که قادر است کوتاهترین مسیر بین دو شهر در هلند را پیدا کند.
الگوریتم Dijkstra از تئوری گراف برای پیدا کردن کوتاهترین مسیر بهره می‌برد و همان‌طور که می‌دانید گراف یکی از مباحث و زیر شاخه‌های ریاضیات گسسته است. برای استفاده از الگوریتم Dijkstra برای محاسبه کوتاهترین مسیر بین مبدا و مقصد به این صورت عمل می‌شود که شهرها را بعنوان نودهای گراف و شهرهای همسایه را به وسیله یال‌ها به یکدیگر متصل می‌کنند و مسافت بین شهرها را بعنوان وزن یال‌ها در نظر می‌گیرند، سپس با اجرای الگوریتم روی این گراف کوتاهترین مسیر از مبدا به مقصد بدست می‌آید.
از نظر ریاضی نشان داده شده است که الگوریتم دایجسترا همیشه سریعترین و کوتاهترین مسیر را پیدا می‌کند و یکی از ویژگی‌های منحصر بفرد الگوریتم در برنامه Google Map این است که می‌تواند اطلاعات اضافی مانند اطلاعات ترافیک یا وجود ازدحام را به سادگی با تغییر وزن‌های گراف بدست آورد.
برنامه ریزی خطوط راه آهن
امروزه افراد زیادی چه برای کار و چه برای مسافرت و تفریح از خطوط ریلی استفاده می‌کنند و جالب است بدانید که حدود یک میلیون کیلومتر خطوط ریلی در جهان وجود دارد که سالیانه به بیش از سه تریلیون مسافر خدمت رسانی می‌کند. بنابراین اطمینان از اینکه قطارها، مسافران را مقرون به صرفه و با امنیت کامل و خیال راحت به مقصدشان می‌رسانند کار ساده‌ای نیست. اگر بخواهیم در یک شهر یا کشور حمل و نقل ریلی راه اندازی و یا حتی تغییرات کوچکی اعمال کنیم، به دلیل جزئیات زیاد و متعددی که سیستم راه آهن دارد این کار بسیار پیچیده و سخت است. بنابراین به منظور حل بهتر این مسئله بزرگ و پیچیده، طرح عملیاتی را در قالب چندین مرحله در نظر می‌گیرند و برای هر مرحله راه حل مخصوص به خود آن ارائه می‌شود.
برنامه ریزی شبکه خطوط: تعیین مکان و اتصالات مسیرها، ایستگاه ها و محوطه ها
به طور معمول شهرهای کمی امکان ساخت و راه اندازی یک سیستم راه آهن کاملاً جدید را دارند، بنابراین زیرساخت‌های راه آهن اغلب باتوجه به مسائل اقتصادی، جغرافیایی و محدودیت‌های سیاسی به صورت تدریجی و پلکانی رشد پیدا می‌کنند. متناسب با گسترش و رشد شهرها، الگوی فعالیت افراد جامعه نیز تغییر می‌یابد و افراد، نیازمند انجام سفر در مسیرهای بیشتری هستند. از این رو سازماندهی مجدد پایانه‌ها و خطوط قطارها یکی از روشهای پاسخگوئی به این نیاز است. به این روش حل مسئله، برنامه ریزی خطوط می‌گویند.
در سیستم راه آهن ، شبکه ریلی در قالب یک گراف مدل سازی شده که در آن ایستگاه‌ها را بعنوان نودها و راه‌های ارتباطی میان آنها بصورت یال در نظر گرفته می‌شود. هر مسیر بر روی این شبکه می‌تواند به عنوان یک خط ریلی در نظر گرفته شود، بنابراین ایستگاه‌ها از طریق مسیرهای زیادی می‌توانند به یکدیگر متصل شوند. اما در این میان تنها زیرمجموعه‌ای از این مسیرها، بعنوان خطوط ریلی در نظر گرفته می‌شوند.
امروزه با رواج سیستم‌های خرید کارت بلیط هوشمند، امکان محاسبه و تخمین دقیق الگوی تقاضا مبدأ به مقصد مسافران براساس روزهای هفته و یا حتی یک زمان خاص از روز وجود دارد. مسئله برنامه ریزی خطوط به کمک این الگو، مسیرها را در بهینه‌ترین حالت ممکن با درنظر گرفتن مسائل ایمنی و سرویس‌دهی مناسب به مسافران انتخاب می‌کند. مجموعه خطوط طوری انتخاب می‌شوند که تقاضای مسافران پیش بینی شده را پوشش دهد.
یک محدودیت دیگر برای حل مسائل برنامه ریزی خطوط این است که، مسافران ترجیح می‌دهند در یک خط ریلی مستقیم سفر کنند و در طول سفر خود مجبور به تعویض قطار نشوند. بنابراین یک هدف احتمالی برای برنامه ریزی خطوط این است که تعداد سفرهای مستقیم مسافران را به حداکثر برساند.
جدول زمانبندی
یکی دیگر از مسائل مورد توجه در سیستم راه آهن، برنامه ریزی دقیق و منظم حرکت قطارها از ایستگاه‌های خطوط است. مسئله جدول زمانبندی باتوجه به مجموعه خطوط و میزان تقاضای مسافرین، زمان دقیق اعزام قطارها از هر ایستگاه را به طور مشخص تعیین می‌کند. جدول زمانبندی برای قطارهای حومه‌ای به علت تقاضای کمتر به صورت متناوب (پریودیک) تعیین می‌شود اما متناسب با ساعات شلوغی و روزهای آخر هفته می‌تواند متغیر باشد.
یکی از مدل‌های پرکاربرد ریاضی برای حل مسائل زمان بندی ، مدل PEPS (periodic event scheduling problem) است که توسط دو ریاضیدان معروف به نامهای Paolo Serafini و Walter Ukovich معرفی شد. این مدل محاسباتی ترکیبی از تکنیک‌های برنامه نویسی اعداد صحیح، توابع اکتشافی (هیورستیک) و مفاهیم شبکه است که مبانی علم ریاضیات به ویژه ریاضی گسسته نقش مهمی در پیدایش آن دارند. در مسئله زمانبندی راه آهن این مدل محاسباتی در یک دوره زمانی (T) با داشتن مجموعه‌ای از رویدادها (V) که درآن یک رویداد نشان‌دهنده ورود و خروج قطار هدایت شده در یک ایستگاه معین است؛ با درنظرگرفتن محدودیت‌ها (مانند توالی ورود و خروج قطارها، فواصل ایمنی میان آنها و اشتراک گذاری خطوط ریلی)، بهترین جدول زمانبندی ممکن را برنامه ریزی و طراحی می‌کند. جالب است بدانید محققین با بهره بردن از این مدل به سیستم حمل و نقل عمومی شهر برلین کمک کرده‌اند.
برنامه ریزی تجهیزات و خدمه
این مسئله برنامه ریزی به تعیین تجهیزات (لوکوموتیو و واگن) و خدمه (رانندگان قطارها) برای انجام سفرها می‌پردازد. یک روش ساده برای حل مسئله تجهیزات و خدمه این است که فرض می‌شود تمامی قطارها دارای امکانات یکسان و نقطه شروع مشترک هستند تا بتوان آن را در قالب یک گراف جهت دار مدل سازی کرد. هر سفر در برنامه هفتگی بعنوان یک نود گراف نشان داده می‌شود. حال اگر از یک قطار به صورت متوالی در میان این سفرها استفاده شود، بین هرکدام از نودها می‌توان یک یال در نظر گرفت. در تمامی گراف‌ها، ایستگاه ابتدایی بعنوان نود شروع (start) و ایستگاه آخر بعنوان یک نود پایانی (terminate) ترسیم می‌شود.
از آنجایی که لوکوموتیوها و قطارها تجهیزات گران قیمتی هستند، بکارگیری تعداد قطار کمتر برای انجام سفر میان ایستگاه‌ها در یک جدول زمانی معین را می‌توان بعنوان یک هدف در نظر گرفت. پس از تعیین قطارها، خدمه نیز باید به هریک از سفرها اختصاص داده شوند. نحوه تخصیص خدمه نیز شبیه به برنامه ریزی تجهیزات است اما محدودیت‌های بیشتری در نظر گرفته می‌شود. این محدودیت‌ها عبارتند از: مدت زمان شیفت، وقفه‌های غذا و استراحت، روزهای تعطیل مورد نیاز در طول یک هفته یا ماه و غیره. برخلاف قطارها و لوکومتیوها که بعد از اتمام سفر الزامی به بازگشت به ایستگاه اولیه‌شان ندارند، خدمه قطارها روز کاری خودشان را در یک ایستگاه شروع و در همان مکان خاتمه می‌دهند. این موضوع به این معناست که مسئله برنامه ریزی تجهیزات باید به گونه‌ای طراحی شود که بتوان خدمه قطارها را در این میان تغییر داد. علاوه بر این، تمام خدمه از مهارت کافی برای انجام برخی سفرها برخوردار نیستند و این اغلب منجر به پیچیدگی و بزرگی مسئله برنامه ریزی می‌شود. یکی از مدل‌های بکار رفته در حل این مسائل، مدل column generation است که یک الگوریتم بهینه جهت حل مسائل برنامه ریزی خطی است. ایده این مدل برای حل مسئله آن است که تنها زیرمجموعه‌ای از متغیرها را برای شروع حل مسئله برنامه ریزی در نظر می‌گیرد.
لازم به ذکر است که ریاضیات گسسته اساس و پایه مسائل برنامه ریزی خطی است.
سیستم رای گیری
در کشورهای بسیاری از جمله کشور ما هر 4 سال یکبار به صورت رسمی مراسم رای گیری ریاست جمهوری برگزار می‌شود. انتخابات و رأی گیری برای هر نظام مبتنی بر دموکراسی، امری بسیار ضروری است؛ اما انتخاب رئیس جمهور روندی بسیار پیچیده دارد بطوری که به محض انتخاب رئیس جمهور جدید، کاندیداهای دوره‌های بعد شروع به برنامه ریزی و فعالیت و همچنین راه انداختن کمپین‌ها و جمع‌آوری پول برای تبلیغات خود می‌کنند. از این رو، دقت شمارش آراء در زمان انتخابات، مسئله‌ای کاملا جدی و حساس است و همیشه این سوال که "آیا اعداد گزارش شده به همان اندازه میزان آراء، دقیق هستند یا خیر" در اذهان عمومی ایجاد می‌شود. به همین دلیل، امروزه ریاضیدانان و دانشمندان کامپیوتر به دنبال بررسی و پیدا کردن روشهای نوینی در حوزه امنیت رأی گیری و دقت شمارش آراء هستند.
روش الکترال بعنوان یکی از روشهای نوین در سیستم رأی گیری معرفی شده که فرد منتخب نه براساس رأی مردم، بلکه براساس رأی هیئت الکترال انتخاب می‌شود. در روش الکترال، براساس تقسیم بندی‌های کشوری (کشور آمریکا دارای 50 ایالت است) هر قسمت را بعنوان یک بلوک آراء در نظر می‌گیرند و به هریک از این بلوک‌ها براساس میزان جمعیت و اهمیت آن شهر یا ایالت از نظر سیاسی و اقتصادی وزن مشخصی می‌دهند. بعنوان مثال ایالت کالیفرنیا آمریکا، با داشتن 39 میلیون نفر جمعیت دارای 55 رأی الکترال است. بنابراین اگر در یک ایالت نامزدی برنده رأی مردمی باشد تمام آرای الکترال به او اختصاص خواهد یافت. بعنوان مثال اگر کاندیدی 1/50 درصد از آراء ایالت کالیفرنیا را کسب کرده باشد، تمامی 55 الکترال این ایالت از آن او خواهد بود. بنابراین شیوه تلاش نامزدهای انتخاباتی نه تنها به تعداد آرائی که کسب می‌کنند بستگی دارد، بلکه به این که این آراء در کدام شهر یا ایالت نیز کسب شده وابسته است.
انتخابات و رأی دادن شاید یک حوزه سنتی علوم سیاسی باشد ولی امروزه افراد مشهور زیادی در حوزه علوم ریاضی و آمار مشغول به فعالیت و طراحی و ارائه سیستم‌های رأی گیری هستند. اما نقش ریاضیات در این میان، دسته‌بندی و تجزیه برگه‌های رأی براساس گزینه‌ها و کاندیداهای موجود است.
یکی از روشهای تصمیم گیری و انتخاب نامزد برنده را روش کندورسه (Condorcet) می‌نامند که براساس نظام رأی‌گیری ترجیحی (هر رأی‌دهنده با استفاده از اعداد، این فهرست را به ترتیب اولویت رتبه‌بندی می‌کند) بنا شده است. در این روش نامزدی که بتواند بیشترین تعداد برد "رو در رو" با دیگر نامزدها را کسب کند برنده است. از ریاضیات گسسته می‌توان برای میزان نزدیکی رتبه‌های مختلف n کاندید استفاده کرد. به عنوان مثال، برای سه نامزد، می‌دانیم که شش رتبه‌بندی احتمالی از نامزدها وجود دارد.
| B | B | C | C | A | A |
| A | C | B | A | C | B |
| C | A | A | B | B | C |
| 7 | 2 | 3 | 8 | 5 | 5 |
(ACB = 5 به این معناست که ترتیب ترجیحات پنج نفر از رأی دهندگان به صورت A>C>B است)
براساس این مدل هر نامزد را با نامزد دیگر در یک رقابت "رو در رو" وارد می‌کنند، برنده این رقابت کسی است که اکثریت او را بر دیگری ترجیح داده باشند. تا زمانیکه بین دو نامزد رقابت صورت می‌گیرد همیشه یکی از آنها حائز اکثریت آراء می‌شود مگر اینکه هر دو برابر شوند. پس زمانی که دو نامزد A و B مقایسه می‌شوند، می‌بایست تمام فهرست‌هایی که A را بالاتر از B و همچنین B را بالاتر از A رتبه‌بندی کرده‌اند شمرده شود. هرکدام که تعداد بیشتری رتبه بالا کسب کرده باشد، برنده این رقابت دونفری است.
مثلاً در مقابله رودرروی A وB جدول بالا ، 18 نفر از رأی دهندگان A را به B ترجیح داده‌اند و 12 نفر B را به A. بعد از انجام محاسبات، باید قوی‌ترین مسیرها را مشخص کرد. برای آنکه قوی‌ترین مسیرها به آسانی به چشم آیند، نتایج مقابله‌های "رو در رو"، در گراف جهت‌دار ترسیم شده‌اند.
تنها مرحله دشوار در اجرای این روش، محاسبه قدرت قوی‌ترین مسیرهاست. این مشکل مسئله‌ای مشهور در نظریه گراف‌ها موسوم به مسئله عریض‌ترین مسیر است که یک روش ساده برای حل این مسئله، بکارگیری الگوریتم کارایی بنام فلوید-وارشال است. در این مبحث نیز نقش ریاضیات گسسته در انجام مدل های محاسباتی و ترسیم گراف ها کاملاً مشهود و قابل درک است.
پیاده سازی تست ویروس کرونا (Covid-19):
با شیوع و همه گیری ویروس کرونا در جهان خیلی از فعالیت‌های اقتصادی تعطیل شدند. پل رومر (Paul Romer) اقتصاددان برنده جایزه نوبل، تعطیلی ناشی از کووید 19 را یک فاجعه اقتصادی می‌دانست که تریلیون‌ها دلار ضرر اقتصادی به افراد، مشاغل و دولت‌ها وارد کرده است. او پیشبینی کرد که اگر جامعه به زودی فعالیت‌های پیش از شیوع ویروس را از سر نگیرد، این ضررها دائمی خواهند شد. او معتقد بود تنها شرط خروج از این بحران، انجام آزمایشات تست کرونا در سطح گسترده‌ای از جامعه است و پیشنهاد داد که همه افراد در ایالات متحده هر دو هفته یک بار آزمایش شوند. با استفاده از این شبیه سازی، دولت می‌توانست افراد آلوده به ویروس کووید را شناسایی و قرنطینه کند و میزان موارد ابتلای افراد را زیر پنج درصد نگه دارد تا اینکه تعداد کمتری از مردم آلوده شوند و وضعیت اقتصادی با سرعت بیشتری بهبود یابد. اما متاسفانه امکان این سطح از آزمایش که شامل غربالگری روزانه هفت درصد از جمعیت بود، وجود نداشت. و تنها 4 درصد از جمعیت ایالات متحده از ماه مارس تا می آزمایش شده بودند.
دیوید دونوهو (آماردان آمریکایی) با همکاری دانشمندان حوزه ریاضی سایرکشورها از جمله هند، اسپانیا، آلمان و ... و مشارکت جامعه پزشکی جهت دریافت اطلاعات آماری، با بهره گیری از ایده‌های ریاضی و آماری به یک روش نوین در انجام آزمایشات گسترده غربالگری دست یافتند. عدم نیاز به افزایش تعداد ایستگاه‌های آزمایش و یا استفاده از کیت‌های اضافی تست کرونا، یکی از اصلی‌ترین مزیت‌های این روش محسوب می‌شد.
یک اصل مورد توجه در تحقیقات این است که بیشتر افراد جامعه آلوده نمی‌شوند و درنتیجه ویروس فعال در نمونه‌های آزمایشی خود نخواهند داشت. در روش پیشنهادی مطرح شده بجای مصرف یک کیت آزمایشی به ازای هر نفر، از ترکیب روش مالتی پلکسینگ (ادغام نمونه‌های آزمایشی چندین بیمار) و علم ریاضیات بعنوان جایگزین مناسبی استفاده شده است. در این روش، نمونه آزمایش هر فرد در چندین لوله کوچک واکنش(pool) ظاهر می‌شود و هر لوله شامل نمونه‌هایی از چندین بیمار است. مرحله بعدی، آزمایش تمام لوله‌ها (pool) داخل دستگاه PCR است که برای اطمینان بیشتر از نتیجه بدست آمده، چندین بار مورد آزمایش قرار می‌گیرند. بعد از نهایی شدن نتیجه آزمایش و جداسازی لوله‌های واکنش آلوده به ویروس (تست مثبت)، تشخیص نمونه آلوده از میان نمونه‌های ادغام شده مهم‌ترین مرحله به شمار می‌آید.
دقیقاً در همین مرحله است که به کمک علم ریاضیات و با بکارگیری روشهای پیچیده محاسباتی خطی و ماتریسی ریاضیات گسسته، نتیجه آزمایش را رمزگشایی کرده تا بطور مشخص نمونه حاوی ویروس کووید 19 و فرد آلوده شناسایی شود. نکته کلیدی و ارزشمند این روش آن است که پزشکان برای ارزیابی وضعیت بیماری افراد در سطح گسترده از تعداد کمتری کیت آزمایشگاهی استفاده می‌کنند و این موفقیت بزرگی در بهبود وضعیت جامعه و اقتصاد شمرده می‌شود.
جمع‌بندی
ریاضیات گسسته کاربردهای زیادی در زندگی روزمره دارد و در این مقاله فقط چند نمونه کوچک آن مورد بررسی قرار گرفت. امروزه نقش مهم و اساسی ریاضیات در علوم مختلف بیش از روزهای گذشته قابل درک است و در بسیاری از تحقیقات علمی مهم و پیشرفته مورد استفاده قرار می‌گیرد.
