CS teórico e matemática - recomendações de auto-estudo

14

Eu não sou graduado em CS e meu campo de estudo não tem relação com CS. No entanto, como parte de um plano maior de me tornar um cientista da computação, quero obter uma sólida formação em ciência da computação teórica e matemática no que se refere ao CS. Pesquisei bastante e selecionei os seguintes / melhores livros sobre o tema CS e matemática e gostaria de pedir sua opinião sobre:

  • Abrangência dos tópicos abordados (recomende qualquer coisa que eu tenha perdido)
  • Sobreposição de área coberta / excesso de material (por favor, recomende livros que devem ser removidos da lista)
  • Ordem para estudar os livros (listei na ordem em que acho que deveriam ser estudados)

A lista é excessivamente longa, então eu gostaria de receber recomendações para remover alguns livros, sem a perda do conhecimento básico necessário para o CS.

Então, os livros são:

  1. O prazer do matemático por WW Sawyer
  2. Como provar: uma abordagem estruturada por Daniel J. Velleman
  3. Como Resolvê-lo: Um Novo Aspecto do Método Matemático por G. Polya
  4. Introdução à Programação Funcional Através do Cálculo Lambda de Greg Michaelson
  5. Fundamentos de Ciência da Computação de Al Aho e Jeff Ullman (http://i.stanford.edu/~ullman/focs.html)
  6. Matemática concreta: uma fundação para a ciência da computação por Graham, Knuth e Patashnik
  7. Introdução à Teoria da Computação por Michael Sipser
  8. Introdução à Teoria dos Autômatos, Idiomas e Computação por John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
  9. Complexidade computacional: uma perspectiva conceitual de Oded Goldreich
  10. Complexidade computacional: uma abordagem moderna de Sanjeev Arora, Boaz Barak
  11. Um Curso de Combinatória por JH van Lint, RM Wilson
  12. Computabilidade: Uma Introdução à Teoria da Função Recursiva por Nigel Cutland
  13. Computadores e Intratabilidade: Um Guia para a Teoria da Completude NP por MR Garey, DS Johnson
  14. Teoria das Funções Recursivas e Computabilidade Efetiva por Hartley Rogers
  15. Desigualdades de GH Hardy, JE Littlewood, G. Polya
  16. Lógica Matemática: Um Curso Com Exercícios (Parte I): Cálculo Proposicional, Álgebras Bookeanas, Cálculo Predicado de René Cori, Daniel Lascar
  17. Lógica Matemática: Um Curso Com Exercícios (Parte II): Teoria da Recursão, Teoremas de Godel, Teoria dos Conjuntos, Teoria dos Modelos por René Cori, Daniel Lascar
CSLover
fonte
Consulte esta pergunta cstheory.stackexchange.com/questions/3253/…
Bartosz
Comece com um livro conhecido de Algoritmo, se você ainda não tem experiência neste tópico.
AJed
@Bartek: Obrigado, mas essa foi uma das perguntas que eu olhei antes para compilar a lista em primeiro lugar. Minha pergunta é mais sobre como ler praticamente todo o ótimo material existente. O tempo é sempre uma restrição, então eu quero saber o que os livros que eu deveria "não" ler para evitar a repetição etc.
CSLover
@AJed: Você está sugerindo começar com o livro nº 5 da lista, em vez de alguns dos livros de matemática nº 1-4? Eu acredito que o número 5 fornece uma introdução suave a algoritmos e estruturas de dados.
precisa
Demais aqui. Eu apenas escolhia uma e saía, então me preocupava com o que virá a seguir quando você chegar lá. Eu recomendo que a Sipser comece para um iniciante que queira uma sólida formação em fundações da CS.
usul

Respostas:

10

Sua lista é extremamente problemática.

Para começar, eu pularia os livros 6,11,12,14,15,16,17: os livros 6, 11 e 15 são matemática geral que não é realmente necessária, a menos que você se torne um pesquisador teórico . Os livros 12 e 14 abordam a teoria da recursão que não é ciência da computação (embora lide com a computabilidade!). Os livros 16 e 17 abordam tópicos avançados em lógica, enquanto você só precisa conhecer uma lógica muito básica.

Dos livros 1,2,3, eu escolheria apenas um para servir como uma introdução geral à matemática e às provas.

Os livros 5,7,8,9,10,13 abrangem vários assuntos: teoria dos autômatos, algoritmos e teoria da complexidade. Deixe-me sugerir que você siga Sipser (Livro 7) para teoria dos autômatos e teoria da complexidade e Introdução aos algoritmos de Cormen, Leiserson, Rivest e Stein ("CLRS") para algoritmos.

O livro 4 trata da programação funcional. Embora minha formação em ciência da computação nunca tenha incluído nenhum curso sobre esse assunto, é justo dizer que muitos pesquisadores em ciência da computação teórica consideram a programação funcional como parte dos fundamentos essenciais.

Resumindo: você permanece com

  • Um dos livros 1-3 (ou qualquer texto "introdução à prova" comparável)
  • CLRS
  • Livro 4 (programação funcional)
  • Livro 7 (teoria dos autômatos e teoria da complexidade)
Yuval Filmus
fonte
Muito obrigado por uma resposta tão completa. Eu sabia que a lista era excessiva, mas lendo todos os tipos de recomendações de livros para cientistas da computação, você acaba com uma longa lista. Sua recomendação é muito prática, e é isso que eu estou buscando. Muito obrigado !!
precisa
1
Discordo do conselho de que "a matemática não é necessária". Escolha qualquer aspecto da ciência da computação e eu mostrarei como a matemática é necessária. Quanto mais você aprender matemática, melhor estará. Por outro lado, é quase impossível aprender matemática real por conta própria, sem ir à escola. Então você provavelmente está melhor se concentrando em ciência da computação, que é mais fácil de aprender.
Andrej Bauer
5

Você também pode aproveitar alguns dos muitos cursos on-line disponíveis. Por exemplo, tanto o Stanford quanto o MIT oferecem cursos on-line (gratuitos) de ciência da computação, e acho que existem muitos outros disponíveis também.

No que diz respeito aos livros, eu apóio a maioria das recomendações de Yuval, exceto que o CLRS é uma ótima referência, mas um pouco avassalador como livro introdutório, para apenas sentar e ler. Para uma primeira passagem na parte de algoritmos, eu poderia recomendar Algoritmos de Dasgupta et al. . O link anterior é para a pré-impressão on-line gratuita, mas também é muito barato comprar em brochura.

Joe
fonte
Está bem. Agradeço sua resposta. Muito obrigado.
precisa
2

As referências que você está sugerindo tornariam um cientista da computação "muito" teórico. mas sinceramente não encontro nenhum benefício em ler todos esses livros, se você não é formado em ciências da computação. É claro que tudo depende do que você precisa.

Acho que alguns livros, como os livros 14, 15, 16, 17, não são destinados a cientistas da computação. O livro 3 é detalhado. É apenas geral para qualquer aluno. Portanto, assumo que os livros 1 e 2 são iguais.

Para mim - estando na mesma situação que não era originalmente um cientista da computação (mas um engenheiro elétrico / de computação) - proponho duas direções iniciais:

  • design e análise de algoritmos (muitas pessoas sugerem a Introdução aos Algoritmos do CLRS . É uma ótima referência, mas eu realmente não sou fã dele e, inicialmente, foi uma aposta mais difícil de entender e, às vezes, muito detalhada. Sugiro que você siga seu índice e, a partir daí, verifique os cursos on-line para obter referências mais claras).

--- certifique-se de dominar uma linguagem de programação para IMPLEMENTAR os algoritmos e estruturas de dados que você aprende - portanto, sugiro a série de algoritmos, de Sedgewick (incrível!)

--- ADICIONADO: Eu também sugiro este livro: Algoritmos Combinatórios: Geração, Enumeração e Pesquisa por D. Kreher. Este é um livro muito legal. Fornecerá uma perspectiva diferente para muitos problemas nos algoritmos.

  • combinatória (especialmente teoria dos grafos), Um curso de combinatória de JH van Lint, RM Wilson , é bom. Existem muitas outras referências. Normalmente, qualquer livro combinatório conhecido é suficiente - tudo o que você obteria com referências adicionais da Internet. Eu pessoalmente gostei: peter j cameron combinatorics e Bondy e Murty Graph Theory.

  • uma aposta de probabilidade (sempre necessária). É impressionante que muitos campos da ciência não usem probabilidade. Mas acredite em mim, tudo que você precisa saber é o básico.

Então: Muitos pesquisadores que se autodenominam cientistas da computação teóricos se concentram tanto na teoria da computação (automota e outras). Existem alguns bons livros para isso (veja o post do Yuvul Filmus),

Aho e Ullman são bons (na verdade, todos os livros de Ullman são bons). Sinta-se à vontade com o design do compilador (consulte http://infolab.stanford.edu/~ullman/ullman-books.html ).

Depois disso: tudo depende do que você deseja fazer. Diferentes direções que você pode seguir: 1) bancos de dados, 2) reconhecimento de padrões e mineração de dados, 3) algoritmos distribuídos, 4) bases de linguagens de programação, 4) algoritmos aleatórios e muitos outros. [cada uma delas requer outra publicação], mas tente ter uma idéia sobre tudo!

