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

نظرية علم الحاسوب

من ويكيبيديا، الموسوعة الحرة
(بالتحويل من معلوماتية نظرية)
اذهب إلى: تصفح، ‏ ابحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016)

نظرية علوم الحاسوب هو فرع من علم الحاسوب والرياضيات والذي يهتم اكثر بالمواضيع المجردة او المفاهيم الرياضية للحاسوبية ومن ضمنه أيضا نظرية الحاسوبية .

الحوسبة[عدل المصدر]

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

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

الحوسبة كمفهوم معلوماتي[عدل المصدر]

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

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

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

نظرية الحاسوب[عدل المصدر]

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

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

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

انظر أيضا[عدل المصدر]