Errata: Algoritmos - Teoria e Prática

Livro Texto em Português:
Algoritmos: teoria e prática, de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, tradução da 2ª edição [americana], Vandenberg D. de Souza,  Ed. Campus, 2002.  ISBN 85-352-0926-3.

Livro Original em Inglês:
Introduction to Algorithms, 2nd edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press and McGraw-Hill Book Company, 2001.  ISBN 0-262-03293-7 (MIT Press); ISBN 0-07-013151-1 (McGraw-Hill).

Tradução de termos técnicos

Algumas expressões técnicas relativas a algoritmos em inglês têm uma tradução padrão, consolidada por anos de uso entre os pesquisadores brasileiros de algoritmos.  No livro-texto adotado foram utilizadas traduções alternativas, o que pode introduzir confusão entre os leitores, ao consultarem outras obras em português sobre o assunto.  A tabela abaixo pode ajudar a sanar esta confusão.

Termo em inglês Tradução padrão
Tradução usada no livro (não-padrão)
full binary tree
(árvore binária onde cada nó tem 0 ou 2 filhos)
árvore binária completa
complete binary tree
árvore binária completa
árvore binária completa
rank
posto
ordem
union by rank
união por posto
união por ordenação
minimum spanning tree
árvore espalhada mínima, ou árvore geradora mínima
árvore de amplitude mínima
matching
emparelhamento
correspondência
connected components
componentes conexos
componentes conectados
sink
sumidouro
depósito
breadth-first search
busca em largura
pesquisa primeiro na extensão
depth-first search
busca em profundidade
pesquisa primeiro na profundidade
transitive closure
fecho transitivo
fechamento transitivo
skew symmetry
anti-simetria
simetria oblíqua
augmenting path
caminho aumentante
caminho em ampliação

Correções

Notas:

  1. Os parágrafos são numerados a partir do primeiro de uma página, mesmo que incompleto.
  2. Legendas de figuras não contam como parágrafos.
  3. Cada item de uma lista conta como um parágrafo.
  4. Fórmulas, numeradas ou não, contam como parágrafos.
  5. Títulos de seções não contam como parágrafos.
  6. Algoritmos (com título, pseudocódigo e numeração de linhas) não contam como parágrafos.
Página
Local
Linha
Detalhes
Como está Como deveria estar
Tipo de erro
Presente também na edição americana?
260
parágrafo 2
5

Denotamos o j-ésima estação Denotamos a j-ésima estação tipográfico

261
parágrafo 3
5

S1, J S1,  j tipográfico

263
fórnulas 15.4, 15.5, 15.6, 15.7
1 e 2

parêntesis aberto e não fechado
parêntesis fechado
tipográfico

265
algoritmo PRINT-STATIONS
5

sem indentação
com indentação
lógico

287
parágrafo 5
5

recortar TY de T e colar em T″ recortar T′ de T e colar T″ lógico

289
fórmula 15.20


... pj + qj ... pj + qj formatação

294
último parágrafo
1

n n
n × n
tipográfico

297
título da seção 16.1

atividade
atividades
tipográfico

300
parágrafo 1
1

Aij = {ak}  ∪ {am}
Aij = (Aij \ {ak})  ∪ {am} lógico

301
algoritmo RECURSIVE-ACTIVITY-SELECTOR
5

{am} ← RECURSIVE-ACTIVITY-SELECTOR(s,f,m,j)
{am} ∪ RECURSIVE-ACTIVITY-SELECTOR(s,f,m,j) tipográfico

301
parágrafo 2
6

RECURSIVE-ACTIVITY%SELECTOR RECURSIVE-ACTIVITY-SELECTOR tipográfico
301
algoritmo GREEDY-ACTIVITY-SELECTOR 2

A ← {1}
A ← {a1}
tipográfico
304
segunda seqüência de etapas
etapa 2
torna a escolha gulosa usa a escolha gulosa lógico

312
parágrafo 1
6

produzir uma árvore T
produzir uma árvore T lógico

312
parágrafo 3
4

Então, B(T ′) ≤ B(T)
Então, B(T ″) ≤ B(T) lógico

