Lista de publicações importantes em ciência da computação teórica - List of important publications in theoretical computer science

Esta é uma lista de publicações importantes em ciência da computação teórica , organizada por área.

Alguns motivos pelos quais uma determinada publicação pode ser considerada importante:

  • Criador do tópico - uma publicação que criou um novo tópico
  • Breakthrough - Uma publicação que mudou o conhecimento científico significativamente
  • Influência - Publicação que influenciou significativamente o mundo ou teve um impacto massivo no ensino da ciência da computação teórica.

Computabilidade

Computabilidade de Cutland : Uma Introdução à Teoria da Função Recursiva (Cambridge)

  • Cutland, Nigel J. (1980). Computabilidade: Uma Introdução à Teoria da Função Recursiva . Cambridge University Press . ISBN 978-0-521-29465-2.

A revisão deste texto inicial por Carl Smith da Purdue University (na Society for Industrial and Applied Mathematics Reviews ), relata que este é um texto com uma "mistura apropriada de intuição e rigor ... na exposição de provas" que apresenta "o fundamento resultados da teoria clássica da recursão [RT] ... em um estilo ... acessível a alunos de graduação com formação matemática mínima ". Enquanto ele afirma que "seria um excelente texto introdutório para um curso introdutório em [RT] para alunos de matemática", ele sugere que um "instrutor deve estar preparado para aumentar substancialmente o material ..." quando for usado com alunos de ciência da computação ( dada a escassez de material sobre aplicações RT para esta área).

Decidibilidade de teorias de segunda ordem e autômatos em árvores infinitas

Descrição: O artigo apresentou o autômato de árvore , uma extensão do autômato . O autômato de árvore teve inúmeras aplicações para provas de correção de programas .

Autômatos finitos e seus problemas de decisão

Descrição: Tratamento matemático de autómatos , prova das propriedades do núcleo e definição de autómato finito não determinístico .

Introdução à teoria, linguagens e computação dos autômatos

Descrição: um livro popular.

Em certas propriedades formais de gramáticas

Descrição: Este artigo apresentou o que agora é conhecido como hierarquia de Chomsky , uma hierarquia de contenção de classes de gramáticas formais que geram linguagens formais .

Em números computáveis, com um aplicativo para o Entscheidungsproblem

Descrição: Este artigo define os limites da ciência da computação. Ele definiu a Máquina de Turing , um modelo para todos os cálculos. Por outro lado, ele provou a indecidibilidade do problema da parada e Entscheidungsproblem e, ao fazer isso, encontrou os limites de computação possível.

Rekursive Funktionen

O primeiro livro sobre a teoria das funções recursivas . O livro teve várias edições e rendeu a Péter o Prêmio Kossuth do governo húngaro . As resenhas de Raphael M. Robinson e Stephen Kleene elogiaram o livro por fornecer uma introdução elementar eficaz para os alunos.

Representação de eventos em redes nervosas e autômatos finitos

Descrição: este artigo introduziu autômatos finitos , expressões regulares e linguagens regulares , e estabeleceu sua conexão.

Teoria da complexidade computacional

Arora & Barak's Computational Complexity e Goldreich's Computational Complexity (ambos Cambridge)

  • Sanjeev Arora e Boaz Barak, "Computational Complexity: A Modern Approach," Cambridge University Press, 2009, 579 páginas, capa dura
  • Oded Goldreich, "Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, 606 páginas, capa dura

Além da estimável imprensa trazendo esses textos recentes, eles são avaliados de forma muito positiva no SIGACT News da ACM por Daniel Apon da Universidade de Arkansas, que os identifica como "livros didáticos para um curso de teoria da complexidade, voltado para a graduação precoce ... ou ... alunos de graduação avançados ... [com] numerosos e únicos pontos fortes e muito poucos pontos fracos ", e afirma que ambos são:

