ریاضیات گسسته

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

ریاضیات گسسته که به آن «ریاضیات محدود» یا «ریاضیات تصمیم» نیز می‌گویند، به بخش‌هائی از ریاضیات گفته می‌شود که با ساختارهای گسسته (یعنی ساختارهایی که در آن‌ها مفهوم پیوستگی وجود ندارد) سر و کار دارد. بیش تر مواردی که در ریاضیات گسسته مورد بررسی قرار می‌گیرند مجموعه‌های شمارش پذیر هستند. مانند اعداد صحیح و گراف‌های محدود و زبان‌های رسمی.

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

برخی از بخش‌های ریاضیات گسسته عبارت‌اند از:

کاربردهای همنهشتی[ویرایش]

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

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

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

تولید اعداد تصادفی[ویرایش]

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

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

رقم‌های کنترلی[ویرایش]

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

تابع درهم‌ساز[ویرایش]

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

روش همنهشتی خطی[ویرایش]

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

رقم‌های کنترلی[ویرایش]

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

منابع[ویرایش]

  1. Discrete Mathematics and its Applications- Kenneth H. Rosen

Kenneth H, Rosen. “Number Theory and Cryptography”. In Discrete Mathematics and its Applications. SIGS Reference Library. William C Brown Pub; 4th edition, 1998. ISBN ‎0072899050. Retrieved 2007. 

[منابع برای] مطالعه بیشتر[ویرایش]

https://en.wikipedia.org/wiki/Discrete_mathematics