Algoritmos en pocas palabras, 2ª edición

Prefacio a la Segunda Edición

Este trabajo se ha traducido utilizando IA. Agradecemos tus opiniones y comentarios: [e-mail]

Revisar un libro para una nueva edición es siempre una tarea ardua. Queríamos asegurarnos de conservar todas las buenas cualidades de la primera edición, publicada en 2009, al tiempo que corregíamos algunas de sus deficiencias y añadíamos material adicional. Continuamos siguiendo los principios esbozados en la primera edición:

• Utiliza código real, no sólo pseudocódigo para describir algoritmos

• Separar el algoritmo del problema que se resuelve

• Introduce las matemáticas justas

• Apoyar empíricamente el análisis matemático

Al actualizar esta segunda edición, hemos reducido la longitud de las descripciones del texto y simplificado la maquetación para dar cabida a nuevos algoritmos y material adicional. Creemos que seguimos ofreciendo una perspectiva Nutshell sobre un área importante de la informática que tiene un impacto significativo en los sistemas de software prácticos.

Cambios en la Segunda Edición

Al actualizar este libro para la segunda edición, hemos seguido estos principios:

Seleccionar nuevos algoritmos

Tras la publicación de la primera edición, recibimos a menudo comentarios como "¿Por qué se dejó fuera la Ordenación por Fusión?" o "¿Por qué no cubristeis la Transformada Rápida de Fourier (FFT)?". Fue imposible satisfacer todas estas peticiones, pero pudimos añadir los siguientes algoritmos:

• Algoritmo de Fortune, para calcular el Diagrama de Voronoi de un conjunto de puntos ("Diagrama de Voronoi")

• Ordenarpor Fusión, tanto para datos de la memoria interna como para archivos externos ("Ordenar por Fusión")

• Ordenación rápida multihilo ("Algoritmos paralelos")

• Implementacióndel Árbol Binario Equilibrado AVL ("Solución")

• Un nuevo capítulo sobre Algoritmos Espaciales(Capítulo 10) contiene Árboles R y Cuadráticos

En total, el libro abarca casi 40 algoritmos esenciales.

Racionalizar la presentación

Para dar cabida al nuevo material, hemos revisado casi todos los aspectos de la primera edición. Simplificamos la plantilla utilizada para describir cada algoritmo y redujimos las descripciones que lo acompañan.

Añadir implementaciones de Python

En lugar de reimplementar los algoritmos existentes en Python, hemos utilizado intencionadamente Python para implementar la mayoría de los nuevos algoritmos añadidos.

Gestionar recursos de código

El código de la primera edición estaba disponible como archivo ZIP. Desde entonces hemos pasado a un repositorio GitHub. A lo largo de los años hemos mejorado la calidad del código y su documentación. Hemos incorporado una serie de entradas de blog que se escribieron después de la publicación de la primera edición. Hay más de 500 casos de pruebas unitarias y utilizamos herramientas de cobertura del código para garantizar la cobertura del 99% de nuestro código Java. En total, el repositorio de código consta de más de 110 KLOC.

Audiencia

Pretendemos que este libro sea tu principal referencia cuando busques información práctica sobre cómo implementar o utilizar un algoritmo. Abarcamos una serie de algoritmos existentes para resolver un gran número de problemas y nos ceñimos a los siguientes principios:

• Al describir cada algoritmo, utilizamos una plantilla estilizada para enmarcar adecuadamente cada debate y explicar los puntos esenciales de cada algoritmo

• Utilizamos diversos lenguajes para implementar cada algoritmo (incluidos C, C++, Java y Python). De este modo, concretamos el debate sobre los algoritmos y hablamos utilizando lenguajes con los que ya estás familiarizado

• Describimos el rendimiento esperado de cada algoritmo y aportamos pruebas empíricas para apoyar estas afirmaciones

Pretendemos que este libro sea de gran utilidad para los profesionales, programadores y diseñadores de software. Para cumplir tus objetivos, necesitas acceder a un recurso de calidad que explique soluciones reales a algoritmos prácticos que necesitas para resolver problemas reales. Ya sabes programar en diversos lenguajes de programación. Conoces las estructuras de datos esenciales de la informática, como matrices, listas enlazadas, pilas, colas, tablas hash, árboles binarios y grafos dirigidos y no dirigidos. No necesitas implementar estas estructuras de datos, ya que normalmente las proporcionan las bibliotecas de código.

Esperamos que utilices este libro para aprender soluciones probadas para resolver problemas de forma eficaz. Aprenderás algunas estructuras de datos avanzadas y formas novedosas de aplicar estructuras de datos estándar para mejorar la eficacia de los algoritmos. Tu capacidad para resolver problemas mejorará cuando veas las decisiones clave de cada algoritmo que permiten obtener soluciones eficientes.

Convenciones utilizadas en este libro

En este libro se utilizan las siguientes convenciones tipográficas:

Code

All code examples appear in this typeface.

This code is replicated directly from the code repository and reflects real code. All code listings are “pretty-printed” to highlight the appropriate syntax of the programming language.

Cursiva

Indica los términos clave utilizados para describir algoritmos y estructuras de datos. También se utiliza cuando se hace referencia a variables dentro de la descripción en pseudocódigo de un ejemplo.

Constant width

Indica el nombre de elementos de software reales dentro de una implementación, como una clase Java, el nombre de una matriz dentro de una implementación C y constantes como true o false.