"excelentes textos que cobrem completamente a amplitude e profundidade da teoria da complexidade computacional ... [por] autores ... cada um [que] são gigantes na teoria da computação [onde cada um será] ... um texto de referência excepcional para especialistas no campo ... [e que] ... teóricos, pesquisadores e instrutores de qualquer escola de pensamento acharão qualquer um dos livros útil. "

O revisor observa que há "uma tentativa definitiva em [Arora e Barak] de incluir material muito atualizado, enquanto Goldreich se concentra mais no desenvolvimento de uma base contextual e histórica para cada conceito apresentado", e que ele "aplaude [s ] a todos os ... autores por suas contribuições notáveis. "

Uma teoria independente da máquina da complexidade das funções recursivas

Descrição: Os axiomas de Blum .

Métodos algébricos para sistemas de prova interativos

Descrição: Este artigo mostrou que o PH está contido no IP .

A complexidade dos procedimentos de prova de teoremas

Descrição: Este artigo introduziu o conceito de NP-Completude e provou que o problema de satisfatibilidade Booleana (SAT) é NP-Completo . Observe que ideias semelhantes foram desenvolvidas de forma independente um pouco mais tarde por Leonid Levin em "Levin, Universal Search Problems. Problemy Peredachi Informatsii 9 (3): 265–266, 1973".

Computadores e intratabilidade: um guia para a teoria da NP-completude

Descrição: A principal importância deste livro é devido à sua extensa lista de mais de 300 problemas NP-Completos . Essa lista se tornou uma referência e definição comum. Embora o livro tenha sido publicado apenas alguns anos depois que o conceito foi definido, uma lista tão extensa foi encontrada.

Grau de dificuldade de calcular uma função e uma ordenação parcial de conjuntos recursivos

Descrição: Este relatório técnico foi a primeira publicação falando sobre o que mais tarde foi renomeado para complexidade computacional

Quão bom é o método simplex?

  • Victor Klee e George J. Minty
  • Klee, Victor ; Minty, George J. (1972). "Quão bom é o algoritmo simplex?". Em Shisha, Oved (ed.). Desigualdades III (Anais do Terceiro Simpósio sobre Desigualdades realizado na Universidade da Califórnia, Los Angeles, Califórnia, 1 a 9 de setembro de 1969, dedicado à memória de Theodore S. Motzkin) . New York-London: Academic Press. pp. 159–175. MR  0332165 .

Descrição: Construído a "Klee-Minty cubo" na dimensão  D , cujo 2 D cantos são cada visitado por Dantzig 's algoritmo simplex para otimização linear .

Como construir funções aleatórias

Descrição: Este artigo mostrou que a existência de funções de mão única leva à aleatoriedade computacional .

IP = PSPACE

Descrição: IP é uma classe de complexidade cuja caracterização (baseada em sistemas de prova interativa ) é bastante diferente das classes computacionais limitadas de tempo / espaço usuais. Neste artigo, Shamir estendeu a técnica do artigo anterior de Lund, et al., Para mostrar que PSPACE está contido em IP e, portanto, IP = PSPACE, de modo que cada problema em uma classe de complexidade pode ser resolvido na outra.

Redutibilidade entre problemas combinatórios

  • RM Karp
  • Em RE Miller e JW Thatcher, editores, Complexity of Computer Computations , Plenum Press, New York, NY, 1972, pp. 85-103

Descrição: Este artigo mostrou que 21 problemas diferentes são NP-Completos e mostrou a importância do conceito.

A complexidade do conhecimento dos sistemas de prova interativos

Descrição: Este artigo introduziu o conceito de conhecimento zero .

Uma carta de Gödel para von Neumann

Descrição: Gödel discute a ideia de provador de teoremas universal eficiente.

Sobre a complexidade computacional dos algoritmos

Descrição: Este artigo deu à complexidade computacional seu nome e sua semente.

Caminhos, árvores e flores

Descrição: Existe um algoritmo de tempo polinomial para encontrar uma correspondência máxima em um grafo que não é bipartido e mais um passo em direção à ideia de complexidade computacional . Para obter mais informações, consulte [2] .

