Introduction to Theoretical Computer Science

Livro digital

Título:
Introduction to Theoretical Computer Science

Autor:
Boaz Barak

Categoria:
Tecnologia > Geral

Doador:
Raffaello D. N.

Sinopse:
What does it mean to compute? Boaz Barak answers this question by building the entire intellectual edifice of theoretical computer science from a single starting point: the definition of computation itself. The journey moves from finite automata and regular expressions through Turing machines, universal computation, and the discovery of uncomputable problems. The second half tackles the questions that define modern computer science: what makes a problem efficiently solvable, why NP-completeness matters, how randomness changes the computational landscape, and what quantum computers might eventually achieve. Each chapter builds on the previous one with a clear dependency map that lets readers navigate the material at their own depth. Freely available as an open textbook under active development, the presentation favors conceptual clarity over notational density. Proofs are treated as programs, cryptographic constructions emerge naturally from computational hardness, and even advanced topics like the Cook-Levin theorem are explained with the same patient care given to the opening chapters on sets and functions.