Ciência da computação teórica (TCS) ou informática teórica é uma divisão ou subconjunto de ciência 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.
96px 96px 96px 96px P = NP ? Lógica Matemática Teoria dos Autômatos Teoria dos Números Teoria dos Grafos Teoria da computabilidade Complexidade computacional GNITIRW-TERCES 96px 96px 96px 96px 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"Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2). finita de instruçõesWell defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987:2). bem definidas para o cálculo de uma função."an algorithm is a procedure for computing a function (with respect to some chosen notation for integers) ... this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1). A partir de um estado inicial e de entrada inicial (talvez vazio),"An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5). as instruções descrevem uma computação que, quando executada, prossegue através de um número finito"A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'" (Knuth 1973:5). de estados sucessivos bem definidos, eventualmente produzindo um "output""An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5). 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.Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices . . . carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2.
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.Paul E. Black (ed.), entry for data structure in Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 15 December 2004. Online version Accessed May 21, 2009.Entry data structure in the Encyclopædia Britannica (2009) Online entry accessed on May 21, 2009.
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.. . , p. 10. 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.S.V. Adve et al. (November 2008). "Parallel Computing Research at Illinois: The UPCRC Agenda" (PDF). Parallel@Illinois, University of Illinois at Urbana-Champaign. "The main techniques for these performance benefits – increased clock frequency and smarter but increasingly complex architectures – are now hitting the so-called power wall. The computer industry has accepted that future performance increases must largely come from increasing the number of processors (or cores) on a die, rather than making a single core go faster." 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. Asanovic, Krste et al. (December 18, 2006). "The Landscape of Parallel Computing Research: A View from Berkeley" (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. "Old [conventional wisdom]: Increasing clock frequency is the primary method of improving processor performance. New [conventional wisdom]: Increasing parallelism is the primary method of improving processor performance ... Even representatives from Intel, a company generally associated with the 'higher clock-speed is better' position, warned that traditional approaches to maximizing performance through maximizing clock speed have been pushed to their limit."