Teoria e aplicações de funções de alçapão

Descrição: Este artigo cria uma estrutura teórica para funções de alçapão e descreve algumas de suas aplicações, como em criptografia . Observe que o conceito de funções de alçapão foi trazido para "Novas direções na criptografia" seis anos antes (consulte a seção V "Problemas de relacionamento e portas de armadilha.").

Complexidade computacional

Descrição: uma introdução à teoria da complexidade computacional , o livro explica a caracterização de seu autor de P-SPACE e outros resultados.

Provas interativas e a dureza de cliques aproximados

Verificação probabilística de provas: uma nova caracterização de NP

Verificação de prova e a dureza dos problemas de aproximação

Descrição: Esses três artigos estabeleceram o fato surpreendente de que certos problemas em NP permanecem difíceis mesmo quando apenas uma solução aproximada é necessária. Veja o teorema PCP .

A dificuldade computacional intrínseca de funções

Descrição: Primeira definição da classe de complexidade P. Um dos documentos fundadores da teoria da complexidade.

Algoritmos

"Um programa de máquina para prova de teoremas"

Descrição: o algoritmo DPLL . O algoritmo básico para SAT e outros problemas NP-Completos .

"Uma lógica orientada à máquina baseada no princípio de resolução"

Descrição: Primeira descrição da resolução e unificação usada na prova automatizada de teoremas ; usado em Prolog e programação lógica .

"O problema do caixeiro viajante e as árvores geradoras mínimas"

Descrição: O uso de um algoritmo de spanning tree mínimo como um algoritmo de aproximação para o problema do caixeiro viajante NP-Complete . Os algoritmos de aproximação tornaram-se um método comum para lidar com problemas NP-Completos.

"Um algoritmo polinomial em programação linear"

Descrição: Por muito tempo, não houve um algoritmo de tempo polinomial comprovado para o problema de programação linear . Khachiyan foi o primeiro a fornecer um algoritmo polinomial (e não apenas rápido o suficiente na maioria das vezes como os algoritmos anteriores). Mais tarde, Narendra Karmarkar apresentou um algoritmo mais rápido em: Narendra Karmarkar, "Um novo algoritmo de tempo polinomial para programação linear", Combinatorica , vol 4, no. 4, pág. 373–395, 1984.

"Algoritmo probabilístico para testar a primalidade"

Descrição: O artigo apresentou o teste de primalidade de Miller-Rabin e delineou o programa de algoritmos randomizados .

"Otimização por recozimento simulado"

Descrição: Este artigo descreveu o recozimento simulado , que agora é uma heurística muito comum para problemas NP-Completos .

A Arte da Programação de Computador

Descrição: esta monografia possui quatro volumes que abrangem algoritmos populares. Os algoritmos são escritos em inglês e em linguagem assembly MIX (ou linguagem assembly MMIX em fascículos mais recentes). Isso torna os algoritmos compreensíveis e precisos. No entanto, o uso de uma linguagem de programação de baixo nível frustra alguns programadores mais familiarizados com as linguagens de programação estruturadas modernas .

Algoritmos + Estruturas de Dados = Programas

Descrição: Um livro antigo e influente sobre algoritmos e estruturas de dados, com implementações em Pascal.

O Projeto e Análise de Algoritmos de Computador

Descrição: um dos textos padrão sobre algoritmos para o período de aproximadamente 1975–1985.

Como resolver por computador

Descrição: Explica a Porque s de algoritmos e de dados-estruturas. Explica o processo criativo , a linha de raciocínio , os fatores de design por trás de soluções inovadoras.

Algoritmos

Descrição: um texto muito popular sobre algoritmos no final dos anos 1980. Era mais acessível e legível (mas mais elementar) do que Aho, Hopcroft e Ullman. Existem edições mais recentes.

Introdução aos Algoritmos

Descrição: Este livro tornou-se tão popular que é quase o padrão de fato para o ensino de algoritmos básicos. A 1ª edição (com os três primeiros autores) foi publicada em 1990, a 2ª edição em 2001 e a 3ª em 2009.

