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:^[1]

"O campo da ciência da computação teórica é interpretado de forma ampla, de modo a incluir algoritmos, estruturas de dados, teoria da complexidade computacional, computação distribuída, computação paralela, VLSI, aprendizado de máquina, biologia computacional, geometria computacional, teoria da informação, criptografia, computação quântica, teoria dos números e álgebra, semântica de programas e sua verificação, teoria dos autômatos, e o estudo da aleatoriedade. O trabalho neste campo é muitas vezes distinguido por sua ênfase na técnica matemática e rigor."

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.^[2] 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”.^[3] 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^[4] finita de instruções^[5] bem definidas para o cálculo de uma função.^[6] A partir de um estado inicial e de entrada inicial (talvez vazio),^[7] as instruções descrevem uma computação que, quando executada, prossegue através de um número finito^[8] de estados sucessivos bem definidos, eventualmente produzindo um "output"^[9] 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.^[10]

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.^[11]^[12]

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.^[13] 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.^[13] 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.^[14] 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,^[15] 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.^[16] 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. ^[17]

Programas de computador paralelos são mais difíceis de escrever do que os seqüenciais ^[18] 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.^[19] Tais algoritmos operam através da construção de um modelo baseado em dados^[20]^: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)^[21] os motores de busca e visão computacional. Aprendizado de máquina é por vezes confundida com a mineração de dados,^[22] apesar de que se concentra mais na análise exploratória de dados.^[23] Aprendizado de máquina e reconhecimento de padrões "podem ser vistos como duas facetas de um mesmo campo."^[20]^: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.^[24] 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.^[25]

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,^[26] evolução^[27] e da função^[28] de códigos moleculares, seleção de modelos em ecologia,^[29] física térmica,^[30] computação quântica, linguística, detecção de plágio,^[31] reconhecimento de padrões, detecção de anomalias e outras formas de análise de dados.^[32]

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).^[33] Em termos mais gerais, é sobre a construção e análise de protocolos que superam a influência de adversários^[34] 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.^[35] 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..^[36] 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^[37] e Richard Feynman, em 1982.^[38]^[39] 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.^[40]

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.^[41] 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.^[42]

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.^[43] 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.^[44]

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.^[45]

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

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) ^[46]
Annual IEEE Symposium on Foundations of Computer Science (FOCS) ^[46]
ACM–SIAM Symposium on Discrete Algorithms (SODA) ^[46]
Annual ACM Symposium on Computational Geometry (SoCG) ^[47]
International Colloquium on Automata, Languages and Programming (ICALP) ^[47]
Symposium on Theoretical Aspects of Computer Science (STACS) ^[47]
European Symposium on Algorithms (ESA) ^[47]
IEEE Symposium on Logic in Computer Science (LICS) ^[46]
International Symposium on Algorithms and Computation (ISAAC) ^[47]
Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) ^[47]
Workshop on Randomization and Computation (RANDOM) ^[47]
Computational Complexity Conference (CCC) ^[47]
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) ^[47]
ACM Symposium on Principles of Distributed Computing (PODC) ^[46]

Veja também

Notas

