A arte da programação de computadores

The Art of Computer Programming (TAOCP) é uma monografia abrangente escrita pelo cientista da computação Donald Knuth. apresentando algoritmos de programação e sua análise. Os volumes 1 a 5 pretendem representar o núcleo central da programação de computadores para máquinas sequenciais.

Quando Knuth iniciou o projeto em 1962, ele originalmente o concebeu como um único livro com doze capítulos. Os primeiros três volumes do que então se esperava que fosse um conjunto de sete volumes foram publicados em 1968, 1969 e 1973. O trabalho começou para valer no Volume 4 em 1973, mas foi suspenso em 1977 para o trabalho de composição tipográfica solicitado pela segunda edição. do Volume 2. A redação da cópia final do Volume 4A começou à mão em 2001, e o primeiro pré-fascículo online, 2A, apareceu no final de 2001. A primeira parcela publicada do Volume 4 apareceu em brochura como Fascículo 2 em 2005. O volume 4A de capa dura, combinando o Volume 4, Fascículos 0–4, foi publicado em 2011. O Volume 4, Fascículo 6 ("Satisfiabilidade") foi lançado em dezembro de 2015; Volume 4, Fascicle 5 ("Mathematical Preliminaries Redux; Backtracking; Dancing Links") foi lançado em novembro de 2019.

O volume 4B consiste em material evoluído dos Fascículos 5 e 6. O manuscrito foi enviado à editora em 1º de agosto de 2022 e o volume foi publicado em setembro de 2022. O Fascículo 7, planejado para o Volume 4C, foi o tema da palestra de Knuth em 3 de agosto de 2022.

Histórico

Depois de ganhar uma bolsa de estudos da Westinghouse Talent Search, Knuth matriculou-se no Case Institute of Technology (agora Case Western Reserve University), onde seu desempenho foi tão notável que o corpo docente votou para conceder-lhe um mestrado em ciências após a conclusão do bacharelado. #39;s grau. Durante as férias de verão, Knuth foi contratado pela Burroughs Corporation para escrever compiladores, ganhando mais nos meses de verão do que professores titulares durante um ano inteiro. Tais façanhas fizeram de Knuth um tópico de discussão entre o departamento de matemática, que incluía Richard S. Varga.

Em janeiro de 1962, quando era estudante de pós-graduação no departamento de matemática da Caltech, Knuth foi abordado por Addison-Wesley para escrever um livro sobre design de compiladores e propôs um escopo maior. Ele elaborou uma lista de doze títulos de capítulos no mesmo dia. No verão de 1962 ele trabalhou em um compilador FORTRAN para UNIVAC. Nesse período, ele também apresentou uma análise matemática de sondagem linear, que o convenceu a apresentar o material com uma abordagem quantitativa. Depois de receber seu Ph.D. em junho de 1963, ele começou a trabalhar em seu manuscrito, cujo primeiro rascunho terminou em junho de 1965, em 3000 páginas escritas à mão. Ele presumiu que cerca de cinco páginas escritas à mão seriam traduzidas em uma página impressa, mas seu editor disse que cerca de 1+1⁄2 páginas escritas à mão traduzidas em uma página impressa. Isso significava que ele tinha aproximadamente 2.000 páginas impressas de material, o que corresponde ao tamanho das três primeiras publicadas volumes. Neste ponto, Knuth recebeu apoio de Richard S. Varga, que era o consultor científico da editora. Varga estava visitando Olga Taussky-Todd e John Todd no Caltech. Com o endosso entusiástico de Varga, a editora aceitou os planos expandidos de Knuth. Em sua versão ampliada, o livro seria publicado em sete volumes, cada um com apenas um ou dois capítulos. Devido ao crescimento do Capítulo 7, que tinha menos de 100 páginas do manuscrito de 1965, por Vol. 4A pág. vi, o plano para o Volume 4 foi expandido desde então para incluir os Volumes 4A, 4B, 4C, 4D e possivelmente mais.

Em 1976, Knuth preparou uma segunda edição do Volume 2, exigindo que ele fosse composto novamente, mas o estilo de tipo usado na primeira edição (chamado de tipo quente) não estava mais disponível. Em 1977, decidiu passar algum tempo criando algo mais adequado. Oito anos depois, ele voltou com o TEX, que atualmente é utilizado para todos os volumes.

