Ciência da Computação Teórica

Desde o livro de Chris Okasaki, de 1998, "Estruturas de dados puramente funcionais", não vi muitas novas estruturas de dados puramente funcionais interessantes; Eu posso citar apenas alguns: IntMap (também inventado por Okasaki em 1998, mas não presente nesse livro) Dedo árvores (e sua...

Esta pergunta é (inspirada por) / (vergonhosamente roubada) uma pergunta semelhante no MathOverflow , mas espero que as respostas aqui sejam bem diferentes. Todos nós temos artigos favoritos em nossas próprias áreas de teoria. De vez em quando, encontramos um artigo tão surpreendente (por exemplo,...

Paul Erdos falou sobre o "Livro", onde Deus guarda a prova mais elegante de cada teorema matemático. Isso até inspirou um livro (que eu acredito que está agora em sua 4ª edição): Provas do livro . Se Deus tivesse um livro semelhante para algoritmos, quais algoritmos você acha que seriam...

Para demonstrar a importância dos algoritmos (por exemplo, para estudantes e professores que não fazem teoria ou são de campos totalmente diferentes), às vezes é útil ter à mão uma lista de exemplos em que os algoritmos principais foram implantados em setores comerciais, governamentais, ou software...

Estive revisando a Teoria da Computação por diversão e essa pergunta me incomoda há um tempo (engraçado nunca pensei nisso quando aprendi a Teoria dos Autômatos na minha graduação). Então, "por que" exatamente estudamos autômatos finitos determinísticos e não determinísticos (DFA / NFAs)? Então,...

Norbert Blum postou recentemente uma prova de 38 páginas de que . Está correto?P≠ NPP≠NPP \ne NP Também no tópico: onde mais (na internet) sua correção está sendo discutida? Nota: o foco deste texto da pergunta mudou com o tempo. Veja os comentários da pergunta para obter...

[ 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...

A Wikipedia lista apenas dois problemas em "problemas não resolvidos em ciência da computação" : P = NP? A existência de funções unidirecionais Quais são outros problemas importantes que devem ser adicionados a esta lista? Regras: Apenas um problema por resposta Forneça uma breve descrição e...

Suponha que Mario esteja andando na superfície de um planeta. Se ele começar a andar de um local conhecido, em uma direção fixa, por uma distância predeterminada, com que rapidez podemos determinar onde ele irá parar? Mais formalmente, suponha que recebamos um pólipo convexo no espaço 3, um...

A Universidade de Stanford agora tem um canal no Youtube , com acesso gratuito a vídeos em HD de cursos completos sobre tudo, desde sistemas dinâmicos a entrelaçamento quântico. Mais conferências e workshops estão filmando suas palestras. Quais são os vídeos on-line que você acha que todos deveriam...

Factoring e isomorfismo gráfico são problemas em NP que não são conhecidos por estar em P nem por NP-Complete. Quais são alguns outros problemas naturais (suficientemente diferentes) que compartilham essa propriedade? Exemplos artificiais provenientes diretamente da prova do teorema de Ladner não...

Depois de ler a pergunta de Daniel Apon , comecei a pensar que poderia ser útil (especialmente para pesquisadores juniores e estudantes de pós-graduação como eu) fazer uma pergunta mais ampla e geral para que possamos aprender com a experiência de pesquisadores mais experientes. Então aqui está a...

Um embaralhamento de duas strings é formado pela intercalação dos caracteres em uma nova string, mantendo os caracteres de cada string em ordem. Por exemplo, MISSISSIPPIé um embaralhamento de MISIPPe SSISI. Deixe-me chamar um quadrado de cadeia de caracteres, se for uma mistura de duas cadeias...

Houve várias perguntas com o mesmo esquema que este: Que papéis todos deveriam ler Que livros todos deveriam ler Quais são os livros recentes do TCS cujos rascunhos estão disponíveis on-line quais vídeos todos deveriam assistir Eu relutava em postar mais uma, mas as anotações de Jeff Erickson...

A ciência da computação teórica forneceu alguns exemplos do "preço da abstração". Os dois mais proeminentes são para eliminação e classificação gaussiana. Nomeadamente: Sabe-se que a eliminação gaussiana é ideal para, digamos, calcular o determinante se você restringir as operações a linhas e...

Eu tenho aprendido alguns pedaços da teoria das categorias. Certamente é uma maneira diferente de ver as coisas. (Resumo muito rudimentar para quem ainda não a viu: a teoria das categorias fornece maneiras de expressar todos os tipos de comportamentos matemáticos apenas em termos de relações...

Após o post Que livros todos deveriam ler , notei que existem livros recentes cujos rascunhos estão disponíveis online. Por exemplo, a entrada Algoritmos de aproximação do post acima cita um livro de 2011 (ainda a ser publicado) intitulado O design de algoritmos de aproximação . Eu acho que...

Muitos algoritmos de busca de caminhos foram desenvolvidos nos últimos anos, que podem calcular o melhor caminho em resposta a alterações de gráficos muito mais rapidamente que A * - o que são e como diferem? Eles são para situações diferentes, ou alguns outros obsoletos? Estes são os que...

Estou me preparando para uma palestra voltada para alunos de graduação em matemática e, como parte disso, estou pensando em discutir o conceito de decidibilidade. Quero dar um exemplo de um problema que atualmente não sabemos ser decidível ou indecidível. Existem muitos desses problemas, mas nenhum...

Gostaria de pedir ajuda para compilar uma lista do maior número possível de conferências e workshops relacionados ao TCS. Minha principal motivação para fazer isso é planejar uma possível cobertura do blog de mais espaços teóricos - encontrar correspondentes que participem desses eventos e que...