314
exercício 16.3-7
4

7
(nada)
tipográfico
321
problema 16-1

em todo o enunciado
troca
troco
lógico

381
parágrafo 4
2

livremente
vagamente, ou levemente
lógico

383
fórmula 20.1


t(H) = 2m(H)
t(H) + 2m(H)
tipográfico

387
parágrafo 2
1
item 1 da lista de itens
chave[x] = chave[y]
chave[x] ≤ chave[y] lógico

387
algoritmo CONSOLIDATE
16

A[i] NIL
A[i] ≠  NIL
tipográfico
407
parágrafo 2
1

Ak(j)
Ak(j)
tipográfico
407
parágrafo 8 2 e 3

A2
A2
tipográfico
409
parágrafo 4 3

a potencial
o potencial
tipográfico
409
parágrafo 5 2
maiúsculo para minúsculo
Φq(x)
φq(x)
tipográfico
409
parágrafo 6 2
maiúsculo para minúsculo
&Phiq(x) φq(x) tipográfico
415
título do problema 21-3


ancestrais menos comuns
ancestrais comuns mais profundos
lógico

416
parágrafo 2
1 e 4
faltou fechar parêntesis
Ω(m α(m,n)
Ω(m α(m,n)) tipográfico

423
algoritmo BFS
4 e 7

α
π
tipográfico
424
figura 22.3
item (f)

aresta (r,s)  simples
aresta (r,s)  sombreada gráfico

425
parágrafo 9
2

δ(s,v)
δ(s,s)
tipográfico

429
parágrafo 2
3

π[u]
π[v]
lógico

430
algoritmo DFS-VISIT
5

cor[u]
cor[v]
lógico

431
título do Teorema 22.6


22.6
22.7
lógico

438
exercício 22.4-5
2

dar saída a ele
imprimí-lo
lógico

448
parágrafo 4
1

w(T ′) - w(x,y) + w(u,v)
w(T) - w(x,y) + w(u,v) tipográfico

450
parágrafo 3
2

w(x,y)
w(x,y) - k
lógico

451
figura 23.4
itens (l), (m) e (n)

aresta (c,i) sem peso
aresta (c,i) com peso 2
gráfico
SIM
454
parágrafo 7
penúltima

O(V lg V + E lg V) O(E lg V)
O(V lg V + E lg V) = O(E lg V) tipográfico

460
Lema 24.1
3
enunciado do lema
vI vi tipográfico

463
parágrafo 7
1

π[v] NIL
π[v] = NIL
tipográfico
467
parágrafo 9
2

d[vi] d[vi] tipográfico

491
parágrafo 11
4

gl lg tipográfico

493
parágrafo 6
2

L(m) (lij(m)) L(m) = (lij(m)) tipográfico

493
algoritmo EXTEND-SHORTEST-PATHS
3

for ito n for i ← 1 to n tipográfico

494
algoritmo MATRIX-MULTIPLY
8

cij cij tipográfico

494
parágrafo 4
3

denota denotar tipográfico

494
algoritmo SLOW-ALL-PAIRS-SHORTEST-PATHS
2

W0 W tipográfico

494
algoritmo SLOW-ALL-PAIRS-SHORTEST-PATHS
4

L(m) L(m) tipográfico

510
parágrafo 5
1
definição da segunda prop. de fluxos
f(u,v) = -f(u,v) f(u,v) = -f(v,u) tipográfico

516
parágrafo 2
1

Gf Gf formatação

516
parágrafo 2
2

Ef Ef formatação

516
parágrafo 4
3

Gf Gf formatação

516
parágrafo 8
3

| f | + | f ′ | = | f | + | f ′ | | f + f ′ | = | f | + | f ′ | tipográfico

517
parágrafo 1
2, 3, 4
definição da segunda prop. de fluxos
(u,v) (v,u) tipográfico

517
parágrafo 3
2

c (c (u,v) - f ′ (u,v) c (u,v) - f (u,v) tipográfico

518
Lema 26.3, parágrafo 2
1
definição de fp(u,v)
cf cf(p) tipográfico