A oferta do chamado cheque de recompensa Knuth no valor de "um dólar hexadecimal" (100_HEX base 16 centavos, em decimal, é $ 2,56) por quaisquer erros encontrados, e a correção desses erros em impressões subsequentes contribuiu para a natureza altamente polida e ainda confiável do trabalho, muito depois de sua primeira publicação. Outra característica dos volumes é a variação na dificuldade dos exercícios. Knuth ainda possui uma escala numérica de dificuldade para avaliar esses exercícios, variando de 0 a 50, onde 0 é trivial e 50 é uma questão em aberto na pesquisa contemporânea.

Knuth 's dedication reads:

Esta série de livros é carinhosamente dedicada
para o computador Tipo 650 uma vez instalado em
Instituto de Tecnologia,
com quem passei muitas noites agradáveis.

Linguagem Assembly no livro

Todos os exemplos nos livros usam uma linguagem chamada "linguagem assembly MIX", que roda no hipotético computador MIX. Atualmente, o computador MIX está sendo substituído pelo computador MMIX, que é uma versão RISC. Softwares como o GNU MDK existem para fornecer emulação da arquitetura MIX. Knuth considera o uso da linguagem assembly necessário para que a velocidade e o uso de memória dos algoritmos sejam julgados.

Resposta crítica

