Introduccion Al Dise O Y An Lisis De Algoritmos Lee Tseng Chang Y Tsai

.

Introducción
al diseño y análisis
de algoritmos
Un enfoque estratégico

.

Introducción
al diseño y análisis
de algoritmos
Un enfoque estratégico
R. C. T. Lee
National Chi Nan University, Taiwan

S. S. Tseng
National Chiao Tung University, Taiwan

R. C. Chang
National Chiao Tung University, Taiwan

Y. T. Tsai
Providence University, Taiwan
Revisión técnica
Miguel A. Orozco Malo
InstitutoTecnológico y de Estudios Superiores
de Monterrey, Campus Ciudad de México
Jorge Valeriano Assem
Universidad Nacional Autónoma de México
Carlos Villegas Quezada
Universidad Iberoamericana

MÉXICO • BOGOTÁ • BUENOS AIRES • CARACAS • GUATEMALA
LISBOA • MADRID • NUEVA YORK • SAN JUAN • SANTIAGO
AUCKLAND • LONDRES • MILÁN • MONTREAL • NUEVA DELHI
SAN FRANCISCO • SINGAPUR • SAN LUIS • SIDNEY • TORONTODirector Higher Education: Miguel Ángel Toledo Castellanos
Director editorial: Ricardo del Bosque Alayón
Editor sponsor: Pablo Eduardo Roig Vázquez
Editora de desarrollo: Ana Laura Delgado Rodríguez
Supervisor de producción: Zeferino García García
Traducción: Hugo Villagómez Velázquez
INTRODUCCIÓN AL DISEÑO
Y ANÁLISIS DE ALGORITMOS.
Un enfoque estratégico
Prohibida la reproducción total oparcial de esta obra,
por cualquier medio, sin la autorización escrita del editor.

DERECHOS RESERVADOS © 2007, respecto a la primera edición en español por
McGRAW-HILL/INTERAMERICANA EDITORES, S.A. DE C.V.
A Subsidiary of The McGraw-Hill Companies, Inc.
Edificio Punta Santa Fe
Prolongación Paseo de la Reforma 1015, Torre A
Piso 17, Colonia Desarrollo Santa Fe
Delegación Álvaro Obregón
C.P. 01376,México, D.F.
Miembro de la Cámara Nacional de la Industria Editorial Mexicana, Reg. Núm. 736
Traducido de la primera edición de: Introduction to the Design and Analysis of Algorithms.
A Strategic Approach.
Copyright © MMV by McGraw-Hill Education (Asia). All rights reserved.
ISBN 007-124346-1
ISBN-13: 978-970-10-6124-4
ISBN-10: 970-10-6124-1

1234567890

09865432107

Impreso en México

Printed inMexico

Acerca de los autores
R.C.T. LEE se recibió como maestro en ciencias en el Departamento de Ingeniería
Eléctrica de la Universidad Nacional de Taiwán y se doctoró en el Departamento de
Ingeniería Eléctrica y Ciencias de Computación de la Universidad de California en
Berkeley. Es profesor en los departamentos de Ciencias de Computación e Ingeniería
de la Información en la Universidad NacionalChi Nan. El profesor Lee es miembro de
la IEEE. Es coautor del libro Symbolic Logic and Mechanical Theorem Proving, que
ha sido traducido al japonés, ruso e italiano.
S.S TSENG y R.C. CHANG recibieron sus grados de maestría y doctorado en el Departamento de Ingeniería de Computación de la Universidad Nacional Chiao Tung de
Taiwán, donde ambos son profesores en el Departamento de Computación yCiencias
de la Información.
Y.T. TSAI terminó la maestría en el Departamento de Computación y Ciencias de la
Información en la Universidad Nacional Chiao Tung de Taiwán, y se doctoró en el
Departamento de Ciencias de Computación en la Universidad Nacional Tsing-Hua.
Actualmente es profesor asociado en el Departamento de Ciencias de la Información y
Administración en la Universidad Providence.

v.

Contenido
Prefacio

xi

Capítulo 3
El método codicioso

Capítulo 1
Introducción 1

71

3-1

Método de Kruskal para encontrar
un árbol de expansión
mínima 75
3-2 Método de Prim para encontrar un
árbol de expansión mínima 79
3-3 El problema de la ruta más corta de
origen único 86
3-4 Problema de mezclar 2 listas
(2-way merge) 91
3-5 El problema del ciclo base mínimo
(minimum cycle basis)resuelto con
el algoritmo codicioso 98
3-6 Solución por el método codicioso
del problema de 2 terminales
(uno a cualquiera/uno a
muchos) 103
3-7 El problema del mínimo de guardias
cooperativos para polígonos de
1-espiral resuelto por el método
codicioso 108
3-8 Los resultados experimentales 114
3-9 Notas y referencias 115
3-10 Bibliografía adicional 115
Ejercicios 116

Capítulo 2
Complejidad de los...