Lista de livros introdutórios do TCS para quem não conhece muito o TCS [fechado]

Se você precisar recomendar livros para alguém que queira aprender mais sobre o TCS no nível introdutório, como teoria de autômatos, algoritmos, teoria da complexidade, etc., quais livros você recomendaria para aqueles que estão interessados ​​e desejam aprender mais sobre TCS, mas não teve nenhuma exposição a ele?

Se você gostaria de ter uma introdução geral sem se aprofundar nos detalhes técnicos, sugiro Algorithmics de David Harel : The Spirit of Computing . Depois disso, esta é minha lista de favoritos:

• Introdução de Michael Sipser à teoria da computação : a melhor introdução à teoria dos autômatos, computabilidade e complexidade.
• Algoritmos de S. Dasgupta, CH Papadimitriou e UV Vazirani: a introdução mais intuitiva a algoritmos com foco mais forte na intuição do que em provas técnicas.
• Pérolas de programação de Jon Bentley : este não é um livro sobre algoritmos, mas demonstra lindamente como usar técnicas de design de algoritmos para resolver problemas reais que irritavam programadores reais. :-) Esse pode ser um bom começo se você tiver algum conhecimento prévio sobre programação.

• Introdução aos Algoritmos por Cormen, Leiserson, Rivest, Stein é uma escolha popular, o título fala por si.
• Compiladores: Princípios, Técnicas e Ferramentas de Aho, Ulman e Sethi é um bom livro sobre compiladores, também contém algum material de introdução sobre a teoria dos autômatos.
• Princípios de verificação de modelo é um livro massivo que pode ser usado como uma introdução à verificação de modelo

Para a matemática necessária na análise de algoritmos, recomendo o primeiro e único GKP:

Matemática Concreta de Graham, Knuth, Patashnik
Um tratamento abrangente e de alta qualidade de praticamente toda a matemática necessária em algoritmos (básicos). É uma leitura divertida e inclui diversos exercícios (e soluções).

Algoritmos 4. Edição R. Sedgewick

Uma Introdução à Análise de Algoritmos P. Flajolet, R. Sedgewick

Introdução à Teoria dos Autômatos, Idiomas e Computação JE Hopcroft, JD Ullman, (R. Motwani)
A primeira edição de 1979 apresenta mais resultados teóricos que estão faltando na segunda edição de 2001. Ainda não olhei para o terceiro Ed.

Introdução à teoria formal da linguagem MA Harrison
É de 1978, mas eu ainda gostaria de vê-lo na lista.

Logicomix: uma busca épica pela verdade A. Doxiadis, CH Papadimitriou
Porque é totalmente incrível!

Novamente, 1979
, Computadores e Intratabilidade de Garey e Johnson : Um Guia para a Teoria da Completude NP

Eu adoraria ter o TAoCP na lista, mas temo que a abordagem meticulosa de Don Knuth não seja nada que possa ser considerado "introdutório". Infelizmente...

Se você é totalmente novo no campo do TCS, a Introdução à Teoria da Computação da Sipser é definitivamente o melhor livro para você começar. Li outros livros introdutórios, e nenhum deles, na minha opinião, chega perto da maneira de Sipser de trazer o assunto.

Outros livros teóricos mais específicos e bons são:

• Tipos e linguagens de programação de Benjamin Pierce . Isso é ciência da computação teórica e lógica de uma perspectiva diferente.
• Gemas de Ciência da Computação Teórica de U. Schöning e R. Pruim.

Alguns bons livros que cobrem a parte da teoria B do TCS:

• Lógica no CS : Lógica em Ciência da Computação: Modelagem e Raciocínio sobre Sistemas Por Michael Huth e Mark Ryan.
  Ampla cobertura de vários usos da lógica em ciência da computação. Cerca de terceiro ano de graduação.

• O cálculo Lambda : Lambda-Calculus e combinadores. Uma introdução por J. Roger Hindley e Jonathan P. Seldin.
  Introduz o cálculo lambda, que é um ingrediente essencial nos fundamentos das linguagens de programação. Cerca de terceiro ano de graduação.

• Conduzir para a teoria de domínio : Introdução a Malhas e Ordem (2ª ed.) Por Davey, BA e Priestley, HA Cambridge University Press. (2002)
  Abrange um tópico muito útil, especialmente se você planeja trabalhar com semântica. É um pouco mais matemático do que os outros tópicos, mas os primeiros capítulos certamente estão em um nível avançado de graduação.

• Semântica : Semântica com Aplicações: Um Aperitivo de Hanne Riis Nielson e Flemming Nielson.
  Uma introdução muito boa à semântica da linguagem de programação. Em vez de se aprofundar em qualquer formalismo em particular, ele oferece uma apresentação ampla e inclui aplicativos geralmente não considerados em outros livros sobre semântica. Pode ser útil para alunos do segundo ano do ensino médio.

Esta é uma resposta agregada que contém livros de respostas com pontuação de pelo menos cinco. Por favor, discuta seu conteúdo no chat .

Algoritmos e estruturas de dados

• Introdução a Algoritmos por Cormen, Leiserson, Rivest, Stein (3ª ed. 2009)
  Um tratamento abrangente de algoritmos básicos e estruturas de dados e suas análises sem se aprofundar muito.
• Algoritmos de Dasgupta, Papadimitriou, Vazirani (2006)
  A introdução mais intuitiva a algoritmos com foco mais forte na intuição do que em provas técnicas.

Computabilidade e complexidade

• Introdução à Teoria da Computação por Sipser (2ª edição, 2005)
  A melhor introdução à teoria, computabilidade e complexidade dos autômatos.

Linguagens formais e autômatos

• Compiladores: Princípios, Técnicas e Ferramentas de Aho, Ulman e Sethi (2ª ed. 2006)
  O livro padrão sobre compiladores; muito abrangente. Também toca na teoria dos autômatos.

Teoria Aplicada

• Princípios de verificação de modelo por Baier, Katoen (2008)
  Livro maciço que pode ser usado como uma introdução abrangente à verificação de modelo.
• Programming Pearls, de Jon Bentley (2ª ed. 1999)
  Não é um livro sobre algoritmos, mas demonstra lindamente como usar técnicas de design de algoritmos para resolver problemas reais. Pode ser um bom começo se você tiver algum conhecimento prévio sobre programação.