Teoria da Computação

Este livro destina-se às disciplinas de nível universitário que foquem a computação e/ou a complexidade. Primeiro estuda-se a própria computação, na perspectiva das máquinas de registos e das funções recursivas. São duas visões complementares da computação, com princípios muito diferentes mas desenvolvidas, neste livro, até convergirem nas suas conclusões. Estudam-se os limites teóricos da computação, ilustrando alguns problemas que não têm resolução algorítmica, bem como os limites práticos da computação através da teoria da complexidade,uma ferramenta essencial para programadores e engenheiros informáticos na análise de desempenho das suas soluções informáticas. Por fim, num extenso anexo e de forma a auto-conter esta obra dentro do razoável e possível, são apresentados os conceitos matemáticos necessários ao rigor do restante texto.