Atualmente, sou estudante de graduação, que deve se formar este ano. Após a formatura, estou pensando em trabalhar para um mestrado / doutorado em TCS. Comecei a me perguntar que campos da matemática são considerados úteis para o TCS, especialmente a teoria da complexidade (clássica).
Quais campos você considera essenciais para alguém que deseja estudar a teoria da complexidade? Você conhece algum bom livro didático que cubra esses campos e, em caso afirmativo, inclua o nível de dificuldade (introdutório, de pós-graduação etc.).
Se você considerar um campo que não é muito usado na teoria da complexidade, mas o considera crítico para o TCS, consulte-o também.
Respostas:
Se você olhar as respostas para esta pergunta do TCS StackExchange , verá que existe a possibilidade de praticamente qualquer área da matemática ser importante na teoria da complexidade. Portanto, se você está realmente interessado em alguma área da matemática que não parece relacionada, vá em frente e estude-a assim mesmo. Se alguma vez se tornar relevante para a teoria da complexidade, você será um dos poucos teóricos da complexidade que a entenderá.
fonte
Você deve adicionar o livro de Dexter Kozen sobre a teoria da computação à sua lista. Abrange os conceitos básicos da teoria da complexidade de maneira muito eficaz, e o formato de palestra curta é ótimo.
Em termos de formação matemática, além do mencionado acima:
Não acho que você precise dominar esses tópicos para começar, mas definitivamente ajuda a ter um certo nível de conforto.
fonte
É (que eu saiba) o único livro publicado que trata o 'método da álgebra linear em combinatória' em profundidade - uma ferramenta inteligente e poderosa para se conhecer. Há um rascunho de manuscrito de Babai e Frankl que é muito mais aprofundado, mas não publicado ou on-line:
https://cs.uchicago.edu/page/linear-algebra-methods-combinatorics-applications-geometry-and-computer-science
fonte
As respostas anteriores já listavam as básicas: teoria das probabilidades, combinatória, álgebra linear, álgebra abstrata (campos finitos, teoria de grupos, etc.).
Eu adicionaria:
Análise de Fourier , veja, por exemplo, o curso de Ryan O'Donnel: http://www.cs.cmu.edu/~odonnell/boolean-analysis/
Teoria da codificação , veja o curso de Madhu Sudão: http://people.csail.mit.edu/madhu/coding/course.html
Teoria da informação , o livro padrão é Elements of Information Theory: http://www.amazon.com/Elements-Information-Theory-Telecommunications-Processing/dp/0471241954
Também há teoria das representações, passeios aleatórios e muito mais que eu provavelmente esqueço ...
fonte
Além das coisas básicas, provavelmente:
Eu gosto de matemática concreta por Knuth. Ele fornece uma boa visão geral / conhecimento básico de muitas ferramentas importantes.
Se você gosta de geração de funções (ver generationfunctionology por Wilf) como uma ferramenta, análise complexa vem a calhar também.
fonte
Sanjeev Arora tem um bom documento para um curso de graduação (para alunos do primeiro ano do ensino médio) que ele ensinou chamado "kit de ferramentas do teórico", que possui grande parte do material básico que um aluno de teoria deve conhecer. Você pode esperar muitas dessas coisas até a escola para aprender, mas isso lhe dará uma boa idéia do que você precisa saber e de alguns dos pré-requisitos.
fonte
Um paradigma comum, embora certamente não universal, para muitos pesquisadores bem-sucedidos na comunidade do TCS é o seguinte: Conheça algumas noções básicas de graduação, como lógica, álgebra linear, probabilidade, otimização, teoria de grafos, combinatória e álgebra abstrata básica. Além disso, não se force a aprender mais nada até que você realmente pense que precisa resolver o problema com o qual está lutando há meses, ou se você acha que realmente gostaria de aprender algo por causa disso.
"Como sei que preciso se nunca o vi antes?", Você pergunta? Boa pergunta. Às vezes, você tem sorte e sente: "Sabe, este sub-problema que estou tentando resolver soa muito parecido com aquela coisa de transformação de quatro quarteirões que Fred não cala a boca. Vou ter que verificar isso ou prender Fred em uma sala e peça para ele me dar uma rápida olhada no básico ". Outras vezes, você prende um grupo de pessoas mais instruídas do que você em uma sala, por exemplo, dando uma palestra em um seminário ou algo assim, e se queixa de como não pode resolver esse problema até que Fred grite com "Ei, aposto que você pode resolver isso com a análise de Fourier. Deixe-me mostrar como. " No final, você recebe um documento conjunto com Fred, aprendeu algo novo, e você e Fred são melhores amigos agora e saem para beber todos os sábados à noite.
fonte
Eu acho que uma lista de campos de matemática que não são úteis seria muito menor do que uma lista de campos que são! Não consigo pensar em nada.
Estude qualquer matemática que pareça interessante e / ou o que parecer que você precisa no momento. Mesmo que você não o use diretamente, isso ajudará você a aprender outras coisas que você faz.
fonte
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
fonte
Eu recomendo dar uma olhada nestes livros:
Além disso, os tópicos da conferência MFCS (Mathematics Foundations of Computer Science) podem levar você a que tipo de histórico você pode precisar. (Advertência: a conferência inclui tópicos altamente avançados. Você não precisa dominá-los. Apenas tente entender tudo.)
fonte
A teoria dos números não foi mencionada, mas é uma ferramenta muito importante para muitas construções criptográficas e teóricas da complexidade.
fonte
A teoria da representação de grupos finitos (também sobre campos finitos) pode ser surpreendentemente útil para várias tarefas, incluindo:
algoritmos de multiplicação de matrizes ( Cohn - Kleinberg-Szegedy-Umans )
construção de códigos decodificáveis localmente (veja, por exemplo, este artigo de Klim Efremenko)
aplicações em computação quântica (problema de subgrupo oculto para grupos não-belianos, método multiplicativo de adversários)
fonte
Eu recomendo a leitura do livro de Garey e Johnson
Computadores e Intratabilidade: Um Guia para a Teoria da Completude NP .
Isso pode ser lido com muito pouco conhecimento matemático. Acho que este livro é uma alegria de ler, e eu o recomendaria como primeiro livro sobre Papadimitriou e Arora / Barak. Depois de ler isso, você poderá se aprofundar nos outros livros e identificar vários pedaços de matemática necessários para entender os tópicos avançados nos quais está interessado.
fonte
Era uma vez o curso de graduação CS464 (2002) na UWaterloo CS, que usava a complexidade computacional de Christos H. Papadimitriou , Addison-Wesley, 1994.
Os tópicos de segundo plano listados incluem máquinas de Turing, indecidibilidade, complexidade de tempo e integridade do NP.
Como pano de fundo, navegue pela sua biblioteca perto de QA267.G57 (A introdução da teoria da computação de Goddard , com base em uma leitura rápida ou duas e sua disponibilidade para mim, parece cobrir o lado CS do plano de fundo; tenho a sensação de que algum conjunto e grupo a teoria do lado da matemática pura também seria útil.)
fonte