نظرية الحوسبة والتعقيد الحسابي
السلام عليكم ورحمة الله وبركاتة
نظرية الحوسبة والتعقيد الحسابي
الحوسبة : تعريفا سلسلة الخطوات الوسيطة intermediate steps التي نستخدمها في انجاز خوارزمية مصممة لحل مشكلة أو مسألة ما بطريقة حاسوبية . يمكن تعريفها أيضا على انها خوارزمية algorithm نقوم بها لتحويل مدخلات input مسألة ما إلى مخرجات outputs (خرج , نتائج) أي حلول للمسألة المطروحة . أي حاسوب يقوم بعملية حوسبة computation عندما ينجز برنامجا ما program ليعطيك نتائج ما أعطيته .
في أي خوارزمية , هناك مجموعة من العمليات الحسابية و المنطقية المتسلسلة , نتيجة كل عملية تستخدم كمدخل للعملية التالية , و يقوم البرنامج المعطى الممثل للخوارزمية برتتيب العمليات و تحديد شروط الانتقال من عملية لأخرى و حتى إمكانية العودة إلى عملية سابقة أو الانتقال إلى عملية لاحقة (ليست تالية) (القفز إلى اعلى و إلى أسفل) .
هذه التعريفات تشكل أساسا لنظرية الحسوبية computability theory و نظرية التعقيد الحسابي computational complexity theory .
يمكن تعريف الحوسبة بأنها إيجاد حلول مسألة مطروحة ابتداءا من معطيات مطروحة لها باستخدام خوارزمية . و يمكن تمديد هذا العلم لإيجاد الخوارزميات المناسبة لحل نمط معين من المسائل . بدورها تتناول نظرية الحوسبة : تحليل المسائل و مدخلاتها Inputs اضافة للخوارزميات Algorithms المطروحة لحلها
نظرية الحسوبية : أحد فروع المعلوماتية النظرية theoretical computer science التي تدرس مسائل قابلة للحل حاسوبيا computationally solvable باستخدام نماذج مختلفة للحوسبة .
نظرية الحسوبية تختلف عن التخصصات المشابهة لنظرية التعقيد الحسابي computational complexity theory , فالأخيرة تتعامل مع سؤال كيفية حل المسألة حاسوبيا بفعالية , بدل من سؤال إذا كانت حسوبة solvable أم لا الذي تتناوله نظرية الحسوبية
نظرية التعقيد الحسابي : احدى اجزاء نظرية الحوسبة و تتعامل مع الموارد المطلوبة في عملية الحوسبة . أكثر هذه الموارد شيوعا هي الزمن (بمعنى كم من الخطوات أو ما يقابلها من الوقت يلزم لحل المسألة ) و المكان (بمعنى ما حجم الذاكرة اللازمة لحل المسألة) , يمكن ان يدخل بالاعتبار موارد أخرى , مثل : كم عدد المعالجات المتوازية اللازمة لإنجاز الحساب باستخدام برمجة متوازية .
تختلف نظرية التعقيد عن نظرية الحسوبية في أن نظرية الحسوبية تدرس فيما إذا كانت المسألة قابلة للحساب ام لا بشكل مطلق , اما نظرية التعقيد فتدرس كيفية إنجاز الحسابات بكفاءة و سرعة