Teoria da Informação Algorítmica

"Em tabelas de números aleatórios"

Descrição: Proposta de abordagem computacional e combinatória para probabilidade.

"Uma teoria formal de inferência indutiva"

Descrição: Este foi o início da teoria da informação algorítmica e da complexidade de Kolmogorov . Observe que embora a complexidade de Kolmogorov tenha o nome de Andrey Kolmogorov , ele disse que as sementes dessa ideia se devem a Ray Solomonoff . Andrey Kolmogorov contribuiu muito para essa área, mas em artigos posteriores.

"Teoria da informação algorítmica"

Descrição: Uma introdução à teoria da informação algorítmica por uma das pessoas importantes na área.

Teoria da informação

"Uma teoria matemática de comunicação"

Descrição: Este artigo criou o campo da teoria da informação .

"Códigos de detecção e correção de erros"

Descrição: Neste artigo, Hamming introduziu a ideia de código de correção de erros . Ele criou o código de Hamming e a distância de Hamming e desenvolveu métodos para provas de otimização de código.

"Um método para a construção de códigos de redundância mínima"

Descrição: A codificação de Huffman .

"Um algoritmo universal para compressão de dados sequencial"

Descrição: o algoritmo de compressão LZ77 .

Elementos da Teoria da Informação

Descrição: Uma introdução popular à teoria da informação.

Verificação formal

Atribuindo Significado aos Programas

Descrição: O artigo de referência de Robert Floyd Assigning Meanings to Programs introduz o método de asserções indutivas e descreve como um programa anotado com asserções de primeira ordem pode ser mostrado para satisfazer uma especificação de pré e pós-condição - o artigo também introduz os conceitos de invariante de loop e condição de verificação.

Uma base axiomática para a programação de computador

Descrição: O artigo de Tony Hoare, Uma Base Axiomática para Programação de Computadores, descreve um conjunto de regras de inferência (isto é, prova formal) para fragmentos de uma linguagem de programação semelhante a Algol descrita em termos de (o que agora é chamado de) triplas Hoare.

Comandos protegidos, não determinação e derivação formal de programas

Descrição: O artigo de Edsger Dijkstra Guarded Commands, Nondeterminacy and Formal Derivation of Programs (expandido por seu livro de nível de pós-graduação de 1976 A Discipline of Programming) propõe que, em vez de verificar formalmente um programa depois de ter sido escrito (ou seja, post facto), programas e suas provas formais devem ser desenvolvidas lado a lado (usando transformadores de predicado para refinar progressivamente as pré-condições mais fracas), um método conhecido como refinamento (ou derivação) de programa (ou formal) ou, às vezes, "correção por construção".

Provando afirmações sobre programas paralelos

Descrição: O artigo que introduziu provas de invariância de programas concorrentes.

Uma técnica de prova axiomática para programas paralelos I

Descrição: Neste artigo, junto com o artigo do mesmo autor "Verificando Propriedades de Programas Paralelos: Uma Abordagem Axiomática. Commun. ACM 19 (5): 279–285 (1976)", a abordagem axiomática para verificação de programas paralelos foi apresentada.

Uma Disciplina de Programação

Descrição: O clássico livro de nível de pós-graduação de Edsger Dijkstra, A Discipline of Programming, estende seu artigo anterior Guarded Commands, Nondeterminacy and Formal Derivation of Programs e estabelece firmemente o princípio de programas formalmente derivados (e suas provas) de suas especificações.

Semântica Denotacional

Descrição: A Semântica Denotacional de Joe Stoy é a primeira exposição em livro (nível de pós-graduação) da abordagem matemática (ou funcional) da semântica formal das linguagens de programação (em contraste com as abordagens operacional e algébrica).

A lógica temporal de programas

Descrição: O uso da lógica temporal foi sugerido como um método para verificação formal.

