Teoria da Computação: Computabilidade e Complexidade

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 comp utação, com princípios muito diferentes mas desenvolvidos, 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 d a 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 fi m, num extenso anexo e de forma a autoconter esta ora dentro do r az oável e possível, são apresentados os conceitos matemáticos necessários ao rigor do restante texto.