* A idéia geral: se você é novo no CS, sinta-se à vontade com o maior número possível de subdomínios do CS. Restringir-se à "teoria" fará com que você perca muito da criatividade em CS! * (minha opinião)

AJed
fonte
Para mim programação funcional. Não use um livro legado como o que você citou. Atualmente, os idiomas funcionais são necessários no setor. Existem alguns tutoriais na Internet sobre idiomas como Scheme, Haskel e Erlang. Não fique muito teórico, este é o meu conselho.
AJed
Todos os bons comentários. Meu objetivo é criar um programa completo de auto-estudo e essa pergunta lida apenas com uma seção do programa, que eu achei que era a mais desafiadora de organizar. Outras áreas incluem: estruturas de dados e algoritmos, arquitetura de computadores, sistemas operacionais, redes, segurança e criptografia, paralelismo, métodos formais, inteligência artificial, gráficos e simulação, bancos de dados, linguagens de programação, compiladores, engenharia de software e, finalmente, filosofia e administração do Unix. A maioria destes eu acho que são bastante fundamental para CS, mas teria mandado uma questão separada
CSLover
Seu melhor truque é uma base sólida no design e análise de algoritmos. - todos os outros campos são um subcampo de design e análise de algoritmos.
AJed
Você gostaria de esclarecer quais algoritmos de Sedgewick recomendam? Ele tem um chamado "Algoritmos", mas não é uma série. Ele também tem "Algoritmos em C ++" (ou outras línguas), que são 2 livros que acredito, com um total de 5 partes.
CSLover
O que eu usei foram os C ++. Eu os usei como referência, no entanto. Este é o site dele cs.princeton.edu/~rs
AJed