Que livros todos deveriam ler?

[ Linha do tempo ]

Essa pergunta tem o mesmo espírito de quais papéis todos deveriam ler e quais vídeos todos deveriam assistir . Ele pede livros notáveis ​​em diferentes áreas da ciência da computação teórica.

Os livros podem ser orientados para a matemática, mas você pode achar ótimo para um cientista da computação. Exemplos:

• Probabilidade
• Desigualdades
• Lógica
• Teoria dos grafos
• Combinatória
• Projeto e Análise de Algoritmo
• Teoria da Computação / Teoria da Complexidade Computacional

Dedique cada resposta a livros do mesmo assunto (por exemplo, livros sobre combinatória).

Nota: O título pode ser enganoso. Aqui está um esclarecimento: sejam X e Y dois campos da ciência da computação. Existem livros que todo mundo

• no campo X deve ler.
• no campo Y deve ler.
• em ambos os campos deve ler.

Esta questão busca todos os três casos. Em outras palavras, NÃO é específico para o último caso.

Editar: Como sugerido por Dai Le , destaque os motivos pelos quais você também gosta do livro.

Tópicos relacionados:

• Referências para técnicas de prova TCS
• Livros sobre teoria dos autômatos para auto-estudo
• Livros para probabilidade
• Livro de matemática popular favorito
• Guia do iniciante para des aleatorização
• Referências sobre os limites inferiores do circuito
• Artigo de pesquisa sobre a teoria das funções recursivas
• Livros sobre semântica da linguagem de programação
• Quais são os livros recentes do TCS cujos rascunhos estão disponíveis on-line
• Livros sobre probabilidade

Complexidade computacional:

Se você está procurando por livros didáticos de complexidade recente. Os dois seguintes são obrigatórios.

• Complexidade computacional: uma abordagem moderna de Sanjeev Arora e Boaz Barak ( página inicial do livro )

• Complexidade computacional: uma perspectiva conceitual de Oded Goldreich ( página de livro didático )

A maioria do conteúdo entre esses dois livros é comparável. No entanto, existem algumas diferenças importantes: Goldreich dedica mais espaço para explorar a base conceitual e filosófica da teoria da complexidade, enquanto Arora / Barak cobre uma seleção mais ampla de tópicos, incluindo modelos concretos de complexidade, computação quântica e limites inferiores do circuito ausentes na maioria das vezes. do primeiro.

Outra opção, um livro antigo, mas atemporal, em complexidade é:

• Complexidade computacional de Christos Papadimitriou

O livro de Papadimitriou é notável por capítulos que abordam a lógica de primeira ordem, bem como as classes SNP, MaxSNP 0 e APX (os fundamentos teóricos da dureza da aproximação), que estão ausentes nos textos mais modernos.$_0$

Outro clássico (comparativamente) antigo, mas bastante notável é:

• Introdução à Teoria da Computação por Michael Sipser

Este é um dos poucos / primeiros livros didáticos que inclui explicitamente "Prova de idéia:" entre "Teorema:" e "Prova:" e é um dos livros de matemática mais bem escritos sobre qualquer tópico. Por outro lado, é apenas uma introdução à complexidade, dedicando apenas um capítulo de 50 páginas a "tópicos avançados" (incluindo aproximação, algoritmos probabilísticos, IP = PSPACE e criptografia). Como um primeiro livro sobre complexidade, ou como um exemplo de redação realmente excelente, este livro é ótimo .

• A natureza da computação de Cristopher Moore e Stephan Mertens

Scott Aaronson escreve que este livro tem "a diversão de um livro popular com o peso intelectual de um livro". Ele conta histórias e fornece muitos exemplos e referências divertidos (Game of Life, e muitos outros exemplos para máquinas completas de Turing). Não se aprofunda muito na teoria da complexidade, mas tem uma grande amplitude. Especialmente dignas de nota são suas conexões com a física estatística.

NP-Completeness:

