AEDS - Primeiros conceitos

Algoritmo é um conjunto finito (preferencialmente pequeno) de instruções destinadas a solucionar determinado problema. Há uma definição formal de algoritmos chamada Máquia de Turing. Todo algoritmo pode ser expresso por uma MT que, em resumo, é uma máquina que interpreta uma sequência de bits - uma abstração do computador.
Características desejáveis em algoritmos:

• Correção: o algoritmo apresenta a saída correta para qualquer entrada válida
• Eficiência: uso eficiente dos recursos computacionais
• Elegância: ser simples e claro, de fácil interpretação
• Robustez: ser capaz de lidar com qualquer entrada de dados
• Generalidade: ser adaptável a dados e sistemas diferentes

Estrutura de dados é a abstração de um conjunto de dados, sua representação. A escolha da estrutura de dados correta é importantíssima, pois ela limita ou define quais algoritmos usar. Algoritmos e estruturas de dados são interdependentes, e juntos compõem programas.

O problema que o algoritmo visa solucionar é o que fazer com uma entrada para que ela gere a saída desejada; é a relação entre entrada e saída. O algoritmo especifica como fazer isso com a entrada.

Computabilidade é a existência de uma solução algorítmica para um problema. Por exemplo, achar o enésimo termo da sequência de Fibonacci é um problema computável, mas achar o segredo da felicidade não (profundo, hein). Toda função computável pode ser expressa por uma MT.

Teoria de algoritmos é uma área que trata da eficiência dos algoritmos. As soluções para problemas computáveis são uma fração de todos os problemas, e soluções eficientes são uma fração destas.