↑ «SIGACT». Consultado em 29 de março de 2009
↑ «ToCT». Consultado em 9 de junho de 2010. Arquivado do original em 4 de novembro de 2010
↑ «Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing». Consultado em 29 de março de 2009
↑ "Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).
↑ Well 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).
↑ "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).
↑ "An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5).
↑ "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).
↑ "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5).
↑ 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.
↑ 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.
↑ ^a ^b Coulouris, George; Jean Dollimore; Tim Kindberg; Gordon Blair (2011). Distributed Systems: Concepts and Design (5th Edition). Boston: Addison-Wesley. ISBN 0-132-14301-1
↑ Andrews (2000). Dolev (2000). Ghosh (2007), p. 10.
↑ Gottlieb, Allan; Almasi, George S. (1989). Highly parallel computing. Redwood City, Calif.: Benjamin/Cummings. ISBN 0-8053-0177-1
↑ S.V. Adve et al. (November 2008). "Parallel Computing Research at Illinois: The UPCRC Agenda" Arquivado em 9 de dezembro de 2008, no Wayback Machine. (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."
↑ 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."
↑ Hennessy, John L.; Patterson, David A.; Larus, James R. (1999). Computer organization and design : the hardware/software interface 2. ed., 3rd print. ed. San Francisco: Kaufmann. ISBN 1-55860-428-6
↑ Ron Kovahi; Foster Provost (1998). «Glossary of terms». Machine Learning. 30: 271–274
↑ ^a ^b C. M. Bishop (2006). Pattern Recognition and Machine Learning. [S.l.]: Springer. ISBN 0-387-31073-8
↑ Wernick, Yang, Brankov, Yourganov and Strother, Machine Learning in Medical Imaging, IEEE Signal Processing Magazine, vol. 27, no. 4, July 2010, pp. 25-38
↑ Mannila, Heikki (1996). Data mining: machine learning, statistics, and databases. Int'l Conf. Scientific and Statistical Database Management. IEEE Computer Society
↑ Friedman, Jerome H. (1998). «Data Mining and Statistics: What's the connection?». Computing Science and Statistics. 29 (1): 3–9
↑ «NIH working definition of bioinformatics and computational biology» (PDF). Biomedical Information Science and Technology Initiative. 17 de julho de 2000. Consultado em 18 de agosto de 2012. Arquivado do original (PDF) em 5 de setembro de 2012
↑ «About the CCMB». Center for Computational Molecular Biology. Consultado em 18 de agosto de 2012
↑ F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek (1997). Spikes: Exploring the Neural Code. [S.l.]: The MIT press. ISBN 978-0262681087
↑ cf. Huelsenbeck, J. P., F. Ronquist, R. Nielsen and J. P. Bollback (2001) Bayesian inference of phylogeny and its impact on evolutionary biology, Science 294:2310-2314
↑ Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider, Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene 215:1, 111-122
↑ Burnham, K. P. and Anderson D. R. (2002) Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science, New York) ISBN 978-0-387-95364-9.
↑ Jaynes, E. T. (1957) Information Theory and Statistical Mechanics, Phys. Rev. 106:620
↑ Charles H. Bennett, Ming Li, and Bin Ma (2003) Chain Letters and Evolutionary Histories, Scientific American 288:6, 76-81
↑ David R. Anderson (1 de novembro de 2003). «Some background on why people in the empirical sciences may want to better understand the information-theoretic methods» (PDF). Consultado em 23 de junho de 2010. Arquivado do original (PDF) em 23 de julho de 2011
↑ Rivest, Ronald L. (1990). «Cryptology». In: J. Van Leeuwen. Handbook of Theoretical Computer Science. 1. [S.l.]: Elsevier
↑ Bellare, Mihir; Rogaway, Phillip (21 de setembro de 2005). «Introduction». Introduction to Modern Cryptography. [S.l.: s.n.] p. 10
↑ Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A. Handbook of Applied Cryptography. [S.l.: s.n.] ISBN 0-8493-8523-7
↑ "Quantum Computing with Molecules" article in Scientific American by Neil Gershenfeld and Isaac L. Chuang
↑ Manin, Yu. I. (1980). Vychislimoe i nevychislimoe [Computable and Noncomputable] (em russo). [S.l.]: Sov.Radio. pp. 13–15. Consultado em 4 de março de 2013. Arquivado do original em 10 de maio de 2013
↑ Feynman, R. P. (1982). «Simulating physics with computers». International Journal of Theoretical Physics. 21 (6): 467–488. doi:10.1007/BF02650179
↑ Deutsch, David (6 de janeiro de 1992). «Quantum computation». Physics World
↑ Finkelstein, David (1968). «Space-Time Structure in High Energy Interactions». In: Gudehus, T.; Kaiser, G. Fundamental Interactions at High Energy. New York: Gordon & Breach
↑ «New qubit control bodes well for future of quantum computing». Consultado em 26 de outubro de 2014
↑ Quantum Information Science and Technology Roadmap for a sense of where the research is heading.
↑ R. W. Butler (6 de agosto de 2001). «What is Formal Methods?». Consultado em 16 de novembro de 2006
↑ C. Michael Holloway. «Why Engineers Should Consider Formal Methods» (PDF). 16th Digital Avionics Systems Conference (27–30 October 1997). Consultado em 16 de novembro de 2006. Arquivado do original (PDF) em 16 de novembro de 2006
↑ Monin, pp.3-4
↑ ^a ^b ^c ^d ^e The 2007 Australian Ranking of ICT Conferences Arquivado em 2 de outubro de 2009, no Wayback Machine.: tier A+.
↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ The 2007 Australian Ranking of ICT Conferences Arquivado em 2 de outubro de 2009, no Wayback Machine.: tier A.

Leitura complementar

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

SIGACT directory of additional theory links
Theory Matters Wiki Theoretical Computer Science (TCS) Advocacy Wiki
Usenet comp.theory^{[ligação inativa]}
List of academic conferences in the area of theoretical computer science at confsearch
Theoretical Computer Science - StackExchange, a Question and Answer site for researchers in theoretical computer science
Computer Science Animated
http://theory.csail.mit.edu/ @ Massachusetts Institute of Technology

[1] «SIGACT». Consultado em 29 de março de 2009

[2] «ToCT». Consultado em 9 de junho de 2010. Arquivado do original em 4 de novembro de 2010

[3] «Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing». Consultado em 29 de março de 2009

[4] "Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).

[5] Well 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).

[6] "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).

[7] "An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5).

[8] "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).

[9] "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5).

[10] 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.

[11] 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.

[12] Entry data structure in the Encyclopædia Britannica (2009) Online entry accessed on May 21, 2009.

[Coulouris-13] Coulouris, George; Jean Dollimore; Tim Kindberg; Gordon Blair (2011). Distributed Systems: Concepts and Design (5th Edition). Boston: Addison-Wesley. ISBN 0-132-14301-1

[14] Andrews (2000). Dolev (2000). Ghosh (2007), p. 10.

[15] Gottlieb, Allan; Almasi, George S. (1989). Highly parallel computing. Redwood City, Calif.: Benjamin/Cummings. ISBN 0-8053-0177-1

