sexta-feira, dezembro 28, 2007

Computação

1) Introdução

Computação é uma Mudança de Estado (Comportamento) de um Fenômeno da Realidade capaz de ser descrita ou modelada através de um Algoritmo, ou seja Computação é um Processo da Realidade. Em ourtras palavras computação é o resultado da execução de um algoritmo.



"Computação também pode ser definida como a busca de uma solução para um problema, a partir de entradas (inputs), com a geração de saídas (outputs), 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". [WIKIPEDIA]

Computation is a general term for any type of information processing that can be resented mathematically. This includes phenomena ranging from human thinking to calculations with a more narrow meaning, computation is a process following a well defined model that is understood and can be expressed in an algorithm, protocol, network topology, etc.

2) Computations as a physical phenomenon

A computation can be seen as a purely physical phenomenon occurring inside a closed physical system called a computer. Examples of such physical systems include digital computers, quantum computers, DNA computers, molecular computers, analog computers or wetware computers. This point of view is the one adopted by the branch of theoretical physics called the physics of computation.

An even more drastic point of view is the postulate of digital physics that the evolution of the universe itself is a computation.

Computation is a form of calculation, the procedure of calcultaing; determining something by mathematical or logical methods or problem solving that involves numbers or quantities.

3) Mathematical models of computation

In the theory of computation, mathematical models of computers are defined. A computation is the evolution over discrete time epochs of this model. Typical mathematical models of computers are the following:

  1. Turing Machine
  2. push-down automaton
  3. Finite state automaton

Different mathematical models of computers can be classified according to their expressive power, see the Chomsky hierarchy.

4) Classes of computation

Computation can be classified by at least three orthogonal criteria: digital vs analog, sequential vs parallel, batch vs interactive.

In practice, digital computation is often used to simulate natural processes (for example, Evolutionary computation), including those that are more naturally described by analog models of computation (for example, Artificial neural network). In this situation, it is important to distinguish between the mechanism of computation and the simulated model.

5) Referências Bibliográficas:

  1. 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. Uma referência padrão aos problemas do tipo NP-Completo, uma importante categoria de problemas cuja solução parece requerer um tempo impraticavelmente longo para efetivar sua computação.
  2. Hein, James L: Theory of Computation. Sudbury, MA: Jones & Bartlett, 1996. Uma introdução suave ao assunto da Teoria da Computação, apropriado para alunos do segundo ano de um curso de graduação em Ciência da Computação.
  3. Hopcroft, John E., and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Reading, MA: Addison-Wesley, 1979. Uma das referências padrão na área de autômatos finitos e linguagens formais.
  4. Taylor, R. Gregory: Models of Computation. New York: Oxford University Press, 1998. Um dos raros textos facilmente legíveis sobre Teoria da Computação, apropriado para alunos de gradução ou mestrado.

Nenhum comentário: