مسائل PSPACE كاملة

في نظرية التعقيد الحسابي، مجموعة مسائل التقرير بيسبايس-كاملة (بالإنجليزية: PSPACE-complete) هي مسائل تابعة لقسمالتعقيد PSPACE، بحيث يمكن أن تختصر كل مسألة في PSPACE اليها بوقت متعدد الحدود (انظر التعقيد الكامل). ^[1]

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

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

1. 12 علاقات: كثير حدود (تعقيد)، كثير حدود غير قطعي، قسم تعقيد، لعبة ريفيرسي، نظرية التعقيد الحسابي، مبرهنة سافيتش، مسألة كثير حدود وكثير حدود غير قطعي، اللغة الإنجليزية، بيسبايس، جغرافيا، خوارزمية، شطرنج.

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

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

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

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

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

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

رؤية مسائل PSPACE كاملة وكثير حدود غير قطعي

قسم تعقيد

في علمالتعقيد الحسابي، قسمتعقيد هي مجموعة من المسائل المُتعلقة بالاساس فيما بينها بمورد مُعين، اغلب الاقساملديها التعريف التالي: على سبيل المثال: القسمNP هو مجموعة المسائل التي يمكن حلها بوقت حدودي (أي O(n^c)) بواسطة آلة تيورنج غير حتمية، مثال آخر هو القسمبيسبايس وهو مجموعة المسائل التي يمكن حلها بواسطة آلة تيورنج حتمية وتستخدممكان اضافي طوله حدودي (أي انها تسخدمO(n^c) مكان اضافي).

رؤية مسائل PSPACE كاملة وقسم تعقيد

لعبة ريفيرسي

لعبة ريفيرسي (تسوقها بريسمان بالإسمالتجاري أوتيللو) هي لعبة ألواح إستراتيجية يشارك فيها لاعبان يلعبان على لوح مقسمإلى 8 × 8 مربعات غير مختلفة اللون.

رؤية مسائل PSPACE كاملة ولعبة ريفيرسي

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

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

رؤية مسائل PSPACE كاملة ونظرية التعقيد الحسابي

مبرهنة سافيتش

في نظرية التعقيد الحسابي مبرهنة سافيتش هي نتيجة اساسية مهمة تحدد العلاقة بين تعقيد المساحة القطعي وغير القطعي.

رؤية مسائل PSPACE كاملة ومبرهنة سافيتش

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

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

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

اللغة الإنجليزية

الإنْجِلِيزِيَّةُ أو الإنْكِلِيزِيَّةُ (English) لُغَةٌ جِرْمَانِيَّةٌ غربيةٌ ظهرتْ في إنْجِلْتِرَا العصورِ الوسطى، وأضحتْ في القرنِ الـ21 مـ (الـ15 هـ) وبفعلِ العَوْلَمَةِ لغةً دوليةً واسعةَ الانتشارِ.

رؤية مسائل PSPACE كاملة واللغة الإنجليزية

بيسبايس

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

رؤية مسائل PSPACE كاملة وبيسبايس

جغرافيا

خارطة الأرض الجُغْرَافيّة أو الجِغْرَافيّة أو الجُغرافيا أو وصف الأرض أو عِلْمُ المَعالِمهي علميدرس فيها وصف الأرض من مظاهر عمران بيد البشر وهي المعالم(جغرافية) البشرية وظواهر الطبيعة وهي المعالم(جغرافية) الطبيعية أو بصورة ميسرة الأرض والظواهر الطبيعية (فيزيائية) وحيل التعامل معها والمظاهر البشرية وصور العمران عليها، ويعود أصل الكلمة إلى اللغة الإغريقية، ترجمتها بالعربية «وصف الأرض».

رؤية مسائل PSPACE كاملة وجغرافيا

خوارزمية

يسار الخوارزمية هي مجموعة من الخطوات الرياضية والمنطقية والمتسلسلة اللازمة لحل مشكلة ما.

رؤية مسائل PSPACE كاملة وخوارزمية

شطرنج

الشَّطْرَنـْج (بفتح الشين) أو الشِّطْرَنـْج (بكسر الشين وهو الأجود)، هي لعبة رقعة استراتيجية يلعبها لاعبان على رقعة الشطرنج.

رؤية مسائل PSPACE كاملة وشطرنج

انظر أيضًا

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

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

المراجع

[1] https://ar.wikipedia.org/wiki/مسائل_PSPACE_كاملة

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

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

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

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

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

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