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

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

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

النطاق

يـُفهم مجال علم الحاسب النظري بشكل واسع على أنه يضم الخوارزميات، بنية البيانات، نظرية التعقيد الحاسوبية، حوسبة موزعة، حوسبة متوازية، 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.

DFAexample.svg Elliptic curve simple.png 6n-graf.svg
المنطق الرياضي Automata theory Number theory Graph theory
Commutative diagram for morphism.svg SimplexRangeSearching.png Blochsphere.svg
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 the functions and appear, then terms of the form 'g(5)=7' or 'h(3,2)=10' might appear. Each entry in this sequence needs to be an application of a basic function or follow from the entries above by using composition, primitive recursion or mu recursion. For instance if , then for 'f(5)=3' to appear, terms like 'g(5)=6' and 'h(5,6)=3' must occur above. The computation terminates only if the final term gives the value of the recursive function applied to the inputs.
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.


انظر أيضا

روابط خارجية