Knuth recebeu o Prêmio Turing de 1974 "por suas principais contribuições à análise de algoritmos [...] e, em particular, por suas contribuições à 'arte da programação de computadores' através de seus livros conhecidos em uma série contínua com este título. American Scientist incluiu este trabalho entre os "100 ou mais livros que moldaram um século de ciência", referindo-se ao século XX, estiloe dentro da comunidade de ciência da computação é considerado o primeiro e ainda o melhor tratamento abrangente de seu assunto. As capas da terceira edição do Volume 1 citam Bill Gates dizendo: "Se você acha que é um programador realmente bom... leia (Knuth's) Art of Programação de Computadores… Você definitivamente deveria me enviar um currículo se puder ler tudo. O The New York Times referiu-se a ele como “o tratado que define a profissão”.

Volumes

Concluído

• Volume 1 – Fundamental Algoritmos
  • Capítulo 1 – Conceitos básicos
  • Capítulo 2 – Estruturas de informação
• Volume 2 – Seminumérico Algoritmos
  • Capítulo 3 – Números aleatórios
  • Capítulo 4 – Aritmética
• Volume 3 – Seleção e pesquisa
  • Capítulo 5 – Classificação
  • Capítulo 6 – Busca
• Volume 4A – Algoritmos Combinatórios
  • Capítulo 7 – Pesquisa combinada (parte 1)
• Volume 4B – Algoritmos Combinatórios
  • Capítulo 7 – Pesquisa combinada (parte 2)

Planejado

• Volume 4C, 4D,... Algoritmos Combinatoriais (capítulos 7 & 8 lançados em vários subvolumes)
  • Capítulo 7 – Pesquisa combinada (continuação)
  • Capítulo 8 – Recursão
• Volume 5 – Sintético Algoritmos
  • Capítulo 9 – digitalização Lexical (também inclui pesquisa de cadeia de caracteres e compressão de dados)
  • Capítulo 10 – Técnicas de separação
• Volume 6 – A teoria das línguas sem contexto
• Volume 7 – Técnicas de compilador

Esboços dos capítulos

Concluído

Volume 1 – Algoritmos Fundamentais

• Capítulo 1 – Conceitos básicos
  • 1.1. Algoritmos
  • 1.2. Preliminares Matemáticas
    • 1.2.1. Indução Matemática
    • 1.2.2. Números, poderes e logaritmos
    • 1.2.3. Somas e Produtos
    • 1.2.4. Integer Funções e Teoria do Número Elementar
    • 1.2.5. Permutações e Fatoriais
    • 1.2.6. Coeficientes Binomiais
    • 1.2.7. Números harmônicos
    • 1.2.8. Números de Fibonacci
    • 1.2.9. Gerar funções
    • 1.2.10. Análise de um Algoritmo
    • 1.2.11. Representações assintóticas
      • 1.2.11.1. A noção O
      • 1.2.11.2. Fórmula de síntese de Euler
      • 1.2.11.3. Alguns cálculos assintomáticos
  • 1.3 MMIX (MIX na cópia hardback, mas atualizado pelo fascículo 1)
    • 1.3.1. Descrição do MMIX
    • 1.3.2. Linguagem da Assembleia MMIX
    • 1.3.3. Aplicações às Permutações
  • 1.4. Algumas técnicas de programação fundamental
    • 1.4.1. Subrotinas
    • 1.4.2. Coroutinas
    • 1.4.3. Rotinas Interpretivas
      • 1.4.3.1. Um simulador MIX
      • 1.4.3. rotinas de rastreamento
    • 1.4.4. Entrada e Saída
    • 1.4.5. História e Bibliografia
• Capítulo 2 – Estruturas de Informação
  • 2.1. Introdução
  • 2.2. Listas lineares
    • 2.2.1. Stacks, Queues e Deques
    • 2.2.2. Alocação sequencial
    • 2.2.3. Alocação vinculada (ordenação topológica)
    • 2.2.4. Listas circulares
    • 2.2.5. Listas duplamente vinculadas
    • 2.2.6. Raios e Listas Ortogonais
  • 2.3. Árvores
    • 2.3.1. Traversing Binary Trees
    • 2.3.2. Representação de árvores binárias
    • 2.3.3. Outras representações das árvores
    • 2.3.4. Propriedades Matemáticas Básicas de Árvores
      • 2.3.4.1. Árvores livres
      • 2.3.4.2. Árvores de orientação
      • 2.3.4.3. O lemma infinito
      • 2.3.4.4. Enumeração de árvores
      • 2.3.4.5. Comprimento do caminho
      • 2.3.4.6. História e bibliografia
    • 2.3.5. Listas e coleta de lixo
  • 2.4. Estruturas multiligadas
  • 2.5. Alocação dinâmica de armazenamento
  • 2.6. História e Bibliografia

Volume 2 – Algoritmos Seminuméricos

• Capítulo 3 – Números aleatórios
  • 3.1. Introdução
  • 3.2. Gerando números aleatórios uniformes
    • 3.2.1. O Método Congruente Linear
      • 3.2.1.1. Escolha de módulo
      • 3.2.1.2. Escolha do multiplicador
      • 3.2.1.3. Potência
    • 3.2.2. Outros métodos
  • 3.3. Testes estatísticos
    • 3.3.1. Procedimentos gerais de teste para estudar dados aleatórios
    • 3.3.2. Testes Empíricos
    • 3.3.3. Testes teóricos
    • 3.3.4. O teste espectral
  • 3.4. Outros tipos de Quantidades Aleatórias
    • 3.4.1. Distribuição numérica
    • 3.4.2. Amostragem aleatória e Shuffling
  • 3.5. O que é uma sequência aleatória?
  • 3.6. Resumo
• Capítulo 4 – Aritmética
  • 4.1. Sistemas de Número Posicionado
  • 4.2. Ponto flutuante Aritmética
    • 4.2.1. Cálculos de uma precisão
    • 4.2.2. Precisão da aritmética de ponto flutuante
    • 4.2.3. Cálculos de dupla precisão
    • 4.2.4. Distribuição dos Números de Pontos Flutuantes
  • 4.3. Aritmética de precisão múltipla
    • 4.3.1. Os Algoritmos Clássicos
    • 4.3.2. Aritmética Modular
    • 4.3.3. Quão rápido podemos multiplicar?
  • Conversão do Radix 4.4.
  • 4.5. Aritmética Racional
    • 4.5.1. Frações
    • 4.5.2. O maior Divisor Comum
    • 4.5.3. Análise do Algoritmo de Euclides
    • 4.5.4. Factoring into Primes
  • 4.6. Aritmética Polinomial
    • 4.6.1. Divisão de Polinomiais
    • 4.6.2. Factorização dos polinômios
    • 4.6.3. Avaliação dos Poderes (exponenciação de cadeia de adição)
    • 4.6.4. Avaliação dos polinômios
  • 4.7. Manipulação da Série de Energia

Volume 3 – Classificação e pesquisa

• Capítulo 5 – Classificação
  • 5.1. Propriedades Combinatórias de Permutações
    • 5.1.1. Inversões
    • 5.1.2. Permutações de um Multiset
    • 5.1.3. Corre
    • 5.1.4. Tableaux e Involuções
  • 5.2. Classificação interna
    • 5.2.1. Seleção por inserção
    • 5.2.2. Seleção por troca
    • 5.2.3. Seleção por seleção
    • 5.2.4. Seleção por fusão
    • 5.2.5. Seleção por Distribuição
  • 5.3. Seleção ótima
    • 5.3.1. Classificação mínima da concorrência
    • 5.3.2. Mínimo-Comparison fusão
    • 5.3.3. Seleção de Mínimo-Comparison
    • 5.3.4. Redes para classificação
  • 5.4. Seleção externa
    • 5.4.1. Seleção de Merging e Substituição Multiway
    • 5.4.2. A fusão da polifase
    • 5.4.3. A fusão da Cascade
    • 5.4.4. Fita de leitura
    • 5.4.5. O tipo oscilante
    • 5.4.6. Considerações práticas para fusão de fita
    • 5.4.7. Seleção externa de raios
    • 5.4.8. Seleção de duas partes
    • 5.4.9. Discos e tambores
  • 5.5. Resumo, História e Bibliografia
• Capítulo 6 – Busca
  • 6.1. Pesquisa Sequencial
  • 6.2. Procurando por Comparação de Chaves
    • 6.2.1. Procurando uma tabela ordenada
    • 6.2.2. Busca de árvores binárias
    • 6.2.3. Árvores equilibradas
    • 6.2.4. Árvores de Multiway
  • 6.3. Pesquisa digital
  • 6.4. Ativação
  • 6,5. Retrieval em chaves secundárias

Volume 4A – Algoritmos Combinatórios, Parte 1

• Capítulo 7 – Combinação Pesquisar
  • 7.1. Zeros e Ones
    • 7.1.1. Básico booleano
    • 7.1.2. Avaliação booleana
    • 7.1.3. Truques e Técnicas Bitwise
    • 7.1.4. Diagramas de decisão binários
  • 7.2. Gerando todas as possibilidades
    • 7.2.1. Gerando padrões combinados básicos
      • 7.2.1.1. Gerar todos os n-tuples
      • 7.2.1.2. Gerando todas as permutações
      • 7.2.1.3. Gerar todas as combinações
      • 7.2.1. Gerar todas as partições
      • 7.2.1.5. Gerar todas as partições definidas
      • 7.2.1.6. Gerando todas as árvores
      • 7.2.1.7. História e outras referências

Volume 4B – Algoritmos Combinatórios, Parte 2

• Capítulo 7 – Pesquisa Combinada (continuação)
  • 7.2. Gerar todas as possibilidades (continuação)
    • 7.2.2. Programação de backtrack
      • 7.2.2.1. Ligações de dança (inclui discussão de cobertura exata)
      • 7.2.2.2. Satisfação

Planejado

Volumes 4C, 4D, 4E, 4F – Algoritmos Combinatórios

• Capítulo 7 – Pesquisa Combinada (continuação)
  • 7.2. Gerar todas as possibilidades (continuação)
    • 7.2.2. Programação de backtrack (continuação)
      • 7.2.2.3. Satisfação de restrição
      • 7.2.2.4. Caminhos e ciclos Hamiltonianos
      • 7.2.2.5. Cliques
      • 7.2.2.6. Coberturas (Cobertura de vértice, Definir problema de cobertura, Tampa exata, tampa de clique)
      • 7.2.2.7. Praças
      • 7.2.2.8. Um potpourri de quebra-cabeças (inclui Invariante digital perfeita)
      • 7.2.2.9. Estimando custos de backtrack (capítulo 6 de "Selected Papers on Analysis of Algorithms", e Fascicle 5, pp. 44−47, sob o título "Running time Estimative")
    • 7.2.3. Gerar padrões inequivalentes (inclui discussão do teorema da enumeração da Pólya) (veja "Tecnologias para a Rejeição Isomorfo", capítulo 4 de "Algumas de Certificação para Códigos e Designs" por Kaski e Östergård)
  • 7.3. Caminhos mais curtos
  • 7.4. Algoritmos gráficos
    • 7.4.1. Componentes e traversais
      • 7.4.1.1. Algoritmos Union-find
      • 7.4.1.2. Depth-first search
      • 7.4.1.3. Conectividade de vértice e borda
    • 7.4.2. Aulas especiais de gráficos
    • 7.4.3. Gráficos expansores
    • 7.4.4. Gráficos aleatórios
  • 7.5. Gráficos e otimização
    • 7.5.1. Combinação bipartida (incluindo correspondência máxima de cartas, problema de casamento estável, Mariages Stables)
    • 7.5.2. O problema da atribuição
    • 7.5.3. Fluxos de rede
    • 7.5.4. Árvores ótimas
    • 7,5.5. Combinação ótima
    • 7.5.6. Pedidos ideais
  • 7.6. Teoria da independência
    • 7.6.1. Estruturas da independência
    • 7.6.2. Algoritmos matróides eficientes
  • 7.7. Programação dinâmica discreta (veja também o método Transfer-matrix)
  • 7.8. Técnicas de Branch-and-bound
  • 7.9. Tarefas hercúleas (problemas NP-hard)
  • 7.10. Otimização próxima
• Capítulo 8 – Recursão (capítulo 22 de "Livros selecionados sobre análise de algoritmos")

Volume 5 – Algoritmos Sintáticos

• Capítulo 9 – digitalização Lexical (inclui também pesquisa de cadeias e compressão de dados)
• Capítulo 10 – Técnicas de separação

Volume 6 – A Teoria das Linguagens Livres de Contexto

Volume 7 – Técnicas de Compilador

Edições em inglês

Edições atuais

Estas são as edições atuais em ordem por número de volume:

• A arte da programação de computador, Volumes 1-4B Boxed Set. (Reading, Massachusetts: Addison-Wesley, 2023), 3904pp. ISBN 978-0-13-793510-9, 0-13-793510-2
  • Volume 1: Algoritmos Fundamentais. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xx+650pp. ISBN 978-0-201-89683-1, 0-201-89683-4. Errata: [1] (2011-01-08), [2] (2022, 49a impressão). Addenda: [3] (2011).
  • Volume 2: Algoritmos seminuméricos. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762pp. ISBN 978-0-201-89684-8, 0-201-89684-2. Errata: [4] (2011-01-08), [5] (2022, 45a impressão). Addenda: [6] (2011).
  • Volume 3: Seleção e pesquisa. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. ISBN 978-0-201-89685-5, 0-201-89685-0. Errata: [7] (2011-01-08), [8] (2022, 45a impressão). Addenda: [9] (2011).
  • Volume 4A: Algoritmos Combinatórios, Parte 1. First Edition (Upper Saddle River, New Jersey: Addison-Wesley, 2011), xv+883pp. ISBN 978-0-201-03804-0, 0-201-03804-8. Errata: [10] (2011), [11] (2022, 22a impressão).
  • Volume 4B: Algoritmos Combinatórios, Parte 2. First Edition (Upper Saddle River, Nova Jersey: Addison-Wesley, 2023), xviii+714pp. ISBN 978-0-201-03806-4, 0-201-03806-4. Errata: [12] (2023).
• Volume 1, Fascículo 1: MMIX – Um computador RISC para o novo milênio. (Addison-Wesley, 2005-02-14) ISBN 0-201-85392-2. Errata: [13] (2020-03-16) (será na quarta edição do volume 1)

Edições anteriores

Volumes completos

Esses volumes foram substituídos por edições mais recentes e estão ordenados por data.

• Volume 1: Algoritmos Fundamentais. Primeira edição, 1968, xxi+634pp, ISBN 0-201-03801-3.
• Volume 2: Algoritmos seminuméricos. Primeira edição, 1969, xi+624pp, ISBN 0-201-03802-1.
• Volume 3: Seleção e pesquisa. Primeira edição, 1973, xi+723pp+foldout, ISBN 0-201-03803-X. Errata: [14].
• Volume 1: Algoritmos Fundamentais. Segunda edição, 1973, xxi+634pp, ISBN 0-201-03809-9. Errata: [15].
• Volume 2: Algoritmos seminuméricos. Segunda edição, 1981, xiii+ 688pp, ISBN 0-201-03822-6. Errata: [16].
• A Arte de Programação de Computador, Volumes 1-3 Conjunto Boxed. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998), pp. ISBN 978-0-201-48541-7, 0-201-48541-9
• A arte da programação de computador, Volumes 1-4A Boxed Set. Third Edition (Reading, Massachusetts: Addison-Wesley, 2011), 3168pp. ISBN 978-0-321-75104-1, 0-321-75104-3

