MO417 - Livro Texto

Criada: 2010-02-26
Revisada: 2010-03-30
Revisada: 2010-05-09
Revisada: 2010-06-13
Revisada: 2010-06-18

Livro texto adotado

Adotaremos o seguinte texto neste semestre:

Introduction to Algorithms 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).

A primeira edição deste livro pode ser usada, porém uma ou outra seção terá que ser obtida da segunda edição pois não existe na primeira edição. Alguns exercícios que utilizaremos também não existem na primeira edição.

Também poderá ser usada a tradução para o português:

Algoritmos: teoria e prática 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.

Porém, esta tradução para o português deve ser usada em conjunto com as correções abaixo. Gostaríamos de agradecer à 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. Ao mesmo tempo, damos nossa permissão para que estas correções sejam usadas em futuras reimpressões do 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. Na versão em português, 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)
strict (falando sobre limites)
estrito
restrito
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
flow network
rede de fluxo
fluxo em rede
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?
15
parágrafo 4
7
item 9.
x ... NIL x ≠ NIL tipográfico

18
parágrafo 5
2
fórmula de T(n)
- c8 + c8 tipográfico

19
parágrafo 3
1
fórmula de soma
n(n - 1) n(n + 1) tipográfico

22
algoritmo MERGE
0
cabeçalho
MERGE(A,P,q,r) MERGE(A,p,q,r) tipográfico

25
parágrafo 3
7

a ... b a ≠ b tipográfico

44
fórmula 3.19
1

αn αn tipográfico

47
exercício 3-3 a.
5
lista de funções
2n 2n tipográfico

47
exercício 3-3 a.
5
lista de funções
22n+1 22n+1 tipográfico

53
parágrafo 12
1

2(cn/2⌋ 2 cn/2⌋ tipográfico

141
parágrafo 3
1

ni ni tipográfico

142
última fórmula
1
antes do =
E[ X2ij ] E[ n2i ] lógico

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, mas corrigida na 4a. reimpressão
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

471
parágrafo 1
3

uV - S uV - S tipográfico

491
parágrafo 11
4

gl lg tipográfico

493
fórmula (25.2)
1
segunda ocorrência
lij(m-1) lik(m-1) tipográfico

493
fórmula (25.2)
2

lij(m-1) lik(m-1) 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


MO417 Home

© 2010 João Meidanis