# Ciência da computação teórica

Ciência da computação teórica (TCS) ou informática teórica é uma divisão ou subconjunto de ciências da computação e matemática que incide sobre os aspectos mais abstratos ou matemáticos da computação e inclui a teoria da computação. Não é fácil delimitar as áreas de teoria com precisão e o Grupo de Interesse Especial da ACM em Algoritmos e Teoria da Computação (SIGACT) descreve seu papel como a promoção da ciência da computação teórica e fornece a seguinte nota:
A esta lista, o jornal Transactions on Computation Theory da ACM acrescenta teoria de códigos, teoria da aprendizagem computacional e aspectos de áreas de ciência da computação teórica, tais como bancos de dados, recuperação de informação, os modelos econômicos e redes. Apesar desse escopo amplo, o "pessoal de teoria" em ciência da computação se auto-identificam como diferente do "pessoal das aplicações." Alguns se caracterizam como fazer a "‘ciência(s)’ (mais fundamental) subjacente à área da computação”. Já as “pessoas da teoria-aplicada” sugerem que é impossível para a teoria e aplicação existirem separadas. Isto significa que as chamadas "pessoas da teoria" usam regularmente ciência(s) experimental feita em áreas menos teóricas, tais como a investigação de sistema de software. Significa, também, que há mais cooperação do que competição mutuamente excludente entre teoria e aplicação.

## História

Enquanto algoritmos formais já existem há milênios (algoritmo de Euclides para determinar o máximo divisor comum de dois números ainda é usado em computação), foi apenas em 1936 que Alan Turing, Alonzo Church e Stephen Kleene formalizaram a definição de um algoritmo em termos de computação. Enquanto os sistemas binários e lógicos da matemática já existiam antes 1703, quando Gottfried Leibniz formalizou lógica com valores binários para o verdadeiro e o falso. Enquanto inferência lógica e prova matemática existiam nos tempos antigos, em 1931 Kurt Gödel provou com seu teorema da incompletude que havia limitações fundamentais sobre quais declarações podem ser provadas ou refutadas.
Esta evolução levou ao estudo moderno da lógica e da computabilidade, e, com certeza, o campo da ciência da computação teórica como um todo. A teoria da informação foi adicionada ao campo a Teoria Matemática da Comunicação por Claude Shannon, em 1948. Na mesma década, Donald Hebb introduziu um modelo matemático de aprendizagem no cérebro. Com a montagem de dados biológicos que apoiam esta hipótese com algumas modificações, foram estabelecidos os campos de redes neurais e processamento paralelo distribuído. Em 1971, Stephen Cook e, trabalhando de forma independente, Leonid Levin, mostraram que existem problemas práticos relevantes que são NP-completos - um marco na teoria da complexidade computacional.
Com o desenvolvimento da mecânica quântica no início do século XX. surgiu o conceito de que as operações matemáticas podem ser realizadas com a totalidade de uma função de onda de partícula. 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 XX que decolou na década de 1990, quando Peter Shor mostrou que tais métodos podem ser utilizados para fatorar grandes números em tempo polinomial, que, se implementadas, tornem os mais modernos sistemas de criptografia de chave pública inutilmente inseguro.
Pesquisas em ciências da computação teórica moderna baseiam-se nestes desenvolvimentos básicos, mas inclui muitos outros problemas matemáticos e interdisciplinares que têm sido colocados.
| $P\rightarrow Q\,$ | | | | | P = NP ? |
| Lógica Matemática | Teoria dos Autômatos | Teoria dos Números | Teoria dos Grafos | Teoria da computabilidade | Complexidade computacional |
| GNITIRW-TERCES | $\Gamma \vdash x:Int$ | | | | |
| Criptografia | Teoria dos Tipos | Teoria das categorias | Geometria Computacional | Otimização Combinatória | Computação_quântica |

## Tópicos
### Algoritmos

Um algoritmo é um procedimento passo-a-passo para cálculos. Algoritmos são utilizados para o cálculo, processamento de dados, e de raciocínio automatizado.
Um algoritmo é um método eficaz expresso como uma lista finita de instruções bem definidas para o cálculo de uma função. A partir de um estado inicial e de entrada inicial (talvez vazio), as instruções descrevem uma computação que, quando executada, prossegue através de um número finito de estados sucessivos bem definidos, eventualmente produzindo um "output" e terminando em um ‘estado final’ final. A transição de um estado para o outro não é necessariamente determinística; alguns algoritmos, conhecidos como algoritmos randomizados, incorporar entrada aleatória.

### Estruturas de Dados

Uma estrutura de dados é uma forma particular de organização de dados em um computador de modo que ele pode ser utilizado de forma eficiente.
Diferentes tipos de estruturas de dados são adequadas para diferentes tipos de aplicações, e alguns são altamente especializados para tarefas específicas. Por exemplo, os bancos de dados usam índices de árvore-B para pequenas percentagens de recuperação de dados e compiladores e bancos de dados usam tabelas de hash dinâmicas como tabelas de consulta.
As estruturas de dados fornecem um meio para gerenciar grandes quantidades de dados de forma eficiente para usos como grandes bancos de dados e serviços de indexação na internet. Normalmente, estruturas de dados eficientes são fundamentais para projetar algoritmos eficientes. Alguns métodos de design formais e linguagens de programação enfatizam estruturas de dados, ao invés de algoritmos, como o fator-chave na organização de design de software. Armazenamento e recuperação pode ser levada a cabo sobre os dados armazenados na memória principal e tanto na memória secundária.

### Teoria da Complexidade Computacional

Teoria da complexidade computacional é um ramo da teoria da computação que se concentra em classificar problemas computacionais de acordo com sua dificuldade inerente, e relacionar essas classe. Um problema computacional é entendido para ser uma tarefa que, em princípio, é passível de ser resolvido por um computador, o que é equivalente a afirmar que o problema pode ser resolvido por aplicação mecânica de passos matemáticos, como um algoritmo.
Um problema é considerado como inerentemente difícil se a sua solução requer recursos significativos, seja qual for o algoritmo usado. A teoria formaliza essa intuição, através da introdução de modelos matemáticos de cálculo para estudar estes problemas e quantificar a quantidade de recursos necessários para resolvê-los, tais como tempo e armazenamento. Também são utilizadas outras medidas de complexidade, tais como a quantidade de comunicação (usado em comunicação complexidade), o número de portas de um circuito (utilizado na complexidade do circuito) e o número de processadores (usado na computação paralela). Um dos papéis da teoria da complexidade computacional é determinar os limites práticos sobre o que os computadores podem e não podem fazer.

### Computação Distribuída

Computação distribuída é o estudo de sistemas distribuídos. Um sistema distribuído é um sistema de software em que os componentes estão localizados em computadores de rede para comunicar e coordenar as suas ações, passando mensagens. Os componentes interagem uns com os outros, a fim de alcançar um objetivo comum. Três características significativas de sistemas distribuídos são: simultaneidade dos componentes, a falta de um relógio global, e falha independente dos componentes. Exemplos de sistemas distribuídos variam de sistemas baseados em SOA (arquitetura orientada a serviço) para “jogos multijogador massivos online” até peer-to-peer (P2P).
Um programa de computador que é executado em um sistema distribuído é chamado de um programa distribuído, e programação distribuída é o processo de escrever esses programas. Há muitas alternativas para o mecanismo de passagem de mensagens, incluindo conectores RPC-like e filas de mensagens. Uma meta importante e desafio dos sistemas distribuídos é a transparência de localização.

### Computação paralela

Computação paralela é uma forma de computação em que muitos cálculos são realizados simultaneamente, operando no princípio de que grandes problemas muitas vezes pode ser divididos em partes menores, que são então resolvidos simultaneamente ("em paralelo"). Existem várias formas diferentes de computação paralela: em nível de bit, nível de instrução, dados e paralelismo de tarefas. Paralelismo tem sido empregado por muitos anos, principalmente em computação de alto desempenho, mas o interesse em que tem crescido nos últimos tempos, devido às limitações físicas que impedem a escala de freqüência. Como o consumo de energia (e, consequentemente, a geração de calor) por computadores tornou-se uma preocupação em últimos anos, computação paralela tornou-se o paradigma dominante na arquitetura de computadores, principalmente na forma de processadores multi-core.
Programas de computador paralelos são mais difíceis de escrever do que os seqüenciais porque a concorrência introduz várias novas classes de bugs de software potenciais, das quais as condições de corrida são os mais comuns. Comunicação e sincronização entre as diferentes sub-tarefas são tipicamente alguns dos maiores obstáculos para a obtenção de bons resultados do programa paralelo.
O possível aumento de velocidade máxima de um único programa, como resultado de paralelização é conhecida como a lei de Amdahl.

### Integração em Larga Escala

Integração em larga escala (VLSI) é o processo de criação de um circuito integrado (CI) por combinação de milhares de transistores em um único chip. VLSI começou na década de 1970, quando as tecnologias complexas de semicondutores e de comunicação estavam sendo desenvolvidos. O microprocessador é um dispositivo VLSI. Antes da introdução da tecnologia VLSI maioria dos CIs tinha um conjunto limitado de funções que poderiam realizar. Um circuito eletrônico pode consistir de uma CPU, ROM, RAM e outra lógica. VLSI permite que os fabricantes de CI adicionar tudo isso em um único chip.

### Aprendizado de Máquina

Aprendizado de máquina é uma disciplina científica que trata da construção e estudo de algoritmos que podem aprender a partir de dados. Tais algoritmos operam através da construção de um modelo baseado em dados$^{:2}$ usando isso para fazer previsões ou decisões, em vez de seguindo as instruções só explicitamente programadas.
Aprendizado de máquina pode ser considerado um subcampo da ciência da computação e estatística. Ele tem fortes laços com a inteligência artificial e otimização, que fornecem métodos, teoria e aplicação ao campo. Aprendizado de máquina é utilizado em uma variedade de tarefas de computação onde projetar e programar explicitamente algoritmos baseados em regras é inviável. Exemplos de aplicação incluem filtragem de spam, reconhecimento óptico de caracteres (OCR) os motores de busca e visão computacional. Aprendizado de máquina é por vezes confundida com a mineração de dados, apesar de que se concentra mais na análise exploratória de dados. Aprendizado de máquina e reconhecimento de padrões "podem ser vistos como duas facetas de um mesmo campo."$^{:vii}$

### Biologia Computacional

Biologia computacional envolve o desenvolvimento e aplicação de métodos de dados analíticos e teóricos, modelagem matemática e técnicas de simulação computacional para o estudo de sistemas biológicos, comportamentais e sociais. O campo é amplamente definido e inclui fundações em ciência da computação, matemática aplicada , animação, estatística, bioquímica, química, biofísica, biologia molecular, genética, ecologia, evolução, anatomia, neurociência, e visualização científica.
Biologia computacional é diferente de computação biológica, que é um ramo da ciência da computação e engenharia da computação por meio da bioengenharia e biologia para construir computadores, mas é semelhante a bioinformática, que é uma ciência interdisciplinar que utilizam computadores para armazenar e processar dados biológicos.

### Geometria Computacional

Geometria computacional é um ramo da ciência da computação dedicada ao estudo de algoritmos que podem ser expressos em termos da geometria. Alguns problemas puramente geométricos surgem do estudo de algoritmos computacionais geométricos, e tais problemas também são considerados parte da geometria computacional. Enquanto geometria computacional moderna é um desenvolvimento recente, é um dos campos mais antigos da computação com uma história que se iniciou na antiguidade. Um precursor antigo é o sânscrito tratadista Shulba Sutras, ou "Regras de Chord", que é um livro de algoritmos escrito em 800 aC. O livro prescreve procedimentos passo-a-passo para a construção de objetos geométricos como altares usando uma estaca e acorde.
O principal impulso para o desenvolvimento da geometria computacional como uma disciplina era um progresso em computação gráfica e desenho/fabricação assistido por computador (CAD / CAM), mas muitos problemas em geometria computacional são clássicos na natureza, e pode vir de visualização matemática.
Outras aplicações importantes da geometria computacional incluem robótica (planejamento de movimento e problemas de visibilidade), sistemas de informação geográfica (SIG) (localização geométrica e de pesquisa, planejamento de rota), o projeto de circuito integrado (IC Design Geometria e verificação), engenharia auxiliada por computador (CAE) (geração de malhas), visão computacional (reconstrução 3D).

### Teoria da Informação

A teoria da informação é um ramo da matemática aplicada, engenharia elétrica e ciência da computação envolvendo a quantificação das informações. A teoria da informação foi desenvolvida por Claude E. Shannon para encontrar limites fundamentais sobre as operações de processamento de sinais, tais como compressão de dados e de forma confiável armazenamento e comunicação de dados. Desde a sua criação, tem se ampliado para encontrar aplicações em muitas outras áreas, incluindo a inferência estatística, processamento de linguagem natural, criptografia, neurobiologia, evolução e da função de códigos moleculares, seleção de modelos em ecologia, física térmica, computação quântica, linguística, detecção de plágio, reconhecimento de padrões, detecção de anomalias e outras formas de análise de dados.
Aplicações dos tópicos fundamentais da teoria da informação incluem a compressão de dados sem perdas (por exemplo, arquivos ZIP), compressão de dados com perdas (por exemplo, MP3 e JPEG), e codificação de canal (por exemplo, para Digital Subscriber Linel, o DSL). O campo é no cruzamento da matemática, estatística, ciência da computação, física, neurobiologia e engenharia elétrica. O seu impacto tem sido crucial para o sucesso das missões Voyager ao espaço, a invenção do CD, a viabilidade de telefones celulares, o desenvolvimento da Internet, o estudo da linguística e da percepção humana, a compreensão dos buracos negros, e vários outros campos. Sub-campos importantes da teoria da informação são codificação de fonte, codificação de canal, a teoria da complexidade algorítmica, teoria da informação algorítmica, segurança da informação teórica, e as medidas de informação.

### Criptografia

A Criptografia é a prática e estudo de técnicas para uma comunicação segura na presença de terceiros (chamados adversários). Em termos mais gerais, é sobre a construção e análise de protocolos que superam a influência de adversários e que estejam relacionados a vários aspectos em segurança da informação, tais como a confidencialidade dos dados, integridade de dados, autenticação e não repúdio. A criptografia moderna cruza as disciplinas de matemática, ciência da computação e engenharia elétrica. Aplicações de criptografia incluem cartões ATM, senhas de computador e comércio eletrônico.
A criptografia moderna é fortemente baseada na prática a teoria e ciência da computação matemática; algoritmos de criptografia são projetados em torno pressupostos da dureza computacional, tornando tais algoritmos difíceis de quebrar, na prática, por qualquer adversário. É teoricamente possível quebrar um tal sistema, mas é inviável fazê-lo por quaisquer meios práticos conhecidos. Estes esquemas são, portanto, denominados computacionalmente seguros; avanços teóricos, por exemplo, melhorias nos algoritmos de fatoração de números inteiros, e mais rápida tecnologia de computação exigem estas soluções de ser adaptadas continuamente. Existem sistemas de informação, teoricamente seguros, que comprovadamente não podem ser quebrados, mesmo com poder computacional ilimitado. Um exemplo é o one-time pad, mas estes regimes são mais difíceis de implementar do que os mecanismos melhor teoricamente quebráveis mas computacionalmente seguros.

### Computação Quântica

Um computador quântico é um sistema de computação que faz uso direto de fenômenos da mecânica quântica, como a superposição e emaranhamento, para executar operações em dados.. Os computadores quânticos são diferentes dos computadores digitais baseados em transistores. Considerando computadores digitais requerem dados a serem codificados em dígitos binários (bits), cada um dos quais está sempre em um dos dois estados definidos (0 ou 1), a computação quântica utiliza qubits (bits quânticos), que podem ser em superposições de estados. Um modelo teórico é a máquina de Turing quântica, também conhecida como o computador quântico universal. Os computadores quânticos compartilham semelhanças teóricas com computadores não-determinísticos e probabilísticos; um exemplo é a capacidade de estar em mais de um estado ao mesmo tempo. O campo da computação quântica foi introduzido pela primeira vez por Yuri Manin em 1980 e Richard Feynman, em 1982. Um computador quântico com spins como bits quânticos também foi formulado para uso como um quantum do espaço-tempo, em 1968.
A partir de 2014, a computação quântica ainda está em sua infância, mas experimentos foram realizados em que as operações computacionais quânticos foram executados em um número muito pequeno de qubits. Pesquisas teóricas e práticas continuam, e muitos fundos do governo e de agências militares dão suporte à pesquisas de computação quântica para desenvolver computadores quânticos para segurança nacional e civil, como a criptoanálise.

### Teoria Computacional dos Números

A Teoria computacional dos números, também conhecida como teoria algorítmica dos números, é o estudo de algoritmos para realizar cálculos numéricos teóricos. O problema mais conhecido no campo é fatoração inteira.

### Computação Simbólica

