Os artigos mais influentes da história da ciência da computação

 (terriblesoftware.org)
6 pontos por GN⁺ 2025-01-24 | 1 comentários | Compartilhar no WhatsApp
  • De 1936 a 1998, 7 artigos de ciência da computação formaram camadas centrais da computação moderna: computabilidade, teoria da informação, bancos de dados, complexidade, internet, web e busca
  • O artigo de 1936 de Alan Turing marcou o ponto de partida do modelo moderno de computação ao distinguir, com a Máquina de Turing, o que as máquinas podem e não podem calcular em princípio
  • Claude Shannon, Edgar F. Codd e Stephen A. Cook criaram, respectivamente, uma linguagem comum para comunicação, dados e dificuldade de problemas por meio da medição da informação e correção de erros, do modelo relacional de dados e da NP-completude com SAT
  • Os artigos de Vinton G. Cerf e Robert E. Kahn, Tim Berners-Lee, Sergey Brin e Larry Page definiram a estrutura da conexão entre redes, da conexão entre documentos e da busca na web com TCP/IP, World Wide Web e PageRank
  • Observando também a lista bônus com Lisp, programação estruturada, relógios lógicos, complexidade de software e Transformer, entender conceitos fundamentais continua sendo uma vantagem mais duradoura do que apenas aprender novas ferramentas

Critérios de seleção e fluxo geral

  • A lista não é um ranking absoluto, mas uma seleção subjetiva feita com base no impacto no mundo atual
  • Os 7 artigos estão em ordem cronológica e mostram um fluxo que vai de computação, comunicação, armazenamento de dados e dificuldade computacional até redes, web e busca
  • Mesmo com o surgimento contínuo de novas linguagens, avanços em IA, saltos quânticos e frameworks JavaScript, os conceitos criados por esses artigos seguem na base da computação moderna

1. “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936)

2. “A Mathematical Theory of Communication” (1948)

3. “A Relational Model of Data for Large Shared Data Banks” (1970)

  • Edgar F. Codd propôs o modelo relacional para armazenar e consultar grandes volumes de dados
  • A ideia central é armazenar dados em tabelas e manipulá-los com operações lógicas
  • Esse projeto levou ao SQL e à família dos bancos de dados relacionais, sustentando bancos, sites de varejo e sistemas corporativos
  • Mesmo na era do NoSQL, conceitos de organização de dados como tabelas, schema e consistência continuam ligados ao modelo de Codd
  • Leia mais:

4. “The Complexity of Theorem-Proving Procedures” (1971)

5. “A Protocol for Packet Network Intercommunication” (1974)

  • O artigo de Vinton G. Cerf e Robert E. Kahn apresentou a base do TCP para conectar redes antes isoladas
  • Surgiu uma linguagem universal para que redes diferentes pudessem conversar, e os dados passaram a ser divididos em pequenos pacotes que seguem por vários caminhos e depois são remontados no destino
  • Graças a essa flexibilidade, tornou-se possível a conexão global sem a necessidade de uma única rede gigantesca
  • Atividades como navegar na web, enviar e-mails e fazer login em sites bancários dependem do TCP/IP para mover bits com confiabilidade
  • Embora algumas aplicações em tempo real usem UDP, a ideia central de rede baseada em IP proposta por Cerf e Kahn reúne dispositivos sob uma única rede global
  • Leia mais:

6. “Information Management: A Proposal” (1989)

  • Depois que as máquinas passaram a se comunicar com facilidade, Tim Berners-Lee propôs a direção da World Wide Web para que as pessoas também pudessem usar isso com mais facilidade
  • A ideia central era um sistema global de hipertexto com hyperlinks, URL e HTTP
  • Com documentos do mundo inteiro deixando de ficar isolados e passando a se conectar entre si, a internet assumiu uma forma que podia ser explorada não só por cientistas, mas também por usuários comuns
  • Sementes de experiências de uso da web como redes sociais, compras online e posts de blog lidos às 3 da manhã nasceram dessa proposta
  • Leia mais:

7. “The Anatomy of a Large-Scale Hypertextual Web Search Engine” (1998)

  • Sergey Brin e Larry Page criaram uma abordagem baseada em análise de links para lidar com a web em rápida expansão de links e páginas, e isso evoluiu para o mecanismo de busca do Google
  • A ideia central, o PageRank, trata links não como simples elementos de cálculo por palavra-chave, mas como votos de confiança
  • Essa abordagem melhorou muito a relevância dos resultados e transformou a web em um espaço pesquisável
  • A experiência de digitar uma pergunta no Google e obter uma resposta imediata se apoia no PageRank e em muitas inovações posteriores
  • O PageRank redefiniu a forma de navegar por informação online e abriu caminho para uma nova era de tecnologias baseadas em dados, como publicidade, análise e machine learning
  • Leia mais:

5 artigos que quase entraram no texto principal

  • “Recursive Functions of Symbolic Expressions and Their Computation by Machine” (1960) – John McCarthy
    • Introduziu Lisp e o estilo de programação funcional, que ainda permanece em linguagens e frameworks modernos
  • “Go To Statement Considered Harmful” (1968) – Edsger Dijkstra
    • Criticou o goto por gerar código confuso e não estruturado, desencadeando a revolução da programação estruturada
  • “Time, Clocks, and the Ordering of Events in a Distributed System” (1978) – Leslie Lamport
    • Em sistemas distribuídos, como não é possível sincronizar perfeitamente relógios reais, são necessários relógios lógicos
  • “No Silver Bullet—Essence and Accident in Software Engineering” (1986) – Fred Brooks
    • Defende que não existe um único método mágico capaz de resolver a complexidade essencial do desenvolvimento de software
  • “Attention Is All You Need” (2017) – Vaswani et al.
    • Apresenta a arquitetura Transformer que está por trás do GPT e de vários modelos famosos de IA

O impacto duradouro dos conceitos fundamentais

  • Hoje continuam surgindo sem parar novas linguagens, inovações em IA, saltos quânticos e frameworks JavaScript a cada semana
  • Sem entender de onde vieram conceitos centrais como estruturas de dados, algoritmos e a web, a tendência é apenas continuar acumulando novas ferramentas
  • Esses 7 artigos e os bônus ajudam a revisitar as ideias que se tornaram a base central da computação moderna

Leituras relacionadas

