كثير حدود (تعقيد)

في علمالتعقيد الحسابي الصنف P هو مجموعة كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج قطعية بوقت بلونومي، لهذا الصنف من المسائل اهمية بالغة في علمالحاسوب والرياضيات إذ يُنظر اليها على انها مجموعة المسائل التي يمكن تطبيقها بشكل عملي معنى الكلام: هذه المجموعة من المسائل يمكن حلها بواسطة الحاسوب المعروف وذلك لان الات تيورنج عبارة عن محاكاة للحاسوب فهو النموذج الرياضي له وقد تحوي هذه المجموعة مسائل غير قابلة للتطبيق في الواقع لان كمية الخطوات بولونومي ولكن قد يفوق القدرة الحسابية للحاسوب مثلا: مسالة وقت حلها n^ ، هذه المسالة غير عملية بالنسبة للحاسوب ولا يمكن تنفيذها أبدًا! حتى ولو كانت كمية المدخلات 2! يتجلى من هذا انه ليس كل ما كان بولونومي يكون حله عملي. ^[1]

جرب الذكاء الاصطناعي

جدول المحتويات

1. 13 علاقات: BPP، EXPTIME، كثير حدود غير قطعي، قاسم مشترك أكبر، نظرية التعقيد الحسابي، متعددة الحدود، مسألة كثير حدود وكثير حدود غير قطعي، بيسبايس، بت، برمجة خطية، رياضيات، علم الحاسوب، عدد أولي.

2. أقسام التعقيد الحسابي

BPP

في علمالتعقيد الحسابي قسمالتعقيد هو قسمالمسائل التي يوجد آلة تيورنج احتمالية وقتها كثير حدود بحيث أن احتمال الخطأ على الأكثر 1/3 لكل المُدخلات.

رؤية كثير حدود (تعقيد) وBPP

EXPTIME

في نظرية التعقيد EXPTIME أو EXP للاختصار هي مجموعة مسائل التي يمكن حلها بوقت أُسي بواسطة آلة تورنغ حتمية.

رؤية كثير حدود (تعقيد) وEXPTIME

كثير حدود غير قطعي

شكل لمسائل كثيري الحدود هي قسم(class) لغات، اللغة(language) في سياقنا هذا هي مجموعة سلاسل (strings) من رموز الابجدية (alphabet) ومسألة التقرير (Decision problem) هي باعطانا سلسلة(string) من الرموز هل هي موجودة باللغة املا أي: L \subseteq \Sigma^*، ويوجد خوارزمية A بحيث ان A(s).

رؤية كثير حدود (تعقيد) وكثير حدود غير قطعي

قاسم مشترك أكبر

في الرياضيات، القاسمالمشترك الأكبر لعددين كما يدل على ذلك اسمه هو أكبر عدد يقسمفي نفس الوقت العددين معاً بدون أي باقي قسمة، فمثلاً القاسمالمشترك الأكبر للعددين 48 و 60 هو 12.

رؤية كثير حدود (تعقيد) وقاسم مشترك أكبر

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

نظرية التعقيد هي فرع من فروع نظرية الحوسبة والرياضيات، وهذه النظرية تتركز في تصنيف المسائل الحاسوبية حسب صعوبتها وربط أقسامالتعقيد complexity classes ببعضها، والمسألة الحاسوبية هي المسألة التي يستطيع الحاسوب بحلها.

رؤية كثير حدود (تعقيد) ونظرية التعقيد الحسابي

متعددة الحدود

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

رؤية كثير حدود (تعقيد) ومتعددة الحدود

مسألة كثير حدود وكثير حدود غير قطعي

يسار إن العلاقة بين مسائل التعقيد كثيرة الحدود وكثير حدود غير قطعي هي مسألة غير محلولة في المعلوماتية النظرية.

رؤية كثير حدود (تعقيد) ومسألة كثير حدود وكثير حدود غير قطعي

بيسبايس

بيسبايس PSPACE في نظرية التعقيد الحسابي قسمالتعقيد هو قسمكل المسائل التي يمكن حلها بكمية موارد حدودية (polynomial space), هذه المجموعة يُعتقد انها أكبر من NP, ولهذا القسماهمية كبيرة في حل الألعاب إذ انه مُعظمالألعاب هي PSPACE صعبة ومسألة التقرير لكثير من الألعاب هي PSPACE كاملة.

رؤية كثير حدود (تعقيد) وبيسبايس

بت

البت أو الثُّنَائِيَّة أو وَأسَمٌ وتجمع على وَأْسَمَاتٌ يتمفي الحواسيب تخزين المعلومات ومعالجتها على شكل بتات (bits) وبذلك يكون نظريا البت أصغر وحدة حاملة أو ناقلة لمعلومة.

رؤية كثير حدود (تعقيد) وبت

برمجة خطية

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

رؤية كثير حدود (تعقيد) وبرمجة خطية

رياضيات

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

رؤية كثير حدود (تعقيد) ورياضيات

علم الحاسوب

تتعامل علومالحاسوب مع النظريات الأساسية للمعلومات والحساب، والتقنيات العملية لتنفيذها وتطبيقها.

رؤية كثير حدود (تعقيد) وعلم الحاسوب

عدد أولي

العدد الأولي والعدد الأول هو عدد طبيعي أكبر قطعاً من 1، لا يقبل القسمة إلا على نفسه وعلى واحد فقط.

رؤية كثير حدود (تعقيد) وعدد أولي

انظر أيضًا

أقسام التعقيد الحسابي

• AC0
• ALL (تعقيد حسابي)
• DLOGTIME
• EXPTIME
• PH(التعقيد الحسابي)
• إس إل (تعقيد حسابي)
• بيسبايس
• قسم تعقيد
• كثير حدود (تعقيد)
• كثير حدود غير قطعي
• كو-إن بي
• مسألة كثيرة حدود غير قطعية كاملة
• مسائل NP صعبة
• مسائل PSPACE كاملة
• مسائل co-NP كاملة
• هرمية كثيرة الحدود
• يو بي (تعقيد حسابي)

المراجع

[1] https://ar.wikipedia.org/wiki/كثير_حدود_(تعقيد)

يونيونبيديا هو عبارة عن خريطة مفهوم أو الشبكة الدلالية تنظيم مثل الموسوعة أو القاموس. أنه يعطي تعريف موجز لكل مفهوم وعلاقاتها.

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

المعلومات مبنية على مقالات من ويكيبيديا ومشاريع ويكيميديا الأخرى، وهي متاحة بموجب رخصة المشاع الإبداعي النسبة-الترخيص بالمثل.

لا يتم اعتماد يونيونبيديا من قبل مؤسسة ويكيميديا أو التابعة لها.

جوجل اللعجوجل اللعGoogle PlayوAndroid وشعار Google Play هي علامات تجارية لشركة Google Inc.

سياسة الخصوصية