Caracterizando propriedades de correção de programas paralelos usando pontos fixos (1980)

Descrição: a verificação de modelo foi introduzida como um procedimento para verificar a exatidão de programas concorrentes.

Communicating Sequential Processes (1978)

Descrição: O artigo (original) de Tony Hoare com processos sequenciais de comunicação (CSP) apresenta a ideia de processos concorrentes (ou seja, programas) que não compartilham variáveis, mas cooperam apenas trocando mensagens síncronas.

Um cálculo de sistemas de comunicação

Descrição: O artigo A Calculus of Communicating Systems (CCS) de Robin Milner descreve uma álgebra de processo que permite que sistemas de processos concorrentes sejam raciocinados formalmente, algo que não era possível para modelos anteriores de simultaneidade (semáforos, seções críticas, CSP original).

Desenvolvimento de software: uma abordagem rigorosa

Descrição: O livro de Cliff Jones Software Development: A Rigorous Approach é a primeira exposição completa do Método de Desenvolvimento de Viena (VDM), que evoluiu (principalmente) no laboratório de pesquisa da IBM em Viena na década anterior e que combina a ideia de programa refinamento como por Dijkstra com aquele de refinamento de dados (ou reificação) por meio do qual tipos de dados abstratos definidos algebricamente são formalmente transformados em representações progressivamente mais "concretas".

A Ciência da Programação

Descrição: O livro de David Gries, The Science of Programming, descreve o método de pré-condição mais fraco de Dijkstra para derivação de programa formal, exceto de uma maneira muito mais acessível do que o anterior A Discipline of Programming de Dijkstra .

Mostra como construir programas que funcionam corretamente (sem bugs, a não ser por erros de digitação). Ele faz isso mostrando como usar expressões de predicado de pré-condição e pós-condição e técnicas de teste de programa para guiar a maneira como os programas são criados.

Os exemplos no livro são todos em pequena escala e claramente acadêmicos (em oposição ao mundo real). Eles enfatizam algoritmos básicos, como classificação e mesclagem e manipulação de strings. As sub-rotinas (funções) estão incluídas, mas os ambientes de programação orientada a objetos e funcionais não são abordados.

Communicating Sequential Processes (1985)

Descrição: O livro de Tony Hoare Communicating Sequential Processes (CSP) (atualmente a terceira referência de ciência da computação mais citada de todos os tempos) apresenta um modelo CSP atualizado no qual os processos de cooperação nem mesmo têm variáveis ​​de programa e que, como o CCS, permite que sistemas de processos ser fundamentado formalmente.

Lógica linear (1987)

Descrição: a lógica linear de Girard foi uma inovação no projeto de sistemas de tipagem para computação sequencial e simultânea, especialmente para sistemas de digitação com recursos conscientes.

A Calculus of Mobile Processes (1989)

Descrição: Este artigo apresenta o Pi-Calculus , uma generalização do CCS que permite a mobilidade do processo. O cálculo é extremamente simples e se tornou o paradigma dominante no estudo teórico de linguagens de programação, sistemas de digitação e lógicas de programa.

A notação Z: um manual de referência

Descrição: O livro clássico de Mike Spivey, The Z Notation: A Reference Manual, resume a notação Z da linguagem de especificação formal , que, embora originada por Jean-Raymond Abrial, evoluiu (principalmente) na Universidade de Oxford na década anterior.

Comunicação e Simultaneidade

Descrição: O livro de Robin Milner Communication and Concurrency é uma exposição mais acessível, embora ainda tecnicamente avançada, de seu trabalho anterior de CCS.

uma Teoria Prática da Programação

Descrição: a versão atualizada da programação Predicativa . A base para o UTP de CAR Hoare . Os métodos formais mais simples e abrangentes.

Referências

  • Grupo de interesse especial da ACM em Algoritmos e Teoria da Computação (2011). "Prêmios: Prêmio Gödel" . Arquivado do original em 22 de abril de 2018 . Página visitada em 8 de outubro de 2011 .