Bem, acho que os computadores e a intratabilidade de Garey e Johnson : um guia para a teoria da completude da NP serão encontrados entre os principais livros desta lista.

Projeto e Análise de Algoritmos:

Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest e Clifford Stein. Introdução aos algoritmos.

R. Motwani, P. Raghavan. Algoritmos randomizados.

Encontrei este livro sugerido por Ryan Williams no MathOverflow: Algorithm Design by Kleinberg & Tardos .

Outro excelente livro é Introdução aos algoritmos: uma abordagem criativa de Udi Manber . Este livro não é um catálogo de algoritmos; ao contrário, tenta fornecer ao leitor intuição para "reconhecer a estrutura matemática em problemas abstratos". (citado de uma revisão)

Matemática Geral para Ciência da Computação:

• Matemática concreta: uma fundação para a ciência da computação por Graham, Knuth e Patashnik.

• O companheiro de Princeton à matemática por Gowers et al.

• Provas do livro de Aigner e Ziegler.

Sistemas de tipos e semântica da linguagem de programação:

Tipos e linguagens de programação de Benjamin Pierce e o volume de acompanhamento Tópicos avançados em Tipos e linguagens de programação . Eles fornecem uma visão geral sólida, porém compreensível, do papel da teoria dos tipos no design da linguagem de programação, além de usar a semântica operacional para expressar a semântica da linguagem de programação.

Desigualdades:

Outro livro valioso para qualquer um na ciência da computação que queira vincular qualquer quantidade (então, todo mundo!) É: A classe principal de Cauchy-Schwarz: uma introdução à arte das desigualdades matemáticas por Michael Steele.

Um livro enciclopédico sobre o tema é Um dicionário de desigualdades . Embora este livro não seja para leitura de capa a capa, é bom tê-lo à sua disposição. Veja também o suplemento do livro.

Além disso, a Wikipedia possui uma excelente lista de desigualdades .

Para tópicos específicos, você pode consultar:

• Desigualdades probabilísticas
• Desigualdades matriciais
• Desigualdades geométricas
• O livro "A = B" de Petkovsek, Wilf e Zeilberger

Interessante. Ninguém mencionou volumes de The Art of Computer Programming, de Donald E. Knuth . Um tratamento muito detalhado de tópicos com muito bons exercícios.

Encontrei gemas como 'amostragem de resorvoir' neste livro apenas para mencionar um exemplo.

Como Sylvain Peyronnet já mencionou, a lógica é uma parte importante da ciência da computação teórica. No entanto, não é suficiente aprender lógica de livros didáticos elaborados para matemáticos puros. Em outras palavras, também é importante aprender lógica de uma perspectiva mais "informática".

Teoria do Modelo Finito

Queremos aprender técnicas que lidam com estruturas finitas. É sabido que muitas ferramentas tradicionais da teoria dos modelos, por exemplo, compacidade e teorema de Löwenheim-Skolem, não são aplicáveis ​​a modelos finitos. Isso nos leva ao estudo da Teoria dos Modelos Finitos . Para esta área, recomendo os seguintes excelentes livros:

• Leonid Libkin, Elementos da Teoria do Modelo Finito . (livro didático)
• Grädel et al., Teoria dos Modelos Finitos e Suas Aplicações . (artigos e aplicativos de pesquisa)

Uma subárea da teoria de modelos finitos é a complexidade descritiva , na qual queremos caracterizar as classes de complexidade pelo tipo de lógica necessária para definir as linguagens. A referência definitiva para a complexidade descritiva é:

• Neil Immerman, Complexidade Descritiva .

Complexidade de prova

Outra área importante da lógica na ciência da computação é a Proof Complexity , um estudo de relações de três vias entre classes de complexidade, sistemas lógicos fracos e sistema de prova proposicional. Os dois aspectos relacionados a seguir são considerados: (i) a complexidade de provas de fórmulas proposicionais e (ii) o estudo de teorias fracas da aritmética, denominadas aritmética limitada .

