𝖂𝖎ƙ𝖎𝖊

Computação: mudanças entre as edições

imported>Mschlindwein
Sem resumo de edição
imported>Carribeiro~ptwiki
(Várias edições. Traduzi alguns parágrafos, e corrigi o tempo verbal de um parágrafo - o original em inglês estava no passado, ajustei de acordo)
Linha 3: Linha 3:
A '''computação''' pode ser definida como a busca de uma solução para um problema, a partir de [[entrada]]s (''inputs''), e através de um [[algoritmo]]. É com isto que lida a ''teoria da computação'', subcampo da [[ciência da computação]] e da [[matemática]]. Durante milhares de anos, a computação foi executada com caneta e papel, ou com giz e ardósia, ou mentalmente, por vezes com o auxílio de tabelas.
A '''computação''' pode ser definida como a busca de uma solução para um problema, a partir de [[entrada]]s (''inputs''), e através de um [[algoritmo]]. É com isto que lida a ''teoria da computação'', subcampo da [[ciência da computação]] e da [[matemática]]. Durante milhares de anos, a computação foi executada com caneta e papel, ou com giz e ardósia, ou mentalmente, por vezes com o auxílio de tabelas.


A '''''teoria''' da [[computação]]'' teve início nos primeiros anos do século XX, antes da invenção dos modernos computadores electrónicos.
A '''''teoria''' da '''computação''''' teve início nos primeiros anos do século XX, antes da invenção dos modernos computadores electró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.


Neste tempo, [[matemáticos]] estão tentando achar qual problema matemático pode ser resolvido por um método simples. O primeiro passo estava em definir o significado deles por um " método  Simples" para resolver o problema. Em outras palavras, eles precisam 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ção recursiva|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 [[Algoritmo de Markov|algoritmos de Markov]] e dos [[Sistemas de Post|sistemas de Post]].


Several different computational models were devised by these early researchers.  One model, the [[Turing machine]], stores characters on an infinitely long tape, with one square at any given time being scanned by a read/write head. Another model, [[recursive function|recursive functions]], uses functions and function composition to operate on numbers. The [[lambda calculus]] uses a similar approach. Still others, including [[Markov algorithm]]s and [[Post system]]s, use grammar-like rules to operate on strings.  All of these formalisms were shown to be equivalent in computational power -- that is, any computation that can be performed with one can be performed with any of the others.  They are also equivalent in power to the familiar electronic
Todos os formalismos propostos acima são equivalentes em termos de poder computacional -- ou seja, qualquer computação que possa ser realizada com um pode ser realizada com qualquer um dos outros. Ainda em termos teóricos, os modelos propostos são equivalentes aos computadores eletrônicos, desde que não hajam 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 à uma máquina de Turing; esta é a [[Tese de Church-Turing|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|teoria da computabilidade]].
computer, if one pretends that electronic computers have infinite memory. Indeed, it is widely believed that all "proper" formalizations of the concept of algorithm will be equivalent in power to Turing machines; this is known as the [[Church-Turing thesis]]. In general, questions of what can be computed by various machines are investigated in [[computability theory]].


The theory of computation studies these models of general computation, along with the limits of computing: Which problems are (provably) unsolvable by a computer?  (See the [[Halting Problem|halting problem]] and the [[Post correspondence problem]].) Which problems are solvable by a computer, but require such an enormously long time to compute that the solution is impractical? (See [[Presburger arithmetic]].) Can it be harder to solve a problem than to check a given solution? (See [[complexity classes P and NP]]). In general, questions concerning the time or space requirements of given problems are investigated in [[Computational complexity theory| complexity theory]].
A teoria da computação estuda os modelos de computação genéricos, assim como os limites da computação:


