MO417 - Livro Texto

Criada: 2013-02-24

Livro texto adotado

Adotaremos o seguinte texto neste semestre:

Introduction to Algorithms Introduction to Algorithms, 3rd edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press, 2009. ISBN 9780262033848.

Link para dicas de soluções.

Consulte também as soluções dos autores para alguns exercícios e problemas.

Nos anos de 2003, 2009 e 2010, os alunos prepararam também atas de soluções de exercícios.

A primeira ou segunda edições deste livro também podem ser usadas, porém uma ou outra seção terá que ser obtida da terceira edição pois não existe nas anteriores. E, mesmo nas seções que existem nas outras edições, alguns exercícios podem estar ausentes nas edições anteriores.

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(c⌊n/2⌋ 2 c⌊n/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
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, 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
u ≥ V - S u ∈ V - 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 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

MO417 Home

© 2013 João Meidanis