Fascículos

Volume 4, Fascículos 0–4 foram revisados e publicados como Volume 4A.

• Volume 4, Fascículo 0: Introdução aos Algoritmos Combinatoriais e Funções Booleanas. (Addison-Wesley Professional, 2008-04-28) vi+240pp, ISBN 0-321-53496-4. Errata: [17] (2011-01-01).
• Volume 4, Fascículo 1: Truques e Técnicas Bitwise; Diagramas de Decisão Binária. (Addison-Wesley Professional, 2009-03-27) viii+260pp, ISBN 0-321-58050-8. Errata: [18] (2011-01).
• Volume 4, Fascículo 2: Gerando todos os Tuplas e Permutações. (Addison-Wesley, 2005-02-14) v+127pp, ISBN 0-201-85393-0. Errata: [19] (2011-01).
• Volume 4, Fascículo 3: Gerando todas as combinações e partições. (Addison-Wesley, 2005-07-26) vi+150pp, ISBN 0-201-85394-9. Errata: [20] (2011-01).
• Volume 4, Fascículo 4: Gerando todas as árvores; História da Geração Combinatória. (Addison-Wesley, 2006-02-06) vi+120pp, ISBN 0-321-33570-8. Errata: [21] (2011-01).

Volume 4, Fascículos 5–6 foram revisados e publicados como Volume 4B.

