رياضيات متقطعة

رياضيات متقطعة

صنف فرعي من	مجالات الرياضيات — رياضيات بحتة
جزء من	رياضيات
فروع	تحليل توافيقي

تعديل - تعديل مصدري - تعديل ويكي بيانات

إن الرسوم البيانية مثل الرسمة الموجودة أعلاه هي أحد المواضيع التي تتم دراستها في الرياضيات المتقطعة، وذلك بسبب خواصها الرياضياتية، وفوائدها في حل مسائل العالم الحقيقي، وأهميتها في تحسين الخوارزميات الحاسوبية.

الرياضيات المتقطعة أو الرياضيات المنفصلة (بالإنجليزية: Discrete mathematics)‏ أو تدعى أيضا الرياضيات المتناهية أو الرياضيات المحددة (بالإنجليزية: finite mathematics)‏، هي دراسة البنى الرياضية التي تكون متقطعة أساسا، بمعنى أنها لا تستدعي وجود صفة الاتصال ولا تتطلبه لكي تدرس هذا الموضوع.^[1][2][3]

معظم الموضوعات التي تدرسها الرياضيات المتقطعة ترتبط بمجموعات عدودة (قابلة للعد) countable sets (و هو مفهوم مغاير تماما لمفهوم المجموعات المنتهية)، أحد أمثلته: مجموعة الأعداد الصحيحة integers.

إن المواضيع التي تتم دراستها في الرياضيات المتقطعة هي إما أن تكون محددة أو غير محددة. وتُستعمل مصطلح الرياضيات المحددة في بعض الأحيان للإشارة إلى حقول الرياضيات المتقطعة التي تتعامل مع المجموعات المحددة، وخصوصاً في المجالات التي لها صلة بقطاع الأعمال.

اكتسبت الرياضيات المتقطعة شعبية واسعة خلال العقود الأخيرة بسبب تطبيقاتها الواسعة في علوم الحاسوب. فمصطلحات وترميزات الرياضيات المتقطعة مفيدة لدراسة والتعبير عن مسائل الأغراض objects في البرمجة الحاسوبية والخوارزميات. بعض فروع الرياضيات المتقطعة تفيد أيضاً في دراسة بعض مسائل الأعمال والاقتصاد.

المواضيع التي تدرسها

منطق رياضي|المنطق

المنطق هو العلم الذي يبحث في القواعد التي تتبع في التفكير وطرائق الاستدلال الصحيح وأساليب الاستنتاج ومعقوليتها. وهو بذلك أداة للتفكير لأنه يعنى بتحليل طرائق التفكير و صيانته من الخطأ. والعملية المنطقية تهتم بفئة من الصيغ أو القضايا. للمزيد منطق رياضي.

نظرية المجموعات

هو فرع من علم المنطق الرياضي، تهتم بدراسة المجموعات والتي هي تجميع لكائنات رياضية مجردة والعمليات المطبقة عليها، وتشكل إحدى أهم ركائز الرياضيات الحديثة.

نظرية الأعداد

هي فرع من الرياضيات البحتة يهتم بخصائص الأعداد بشكل عام، و بالأعداد الصحيحة بشكل خاص. يدرس العاملون في نظرية الأعداد الأعداد الأولية وخصائص الكائنات المنبثقة عن الأعداد الصحيحة، الأعداد الجذرية مثالا، أو التعميمات للأعداد الصحيحة كما هو الحال بالنسبة للأعداد الصحيحة الجبرية. قد يُنظر إلى الأعداد الصحيحة لذاتها وقد ينظر إليها حلولا لمعادلات ما (هندسة ديوفانتية). وتتضمن عدة مسائل مفتوحة سهلة الفهم، حتى بالنسبة لغير المختصين. بصفة عامة، المجال الذي تدرسه هذه النظرية يهتم بفئة كبيرة من المسائل التي تأتي من دراسة الأعداد الطبيعية. من الممكن تقسيم نظرية الأعداد إلى عدة مجالات حسب الطريقة المستعملة ونوع المسألة. فهي تهتم بدراسة خواص وعلاقات الأعداد الصحيحة وتوسيعاتها الجبرية والتحليلية.

توافقيات

