A computabilidade parte de uma questão fundamental da ciência da computação: quais problemas podem, de fato, ser resolvidos por um algoritmo? O livro mostra como essa pergunta levou matemáticos e pesquisadores a transformar a noção intuitiva de cálculo em modelos formais, permitindo distinguir limitações causadas pela tecnologia de barreiras que pertencem à própria lógica da computação.
A máquina de Turing, a tese de Church-Turing e o problema da parada ajudam a compreender por que existem problemas que nenhum computador consegue resolver de maneira geral, mesmo que imaginemos máquinas com memória e tempo ilimitados. A indecidibilidade é apresentada de forma acessível, sem exigir conhecimentos matemáticos avançados, mostrando suas implicações para programas, sistemas e métodos de verificação.
O livro também aborda outro tipo de limite: problemas que podem ser resolvidos em princípio, mas que exigem uma quantidade de tempo ou recursos tão grande que sua solução se torna impraticável. A partir da distinção entre computabilidade e complexidade computacional, você conhece de maneira intuitiva as classes P e NP e entende por que encontrar uma solução pode ser muito mais difícil do que verificar se uma resposta já encontrada está correta.
Aproximações, algoritmos probabilísticos e heurísticas completam o percurso, mostrando como a computação enfrenta problemas para os quais soluções exatas são difíceis, caras ou inviáveis.
| Number of pages | 154 |
| Edition | 1 (2026) |
| Format | A5 (148x210) |
| Binding | Paperback w/ flaps |
| Colour | Black & white |
| Paper type | Offset 80g |
| Language | Portuguese |
Have a complaint about this book? Send an email to [email protected]
login Review the book.