ریاضیات گسسته - ویکی‌پدیا، دانشنامهٔ آزاد

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

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

• منطق – مطالعهٔ استدلال
• نظریه مجموعه‌ها – مطالعهٔ مجموعه‌ای از عناصر
• نظریه اعداد –
• ترکیبیات – مطالعهٔ شمارش
• نظریه گراف –
• هندسه دیجیتال و توپولوژی دیجیتال
• الگوریتم‌شناسی – مطالعهٔ روش‌های محاسبه
• نظریه اطلاعات –
• نظریهٔ محاسبه‌پذیری و پیچیدگی – بررسی محدودیت‌های نظری و عملی الگوریتم‌ها
• نظریه احتمالات بنیادی و زنجیره مارکوف
• جبر خطی – مطالعهٔ معادلات خطی مرتبط
• تابع –
• مجموعه جزئاً مرتب –
• احتمالات –
• برهان (ریاضی) –
• شمارش –
• رابطه دوتایی –

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• رئوس مطالب ریاضیات گسسته

Kenneth H, Rosen (1998). "Number Theory and Cryptography". Discrete Mathematics and its Applications. SIGS Reference Library (به انگلیسی). William C Brown Pub; 4th edition.

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