MO417 - Livro Texto

Criada: 2003-05-18

Antiga página do livro-texto

Livro texto adotado:
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).

Esta página contém uma lista de erros que encontramos durante o semestre no livro-texto adotado. Apenas os capítulos abordados no curso foram lidos, e durante a leitura apareceram as observações que aqui colocamos.  Assim, a errata concentra-se nestes capítulos, embora em alguns casos tenhamos incluido observações referentes a outros capítulos.

Gostaríamos de parabenizar a editora pela iniciativa de traduzir um livro tão importante como este, e enfatizar que a presente compilação de correções tem como objetivo tornar esta iniciativa ainda mais efetiva para disseminar entre nós, falantes de português, este excelente texto.

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
A′ij = {ak}  ∪ {am}
 A′ij = (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 i ← to 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

O(n)

© 2003 João Meidanis