Computação

Predefinição:Emtraducao2

A computação povgvuiode 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.

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 (verde). 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.

Decision Problem

Tipo 0 (Recursivamente enumerável)

colspan=4 |

Tipo 1 (Sensível ao contexto)

PSPACE-Complete

Co-NP

NP

BPP

BQP

NP-Complete

P

NC

P-Complete

Tipo 2 (Livre de contexto)

Type 3 (Regular)

Tópicos de computação

Hardware (Equipamento)
- Microprocessador
- Disco Rígido (HD, Winchester, Hard Disc)
- Tipos de Memória
  - Memória Primária ou Central
    - RAM
    - ROM
    - PROM
    - EPROM
    - EEPROM
  - Memória Secundária ou Externa
    - Disquete (Floppy Disk)
    - Disco Rígido (HD, Winchester, Hard Disc)
    - Tambor Magnético (Já não utilizado actualmente)
  - Memória Terciária ou de Massa
    - Fita Magnética
    - DC ou CD (Disco Compacto)
    - CD-R (Compact Disc - Recordable)
    - CD-RW (Compact Disc - ReWritable (regraváveis))
    - DVD (Digital Versatile Disc, Digital Video Disc)
- Fax-Modem
- Placa-mãe
- Placa de Som
- Placa de Vídeo
- Placa de Rede
- Ponteiro (máuse ou mouse)
- Teclado
- Impressora
- Digitalizador (escaner)

Programas de Computador

Multimédia
- Áudio
- Vídeo

Internet
- World Wide Web
- E-mail
- FTP
- IRC
- P2P (Peer to Peer, File Sharing)

Pessoas

Biocomputação

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.

Predefinição:Ciências-rodapé

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