• Volume 4, Fascículo 5: Preliminares Matemáticos Redux; Backtracking; Dancing Links. (Addison-Wesley, 2019-11-22) xiii+382pp, ISBN 978-0-13-467179-6. Errata: [22] (2020-03-27)
• Volume 4, Fascículo 6: Satisfabilidade. (Addison-Wesley, 2015-12-08) xiii+310pp, ISBN 978-0-13-439760-3. Errata: [23] (2020-03-26)

Pré-fascículos

Volume 1

• O pré-fascículo 1 foi revisado e publicado como Volume 1, fascículo 1.

Volume 4

• Os pré-fascículos 0A, 0B e 0C foram revisados e publicados como Volume 4, fascículo 0.
• Os pré-fascículos 1A e 1B foram revisados e publicados como Volume 4, fascículo 1.
• Os pré-fascículos 2A e 2B foram revisados e publicados como Volume 4, fascículo 2.
• Os pré-fascículos 3A e 3B foram revisados e publicados como Volume 4, fascículo 3.
• Os pré-fascículos 4A e 4B foram revisados * e publicados como Volume 4, fascículo 4.
• Os pré-fascículos 5A, 5B e 5C foram revisados e publicados como Volume 4, fascículo 5.
• O pré-fascículo 6A foi revisado e publicado como Volume 4, fascículo 6.

Os pré-fascículos restantes contêm material preliminar que deverá aparecer em fascículos e volumes futuros.

• Volume 4, pré-fascículo 7A: Satisfação de restrição
• Volume 4, Pré-fascículo 8A: Caminhos Hamiltonianos e Ciclos
• Volume 4, pré-fascículo 8B: cliques
• Volume 4, Pré-fascículo 9B: Um Potpourri de Puzzles
• Volume 4, Pré-fascículo 9C: Estimativa de Custos de Backtrack
• Volume 4, Pré-fascículo 12A: Componentes e Traversal (versão PDF)
• Volume 4, Pré-fascículo 14A: Combinação Bipartida
• Volume 4, Pré-fascículo 16A: Introdução à Recursão