In addition to the general computational models, some simpler computational models are useful for special, restricted applications.  [[Regular expressions]], for example, are used to specify string patterns in [[UNIX]] and in some programming languages such as [[Perl]]. Another formalism mathematically equivalent to regular expressions, [[finite state machines|Finite automata]] are used in circuit design and in some kinds of problem-solving. [[Context-free grammar|Context-free grammars]] are used to specify programming language syntax.  Non-deterministic [[pushdown automaton|pushdown automata]] are another formalism equivalent to context-free grammars. [[primitive recursive function|Primitive recursive functions]] are a defined subclass of the recursive functions.
* 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 solucã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]]).


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
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|teoria da complexidade computacional]].
[[formal language|formal languages]] that the model can generate; this leads to the [[Chomsky hierarchy]] of languages.
 
Além dos modelos genéricos de computação, alguns modelos computacionais mais simples são úteis para aplicações mais restritas. [[Expressão Regular|Expressões regulares]], por exemplo, são 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|autômatos finitos]], que são utilizados em desenho de circuitos e e alguns sistemas de resolução de problemas. As [[Gramáticas Livres de Contexto|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 de empilhamento|autômatos de empilhamento]], 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 [[Linguagem formal|linguagens formais]] que o modelo pode gerar; o resultado é a [[Hierarquia de Chomsky|hierarquia de Chomsky]] das linguagens.


The following table shows some of the classes of problems (or languages, or  
The following table shows some of the classes of problems (or languages, or  

Edição das 18h42min de 3 de agosto de 2004

Predefinição:Emtraducao2

A computação pode ser definida como a busca de uma solução para um problema, a partir de entradas (inputs), e através de um algoritmo. É com isto que lida a teoria da computação, subcampo da ciência da computação e da matemática. Durante milhares de anos, a computação foi executada com caneta e papel, ou com giz e ardósia, ou mentalmente, por vezes com o auxílio de tabelas.

A teoria da computação teve início nos primeiros anos do século XX, antes da invenção dos modernos computadores electró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 algoritmos 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 pode ser realizada com qualquer um dos outros. Ainda em termos teóricos, os modelos propostos são equivalentes aos computadores eletrônicos, desde que não hajam 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 à 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 solucã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, por exemplo, são 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 e 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 de empilhamento, 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.

The following table shows some of the classes of problems (or languages, or grammars) that are considered in computability theory (blue) and complexity theory (green). If class X is a strict subset of Y, then X is shown below Y, with a dark line connecting them. If X is a subset, but it is unknown whether they are equal sets, then the line is lighter and is dotted.

Decision Problem
SolidLine.png SolidLine.png
Type 0 (Recursively enumerable)
Undecidable
SolidLine.png
Decidable
SolidLine.png
EXPSPACE
DottedLine.png
EXPTIME
DottedLine.png
PSPACE
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
Type 1 (Context Sensitive)
 SolidLine.png DottedLine.png DottedLine.png DottedLine.png
PSPACE-Complete
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png
Co-NP
 DottedLine.png
NP
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png DottedLine.png
BPP
BQP
NP-Complete
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png
P
SolidLine.png SolidLine.png DottedLine.png DottedLine.png
SolidLine.png
NC
P-Complete
SolidLine.png SolidLine.png
Type 2 (Context Free)
SolidLine.png
Type 3 (Regular)

Tópicos de computação


ja:計算理論pl:Teoria obliczeńde:Theoretische Informatik

For Further Reading

  • Garey, Michael R., and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. The standard reference on NP-Complete problems - an important category of problems whose solutions appear to require an impractically long time to compute.
  • Hein, James L: Theory of Computation. Sudbury, MA: Jones & Bartlett, 1996. A gentle introduction to the field, appropriate for second-year undergraduate computer science students.
  • Hopcroft, John E., and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Reading, MA: Addison-Wesley, 1979. One of the standard references in the field.
  • Taylor, R. Gregory: Models of Computation. New York: Oxford University Press, 1998. An unusually readable textbook, appropriate for upper-level undergraduates or beginning graduate students.
  • The Complexity Zoo: A huger list of complexity classes, as reference for experts.

This article contains some content from an article by Nancy Tinkham, originally posted on Nupedia. This article is open content.

talvez você goste

Permaneça conectado

Parceiros

Dieta Cetogenica | NutriPro Saúde