1- Limites da Computação
Computadores resolvem uma série de problemas e tarefas mas há problemas e tarefas que ele não consegue realizar.
Em Teoria da Computação estudamos, entre outros temas, os limites da Computação, procurando identificar se pode ser resolvido por uma máquina e a que preço, não só em termos de tempo de processamento mas em número de operações computacionais.
Problemas que tem solução computacional equivalente a funções matemáticas exponenciais costumam ser muito complicados ou mesmo irrealizáveis.
Funções exponenciais crescem muito rápido.
Veja o que aconteceria se fôssemos preencher um tabuleiro de xadrez seguindo a ideia de que a cada casa, teríamos o dobro de elementos da casa anterior:
Autoral, 2022
Cada cssa contém 2n elementos. Se fôssemos representar grãos de areia, não demoraria ao término de preencher o tabuleiro, teríamos mais grãos de areia do que a quantidade total que existe no planeta Terra! Assim soluções exponenciais para certos problemas são muito difíceis de serem tratadas mesmo por um computador
O problema do Caixeiro Viajante: um clássico da Computação
Um vendedor precisa visitar um certo número de cidades e retornar para casa ao fim do dia. Para elevar seus ganhos, precisa percorrer o itinerário mais curto entre essas cidades. Sabe-se qual a distância entre cada uma das cidades.
Exemplo:
Percorrer as cidades A, B, C, D e depois retornar à cidade de origem A.
Autoral, 2022
A velocidade para se encontrar o menor percurso entre um conjunto de cidades depende do computador usado e do número de cidades!
Para 3 cidades existem 3! combinações possíveis, isto é, 6 combinações para serem testadas.
Para 10 cidades existem 10! combinações, mais de 3 milhões de combinações !!
2 - Crescimento Assintótico
Problemas semelhantes a esse são de extrema importância para a indústria, considere, por exemplo, as várias etapas envolvidas na montagem de um motor e que devem ser efetuadas em uma certa ordem - esse é conhecido como Problema do Sequenciamento de Tarefas.