Álgebra computacional, também chamada de computação simbólica ou computação algébrica, é uma área científica que se refere ao estudo e desenvolvimento de algoritmos e software para manipulação de expressões matemáticas e outros objetos matemáticos. Embora, falando corretamente de álgebra computacional deve ser um subcampo da computação científica, eles são geralmente considerados como campos distintos porque a computação científica é geralmente baseada em computação numérica com números de ponto flutuante aproximados, enquanto computação simbólica enfatiza cálculo exato com expressões com variáveis que não têm qualquer dado valor e, portanto, são manipulados como símbolos (daí o nome de computação simbólica).
Os aplicativos de software que executam cálculos simbólicos são chamados sistemas de álgebra computacional, com o sistema de termo aludindo à complexidade das principais aplicações que incluem, pelo menos, um método para representar dados matemáticos em um computador, uma linguagem de programação de usuário (geralmente diferente da língua utilizada para a execução), um gerenciador dedicado de memória, uma interface de usuário para a entrada / saída de expressões matemáticas, um grande conjunto de rotinas para realizar as operações habituais, como a simplificação de expressões, a diferenciação usando a regra da cadeia, fatoração polinomial, integração indefinida, etc .

### Semântica Formal

Na teoria das linguagens de programação, a semântica é o campo preocupado com o estudo matemático rigoroso do significado de linguagens de programação. Ocorre através da avaliação do significado de Strings sintaticamente legais definidos por uma linguagem de programação específica, mostrando o cálculo envolvido. Em tal caso que a avaliação possa ser Strings sintaticamente ilegais, o resultado seria não-cálculo. Semântica descreve os processos de um computador segue ao executar um programa em que a linguagem específica. Isto pode ser mostrado por descrevendo a relação entre a entrada e a saída de um programa, ou uma explicação de como o programa será executado em uma determinada plataforma, criando assim um modelo de computação.

### Métodos Formais

Os métodos formais são um tipo particular de técnicas baseadas em matemáticas para a especificação, desenvolvimento e verificação de sistemas de software e hardware. O uso de métodos formais para design de software e hardware é motivado pela expectativa de que, como em outras disciplinas da engenharia, executando análise matemática adequada pode contribuir para a confiabilidade e robustez de um projeto.
Os métodos formais são melhor descritos como a aplicação de uma variedade bastante ampla de fundamentos teóricos da ciência da computação, em particular cálculos de lógica, linguagens formais, teoria de autômatos, e semântica do programa, mas também tipos de sistemas e tipos de dados algébricos para problemas em especificação e verificação de software e hardware.

### Teoria dos Autômatos

Teoria dos autômatos é o estudo de máquinas e autômatos, bem como os problemas computacionais que podem ser resolvidos usando-os. É uma teoria em ciência da computação teórica, sob a matemática discreta (uma seção de Matemática e também de Ciência da Computação). Automata vem da palavra grega que significa αὐτόματα "auto-agir".
Teoria dos autômatos é o estudo de máquinas virtuais auto-operacionais para ajudar na compreensão lógica do processo de entrada e saída, sem ou com estágio(s) intermediário(s) de computação (ou qualquer função / processo).

### Teoria de Códigos

Teoria do código é o estudo das propriedades de códigos e sua aptidão para uma aplicação específica. Os códigos são utilizados para a compressão de dados, criptografia, de correção de erros e, mais recentemente, também para a codificação de rede. Os códigos são estudados por várias disciplinas científicas, tais como a teoria da informação, engenharia elétrica, matemática e ciência da computação, com a finalidade de projetar métodos de transmissão de dados eficientes e confiáveis. Isso normalmente envolve a remoção de redundância e da correção (ou detecção) de erros nos dados transmitidos.

### Teoria do Aprendizado Computacional

Os resultados teóricos em Aprendizado de Máquina lidam principalmente com um tipo de aprendizado indutivo chamado aprendizado supervisionado. Na aprendizagem supervisionada, um algoritmo é dado amostras que são rotulados de alguma forma útil. Por exemplo, as amostras podem ser as descrições de cogumelos, e as etiquetas podem ser ou não os cogumelos são comestíveis. O algoritmo leva essas amostras previamente marcadas e as utiliza para induzir um classificador. Este classificador é uma função que atribui etiquetas para amostras incluindo as amostras que nunca tenham sido anteriormente observadas pelo algoritmo. O objetivo do algoritmo de aprendizado supervisionado é otimizar alguma medida de desempenho, tais como minimizar o número de erros cometidos em novas amostras.

## Organizações

* European Association for Theoretical Computer Science
* SIGACT

## Jornais e revistas

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

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

## Veja também

* Ciências formais
* Problemas em aberto da ciência da computação