| dbo:abstract
|
- La teoria de la computació és una ciència, en particular una branca de la matemàtica i de la computació que tracta de quins problemes es poden resoldre en un model de càlcul, mitjançant un algorisme, de quina manera es poden resoldre de manera eficient o en quin grau (per exemple, les solucions aproximades enfront de les precises). Dit d'una altra manera, dés la branca que estudia problemes de decidibilitat. El camp es divideix en tres grans branques: teoria dels autòmats i llenguatges formals, teoria de la computabilitat i teoria de la complexitat computacional, que es relacionen amb la pregunta: "Quines són les capacitats i limitacions fonamentals dels ordinadors?". Per tal de realitzar un estudi rigorós de la computació, els informàtics treballen amb una abstracció matemàtica dels ordinadors anomenada model de computació. Hi ha diversos models en ús, però el més freqüentment examinat és la màquina de Turing. perquè és senzilla de formular, es pot analitzar i utilitzar per demostrar resultats i perquè representa el que molts consideren el model de càlcul "raonable" més potent possible. Podria semblar que la capacitat de memòria potencialment infinita és un atribut irrealitzable, però qualsevol problema resolt per una màquina de Turing sempre requerirà només una quantitat finita de memòria. (ca)
- نظرية الحوسبة أو النظرية الحسابية أو النظرية الاحتسابية (بالإنجليزية: Theory of Computation) في علم الحاسوب يدرس إمكانية حل المسائل المطروحة بكفاءة بوساطة حاسوب ويدرس ما يمكن للحاسوب أن يقوم باحتسابة حاليا وإمكانية تطوره في المستقبل. لذلك يمكن تقسيمها إلى : نظرية الحاسوبية ونظرية نظرية التعقيد الحسابي. و كلاهما يتعاملان مع النماذج الرياضية للتحسيب. لإنجاز دراسة منهجية للتحسيب، يشكل علماء الحاسوب نماذج رياضية مجردة من الحواسيب تدعى نموذج التحسيب model of computation. توجد عدة أنماط من هذه النماذج قيد الاستعمال، لكن أهمها وأكثرها شيوعا هو آلة تورنغ. يمكن أن نتصور آلة تورنغ على أنها حاسوب منزلي مع سعة ذاكرة محدودة، ولايمكن الوصول إلا إلى قطاعات صغيرة متفرقة من هذه الذاكرة. تعتبر آلات تورنغ سهلة التصور والتصميم ومن الممكن تحليلها ودراستها للبرهنة عن النتائج المتوقعة بالتالي تمثل نموذجا معقولا لعملية التحسيب. شرط محدودية الذاكرة ضروري جدا لأن هذا ما يجعل آلة تورنغ واقعية، ويجعل تنبؤات آلة تورنغ مقبولة فأي مسألة يمكن حلها بوساطة آلة تورنغ يمكن حلها أيضا بوساطة أي حاسوب شخصي ذو ذاكرة كافية. في علم الحاسوب النظري والرياضيات، نظرية الحوسبة هي الفرع الذي يختص بفعالية حل المشاكل من خلال نموذج حوسبي باستخدام خوارزمية ما. ينقسم هذا المجال إلى ثلاثة أقسام رئيسية هي: نظرية التشغيل الذاتي واللغات، والنظرية الحاسوبية، ونظرية التعقيد الحسابي اللواتي يربطهن السؤال التالي: «ما هي الإمكانات والقيود الأساسية لأجهزة الحاسوب؟». من أجل إجراء دراسة دقيقة للحوسبة، يعمل علماء الحاسوب مع تجريد رياضي للحواسيب يسمى بنموذج الحوسبة. تُستخدم العديد من النماذج لكن أكثرها شيوعًا هي آلة تورنغ. يدرس علماء الحاسوب آلة تورنغ لأنها سهلة التشكيل، ويمكن تحليلها واستخدامها لإثبات النتائج، ولأنها تمثل ما يعتبره كثيرون أقوى نموذج حسابي «منطقي» ممكن. يبدو أن احتمالية وجود سعة ذاكرة لانهائية هي ميزة غير قابلة للتحقيق، لكن أي مشكلة يُقرر حلها عن طريق آلة تورنغ ستتطلب دائمًا كمية ذاكرة محدودة فقط. لذلك من حيث المبدأ، فإن أي مشكلة يمكن (تَقرّر) حلها عن طريق آلة تورنغ بالتالي يمكن حلها من خلال حاسوب يمتلك كمية محدودة من الذاكرة. تاريخها يمكن أن نعتبر أن نظرية الحوسبة هي إنشاء نماذج من جميع الأنواع في مجال علوم الحاسب. ولذلك يُستخدم فيها الرياضيات والمنطق. أصبحت في العقد الأخير قسمًا أكاديميًا مستقلًا وفُصلت عن الرياضيات. كان من ضمن الرائدين في نظرية الحوسبة رامون لول، ألونزو تشرتش، وكورت غودل، وآلان تورنغ، وستيفن كلين، وروزنا بيتر، وجون فون نيومان وكلود شانون. (ar)
- Η θεωρία υπολογισμού είναι ο κλάδος της θεωρητικής πληροφορικής που πραγματεύεται το εάν και το πόσο αποδοτικά είναι δυνατόν να λυθεί κάποιο πρόβλημα με χρήση κάποιου αλγορίθμου σε ένα , μια αφηρημένη μαθηματική έννοια ορισμένη με αυστηρούς κανόνες. Ο τομέας διαιρείται σε δύο κύριους κλάδους: τη θεωρία υπολογισιμότητας και τη θεωρία πολυπλοκότητας, αλλά και οι δύο εφαρμόζονται σε μοντέλα υπολογισμού. Η θεωρία πολυπλοκότητας παρουσιάζει ομοιότητες με την , έναν άλλο θεμελιώδη κλάδο της επιστήμης υπολογιστών, ο οποίος όμως ενδιαφέρεται για την εύρεση των ιδιοτήτων ενός συγκεκριμένου αλγορίθμου που επιλύει κάποιο υπολογιστικό πρόβλημα, και όχι για τις εγγενείς υπολογιστικές ιδιότητες του ίδιου του προβλήματος. Για να πραγματοποιήσουν μια εξονυχιστική μελέτη της έννοιας του υπολογισμού, οι επιστήμονες αξιοποιούν διάφορες διατυπώσεις υπολογιστικών μοντέλων, αλλά συνηθέστερη είναι η μηχανή Τούρινγκ. Μπορεί κανείς να θεωρήσει τη μηχανή Τούρινγκ σαν έναν προσωπικό υπολογιστή με άπειρη μνήμη, αν και η μνήμη αυτή είναι προσβάσιμη μόνο κατά μικρά διακριτά τμήματα. Οι επιστήμονες υπολογιστών μελετούν τη μηχανή Τούρινγκ γιατί έχει απλή μαθηματική διατύπωση και μπορούν να την αναλύσουν, να την χρησιμοποιήσουν σε αποδείξεις, ενώ κατά πολλούς αντιπροσωπεύει το ισχυρότερο εφικτό μοντέλο υπολογισμού. Αυτό σημαίνει ότι ένα πρόβλημα μπορεί να λυθεί αλγοριθμικά αν και μόνο αν υπάρχει μηχανή Τούρινγκ που το επιλύει. Αν και η άπειρη μνήμη μπορεί να θεωρηθεί ανέφικτη, στην πραγματικότητα κάθε πρόβλημα που λύνει η μηχανή Τούρινγκ χρειάζεται πάντα πεπερασμένη μνήμη, άρα κάθε πρόβλημα που μπορεί να λυθεί από μια μηχανή Τούρινγκ θα μπορούσε να λυθεί από έναν προσωπικό υπολογιστή με επαρκή μνήμη. Η θεωρία υπολογισμού για να φτάσει στα συμπεράσματά της αξιοποιεί το γνωστικό πεδίο των τυπικών γλωσσών, καθώς κάθε πρόβλημα δυνάμενο να επιλυθεί αλγοριθμικά μπορεί να εκφραστεί ως πρόβλημα ανάγνωσης ή παραγωγής μίας τυπικής γλώσσας. Αυτή η επικάλυψη της επιστήμης υπολογιστών με τη μαθηματική λογική και τη γλωσσολογία είχε ως αποτέλεσμα την ανάπτυξη συντακτικών και αναλυτών για την εύκολη κατασκευή μεταγλωττιστών. (el)
- La teorio de kalkulado estas la branĉo de komputiko kiu traktas ĉu kaj kiel kompetente povas esti solvitaj per komputilo. La kampo estas dividita en du ĉefaj branĉoj: komputebleca teorio kaj , sed ambaŭ branĉoj alpaŝas formalajn modelojn de kalkulado. Por plenumi rigoran studon de kalkulado, komputilo-sciencistoj laboras kun matematikaj nomataj kiel modelo de kalkulado. Estas kelkaj formulaĵoj uzataj, sed la plej kutime ekzamenata estas la maŝino de Turing. Maŝino de Turing povas esti konceptita kiel labortabla persona komputilo kun malfinia memora kapacito, kvankam ĝi povas atingi tiun memoron nur en malgrandaj diskretaj buloj. Komputikistoj studas la maŝinon de Turing ĉar ĝi estas simple formulebla, povas esti analizita kaj kutime eblas pruvi la rezultojn, kaj ĉar ĝi prezentas tion kion multaj konsideras kiel la plej pova ebla "modera" modelo de kalkulado. Dum la malfinia memora kapacito povus esti konsiderata nefizika atributo, por ajna problemo reale solvata per maŝino de Turing la memoro uzata ĉiam estas finia, do ajna problemo, kiu povas esti solvita per maŝino de Turing povis esti solvita per kutima reala komputilo, kiu havas sufiĉan memoron. (eo)
- La teoría de la computación o teoría de la informática es un conjunto de conocimientos racionales y sistematizados que se centran en el estudio de la abstracción de los procesos, con el fin de reproducirlos con ayuda de sistemas formales; es decir, a través de símbolos y reglas lógicas. La teoría de la computación permite modelar procesos dentro de las limitaciones de dispositivos que procesan información y que efectúan cálculos; como, por ejemplo, el ordenador. Para ello, se apoya en la teoría de autómatas, a fin de simular y estandarizar dichos procesos, así como para formalizar los problemas y darles solución. (es)
- Konputazioaren teoria edo teoria informatikoa prozesuen abstrakzioaren azterketan zentratzen den ezagutza arrazional eta sistematizatuaren multzoa da, sistema formalen laguntzaz erreproduzitzeko, hau da, sinboloen eta arau logikoen bidez. Konputazioaren teoriak prozesuak modelatzeko aukera ematen du informazioa prozesatzen eta kalkuluak egiten dituzten gailuen mugen barruan; adibidez, ordenagailua. Horretarako, automaten teorian oinarritzen da prozesu horiek simulatu eta estandarizatzeko, bai eta arazoak formalizatu eta irtenbideak emateko ere. (eu)
- Teori komputasi adalah cabang ilmu komputer dan matematika yang membahas apakah dan bagaimanakah suatu masalah dapat dipecahkan pada , menggunakan algoritma. Bidang ilmu ini terutama membahas hal terkait komputabilitas dan kompleksitas, dalam kaitannya dengan formalisme komputasi.Bidang teori komputasi dibagi menjadi tiga cabang besar: dan bahasa formal, dan , dimana dihubungkan dengan pertanyaan: "Apa saja kemampuan dan batasan yang dimiliki komputer?". Untuk melakukan studi komputasi dengan ketat, ilmuwan komputer bekerja dengan abstraksi matematika dari komputer yang dinamakan . Ada beberapa model yang digunakan, tetapi yang paling umum dipelajari adalah mesin Turing. Para ilmuwan mempelajari mesin Turing karena mudah untuk diformulasikan, bisa di analisa dan digunakan untuk membuktikan sebuah hasil, dan karena mesin Turing merepresentasikan model komputasi yang kuat dan "cocok" (lihat ). Hal ini sepertinya memiliki potensial kapasitas memori tak terhingga merupakan atribut yang tak disadari, tetapi pada tiap permasalahan logika diselesaikan oleh mesin Turing selalu membutuhkan memori yang terbatas. Sehingga, dalam prinsipnya setiap permasalahan yang bisa diselesaikan (dipilih untuk diselesaikan) oleh mesin Turing bisa diselesaikan oleh komputer ynag memiliki memori yang terbatas. Sebuah mesin Turing dapat dipikirkan sebagai komputer pribadi meja dengan kapasitas memori yang tak terhingga, tetapi hanya dapat diakses dalam bagian-bagian terpisah dan diskret. Ilmuwan komputer mempelajari mesin Turing karena mudah dirumuskan, dianalisis dan digunakan untuk pembuktian, dan karena mesin ini mewakili model komputasi yang dianggap sebagai model paling masuk akal yang paling ampuh yang dimungkinkan. Kapasitas memori tidak terbatas mungkin terlihat sebagai sifat yang tidak mungkin terwujudkan, tetapi setiap permasalahan yang "terputuskan" (decidable) yang dipecahkan oleh mesin Turing selalu hanya akan memerlukan jumlah memori terhingga. Jadi pada dasarnya setiap masalah yang dapat dipecahkan (diputuskan) oleh meisn Turing dapat dipecahkan oleh komputer yang memiliki jumlah memori terbatas. (in)
- La teoria della computazione è quella branca della matematica che si preoccupa di definire quali proprietà possiede uno specifico linguaggio formale. Le principali proprietà ricercate da un linguaggio formale sono:
* La correttezza: ogni volta che un linguaggio formale definisce un enunciato come vero questo enunciato deve effettivamente essere vero.
* La completezza: il linguaggio formale deve essere in grado di estrarre tutti gli enunciati veri, e solo quegli enunciati devono essere veri; se il linguaggio è completo non devono esistere altri enunciati veri al di fuori di quelli precedentemente estratti.
* La terminazione: ogni algoritmo correttamente definito nel linguaggio formale deve terminare sempre in tempo finito. Non tutte le proprietà sono necessarie: spesso i linguaggi formali hanno solo la prima e la seconda proprietà. In alcune applicazioni ci si accontenta di avere anche solo la prima proprietà che chiaramente è irrinunciabile: senza la prima proprietà si potrebbero avere enunciati chiaramente falsi ma che vengono dichiarati veri dal linguaggio formale, generando contraddizioni. Nel caso si abbiano tutte le tre proprietà è conveniente cercare di definire la complessità degli algoritmi definiti del linguaggio formale. La complessità è una funzione che stima il numero di passi necessari ad eseguire uno specifico algoritmo. (it)
- In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., approximate solutions versus precise ones). The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?". In order to perform a rigorous study of computation, computer scientists work with a mathematical abstraction of computers called a model of computation. There are several models in use, but the most commonly examined is the Turing machine. Computer scientists study the Turing machine because it is simple to formulate, can be analyzed and used to prove results, and because it represents what many consider the most powerful possible "reasonable" model of computation (see Church–Turing thesis). It might seem that the potentially infinite memory capacity is an unrealizable attribute, but any decidable problem solved by a Turing machine will always require only a finite amount of memory. So in principle, any problem that can be solved (decided) by a Turing machine can be solved by a computer that has a finite amount of memory. (en)
- 계산 이론(計算理論, Theory of computation)은 컴퓨터 과학의 한 갈래로, 어떤 문제를 컴퓨터로 풀 수 있는지, 또 얼마나 효율적으로 풀 수 있는지를 탐구한다. 이 분야는 크게 계산 가능성 이론과 계산 복잡도 이론으로 나뉘어 있는데, 두 분야 모두 추상 기계를 다룬다. (ko)
- 計算理論（けいさんりろん、theory of computation）は、理論計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。 計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。 (ja)
- Teoria obliczeń – dział informatyki i matematyki, który dzieli się na: teorię automatów i języków formalnych, teorię obliczalności oraz teorię złożoności. Teoria automatów zajmuje się definicjami i własnościami (modelami maszyn liczących). W uproszczeniu zajmuje się ona odpowiedzią na pytanie czym jest komputer, teoria obliczalności odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a teoria złożoności – odpowiedzą na pytanie jakim kosztem (czasowym i pamięciowym) da się to zrobić. Modele obliczeń stosuje się w praktyce, na przykład model zwany automatem skończonym jest wykorzystywany w architekturze komputerów, budowie kompilatorów i w przetwarzaniu tekstu (przetwarzanie języka naturalnego, synteza mowy). Inny model, nazywany gramatyką bezkontekstową, jest używany przy projektowaniu języków programowania i sztucznej inteligencji. Najogólniejszym modelem obliczeń jest maszyna Turinga. Można ją rozumieć jako komputer o nieograniczonych zasobach pamięci. Inne używane modele, takie jak: rachunek lambda, rachunek kombinatorów, , funkcje rekurencyjne są sobie równoważne w tym sensie, że wszystko co jest obliczalne na jednym z nich, da się też obliczyć na maszynie Turinga. Rozważa się również węższe modele tzn. takie, które nie pozwalają na wyrażenie dowolnej funkcji obliczalnej, np. funkcje pierwotnie rekurencyjne. O niektórych problemach związanych z modelami obliczeń wiadomo, że są nierozstrzygalne. Na przykład nie istnieje algorytm, który rozstrzyga czy dwa λ-wyrażenia są równoważne lub czy maszyna Turinga dla danego wejścia zatrzyma się (zob. problem stopu). Podstawowym obiektem badań teorii obliczalności są funkcje obliczalne. Problem P vs NP jest określany jako najważniejszy nierozwiązany problem matematyczny w informatyce. (pl)
- Beräkningsteori, som är en underdisciplin till matematik och datavetenskap, behandlar analys av problem, indata och algoritmer. Beräkning kan definieras som sökandet efter en lösning på ett problem från ett givet indata med hjälp av en algoritm. (sv)
- A teoria da computação é um subcampo da ciência da computação e matemática que busca determinar quais problemas podem ser computados em um dado modelo de computação. A computação pode ser definida como a solução de um problema ou, formalmente, o cálculo de uma função por meio de um algoritmo. Apesar de intuitivo na história humana, o conceito de execução de uma tarefa com passos finitos a fim de se obter um resultado, ou seja, um algoritmo, não possuía uma definição formal até a conceituação do modelo de Máquina Universal de Turing. A teoria da computação teve início nos primeiros anos do século XX, antes da invenção dos modernos computadores eletrônicos. Naquele período, após a famosa palestra do matemático alemão David Hilbert em que ele listou os maiores desafios no campo da matemática para o século vindouro, os matemáticos se debruçavam sobre o décimo problema de Hilbert tentando descobrir quais problemas matemáticos poderiam ser resolvidos por um método efetivo, e quais não poderiam. O primeiro passo estava em definir o significado de um "método efetivo" para resolver o problema. Em outras palavras, eles precisavam de um modelo formal da computação. Diversos modelos diferentes da computação foram propostos pelos primeiros pesquisadores. Um modelo, conhecido como Máquina de Turing, propunha a construção de uma máquina universal, capaz de operar com uma sequência de instruções e dados entremeados em uma fita de comprimento infinito; a máquina poderia operar em um ponto da fita de cada vez utilizando um cabeçote de leitura e escrita, executando assim a programação que lhe fosse passada. Outro modelo se baseia em funções recursivas compostas para operar diretamente sobre os números. Uma abordagem similar é o cálculo lambda. Outra classe de abordagens trabalha com regras gramaticais operando sobre cadeias de caracteres, como é o caso dos cadeias de Markov e dos . Todos os formalismos propostos acima são equivalentes em termos de poder computacional—ou seja, qualquer computação que possa ser realizada com um modelo pode ser realizada com qualquer um dos outros modelos. Ainda em termos teóricos, os modelos propostos são equivalentes aos computadores eletrônicos, desde que não haja restrições de memória envolvidas. Na verdade, acredita-se que todas as formalizações teoricamente possíveis para o conceito de algoritmo são equivalentes em poder a uma máquina de Turing; esta é a tese de Church-Turing. As questões relativas à possibilidade de realizar certos tipos de computação em determinados tipos de máquina (ou formalismo teórico) são investigadas pela teoria da computabilidade. A teoria da computação estuda os modelos de computação genéricos, assim como os limites da computação:
* Quais problemas jamais poderão ser resolvidos por um computador, independente da sua velocidade ou memória? (Ver: Problema da parada, Problema da Correspondência de Post.)
* Quais problemas podem ser resolvidos por um computador, mas requerem um período tão extenso de tempo para completar a ponto de tornar a solução impraticável? (Ver: Aritmética de Presburger.)
* Em que situações pode ser mais difícil resolver um problema do que verificar cada uma das soluções manualmente? (Ver Classes P e NP). Em geral, as questões relativas aos requerimentos de tempo ou espaço (memória, em particular) de problemas específicos são investigadas pela teoria da complexidade computacional. Além dos modelos genéricos de computação, alguns modelos computacionais mais simples são úteis para aplicações mais restritas. Expressões regulares, são por exemplo utilizadas para especificar padrões de cadeias de caracteres, sendo populares em aplicações UNIX e em algumas linguagens de programação, como Perl e Python. Outro formalismo matematicamente equivalente às expressões regulares são os autômatos finitos, que são utilizados em desenho de circuitos e em alguns sistemas de resolução de problemas. As gramáticas livres de contexto são utilizadas para especificar a sintaxe das linguagens de programação; um formalismo equivalente, são os autômatos com pilha, ou pushdown automata. As funções recursivas primitivas formam uma subclasse das funções recursivas. Modelos de computação diferentes podem realizar tarefas distintas. Uma forma de estudar o poder de um modelo computacional é estudar a classe das linguagens formais que o modelo pode gerar; o resultado é a hierarquia de Chomsky das linguagens. As tabelas abaixo mostram algumas das classes de problemas (ou linguagens, ou gramáticas) que são consideradas em teoria da computabilidade (azul) e em teoria da complexidade (vermelho). Se a classe X é um subconjunto propriamente contido em Y, então X é mostrado abaixo de Y, conectados por um linha escura. Se X é um subconjunto, mas não é sabido se os conjuntos são iguais ou não, então a linha que os conecta será mais clara e pontilhada.
* Teoria dos problemas
* Teoria dos grafos
* Linguagem de Computadores
* Linguagem formal
* Hierarquia de Chomsky
* Reconhecedores
* Autômatos
* Modelo computacional
* Máquina de Turing
* Cálculo Lambda
*
* Compilador
* Análise léxica
* Análise sintática
* Análise semântica
* Interpretador (pt)
- 计算理论（英語：Theory of computation）是數學的一個領域，和计算机有密切关系。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。该领域主要关心三个方面的问题：
* 采用什么计算模型（即形式语言、自动机）
* 解决哪些是可计算的、哪些是不可计算的（即可计算性理论及演算法）
* 要用多少时间、要用多少存储（即計算複雜性理論） 這三方面的問題可以用一個問題來總括：「電腦的基礎能力及限制到什麼程度？」 計算理論的「計算」並非指純粹的算術運算（Calculation），而是指從已知的輸入透過算法來取得一個問題的答案（Computation），因此，計算理論屬於理論計算機科學和應用數學。 為了對計算進行嚴謹的研究，電腦科學家會將計算以數學的方式抽象化，稱為计算模型。有幾種目前在使用的计算模型，其中最出名的是圖靈機。電腦科學家研究圖靈機的原因是它很容易敘述，可以分析，用來證明結果，而且用此模式呈現了許多強而有力的計算模型（參照邱奇－图灵论题）。圖靈機有潛在的，數量無限的記憶能力，這似乎是不可能達到的，不過所有圖靈機解決的可判定性問題都只需要有限量的記憶能力。因此理論上，任何可以用圖靈機解決的（可判定性）問題都只需要有限量的記憶能力。 (zh)
- Тео́рия алгори́тмов — раздел математики, изучающий общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. Вместе с математической логикой теория алгоритмов образует теоретическую основу вычислительных наук, теории передачи информации, информатики, телекоммуникационных систем и других областей науки и техники. (ru)
- Теорія алгоритмів (англ. Theory of computation) — окремий розділ математики, що вивчає загальні властивості алгоритмів. Виникла в 30-х роках 20 століття. Алгоритми, проте, простежуються в математиці протягом всього часу її існування. Необхідність точного математичного уточнення інтуїтивного поняття алгоритму стала неминучою після усвідомлення неможливості існування алгоритмів розв'язку багатьох масових проблем, в першу чергу пов'язаних з арифметикою та математичною логікою (проблеми істинності арифметичних формул та формул першопорядкового числення предикатів, 10-та проблема Гільберта про розв'язність діофантових рівнянь та ін.). Для доведення неіснування алгоритму треба мати його точне математичне визначення, тому після сформування поняття алгоритму як нової та окремої сутності першочерговою стала проблема знаходження адекватних формальних моделей алгоритму та дослідження їх властивостей. При цьому формальні моделі були запропоновані як для первісного поняття алгоритму, так і для похідного поняття алгоритмічно обчислюваної функції. (uk)
|
| rdfs:comment
|
- La teoría de la computación o teoría de la informática es un conjunto de conocimientos racionales y sistematizados que se centran en el estudio de la abstracción de los procesos, con el fin de reproducirlos con ayuda de sistemas formales; es decir, a través de símbolos y reglas lógicas. La teoría de la computación permite modelar procesos dentro de las limitaciones de dispositivos que procesan información y que efectúan cálculos; como, por ejemplo, el ordenador. Para ello, se apoya en la teoría de autómatas, a fin de simular y estandarizar dichos procesos, así como para formalizar los problemas y darles solución. (es)
- Konputazioaren teoria edo teoria informatikoa prozesuen abstrakzioaren azterketan zentratzen den ezagutza arrazional eta sistematizatuaren multzoa da, sistema formalen laguntzaz erreproduzitzeko, hau da, sinboloen eta arau logikoen bidez. Konputazioaren teoriak prozesuak modelatzeko aukera ematen du informazioa prozesatzen eta kalkuluak egiten dituzten gailuen mugen barruan; adibidez, ordenagailua. Horretarako, automaten teorian oinarritzen da prozesu horiek simulatu eta estandarizatzeko, bai eta arazoak formalizatu eta irtenbideak emateko ere. (eu)
- 계산 이론(計算理論, Theory of computation)은 컴퓨터 과학의 한 갈래로, 어떤 문제를 컴퓨터로 풀 수 있는지, 또 얼마나 효율적으로 풀 수 있는지를 탐구한다. 이 분야는 크게 계산 가능성 이론과 계산 복잡도 이론으로 나뉘어 있는데, 두 분야 모두 추상 기계를 다룬다. (ko)
- 計算理論（けいさんりろん、theory of computation）は、理論計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。 計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。 (ja)
- Beräkningsteori, som är en underdisciplin till matematik och datavetenskap, behandlar analys av problem, indata och algoritmer. Beräkning kan definieras som sökandet efter en lösning på ett problem från ett givet indata med hjälp av en algoritm. (sv)
- 计算理论（英語：Theory of computation）是數學的一個領域，和计算机有密切关系。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。该领域主要关心三个方面的问题：
* 采用什么计算模型（即形式语言、自动机）
* 解决哪些是可计算的、哪些是不可计算的（即可计算性理论及演算法）
* 要用多少时间、要用多少存储（即計算複雜性理論） 這三方面的問題可以用一個問題來總括：「電腦的基礎能力及限制到什麼程度？」 計算理論的「計算」並非指純粹的算術運算（Calculation），而是指從已知的輸入透過算法來取得一個問題的答案（Computation），因此，計算理論屬於理論計算機科學和應用數學。 為了對計算進行嚴謹的研究，電腦科學家會將計算以數學的方式抽象化，稱為计算模型。有幾種目前在使用的计算模型，其中最出名的是圖靈機。電腦科學家研究圖靈機的原因是它很容易敘述，可以分析，用來證明結果，而且用此模式呈現了許多強而有力的計算模型（參照邱奇－图灵论题）。圖靈機有潛在的，數量無限的記憶能力，這似乎是不可能達到的，不過所有圖靈機解決的可判定性問題都只需要有限量的記憶能力。因此理論上，任何可以用圖靈機解決的（可判定性）問題都只需要有限量的記憶能力。 (zh)
- Тео́рия алгори́тмов — раздел математики, изучающий общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. Вместе с математической логикой теория алгоритмов образует теоретическую основу вычислительных наук, теории передачи информации, информатики, телекоммуникационных систем и других областей науки и техники. (ru)
- نظرية الحوسبة أو النظرية الحسابية أو النظرية الاحتسابية (بالإنجليزية: Theory of Computation) في علم الحاسوب يدرس إمكانية حل المسائل المطروحة بكفاءة بوساطة حاسوب ويدرس ما يمكن للحاسوب أن يقوم باحتسابة حاليا وإمكانية تطوره في المستقبل. لذلك يمكن تقسيمها إلى : نظرية الحاسوبية ونظرية نظرية التعقيد الحسابي. و كلاهما يتعاملان مع النماذج الرياضية للتحسيب. شرط محدودية الذاكرة ضروري جدا لأن هذا ما يجعل آلة تورنغ واقعية، ويجعل تنبؤات آلة تورنغ مقبولة فأي مسألة يمكن حلها بوساطة آلة تورنغ يمكن حلها أيضا بوساطة أي حاسوب شخصي ذو ذاكرة كافية. تاريخها (ar)
- La teoria de la computació és una ciència, en particular una branca de la matemàtica i de la computació que tracta de quins problemes es poden resoldre en un model de càlcul, mitjançant un algorisme, de quina manera es poden resoldre de manera eficient o en quin grau (per exemple, les solucions aproximades enfront de les precises). Dit d'una altra manera, dés la branca que estudia problemes de decidibilitat. El camp es divideix en tres grans branques: teoria dels autòmats i llenguatges formals, teoria de la computabilitat i teoria de la complexitat computacional, que es relacionen amb la pregunta: "Quines són les capacitats i limitacions fonamentals dels ordinadors?". (ca)
- Η θεωρία υπολογισμού είναι ο κλάδος της θεωρητικής πληροφορικής που πραγματεύεται το εάν και το πόσο αποδοτικά είναι δυνατόν να λυθεί κάποιο πρόβλημα με χρήση κάποιου αλγορίθμου σε ένα , μια αφηρημένη μαθηματική έννοια ορισμένη με αυστηρούς κανόνες. Ο τομέας διαιρείται σε δύο κύριους κλάδους: τη θεωρία υπολογισιμότητας και τη θεωρία πολυπλοκότητας, αλλά και οι δύο εφαρμόζονται σε μοντέλα υπολογισμού. Η θεωρία πολυπλοκότητας παρουσιάζει ομοιότητες με την , έναν άλλο θεμελιώδη κλάδο της επιστήμης υπολογιστών, ο οποίος όμως ενδιαφέρεται για την εύρεση των ιδιοτήτων ενός συγκεκριμένου αλγορίθμου που επιλύει κάποιο υπολογιστικό πρόβλημα, και όχι για τις εγγενείς υπολογιστικές ιδιότητες του ίδιου του προβλήματος. (el)
- La teorio de kalkulado estas la branĉo de komputiko kiu traktas ĉu kaj kiel kompetente povas esti solvitaj per komputilo. La kampo estas dividita en du ĉefaj branĉoj: komputebleca teorio kaj , sed ambaŭ branĉoj alpaŝas formalajn modelojn de kalkulado. (eo)
- Teori komputasi adalah cabang ilmu komputer dan matematika yang membahas apakah dan bagaimanakah suatu masalah dapat dipecahkan pada , menggunakan algoritma. Bidang ilmu ini terutama membahas hal terkait komputabilitas dan kompleksitas, dalam kaitannya dengan formalisme komputasi.Bidang teori komputasi dibagi menjadi tiga cabang besar: dan bahasa formal, dan , dimana dihubungkan dengan pertanyaan: "Apa saja kemampuan dan batasan yang dimiliki komputer?". (in)
- In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., approximate solutions versus precise ones). The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?". (en)
- La teoria della computazione è quella branca della matematica che si preoccupa di definire quali proprietà possiede uno specifico linguaggio formale. Le principali proprietà ricercate da un linguaggio formale sono: Non tutte le proprietà sono necessarie: spesso i linguaggi formali hanno solo la prima e la seconda proprietà. In alcune applicazioni ci si accontenta di avere anche solo la prima proprietà che chiaramente è irrinunciabile: senza la prima proprietà si potrebbero avere enunciati chiaramente falsi ma che vengono dichiarati veri dal linguaggio formale, generando contraddizioni. (it)
- A teoria da computação é um subcampo da ciência da computação e matemática que busca determinar quais problemas podem ser computados em um dado modelo de computação. A computação pode ser definida como a solução de um problema ou, formalmente, o cálculo de uma função por meio de um algoritmo. Apesar de intuitivo na história humana, o conceito de execução de uma tarefa com passos finitos a fim de se obter um resultado, ou seja, um algoritmo, não possuía uma definição formal até a conceituação do modelo de Máquina Universal de Turing. (pt)
- Teoria obliczeń – dział informatyki i matematyki, który dzieli się na: teorię automatów i języków formalnych, teorię obliczalności oraz teorię złożoności. Teoria automatów zajmuje się definicjami i własnościami (modelami maszyn liczących). W uproszczeniu zajmuje się ona odpowiedzią na pytanie czym jest komputer, teoria obliczalności odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a teoria złożoności – odpowiedzą na pytanie jakim kosztem (czasowym i pamięciowym) da się to zrobić. (pl)
- Теорія алгоритмів (англ. Theory of computation) — окремий розділ математики, що вивчає загальні властивості алгоритмів. Виникла в 30-х роках 20 століття. Алгоритми, проте, простежуються в математиці протягом всього часу її існування. Необхідність точного математичного уточнення інтуїтивного поняття алгоритму стала неминучою після усвідомлення неможливості існування алгоритмів розв'язку багатьох масових проблем, в першу чергу пов'язаних з арифметикою та математичною логікою (проблеми істинності арифметичних формул та формул першопорядкового числення предикатів, 10-та проблема Гільберта про розв'язність діофантових рівнянь та ін.). Для доведення неіснування алгоритму треба мати його точне математичне визначення, тому після сформування поняття алгоритму як нової та окремої сутності першочерго (uk)
|