[16] S.V. Adve et al. (November 2008). "Parallel Computing Research at Illinois: The UPCRC Agenda" Arquivado em 9 de dezembro de 2008, no Wayback Machine. (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."

[View-Power-17] 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."

[18] Hennessy, John L.; Patterson, David A.; Larus, James R. (1999). Computer organization and design : the hardware/software interface 2. ed., 3rd print. ed. San Francisco: Kaufmann. ISBN 1-55860-428-6

[19] Ron Kovahi; Foster Provost (1998). «Glossary of terms». Machine Learning. 30: 271–274

[bishop-20] C. M. Bishop (2006). Pattern Recognition and Machine Learning. [S.l.]: Springer. ISBN 0-387-31073-8

[Wernick-Signal-Proc-July-2010-21] Wernick, Yang, Brankov, Yourganov and Strother, Machine Learning in Medical Imaging, IEEE Signal Processing Magazine, vol. 27, no. 4, July 2010, pp. 25-38

[22] Mannila, Heikki (1996). Data mining: machine learning, statistics, and databases. Int'l Conf. Scientific and Statistical Database Management. IEEE Computer Society

[23] Friedman, Jerome H. (1998). «Data Mining and Statistics: What's the connection?». Computing Science and Statistics. 29 (1): 3–9

[nih-24] «NIH working definition of bioinformatics and computational biology» (PDF). Biomedical Information Science and Technology Initiative. 17 de julho de 2000. Consultado em 18 de agosto de 2012. Arquivado do original (PDF) em 5 de setembro de 2012

[brown-25] «About the CCMB». Center for Computational Molecular Biology. Consultado em 18 de agosto de 2012

[26] F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek (1997). Spikes: Exploring the Neural Code. [S.l.]: The MIT press. ISBN 978-0262681087

[27] . Huelsenbeck, J. P., F. Ronquist, R. Nielsen and J. P. Bollback (2001) Bayesian inference of phylogeny and its impact on evolutionary biology, Science 294:2310-2314

[28] Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider, Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene 215:1, 111-122

[29] Burnham, K. P. and Anderson D. R. (2002) Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science, New York) ISBN 978-0-387-95364-9.

[30] Jaynes, E. T. (1957) Information Theory and Statistical Mechanics, Phys. Rev. 106:620

[31] Charles H. Bennett, Ming Li, and Bin Ma (2003) Chain Letters and Evolutionary Histories, Scientific American 288:6, 76-81

[32] David R. Anderson (1 de novembro de 2003). «Some background on why people in the empirical sciences may want to better understand the information-theoretic methods» (PDF). Consultado em 23 de junho de 2010. Arquivado do original (PDF) em 23 de julho de 2011

[rivest90-33] Rivest, Ronald L. (1990). «Cryptology». In: J. Van Leeuwen. Handbook of Theoretical Computer Science. 1. [S.l.]: Elsevier

[modern-crypto-34] Bellare, Mihir; Rogaway, Phillip (21 de setembro de 2005). «Introduction». Introduction to Modern Cryptography. [S.l.: s.n.] p. 10

[hac-35] Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A. Handbook of Applied Cryptography. [S.l.: s.n.] ISBN 0-8493-8523-7

[36] "Quantum Computing with Molecules" article in Scientific American by Neil Gershenfeld and Isaac L. Chuang

[manin1980vychislimoe-37] Manin, Yu. I. (1980). Vychislimoe i nevychislimoe [Computable and Noncomputable] (em russo). [S.l.]: Sov.Radio. pp. 13–15. Consultado em 4 de março de 2013. Arquivado do original em 10 de maio de 2013

[Feynman82-38] Feynman, R. P. (1982). «Simulating physics with computers». International Journal of Theoretical Physics. 21 (6): 467–488. doi:10.1007/BF02650179

[39] Deutsch, David (6 de janeiro de 1992). «Quantum computation». Physics World

[40] Finkelstein, David (1968). «Space-Time Structure in High Energy Interactions». In: Gudehus, T.; Kaiser, G. Fundamental Interactions at High Energy. New York: Gordon & Breach

[41] «New qubit control bodes well for future of quantum computing». Consultado em 26 de outubro de 2014

[42] Quantum Information Science and Technology Roadmap for a sense of where the research is heading.

[butler-43] R. W. Butler (6 de agosto de 2001). «What is Formal Methods?». Consultado em 16 de novembro de 2006

[44] C. Michael Holloway. «Why Engineers Should Consider Formal Methods» (PDF). 16th Digital Avionics Systems Conference (27–30 October 1997). Consultado em 16 de novembro de 2006. Arquivado do original (PDF) em 16 de novembro de 2006

[45] Monin, pp.3-4

[core-a-plus-46] The 2007 Australian Ranking of ICT Conferences Arquivado em 2 de outubro de 2009, no Wayback Machine.: tier A+.

[core-a-47] ↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ The 2007 Australian Ranking of ICT Conferences Arquivado em 2 de outubro de 2009, no Wayback Machine.: tier A.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]