1 comentários

 
GN⁺ 2025-01-24
Opiniões no Hacker News

  • Communicating Sequential Processes (Hoare), The Next 700 Programming Languages (Landin), As We May Think (Bush) e Can Programming Be Liberated from the von Neumann Style (Backus) também mereceriam entrar
    E este curso também parece bom: https://canvas.harvard.edu/courses/34992/assignments/syllabu...
    “Este curso aborda artigos que todo cientista da computação deveria ter lido, dos anos 1930 até hoje. É uma experiência abrangente para ajudar alunos avançados de ciência da computação a terem uma visão geral de todo o campo; não é uma simples visão panorâmica, mas uma forma de reviver seu processo de criação. Ao reproduzir em ritmo acelerado toda a evolução da ciência da computação para estudantes que já têm algum conhecimento prévio, o objetivo é construir uma perspectiva integrada sobre a área”

    • Parece que é preciso ter uma conta de Harvard para ver o curso

  • Esta lista parece uma combinação meio estranha. Fica ambíguo se a ideia é escolher artigos que influenciaram a ciência da computação, ou seja, a teoria da computação, ou artigos que influenciaram a tecnologia, ou se estão simplesmente chamando de ciência da computação “tudo relacionado a computadores”
    O artigo de Turing é a base da ciência da computação, mas é questionável se a tecnologia teria se desenvolvido de forma diferente sem ele. A maioria dos engenheiros de software nunca o leu. Por outro lado, o padrão IP é uma pedra fundamental tecnológica, mas quase não tem conteúdo científico; está mais para uma especificação de protocolo relativamente simples que é preciso conhecer para trabalhar com coisas ao redor de redes

    • O artigo do PageRank lado a lado, numa lista curta, com as pesquisas fundamentais de Turing e Shannon sobre computabilidade e teoria da informação parece um pouco deslocado
      “On Computable Numbers, with an Application to the Entscheidungsproblem” já tem quase 90 anos, mas continua tão verdadeiro e válido hoje quanto na época. Não tenho tanta certeza se o PageRank é tão relevante hoje quanto era em 1998, muito menos se ainda será daqui a 50 anos

  • É uma boa lista de artigos. Li 5 dos 7 da lista; os que ainda não li são o artigo de Cerf e Kahn e o de Berners-Lee
    O artigo de computabilidade de Turing foi especialmente difícil de acompanhar, porque ele deu nomes em letras maiúsculas góticas a todo tipo de coisa, e essas letras todas pareciam muito parecidas. Só consegui ler o artigo com materiais auxiliares; hoje eu recomendaria lê-lo junto com o livro comentado de Charles Petzold https://www.amazon.com/Annotated-Turing-Through-Historic-Com...
    O artigo sobre NP-completude de Cook também foi difícil e, como o artigo de Turing, exigiu material auxiliar. Hoje eu recomendaria ler primeiro um livro introdutório de complexidade computacional que acompanhe a prova de Cook
    O artigo de Shannon parece uma obra de arte escrita de forma clara e bela, mas de maneira nenhuma é uma leitura leve
    Os artigos de Brin e Page e de Codd não me parecem, pela memória, ter sido muito difíceis, mas para entender o trabalho de Brin e Page é preciso algum conhecimento de álgebra linear

    • Não sei onde a álgebra linear é necessária no artigo de Brin e Page. A palavra “autovetor” aparece uma vez, mas é uma menção secundária
      O “algoritmo iterativo simples” é uma forma de encontrar o ponto fixo de uma contração arbitrária, seja ela linear ou não. O fato de isso também ser um autovetor é mais um atrapalho do que uma ajuda, e alguém que entende bem disso não usaria eliminação gaussiana
    • Se for possível conseguir o arquivo-fonte .tex, ajuda pedir ao GPT para deixar os nomes das variáveis mais legíveis, trocando-os por nomes com mais de uma letra

  • Se você acha que A Mathematical Theory of Communication, de Shannon, foi sua contribuição mais fundamental para a ciência da computação, é porque ainda não viu a dissertação de mestrado que ele escreveu 10 anos antes
    https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_a...
    Ele mostrou que era possível definir lógica booleana com elementos de chaveamento de circuitos, isto é, transistores
    Claro, isso não quer diminuir a importância de ele ter estabelecido as bases de toda a teoria da informação

  • A explicação de que ele “mostrou que, se algo é computável, em princípio uma máquina pode processá-lo, e delineou a ‘Turing Machine’ hipotética” não é o que Turing provou
    O que ele provou naquele artigo é que existem problemas que não podem ser resolvidos por uma Turing Machine e que, portanto, provavelmente não podem ser resolvidos por nenhuma máquina. O Entscheidungsproblem do título, isto é, o problema da decisão, é exatamente isso
    O que o texto original está apontando é a chamada Tese de Church-Turing, que é literalmente mais próxima de uma tese. Não dá para prová-la de fato, mas há motivos muito fortes para acreditar nela, já que em quase 100 anos não se encontrou nenhum sistema de computação mais poderoso que uma Turing Machine

    • Nos últimos 100 anos, as ideias sobre onde está a inteligência artificial foram justamente na direção completamente oposta
      Em vez de criar uma máquina contendo todas as verdades conhecidas, a busca moderna por inteligência artificial baseada em máquinas acabou ficando, em geral, mais próxima de criar uma máquina de feuilleton que vasculha e organiza comentários humanos, diferente da abordagem axiomática à la Leibniz
    • Acho incorreta a afirmação de que “ninguém encontrou um sistema de computação mais poderoso que uma Turing Machine”. Uma Turing Machine não consegue executar não determinismo, mas o modelo de atores consegue

  • Bom trabalho. Eu estava fazendo algo parecido por conta própria, então vou recomendar mais alguns
    RSA: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (1978)
    PageRank: The PageRank Citation Ranking: Bringing Order to the Web (1999)
    MapReduce: MapReduce: simplified data processing on large clusters (2008)
    Bitcoin: Bitcoin: A Peer-to-Peer Electronic Cash System (2008)
    backpropagation: Learning representations by back-propagating errors (1986)
    lógica de Hoare: An Axiomatic Basis for Computer Programming (1969)

  • Onde foi parar o infame Evolution of Unix time-sharing systems, de Dennis Ritchie?
    https://www.bell-labs.com/usr/dmr/www/cacm.pdf

  • Como todo mundo está acrescentando suas recomendações, vou adicionar uma também: embora Cook tenha sido o primeiro a apresentar a NP-completude, o artigo de Karp que apresentou 21 problemas com redução em tempo polinomial a partir do 3SAT também foi uma enorme pedra fundamental que despertou um interesse mais amplo pela teoria de Cook
    https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_proble...

  • New Directions in Cryptography (1976), de Diffie e Hellman, ficou de fora?

  • Não são artigos acadêmicos, mas Why Software Is Eating the World, de Marc Andreessen, e a primeira carta da Amazon aos acionistas, de 1997, merecem uma menção especial
    “As empresas de todos os setores precisam partir do pressuposto de que a revolução do software está chegando. Isso inclui setores que hoje já são baseados em software”
    https://a16z.com/why-software-is-eating-the-world/
    “Mas agora é o Day 1 da internet e, se executarmos bem, também é o Day 1 para a Amazon.com”
    https://www.aboutamazon.com/news/company-news/amazons-origin...