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, 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, 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:

Os parágrafos são numerados a partir do primeiro de uma página, mesmo que incompleto.
Legendas de figuras não contam como parágrafos.
Cada item de uma lista conta como um parágrafo.
Fórmulas, numeradas ou não, contam como parágrafos.
Títulos de seções não contam como parágrafos.
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)	- c₈	+ c₈	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	2ⁿ	tipográfico
47	exercício 3-3 a.	5	lista de funções	2²ⁿ⁺¹	2^2ⁿ⁺¹	tipográfico
53	parágrafo 12	1		2(c⌊n/2⌋	2 c⌊n/2⌋	tipográfico
141	parágrafo 3	1		ni	n_i	tipográfico
142	última fórmula	1	antes do =	E[ X²_ij ]	E[ n²_i ]	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		S_1,J	S_1,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			... p_j + q_j	... p_j + q_j	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 = {a_k} ∪ {a_m}	A′_ij = (A_ij \ {a_k}) ∪ {a_m}	lógico
301	algoritmo RECURSIVE-ACTIVITY-SELECTOR	5		{a_m} ← RECURSIVE-ACTIVITY-SELECTOR (s,f,m,j)	{a_m} ∪ 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 ← {a₁}	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)	A_k(j)	tipográfico
407	parágrafo 8	2 e 3		A²	A₂	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	&Phi_q(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	v_I	v_i	tipográfico
463	parágrafo 7	1		π[v] NIL	π[v] = NIL	tipográfico
467	parágrafo 9	2		d[vi]	d[v_i]	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	l_ij^(m-1)	l_ik^(m-1)	tipográfico
493	fórmula (25.2)	2		l_ij^(m-1)	l_ik^(m-1)	tipográfico
493	parágrafo 6	2		L^(m) (l_ij^(m))	L^(m) = (l_ij^(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	c_ij	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	G_f	formatação
516	parágrafo 2	2		Ef	E_f	formatação
516	parágrafo 4	3		Gf	G_f	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 f_p(u,v)	c_f	c_f(p)	tipográfico

MO417 Home