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ê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.
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.
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
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.
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.