O aspecto (i) tem a ver com a seguinte pergunta: "Existe um sistema de prova proposicional em que toda tautologia tem uma prova de tamanho polinomial no tamanho da tautologia?"

$C$$VC$$VC$$C$

$\mathsf{PV}$$\mathsf{PV}$

Para excelentes pesquisas sobre a complexidade da prova, recomendo os dois livros a seguir:

• Stephen Cook e Phuong Nguyen, fundamentos lógicos da complexidade da prova . (rascunho disponibilizado aqui )
• Jan Krajíček, aritmética limitada, lógica proposicional e teoria da complexidade .

$\mathsf{P}$$V_0$

O livro de Krajíček é um pouco mais desafiador, pois ele assumiu que os leitores já estão familiarizados com a lógica matemática e a teoria dos modelos (ou dispostos o suficiente para aprender os antecedentes necessários ao longo do caminho). Mas você aprenderá muito lendo e compreendendo este livro.

Algoritmos Aleatórios:

Probabilidade e computação: algoritmos randomizados e análise probabilística por Michael Mitzenmacher e Eli Upfal.

Ótimo livro para explicar o básico de algoritmos aleatórios. Os exemplos e provas são explicados com muita clareza e são fáceis de seguir. Além disso, os exercícios são muito divertidos de fazer.

(respondido por Marcos Villagra)

Análise de Algoritmos Aleatórios:

Qualquer pessoa que trabalhe com algoritmos deve ter Concentração de Medida para Análise de Algoritmos Aleatórios , que também está disponível para download em formato PDF aqui .

Criptografia:

O livro de dois volumes, Foundations of Cryptography, de Oded Goldreich ( Volume 1: Ferramentas básicas e Volume 2: Aplicativos básicos ) é um excelente livro sobre o assunto. (Os primeiros rascunhos estão disponíveis na página inicial do autor .) Também está disponível uma versão abreviada deste livro.

Outro excelente livro é Introdução à criptografia moderna: princípios e protocolos de Katz & Lindell.

Para aqueles interessados ​​em conhecimentos matemáticos de criptografia, Uma Introdução à Criptografia Matemática, de Hoffstein et al. é a escolha natural.

Outros livros excelentes são:

• Handbook of Applied Cryptography por Menezes et al. (O capítulo está disponível online ).
• Criptografia: Teoria e Prática de Stinson.

Tópicos Específicos:

• Livros relacionados à composição avançada de protocolos de segurança:
  • Composição de protocolos multipartidários seguros: um estudo abrangente de Lindell.
  • Zero conhecimento simultâneo de Rosen.
• Provas formais em protocolos de segurança
  • Correção formal dos protocolos de segurança de Bella.
