نگاهی به ریاضیات پیشرفته/ریاضیات گسسته

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

مفاهیم گراف به روش ریاضیات گسسته

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

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

اگرچه موضوعات اصلی مطالعه در ریاضیات گسسته اشیاء گسسته هستند، روش های تحلیلی از ریاضیات "پیوسته" نیز اغلب به کار گرفته می شود.

در برنامه های درسی دانشگاه، "ریاضیات گسسته" در دهه 1980 ظاهر شد، در ابتدا به عنوان یک دوره آموزشی پشتیبانی از علوم کامپیوتر. محتوای آن در آن زمان تا حدودی تصادفی بود. برنامه درسی پس از آن در ارتباط با تلاش های ACM و MAA به دوره ای تبدیل شد که اساساً در نظر گرفته شده است تا بلوغ ریاضی را در دانش آموزان سال اول توسعه دهد. بنابراین امروزه پیش نیاز رشته ریاضی در برخی از دانشگاه ها نیز می باشد.  برخی از کتاب های درسی ریاضیات گسسته در سطح دبیرستان نیز ظاهر شده اند.  در این سطح، ریاضیات گسسته گاهی اوقات به عنوان یک دوره مقدماتی در نظر گرفته می شود، که از این نظر بی شباهت به پیش حساب نیست .

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

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

مباحث ریاضیات گسسته

علوم کامپیتوری نظری

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

نظریه اطلاعات

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

منطق ریاضیات

منطق مطالعه اصول استدلال و استنباط معتبر و همچنین قوام ، درستی و کامل بودن است. به عنوان مثال، در بیشتر سیستم های منطق (اما نه در منطق شهودی ) قانون پیرس ((( P → Q ) → P ) → P ) یک قضیه است. برای منطق کلاسیک، می توان آن را به راحتی با یک جدول حقیقت تأیید کرد . مطالعه برهان ریاضی از اهمیت ویژه ای در منطق برخوردار است و برای اثبات قضیه خودکار و تأیید رسمی نرم افزار کاربرد دارد.

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

تئوری مجموعه ها

نظریه مجموعه‌ها شاخه‌ای از ریاضیات است که مجموعه‌ها را که مجموعه‌ای از اشیاء هستند، مانند {آبی، سفید، قرمز} یا مجموعه (بی نهایت) همه اعداد اول را مطالعه می‌کند. مجموعه ها و مجموعه های جزئی مرتب شده با روابط دیگر در چندین زمینه کاربرد دارند.

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

ترکیبات

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

نظریه گراف

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

نظریه اعداد

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

کاربرد ها

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

منابع

ویکی پدیای انگلیسی

ویکی پدیای فارسی