| dbpedia-owl:abstract
|
- In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into three major branches: automata theory, computability theory and computational complexity theory. 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. 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 bounded amount of memory.
- La teoría de la computación es una rama de la matemática y la computación que centra su interés en las limitaciones y capacidades fundamentales de las computadoras. Específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un cómputo (cuenta o cálculo) y la clasificación de problemas
- Laskettavuus tai laskettavuusteoria on teoreettisen tietojenkäsittelytieteen haara, joka tutkii ongelmien ratkeavuutta ja ratkaisemisen tehokkuutta algoritmisesti. Käytännössä laskettavuusteoriassa pyritään selvittämään, voidaanko jokin ongelma ratkaista tietokoneiden avulla vai ei, ja jos voidaan, kuinka tehokkaasti. Tehokkuus voi tarkoittaa joko laskennan vaatimaa aikaa tai muistikapasiteettia. Ongelmanasettelu on ensin muotoiltava täsmällisesti erilaisten laskennan mallien avulla, joiden voidaan ajatella olevan tietokoneiden matemaattisia malleja. Esimerkki tällaisesta mallista on Turingin kone. Vasta tämän jälkeen voidaan analysoida, kuinka paljon laskentaresursseja tehtävä vaatii tai onko se ylipäänsä ratkaistavissa.
- 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 ad 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.
- 計算理論（けいさんりろん、theory of computation）は、計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。 計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは最も強力な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、チューリングマシンで具体的な問題を解く際に使われるメモリ量は常に有限であり、チューリングマシンで解くことが出来る問題は普通の（メモリをそれなりに搭載した）コンピュータでも解くことが出来る。
- Teoria obliczeń to dział informatyki teoretycznej. Dzieli się on na dwie główne części: teorię obliczalności oraz złożoność obliczeniową. Pierwszy z nich zajmuje się odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a drugi tym jak szybko da się to zrobić. Rozważania tego typu nie są możliwe bez formalnego, matematycznego modelu komputera. Najczęściej używanym modelem jest maszyna Turinga. Taką maszynę można w uproszczeniu rozumieć jako komputer o nieograniczonych zasobach pamięci. Inne używane modele, takie jak: rachunek lambda, rachunek kombinatorów, algorytmy Markowa, 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). 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 się zatrzyma.
- Computação pode ser definida como a solução de um problema ou, formalmente, o cálculo de uma função, através de um algoritmo. A teoria da computação, um subcampo da ciência da computação e matemática, busca determinar quais problemas podem ser computados em um dado modelo de computação. Por milhares de anos, a computação foi feita com lápis e papel, ou giz e quadro, ou mentalmente, às vezes com a ajuda de tabelas. A teoria da computação teve início nos primeiros anos do século XX, antes da invenção dos modernos computadores eletrônicos. Naquela época, os matemáticos estavam tentando descobrir quais problemas matemáticos poderiam ser resolvidos por um método simples, e quais não poderiam. O primeiro passo estava em definir o significado de um "método simples" 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 for 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 sistemas de Post. 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? 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 solucão impraticável? Em que situações pode ser mais difícil resolver um problema do que verificar cada uma das soluções manualmente?. 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 linguages 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 Linguagem While Compilador Análise léxica Análise sintática Análise semântica Interpretador
- 计算理论和计算机有密切关系，解决哪些是能计算的、哪些是不能计算的（即可计算性理论）、有多快、要用多少存储 （即計算複雜性理論），以及采用什么计算模型的理论。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。 計算理論的「計算」並非指純粹的算術運算（Calculation），而是指從已知的輸入透過算法來取得一個問題的答案（Computation），因此，計算理論屬於計算機科學和數學。 計算理論早於現代計算機發明前的20世紀便開始了。
- Тео́рия алгори́тмов — наука, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п.
|
| rdfs:comment
|
- La teoría de la computación es una rama de la matemática y la computación que centra su interés en las limitaciones y capacidades fundamentales de las computadoras. Específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un cómputo (cuenta o cálculo) y la clasificación de problemas
- 計算理論（けいさんりろん、theory of computation）は、計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。 計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは最も強力な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、チューリングマシンで具体的な問題を解く際に使われるメモリ量は常に有限であり、チューリングマシンで解くことが出来る問題は普通の（メモリをそれなりに搭載した）コンピュータでも解くことが出来る。
- 计算理论和计算机有密切关系，解决哪些是能计算的、哪些是不能计算的（即可计算性理论）、有多快、要用多少存储 （即計算複雜性理論），以及采用什么计算模型的理论。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。 計算理論的「計算」並非指純粹的算術運算（Calculation），而是指從已知的輸入透過算法來取得一個問題的答案（Computation），因此，計算理論屬於計算機科學和數學。 計算理論早於現代計算機發明前的20世紀便開始了。
- Тео́рия алгори́тмов — наука, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п.
- In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into three major branches: automata theory, computability theory and computational complexity theory. In order to perform a rigorous study of computation, computer scientists work with a mathematical abstraction of computers called a model of computation.
- Laskettavuus tai laskettavuusteoria on teoreettisen tietojenkäsittelytieteen haara, joka tutkii ongelmien ratkeavuutta ja ratkaisemisen tehokkuutta algoritmisesti. Käytännössä laskettavuusteoriassa pyritään selvittämään, voidaanko jokin ongelma ratkaista tietokoneiden avulla vai ei, ja jos voidaan, kuinka tehokkaasti. Tehokkuus voi tarkoittaa joko laskennan vaatimaa aikaa tai muistikapasiteettia.
- 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.
- Teoria obliczeń to dział informatyki teoretycznej. Dzieli się on na dwie główne części: teorię obliczalności oraz złożoność obliczeniową. Pierwszy z nich zajmuje się odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a drugi tym jak szybko da się to zrobić. Rozważania tego typu nie są możliwe bez formalnego, matematycznego modelu komputera. Najczęściej używanym modelem jest maszyna Turinga.
- Computação pode ser definida como a solução de um problema ou, formalmente, o cálculo de uma função, através de um algoritmo. A teoria da computação, um subcampo da ciência da computação e matemática, busca determinar quais problemas podem ser computados em um dado modelo de computação. Por milhares de anos, a computação foi feita com lápis e papel, ou giz e quadro, ou mentalmente, às vezes com a ajuda de tabelas.
|
