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

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

التحسيب

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

يمكن تعريف التحسيب أيضا بأنه إيجاد حلول مسألة مطروحة ابتداءا من معطيات مطروحة لها باستخدام خوارزمية . و يمكن تمديد هذا العلم لإيجاد الخوارزميات المناسبة لحل نمط معين من المسائل . بدورها تتناول نظرية الحوسبة : تحليل المسائل و مدخلاتها Inputs اضافة للخوارزميات Algorithms المطروحة لحلها .

التحسيب كمفهوم معلوماتي

التحسيب Computation تعريفا سلسلة الخطوات الوسيطة intermediate steps التي نستخدمها في انجاز خوارزمية مصممة لحل مشكلة أو مسألة ما بطريقة حاسوبية . يمكن تعريفها أيضا على انها خوارزمية algorithm نقوم بها لتحويل مدخلات input مسألة ما إلى مخرجات outputs (خرج ، نتائج) أي حلول للمسألة المطروحة . أي حاسوب يقوم بعملية حوسبة computation عندما ينجز برنامجا ما program ليعطيك نتائج ما أعطيته .

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

هذه التعريفات تشكل أساسا لنظرية الحاسوبية computability theory و نظرية التعقيد الحسابي computational complexity theory .

نظرية التحسيب

نظرية التحسيب theory of computation هي فرع من المعلوماتية يدرس إمكانية حل المسائل المطروحة بكفاءة بوساطة حاسوب . لذلك يمكن تقسيمها إلى : نظرية الحاسوبية و نظرية التعقيد الحسابي .و كلاهما يتعاملان مع النماذج الشكلية للتحسيب .

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

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

انظر أيضا

• حوسبة