Citamos numerosos libros, artículos y sitios web a lo largo del libro. Estas citas aparecen en el texto utilizando paréntesis, como (Cormen et al., 2009), y cada capítulo se cierra con un listado de las referencias utilizadas dentro de ese capítulo. Cuando la cita de referencia sigue inmediatamente al nombre del autor en el texto, no duplicamos el nombre en la referencia. Así, nos referimos a los libros El arte de programar ordenadores de Donald Knuth (1998) incluyendo sólo el año entre paréntesis.

Todas las URL utilizadas en el libro se verificaron en enero de 2016, e intentamos utilizar sólo URL que deberían existir durante algún tiempo. Incluimos URL pequeñas, como http://www.oreilly.com, directamente dentro del texto; de lo contrario, aparecen en notas a pie de página y dentro de las referencias al final de un capítulo.

Utilizar ejemplos de código

El material complementario (ejemplos de código, ejercicios, etc.) se puede descargar en https://github.com/heineman/algorithms-nutshell-2ed.

Este libro está aquí para ayudarte a hacer tu trabajo. En general, si se ofrece código de ejemplo con este libro, puedes utilizarlo en tus programas y documentación. No es necesario que te pongas en contacto con nosotros para pedirnos permiso, a menos que estés reproduciendo una parte importante del código. Por ejemplo, escribir un programa que utilice varios trozos de código de este libro no requiere permiso. Vender o distribuir un CD-ROM de ejemplos de los libros de O'Reilly sí requiere permiso. Responder a una pregunta citando este libro y el código de ejemplo no requiere permiso. Incorporar una cantidad significativa de código de ejemplo de este libro en la documentación de tu producto sí requiere permiso.

Agradecemos, pero no exigimos, la atribución. Una atribución suele incluir el título, el autor, la editorial y el ISBN. Por ejemplo"Algorithms in a Nutshell, Segunda Edición" de George T. Heineman, Gary Pollice y Stanley Selkow. Copyright 2016 George Heineman, Gary Pollice y Stanley Selkow, 978-1-4919-4892-7".

Si crees que el uso que haces de los ejemplos de código no se ajusta al uso legítimo o al permiso concedido anteriormente, no dudes en ponerte en contacto con nosotros en [e-mail].

Libros Safari® en línea

Nota

Safari Books Online es una biblioteca digital a la carta que ofrece contenido experto, tanto en forma de libro como de vídeo, de los autores más destacados del mundo en tecnología y empresa.

Los profesionales de la tecnología, los desarrolladores de software, los diseñadores web y los profesionales empresariales y creativos utilizan Safari Books Online como recurso principal para la investigación, la resolución de problemas, el aprendizaje y la formación en certificación.

Safari Books Online ofrece una gama de planes y precios para empresas, administraciones públicas, educación y particulares.

Los miembros tienen acceso a miles de libros, vídeos de formación y manuscritos previos a la publicación en una base de datos en la que se pueden realizar búsquedas completas, de editoriales como O'Reilly Media, Prentice Hall Professional, Addison-Wesley Professional, Microsoft Press, Sams, Que, Peachpit Press, Focal Press, Cisco Press, John Wiley & Sons, Syngress, Morgan Kaufmann, IBM Redbooks, Packt, Adobe Press, FT Press, Apress, Manning, New Riders, McGraw-Hill, Jones & Bartlett, Course Technology y cientos más. Para más información sobre Safari Books Online, visítanos en Internet.

Cómo contactar con nosotros

Dirige tus comentarios y preguntas sobre este libro a la editorial:

• O'Reilly Media, Inc.
• 1005 Gravenstein Highway Norte
• Sebastopol, CA 95472
• 800-998-9938 (en Estados Unidos o Canadá)
• 707-829-0515 (internacional o local)
• 707-829-0104 (fax)

Tenemos una página web para este libro, donde se enumeran erratas, ejemplos y cualquier información adicional. Puedes acceder a esta página en http://bit.ly/algorithms_nutshell_2e.

Para hacer comentarios o preguntas técnicas sobre este libro, envía un correo electrónico a [e-mail].

Para más información sobre nuestros libros, cursos, conferencias y noticias, consulta nuestro sitio web en http://www.oreilly.com.

Encuéntranos en Facebook: http://facebook.com/oreilly

Síguenos en Twitter: http://twitter.com/oreillymedia

Míranos en YouTube: http://www.youtube.com/oreillymedia

Agradecimientos

Queremos agradecer a los revisores del libro su atención al detalle y sus sugerencias, que mejoraron la presentación y eliminaron defectos de borradores anteriores: De la primera edición Alan Davidson, Scot Drysdale, Krzysztof Duleba, Gene Hughes, Murali Mani, Jeffrey Yasskin y Daniel Yoo. Para la segunda edición: Alan Solis, Robert P. J. Day y Scot Drysdale.

George Heineman quiere dar las gracias a quienes le ayudaron a inculcarle la pasión por los algoritmos, como los profesores Scot Drysdale (Dartmouth College) y Zvi Galil (Universidad de Columbia, ahora Decano de Informática en Georgia Tech). Como siempre, George da las gracias a su mujer, Jennifer, y a sus hijos Nicholas (que ahora ha empezado a aprender a programar) y Alexander (al que le encanta hacer creaciones de origami con los borradores impresos de esta edición).

Gary Pollice quiere dar las gracias a su mujer Vikki por 46 años estupendos. También quiere dar las gracias al departamento de informática de WPI por un gran ambiente y un gran trabajo.

Stanley Selkow quiere dar las gracias a su mujer, Deb. Este libro ha sido un paso más en su largo camino juntos.