تهتم التوافقيات بشكل خاص بعدّ الكائنات في المجموعات، مع تحديد متى يمكن تحديد المعايير المطلوبة، مع دراسة بناء وتحليل الكائنات التي تحقق هذه المعايير (كما في التصميم التوافقي ونظرية الماترويد)، يهتم هذا العلم أيضا بإيجاد الكائنات الأكبر أو الأصغر أو الأفضل optimal (فيما يعرف : بالتوافقيات الحجمية Extremal combinatorics والتوافقيات التحسينية.

نظرية المخططات

هي نظرية في الرياضيات وعلوم الحاسب، تدرس خواص المخططات حيث يتم تمثيل مجموعة كائنات تدعى رؤوسا، ترتبط ببعضها بأضلاع و تدعى أحيانا أقواسا، يمكن أن تكون موجهة أي مزودة باتجاه (تستخدم الاسهم بدل الأضلاع) أو بدون اتجاه (أضلاع فقط). التمثيل لهذا المخطط يكون على الورق بمجموعة نقاط تمثل الرؤوس متصلة بخطوط هي حروف (أضلاع أو أسهم) المخطط. تُمكن الاستعانة بالمخططات من حلحلة الكثير من المشاكل العملية، فمثلا بنية موسوعة ويكيبيديا يمكن تمثيلها بمخطط رؤوسه هي أسماء المقالات ونقوم برسم خط موجه بين مقالتين من أ إلى ب إذا كانت المقالة أ تحوي رابطا إلى المقالة ب. تطبيقات هذه النظرية واسعة جدا ولحل مشاكلها يستخدم الحاسوب بشكل واسع. لذلك تهتم علوم الحاسوب بتصميم خوارزميات لنظرية المخططات حيث يمكن معالجة أي مخطط لتمييز خصائصه واستخلاص المعلومات منه. للمزيد نظرية المخططات

خوارزميات

الخوارزمية هي مجموعة من الخطوات الرياضية والمنطقية والمتسلسلة اللازمة لحل مشكلة ما. وسميت الخوارزمية بهذا الاسم نسبة إلى العالم المسلم الطاشقندي الاصل أبو جعفر محمد بن موسى الخوارزمي الذي ابتكرها في القرن التاسع الميلادي. الكلمة المنتشرة في اللغات اللاتينية والأوروبية هي «algorithm» وفي الأصل كان معناها يقتصر على خوارزمية لتراكيب ثلاثة فقط وهي: التسلسل والاختيار (selection) والتكرار.

• التسلسل: تكون الخوارزمية عبارة عن مجموعة من التعليمات المتسلسلة، هذه التعليمات قد تكون إما بسيطة أو من النوعين التاليين.
• الاختيار: بعض المشاكل لا يمكن حلها بتسلسل بسيط للتعليمات، وقد تحتاج إلى اختبار بعض الشروط وتنظر إلى نتيجة الاختبار، إذا كانت النتيجة صحيحة تتبع مسار يحوي تعليمات متسلسلة، وإذا كانت خاطئة تتبع مسار آخر مختلف من التعليمات. هذه الطريقة هي ما تسمى اتخاذ القرار أو الاختيار.
• التكرار: عند حل بعض المشاكل لا بد من إعادة نفس تسلسل الخطوات عدد من المرات. وهذا ما يطلق عليه التكرار.

و قد أثُبت أنه لاحاجة إلى تراكيب إضافية. استخدام هذه التراكيب الثلاث يسهل فهم الخوارزمية واكتشاف الأخطاء الواردة فيها وتغييرها.تُمكن الاستعانة بالمخططات من حلحلة الكثير من المشاكل العملية، فمثلا بنية موسوعة ويكيبيديا يمكن تمثيلها بمخطط رؤوسه هي أسماء المقالات ونقوم برسم خط موجه بين مقالتين من أ إلى ب إذا كانت المقالة أ تحوي رابطا إلى المقالة ب. تطبيقات هذه النظرية واسعة جدا ولحل مشاكلها يستخدم الحاسوب بشكل واسع. لذلك تهتم علوم الحاسوب بتصميم خوارزميات لنظرية المخططات حيث يمكن معالجة أي مخطط لتمييز خصائصه واستخلاص المعلومات منه. للمزيد خوارزمية

نظرية المعلومات

أحد تخصصات وفروع الرياضيات التطبيقية الذي يتضمن تكمية Quantification (التحويل إلى كميات) البيانات بهدف تمكين نقل أو تخزين البيانات ضمن وسط ما أو نقلها عبر قناة اتصال ما بأكبر قدر ممكن. قياس المعلومات يعرف عادة بإنتروبية المعلومات وهو عبارة عن العدد الوسطي من البتات (متوسط عدد النبضات الثنائية) اللازم للتخزين أو الاتصال. مثلا، إذا كان وصف الطقس اليومي له إنتروبية بمقدار 3، فذا يعني انه على مدى عدد كاف من الأيام يمكننا وصف الطقس اليومي يمعدل 3 بتات (نبضات ثنائية) لليوم الواحد.

تطبيقات نظرية المعلومات الأساسية تتضمن: ضغط البيانات غير المنقوص lossless data compression: مثلا زيب (صيغة ملفات) ZIP، ضغط البيانات المنقوص Lossy compression مثل إم.بي.ثري MP3، تشفير قنوات نقل البيانات وسعاتها channel capacity مثل خطوط دي.إس.إل DSL. يقع هذا الفرع عند حدود الرياضيات والإحصاء، وعلوم الحاسب والفيزياء والنيوروبيولوجيا والهندسة الكهربائية. تطبيقاتها كانت أساسية في نجاح مهمات فوياجير الفضائية، واختراع سي.دي CD، وتطبيقات الهاتف المحمول، وتطور الإنترنت. وحتى دراسة اللسانيات والاستشعار الإنساني، وأيضا فهم ظاهرة الثقوب السوداء وغيرها من الحقول والتطبيقات العلمية.للمزيد نظرية المعلومات

برهان رياضياتي|البراهين

المبرهنة الرياضية قانون صحيح دائما، يتم البرهنة على صحته، بواسطة التحليل المنطق، انطلاقا من مسلمات ومبرهنات أخرى. في حالة عدم التمكن من إثبات صحة أو خطأ نظرية تسمى حدسية، ولا تصبح مبرهنة رياضية إلا بعد البرهنة النهائية عليها. بعض طرق البرهنة:

1. برهان بالاستنتاج
2. الاستلزام العكسي
3. برهان بفصل الحالات
4. برهان بالتراجع

نظرية الاحتمالات البدائية وسلاسل ماركوف

نظرية الاحتمال (بالإنجليزية: Probability theory)‏ هي النظرية التي تدرس احتمال الحوادث العشوائية. فالبنسبة للرياضيين، الاحتمالات أعداد محصورة في المجال بين 0 و 1 تحدد احتمال حصول أو عدم حصول حدث معين عشوائي أي غير مؤكد. يتم تحديد احتمال الحدث ${\displaystyle E}$ بالقيمة ${\displaystyle P(E)\!}$ حسب بدهيات الاحتمال. كما ندعو احتمال الحدث ${\displaystyle E}$ علما بحدوث الحدث ${\displaystyle F}$ : الاحتمال الشرطي للحدث ${\displaystyle E}$ مع العلم بحدوث ${\displaystyle F}$. نمثل هذا الاحتمال الشرطي بالنسبة بين احتمال التقاطع بين الحدثين (أي حدوثهما معا) إلى احتمال حدوث الحدث ${\displaystyle F}$، أي ${\displaystyle P(E\cap F)/P(F)}$. إذا لم تتغير قيمة الاحتمال الشرطي للحدث ${\displaystyle E}$ علما بوقوع ${\displaystyle F}$ عن القيمة الأصلية غير الشرطية للحدث أي أن الاحتمال واحد في حال وقوع ${\displaystyle F}$ أو عدم وقوعه عندئذ نقول أن هذين الحدثين مستقلين. تناقش نظرية الاحتمالات مصطلحين غاية في الأهمية: المتغير العشوائي والتوزيع الاحتمالي للمتغير العشوائي. للمزيد نظرية الاحتمالات.

سلسلة ماركوف (بالإنجليزية: Markov Chain)‏ مصطلح رياضي وهو عبارة عن عملية تصادفية تحمل خاصية ماركوفية. في عملية كهذه، تكهُنُ المستقبل انطلاقا من الحاضر لا يحتاج إلى معرفة الماضي. ولقد أخذت اسم مبتكرها الروسي أندريا ماركوف.

سلسلة ماركوف في وقت متقطع هي السلسلة X₁, X₂, X₃,... متكونة من متغيرات عشوائية. مجموعة القيمات الممكنة تدعي فضاء الحالات. وX_n تدعى حالة العملية في الآن n.

إذا كان توزيع الاحتمال الشرطي لX_n+1 على الحالات الفارطة دالة وحده إذن ${\displaystyle P(X_{n+1}=x|X_{0},X_{1},X_{2},\ldots ,X_{n})=P(X_{n+1}=x|X_{n}).\,}$. حيث x هي دالة ما في العملية. المعادلة هذه تعرف بالاحتمال الماركوفي. للمزيد سلسلة ماركوف.

جبر خطي

الجبر الخطي هو فرع من الرياضيات يهتم بدراسة الفضاءات المتجهية (أَو الفضاءات الخطية) والتحويلات الخطية والنظم الخطية.

تُشكل الفضاءات المتجهية موضوعاً مركزياً في الرياضيات الحديثة؛ لذا يُستعمل الجبر الخطي كثيراً في كلا من الجبر المجرد والتحليل الدالي. للجبر الخطي أيضاً أهمية في الهندسة التحليلية. كما أن له تطبيقات شاملة في العلوم الطبيعية والعلوم الاجتماعية. للمزيد جبر خطي.

مجموعات مرتبة جزئياً

• • • • نظرية التحسيب ونظرية التعقيد *****

انظر أيضًا

• نظرية الشبكات

مراجع

1. Graphs on Surfaces, Bojan Mohar and Carsten Thomassen, Johns Hopkins University press, 2001 نسخة محفوظة 11 يونيو 2010 على موقع واي باك مشين.
2. Samuel R. Buss (1998). Handbook of Proof Theory. Elsevier. ص. 13. ISBN:978-0-444-89840-1. مؤرشف من الأصل في 2020-01-27.
3. Brotherston، J.؛ Bornat، R.؛ Calcagno، C. (يناير 2008). "Cyclic proofs of program termination in separation logic". ACM SIGPLAN Notices. ج. 43 ع. 1. CiteSeerX:10.1.1.111.1105. DOI:10.1145/1328897.1328453.