• [Matemática da criptografia de chave pública] ( http://www.amazon.com/Mathematics-Public-Cryptography-Steven-Galbraith/dp/1107013925 ) por Galbraith

Programação Funcional

• Estruturas de dados puramente funcionais por Chris Okasaki . A maioria dos livros sobre estruturas de dados assume uma linguagem imperativa como C ou C ++. No entanto, as estruturas de dados para esses idiomas nem sempre traduzem bem para idiomas funcionais. Este livro é uma das melhores exposições sobre a implementação de estruturas de dados e algoritmos em uma linguagem funcional.
• Programação Funcional: Prática e Teoria por Bruce J. Maclennan . Apesar do nome, este livro é mais orientado por teoria do que por prática. Quem ler este livro terá uma visão muito melhor do assunto do que quem o aprender por meio de programação ad-hoc.
• Pérolas do algoritmo funcional Design por Richard Bird . Uma exposição totalmente nova sobre o assunto, que adota a abordagem de solução de problemas e mostra a beleza do campo, exibindo idéias atraentes no design de algoritmos funcionais.
• Programação certificada com tipos dependentes por Adam Chlipala . É um dos melhores recursos para aprender Coq, e se concentra em particular em como automatizar a certificação de programas e a comprovação de teoremas usando sistemas lógicos / baseados em regras. Exemplos são extensos e fáceis de seguir.

Algoritmos de Aproximação

O livro Algoritmos de Aproximação de Vazirani é o melhor livro sobre o assunto. Outro livro é Algoritmos de aproximação para problemas NP-difíceis de Hochbaum.

Aqui estão comparações de dois revisores:

Eu tenho usado o livro de Dorit Hochbaum sobre algoritmos de aproximação para problemas NP-Hard como uma diretriz para o meu trabalho. O livro de Hochbaum é, sem dúvida, fantástico. No entanto, o formato da pesquisa comprometeu um fluxo suave a favor de reunir as melhores pessoas no campo. O livro de Vazirani corrige isso sendo tão suave e elegante do começo ao fim. Excelentes conjuntos de problemas, excelentes dicas para a maioria dos problemas e há uma seção no final do livro dedicada a problemas em aberto, que é um recurso muito interessante.

e

Tenho procurado livros relacionados à solução de problemas NP-completos e NP-difíceis aproximadamente. Há outro livro de Hochbaum e eu também o tenho. Infelizmente, esse livro é mais um livro orientado para a pesquisa, pois é escrito por vários pesquisadores. É como ler vários trabalhos de pesquisa em duas capas. Isso significa que é preciso ter um tipo de nível intermediário de experiência com algoritmos de aproximação.

Um livro recente é O design de algoritmos de aproximação de Williamson e Shmoys.

Combinatória

Livros introdutórios. Qualquer um dos seguintes livros pode servir como uma excelente introdução ao assunto:

• Manual de Matemática Discreta e Combinatória de Rosen.
• Matemática Discreta e Combinatória: Uma Introdução Aplicada por Grimaldi. Veja também o manual da solução .
• Um passeio pela combinatória e introdução à combinatória enumerativa e introdução à combinatória enumerativa da Bona. O primeiro livro é mais abrangente e clássico. O segundo livro tem considerável sobreposição com o primeiro, mas a ênfase está muito mais nos métodos modernos de contagem.
• Um curso de Combinatória por van Lint & Wilson.
• Combinatória: Tópicos, Técnicas, Algoritmos de Cameron. (Este livro tem muitos exercícios legais.)
• Problemas e exercícios combinatórios de László Lovász (respondidos por @Sazzad)

Textos mais avançados.

• Combinatória Enumerativa, Volume 1 e Volume 2, de Stanley. É simplesmente uma obra-prima da combinatória enumerativa; muito desafiador, muito profundo.
• Algoritmos Combinatórios: Geração, Enumeração e Pesquisa por Kreher & Stinson. Mais adequado para aplicações de ciência da computação de combinatória.
• Combinatória aditiva de Terence Tao e Van H. Vu. Uma referência muito útil para enfrentar um problema combinatório relacionado à teoria dos números.

Combinatória

Quero citar a Analytic Combinatorics , de Philippe Flajolet e Robert Sedgewick. Ele fornece uma sólida base matemática para enumeração e análise de algoritmos. Quero também prestar homenagem a Philippe Flajolet, que morreu há dois dias e foi um grande matemático e cientista da computação.

Verificação do Programa

• Teoria matemática da computação por Zohar Manna
• Princípios de verificação de modelo por Christel Baier e Joost-Pieter Katoen
• Verificação do modelo por Edmund M. Clarke Jr., Orna Grumberg e Doron A. Peled
• Verificação de programas sequenciais e concorrentes por Krzysztof R. Apt, Frank S. de Boer e Ernst-Rüdiger Olderog
• Lógica em Ciência da Computação: Modelagem e Raciocínio sobre Sistemas por M. Huth e M. Ryan

Teoria da Informação

Teoria da informação, inferência e algoritmos de aprendizagem por David MacKay

Outros livros famosos sobre teoria da informação podem ser encontrados na Wikipedia .

Algoritmos distribuídos

Algoritmos distribuídos por Nancy Lynch Este é um texto clássico escrito por um pioneiro da computação distribuída;

Introdução a algoritmos distribuídos por Gerard Tel Introdução muito boa, também adequada para cursos de graduação; focado no modelo de transmissão de mensagens

Computação distribuída: fundamentos, simulações e tópicos avançados de Hagit Attiya e Jennifer Welch Contém materiais avançados, adequados para cursos de nível de doutorado; são discutidos os modelos de passagem de mensagem e memória compartilhada

Projeto e análise de algoritmos distribuídos Por Nicola Santoro Um livro relativamente recente, pode ser usado tanto nos níveis de graduação quanto de doutorado; os materiais são apresentados com ênfase no desenho do protocolo

Computação quântica

• Computação quântica e informação quântica de Nielsen e Chuang , é um ótimo livro de referência , ideal para quem deseja pesquisar no campo. No entanto, para iniciantes, é difícil aprender e definitivamente não é para aprendizes. Como o livro carece de exemplos funcionais, sugiro o seguinte livro:

  • Problemas e Soluções em Computação Quântica e Informação Quântica por Steeb & Hardy . Este livro inclui muitos exemplos, mas ainda não é para iniciantes. Para iniciantes, é sugerido o seguinte livro:

    • Aproximando-se da Computação Quântica de Marinescu e Marinescu . Embora elementar e fácil de aprender, algumas pessoas o acham "cheio de erros". Nesse sentido, as erratas do livro são úteis.

• Computação quântica desde Demócrito, de Scott Aaronson . Um tour-de-force de muito mais do que computação quântica, com relações com a física, filosofia, etc.

Dois outros excelentes livros introdutórios sobre o assunto são:

• Computação Quântica para Cientistas da Computação por Yanofsky & Mannucci .
• Uma introdução à computação quântica de Kaye, Laflamme e Mosca .

Otimização

Eu gostei de Paul Nahin's When Least is Best.

Essencialmente, uma história fofa de otimização através de problemas e personalidades. Há uma boa revisão nas páginas 32-36 em uma das colunas de Bill Gasarch.

$e^{i\pi} = -1$

Complexidade da comunicação:

Este é um livro clássico e muito bem escrito. Embora um pouco velho até agora, ainda é o melhor livro introdutório para o campo. Além disso, os exercícios são extremamente divertidos e são dados exatamente após a explicação dos conceitos, para que você possa corrigir o que acabou de aprender.

A parte da complexidade da comunicação aleatória deve ser complementada com partes do primeiro livro.

Complexidade da comunicação e computação paralela por Juraj Hromkovič.

Muito completo, embora às vezes um pouco difícil de ler. As explicações intuitivas são exercícios muito claros e muito agradáveis. Na segunda parte, apresenta as conexões com a computação paralela.

• Os livros de Matousek & Chazelle sobre Discrepancy são excelentes.

  Quase todos os livros de Matousek , de fato, valem a pena ser lidos em certa medida.

• Os livros de Douglas West sobre teoria dos grafos ( [1] e [2] ) são bons.

• Alon & Spencer também é excelente.
• Pach & Agarwal é bom para geometria discreta, assim como Sharir & Agarwal, se você gosta de sequências de DS.
• O livro de Brass, Moser e Pach sobre problemas abertos em geometria discreta também é muito bom.
• O livro de Vanderbei no LP é muito bom.
• Os livros de Schrijver ( [1] e [2] ) são surpreendentes.

Álgebra Computacional

Como Shiva disse nesta resposta , as literaturas nesse campo estão espalhadas por todo o lugar, sem terminologias comuns. Pode-se encontrar referências úteis pesquisando "computação simbólica", "teoria da complexidade algébrica", "álgebra computacional" ou "álgebra computacional". Conforme sugerido nas respostas a esta pergunta ,

• Álgebra computacional moderna de Joachim von zur Gathen e Jürgen Gerhard.
• Teoria da complexidade algébrica de Peter Bürgisser, Michael Clausen, Mohammad A. Shokrollahi e T. Lickteig.
• Álgebra Algorítmica de Bhubaneswar Mishra.
• Uma Introdução Computacional à Teoria dos Números e Álgebra por Victor Shoup.

Análise Computacional

Um campo interessante também, que lida com cálculos em funções reais. Também conhecido como "análise computável" ou "cálculo computável".

• Análise Computável por Oliver Aberth.
• Análise Computável: Uma Introdução por Klaus Weihrauch.

Combinatória

generatorfunctionology , de Herbert S. Wilf, é uma excelente introdução à teoria de gerar funções, escrita de maneira suave e repleta de exercícios. Se ele escreve todos os seus livros assim, mal posso esperar para começar outro.

A Combinatória Enumerativa de Richard Stanley é uma ótima referência (avançada).

Combinatória: tópicos, técnicas, algoritmos de Peter Cameron e Convite para Matemática Discreta de Matousek e Nesetril são boas introduções à combinatória.

A Applied Combinatorics de Roberts e Tesman é uma referência enciclopédica sobre combinatória aplicada.

Lógica:

Este é um resumo da minha resposta a esta pergunta .

O conhecimento da lógica matemática básica é, na minha opinião, uma vantagem. Você pode dar uma olhada nos dois livros de Cori e Lascar.

Lógica Matemática: Um Curso com Exercícios Parte I

Lógica Matemática: Um Curso com Exercícios Parte II

Lógica / Prova de Redação:

1. Como provar: uma abordagem estruturada por Daniel J. Velleman

Teoria dos Números

Encontrei vários livros frequentemente citados em muitos artigos. Eles são excelentes no assunto, mas alguns deles são bastante antigos. Aqui está uma lista do que me lembro:

• Uma introdução à teoria dos números por Hardy et al. Hardy é um matemático britânico de renome. Ele foi o mentor do matemático indiano Ramanujan . Sua contribuição para o campo da teoria dos números é bastante surpreendente .
• Uma introdução à teoria dos números por Niven, Zuckerman, Montgomery. Outra introdução clássica ao campo.
• Problemas resolvidos e não resolvidos na teoria dos números por Shanks. Este é o livro para aqueles que buscam conjecturas ainda a serem provadas no campo.
• Função Zeta de Riemann, de Edwards. Uma parte importante da moderna teoria dos números, bem como vários algoritmos probabilísticos para tarefas teóricas dos números, são fundados com base na hipótese de Riemann (estendida), conforme descrito neste livro.

Hipergráficos

Não existem muitos livros dedicados exclusivamente a hipergráficos. Um desses livros é

Berge C. Hypergraphs: combinatória de conjuntos finitos .

Teoria da Prova

O livro de Troelstra e Schwichtenberg, Basic Proof Theory, é o texto de fato sobre o assunto agora.

As provas e tipos de Girard, Taylor & LaFont são um livro mais curto sobre o assunto e uma versão está disponível para download em http://www.paultaylor.eu/stable/Proofs%2BTypes.html

Teoria dos grafos

Para introdução à teoria dos grafos: Introdução à teoria dos grafos por West

Mais sobre teoria dos grafos: Teoria dos grafos de Bondy e Murty

O livro abrangente que contém novos desenvolvimentos, bem como resultados clássicos antigos na teoria dos grafos:

Teoria dos grafos: Reinhard Diestel .

Para gráficos em superfícies com abordagem combinatória:

Gráficos em superfícies

E para os digrafos:

Digrafos: Teoria, Algoritmos e Aplicações

Projeto VLSI

Eu não gosto de hardware. No entanto, como as perguntas frequentes incluem o VLSI como um dos subcampos do TCS, perguntei a um especialista sobre livros famosos no design do VLSI. Aqui estão eles:

• Circuitos integrados digitais
• Projeto CMOS VLSI: uma perspectiva de circuitos e sistemas
• Design VLSI moderno: Design baseado em IP