معلوماتية نظرية
تعد نظريةالتحسيب إحدى فروع فهم الحاسوب النظري والرياضيات، والتي تدرس ما إذا كان بالإمكان حل مسائل ما على نموذج تحسيب ما باستخدام خوارزمية ما، ومقدار كفاءة ذلك الحل إذا وجد. يقسم هذا المجال إلى فرعين رئيسين: نظرية التعقيد التحسيبي ونظرية الحسوبية.
تهتم نظرية التحسيب بالمنطق بفرعيه : منطق القضايا (حسبان القضايا) والمنطق الإسنادي إضافة إلى السيمانتيك الشكلي أي بشكل عام نظرية اللغات الشكلية.
النطاق
يـُفهم مجال فهم الحاسب النظري بشكل واسع على أنه يضم الخوارزميات، بنية البيانات، نظرية التعقيد الحاسوبية، حوسبة موزعة، حوسبة متوازية، VLSI, machine learning, فهم الأحياء الحاسوبي، هندسة حاسوبية، نظرية المعلومات، فهم التعمية، quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.
| المنطق الرياضي | Automata theory | Number theory | Graph theory |
| Type theory | Category theory | هندسة حاسوبية | نظرية تحسب كمومي |
التحسيب
في المعلوماتية ، التحسيب computation يعني كيفية تطور حالة الحاسوب مع الزمن، فهما حتى حاسوب هنا يجب حتى تفهم بالمعنى الواسع للحدثة وليس على أنها الحواسيب الرقمية فقط . لكن أحد أمثلة التحسيب الفيزيائي هوتطور حالة الحاسوب الرقمي مع الزمن ، مع ان هناك أمثلة أخرى مثل الحواسب الكمومية، حواسيب الدنا DNA computer أوالحواسيب الجزيئية . في فروع المعلوماتية التي تدرس عمليات التحسيب ، تعهد نماذج رياضية من الحواسيب تدعى آلات تورنگ ، في هذه الحالة يصبح التحسيب شيئا رياضيا بحتاً. الفرع الرياضي الذي يفهم النماذج الرياضية للتحسيب ندعوه نظرية التحسيب .
يمكن تعريف التحسيب أيضا بأنه إيجاد حلول مسألة مطروحة ابتداءا من معطيات مطروحة لها باستخدام خوارزمية . ويمكن تمديد هذا الفهم لإيجاد الخوارزميات المناسبة لحل نمط معين من المسائل .
بدورها تتناول نظرية الحوسبة : تحليل المسائل ومدخلاتها Inputs اضافة للخوارزميات Algorithms المطروحة لحلها .
التحسيب كمفهوم معلوماتي
التحسيب Computation تعريفا سلسلة المراحل الوسيطة intermediate steps التي نستخدمها في انجاز خوارزمية مصممة لحل معضلة أومسألة ما بطريقة حاسوبية . يمكن تعريفها أيضا على انها خوارزمية algorithm نقوم بها لتحويل مدخلات input مسألة ما إلى مخرجات outputs (خرج ، نتائج) أي حلول للمسألة المطروحة . أي حاسوب يقوم بعملية حوسبة computation عندما ينجز برنامجا ما program ليعطيك نتائج ما أعطيته .
في أي خوارزمية ، هناك مجموعة من العمليات الحسابية والمنطقية المتسلسلة ، نتيجة جميع عملية تستخدم كمدخل للعملية التالية ، ويقوم البرنامج المعطى الممثل للخوارزمية برتتيب العمليات وتحديد شروط الانتنطق من عملية لأخرى وحتى إمكانية العودة إلى عملية سابقة أوالانتنطق إلى عملية لاحقة (ليست تالية) (القفز إلى اعلى وإلى أسفل) .
هذه التعريفات تشكل أساسا لنظرية الحسوبية computability theory ونظرية التعقيد الحسابي computational complexity theory .
نظرية التحسيب
نظرية التحسيب theory of computation هي فرع من المعلوماتية يفهم إمكانية حل المسائل المطروحة بكفاءة بوساطة حاسوب . لذلك يمكن تقسيمها إلى : نظرية الحسوبية ونظرية التعقيد الحسابي .وكلاهما يتعاملان مع الناذج الشكلية للتحسيب .
لإنجاز دراسة منهجية للتحسيب ، يشكل فهماء الحاسوب نماذج رياضية مجردة من الحواسيب تدعى نموذج التحسيب model of computation . توجد عدة أنماط من هذه النماذج قيد الاستعمال ، لكن اهمها واكثرها شيوعا هوآلة تورنج . يمكن ان نتصور آلة تورينغ على انها حاسوب منزلي مع سعة ذاكرة محدودة ، ولايمكن الوصول إلا إلى قطاعات صغيرة متفرقة من هذه الذاكرة . تعتبر آلات تورينغ سهلة التصور والتصميم ومن الممكن تحليلها ودراستها للبرهنة عن النتائج المتسقطة بالتالي تمثل نموذجا معقولا لعملية التحسيب .
شرط محدودية الذاكرة ضروري جدا لأن هذا ما يجعل آلة تورينغ واقعية ، ويجعل تنبؤات آلة تورينغ مقبولة فأي مسألة يمكن حلها بوساطة آلوتورينغ يمكن حلها أيضا بوساطة أي حاسوب شخصي ذوذاكرة كافية.
تعاريف شكلية أخرى للتحسيب
Aside from a Turing machine, other equivalent (See: Church–Turing thesis) models of computation are in use.
- تحليل لمبدا
- A computation consists of an initial lambda expression (or two if you want to separate the function and its input) plus a finite sequence of lambda terms, each deduced from the preceding term by one application of Beta reduction.
- منطق توافقي
- is a concept which has many similarities to -calculus, but also important differences exist (e.g. fixed point combinator Y has normal form in combinatory logic but not in -calculus). Combinatory logic was developed with great ambitions: understanding the nature of paradoxes, making foundations of mathematics more economic (conceptually), eliminating the notion of variables (thus clarifying their role in mathematics).
- mu-recursive functions
- a computation consists of a mu-recursive function, i.e. its defining sequence, any input value(s) and a sequence of recursive functions appearing in the defining sequence with inputs and outputs. Thus, if in the defining sequence of a recursive function
- Markov algorithm
- a string rewriting system that uses grammar-like rules to operate on strings of symbols.
- Register machine
- is a theoretically interesting idealization of a computer. There are several variants. In most of them, each register can hold a natural number (of unlimited size), and the instructions are simple (and few in number), e.g. only decrementation (combined with conditional jump) and incrementation exist (and halting). The lack of the infinite (or dynamically growing) external store (seen at Turing machines) can be understood by replacing its role with Gödel numbering techniques: the fact that each register holds a natural number allows the possibility of representing a complicated thing (e.g. a sequence, or a matrix etc.) by an appropriate huge natural number — unambiguity of both representation and interpretation can be established by number theoretical foundations of these techniques.
- P′′
- Like Turing machines, P′′ uses an infinite tape of symbols (without random access), and a rather minimalistic set of instructions. But these instructions are very different, thus, unlike Turing machines, P′′ does not need to maintain a distinct state, because all “memory-like” functionality can be provided only by the tape. Instead of rewriting the current symbol, it can perform a modular arithmetic incrementation on it. P′′ has also a pair of instructions for a cycle, inspecting the blank symbol. Despite its minimalistic nature, it has become the parental formal language of an implemented and (for entertainment) used programming language called Brainfuck.
In addition to the general computational models, some simpler computational models are useful for special, restricted applications. Regular expressions, for example, specify string patterns in many contexts, from office productivity software to programming languages. Another formalism mathematically equivalent to regular expressions, Finite automata are used in circuit design and in some kinds of problem-solving. Context-free grammars specify programming language syntax. Non-deterministic pushdown automata are another formalism equivalent to context-free grammars. Primitive recursive functions are a defined subclass of the recursive functions.
Different models of computation have the ability to do different tasks. One way to measure the power of a computational model is to study the class of formal languages that the model can generate; in such a way to the Chomsky hierarchy of languages is obtained.
انظر أيضا
- حوسبة
روابط خارجية
- صفحة نظرية التحسيب على مسقط معهد MIT لمجموعات الأبحاث
