Ciência da computação teórica

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Wikitext.svg
Este artigo ou seção precisa ser wikificado (desde julho de 2012).
Por favor ajude a formatar este artigo de acordo com as diretrizes estabelecidas no livro de estilo.

Ciência da computação teórica (TCS) é uma divisão ou subconjunto de ciências da computação and matemática que incide sobre os aspectos mais abstratos ou matemáticos da computação.

Essas divisões e subconjuntos incluemanálise de algoritmos e semânticas formais de linguagens de programção. Tecnicamente, há centenas de divisões e subconjuntos além desses dois. Cada uma das várias partes tem seus próprios líderes pessoais individuais e há várias associações e grupos de profissionais e publicações de destaque.

Escopo[editar | editar código-fonte]

Não é fácil limitar as áreas teóricas precisamente e o Grupo de Interesse Especial em Algoritmos e Teoria de Computação da Associação para Maquinaria da Computação (SIGACT) descreve sua missão como a promoção da ciência da computação teórica e notas: [1]

O campo da Ciência da computação teórica é interpretado amplamente de modo a incluir algoritmos, estrutura de dados, teoria da complexidade computacional, computação distribuída, computação paralela, VLSI, aprendizagem de máquina, biologia computacional, geometria computacional, teoria da informação, criptografia, computação quântica, teoria dos números computacionais e álgebra, semânticas de programa e verificação, teoria dos autômatos, e o estudo da aleatoriedade. O trabalho neste campo é muitas vezes distinguido por sua ênfase na técnica e no rigor matemático.

Para essa lista, o jornal de transações em teoria da computação adiciona teoria de códigos, teoria de aprendizagem computacional e os aspectos da área de Ciência da computação teórica como banco de dados, recuperação de informação, modelos econômicos e redes.[2] Apesar dessa abrangência, as "pessoas teóricas" em ciência da computação se auto-identificam como diferentes das "pessoas práticas". Alguns caracterizam-se como fazendo a "ciência mais fundamental subjacente ao campo da computação".[3] As outras "pessoas práticas" sugerem que é impossível separar a teoria da prática . Isto significa que as pessoas chamadas de "teóricas" regularmente usam ciência experimental feita em campos menos teóricos, como a investigação do sistema de software. Significa também que há mais cooperação do que competição entre teoria e prática.

 P \rightarrow Q \, DFAexample.svg Elliptic curve simple.png 6n-graf.svg
Lógica matemática Teoria dos autômatos Teoria dos números Teoria dos grafos
\Gamma\vdash x : Int Commutative diagram for morphism.svg SimplexRangeSearching.png Blochsphere.svg
Teoria dos tipos Teoria das categorias Geometria computacional Teoria da computação quântica

História[editar | editar código-fonte]

Enquanto algoritmos formais tem existido por milênios ( Algoritmo de Euclides para determinar o máximo divisor comum de dois números e ainda é usado na computação), foi somente em 1936 que Alan Turing, Alonzo Church e Stephen Kleene formalizaram a definição de um algoritmo em termos de computação. Enquanto sistemas lógicos e binários na matemática existem desde antes de 1703, quando Gottfried Leibniz formalizou a lógica com valores binários "verdadeiro" ou "falso". Enquanto inferência lógica e prova matemática já existia nos tempos antigos, em 1931 Kurt Gödel provou com o seu teorema da incompletude que havia limitações fundamentais sobre as declarações, mesmo sendo verdade, se poderiam ser provadas.

Estes desenvolvimentos têm levado ao estudo moderno da lógica e da computabilidade, e de fato o campo da ciência da computação teórica como um todo. Informática teórica foi adicionada ao campo com a teoria matemática da comunicação, por Claude Shannon, em 1948. Na mesma década, Donald Hebb introduziu um modelo matemático de aprendizado no cérebro. Com montagem dados biológicos que suportam esta hipótese com algumas modificações, os campos de rede neural e processamento paralelo distribuído foram estabelecidas.

Com o desenvolvimento da mecânica quântica no início do século 20 veio o conceito de que as operações matemáticas poderia ser realizada em função de onda de uma partícula inteira. Em outras palavras, pode-se calcular as funções em estados múltiplos simultaneamente. Isto levou ao conceito de um computador quântico na segunda metade do século 20, que decolou na década de 1990, quando Peter Shor mostrou que tais métodos poderiam ser usados ​​para fatorar números grandes em tempo polinomial, que, se implementado, tornaria a criptografia de chave pública, que são sistemas inseguros, mais moderna.

A pesquisa da ciência da computação teórica moderna baseia-se nestes desenvolvimentos básicos, mas inclui muitos outros problemas matemáticos e interdisciplinares que foram colocados.

Organizações[editar | editar código-fonte]

Jornais e revistas[editar | editar código-fonte]

Predefinição:Unreferenced section

  • Information and Computation
  • Theory of Computing (journal)|Theory of Computing
  • Formal Aspects of Computing
  • Journal of the ACM
  • SIAM Journal on Computing (SICOMP)
  • SIGACT News
  • Theoretical Computer Science (journal)|Theoretical Computer Science
  • Theory of Computings Systems
  • International Journal of Foundations of Computer Science
  • Chicago Journal of Theoretical Computer Science
  • Foundations and Trends in Theoretical Computer Science
  • Journal of Automata, Languages and Combinatorics
  • Acta Informatica
  • Fundamenta Informaticae
  • ACM Transactions on Computation Theory
  • ACM Transactions on Algorithms
  • Information Processing Letters

Conferências[editar | editar código-fonte]

  • Annual ACM Symposium on Theory of Computing (STOC) [4]
  • Annual IEEE Symposium on Foundations of Computer Science (FOCS) [4]
  • ACM–SIAM Symposium on Discrete Algorithms (SODA) [4]
  • Annual ACM Symposium on Computational Geometry (SoCG) [5]
  • International Colloquium on Automata, Languages and Programming (ICALP) [5]
  • Symposium on Theoretical Aspects of Computer Science (STACS) [5]
  • European Symposium on Algorithms (ESA) [5]
  • IEEE Symposium on Logic in Computer Science (LICS) [4]
  • International Symposium on Algorithms and Computation (ISAAC) [5]
  • Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) [5]
  • Workshop on Randomization and Computation (RANDOM) [5]
  • Computational Complexity Conference (CCC) [5]
  • ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) [5]
  • ACM Symposium on Principles of Distributed Computing (PODC) [4]

Veja também[editar | editar código-fonte]

Notas[editar | editar código-fonte]

  1.  SIGACT. Visitado em 2009-03-29.
  2.  ToCT. Visitado em 2010-06-09.
  3. Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing. Visitado em 2009-03-29.
  4. a b c d e The 2007 Australian Ranking of ICT Conferences: tier A+.
  5. a b c d e f g h i The 2007 Australian Ranking of ICT Conferences: tier A.

Leitura complementar[editar | editar código-fonte]

  • Martin Davis, Ron Sigal, Elaine J. Weyuker, Computability, complexity, and languages: fundamentals of theoretical computer science, 2nd ed., Academic Press, 1994, ISBN 0-12-206382-1.

Ligações externas[editar | editar código-fonte]