Algoritmos de aprendizaje

Prefacio

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

A quién va dirigido este libro

Si estás leyendo este libro, supongo que ya tienes conocimientos de un lenguaje de programación, como Python. Si nunca has programado, te animo a que aprendas primero un lenguaje de programación y luego vuelvas a leerlo. En este libro utilizo Python porque es accesible tanto para programadores como para no programadores.

Los algoritmos se diseñan para resolver problemas comunes que surgen con frecuencia en las aplicaciones de software. Cuando enseño algoritmos a estudiantes universitarios, intento tender un puente entre los conocimientos previos de los estudiantes y los conceptos de algoritmo que estoy enseñando. Muchos libros de texto tienen explicaciones cuidadosamente redactadas, pero siempre demasiado breves. Sin una guía que explique cómo navegar por este material, los estudiantes suelen ser incapaces de aprender algoritmos por sí mismos.

En un párrafo y en la Figura P-1, te muestro mi objetivo para el libro. Presento una serie de estructuras de datos que explican cómo organizar la información utilizando tipos primitivos de tamaño fijo, como valores enteros de 32 bits o valores de coma flotante de 64 bits. Algunos algoritmos, como la Búsqueda de Matrices Binarias, funcionan directamente sobre estructuras de datos. Los algoritmos más complicados, especialmente los algoritmos de grafos, se basan en una serie de tipos de datos abstractos fundamentales, que introduzco según sea necesario, como las pilas o las colas de prioridad. Estos tipos de datos proporcionan operaciones fundamentales que pueden implementarse eficazmente eligiendo la estructura de datos adecuada. Al final de este libro, comprenderás cómo consiguen su rendimiento los distintos algoritmos. Para estos algoritmos, mostraré implementaciones completas en Python o te remitiré a paquetes de Python de terceros que proporcionan implementaciones eficientes.

Si revisas los recursos de código asociados que se proporcionan con el libro, verás que para cada capítulo hay un archivo Python book.py que puede ejecutarse para reproducir todas las tablas del libro. Como se dice en el negocio, "tu kilometraje puede variar", pero las tendencias generales seguirán apareciendo.

Figura P-1. Resumen del contenido técnico del libro

Al final de cada capítulo del libro hay ejercicios de desafío que te dan la oportunidad de poner a prueba tus nuevos conocimientos. Te animo a que los pruebes por tu cuenta antes de revisar mis soluciones de ejemplo, que se encuentran en el repositorio de código del libro.

Sobre el Código

Todo el código de este libro puede encontrarse en el repositorio GitHub asociado,http://github.com/heineman/LearningAlgorithms. El código se ajusta a Python 3.4 o superior. Cuando procede, me ajusto a las buenas prácticas de Python utilizando métodos de doble guión bajo, como __str()__y __len()__. En todos los ejemplos de código del libro, utilizo una indentación de dos espacios para reducir la anchura del código en la página impresa; el repositorio de código utiliza una indentación estándar de cuatro espacios. En unos pocos listados de código, formateo el código utilizando una declaración abreviada de una línea if como if j == lo: break.

El código utiliza tres bibliotecas Python de código abierto disponibles externamente:

• NumPy versión 1.19.5

• SciPy versión 1.6.0

• NetworkX versión 2.5

NumPy y SciPy se encuentran entre las bibliotecas de código abierto de Python más utilizadas y tienen una amplia audiencia. Utilizo estas bibliotecas para analizar el rendimiento empírico en tiempo de ejecución. NetworkX proporciona una amplia gama de algoritmos eficientes para trabajar con grafos, como se explica en el Capítulo 7; también proporciona una implementación de tipos de datos de grafos lista para usar. El uso de estas bibliotecas garantiza que no reinvente innecesariamente la rueda. Si no tienes instaladas estas bibliotecas, no tendrás ningún problema, ya que te proporciono soluciones.

Todos los resultados de temporización presentados en el libro utilizan el módulo timeit mediante ejecuciones repetidas de un fragmento de código. A menudo, el fragmento de código se ejecuta un número repetido de veces para garantizar que se puede medir con precisión. Tras varias ejecuciones, se utiliza el tiempo mínimo como rendimiento de temporización, no la media de todas las ejecuciones. Se suele considerar que ésta es la forma más eficaz de obtener una medición precisa del tiempo, porque calcular la media de varias ejecuciones puede sesgar los resultados del tiempo cuando algunas ejecuciones del rendimiento se ven afectadas por factores externos, como la ejecución de otras tareas del sistema operativo.

Cuando el rendimiento de un algoritmo sea muy sensible a su entrada (como el Ordenamiento por inserción del Capítulo 5), indicaré claramente que estoy tomando la media de todas las ejecuciones de rendimiento.

El repositorio de código contiene más de 10.000 líneas de código Python, con scripts para ejecutar todos los casos de prueba y calcular las tablas presentadas en el libro; también se pueden reproducir muchas de las tablas y gráficos. El código está documentado utilizando las convenciones docstring de Python, y la cobertura del código es del 95%, utilizando https://coverage.readthedocs.io.

Si tienes una pregunta técnica o un problema al utilizar los ejemplos de código, envía un correo electrónico a [e-mail].

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 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í requierepermiso.

Agradecemos la atribución, pero en general no la exigimos. Una atribución suele incluir el título, el autor, la editorial y el ISBN. Por ejemplo: "Aprendizaje de Algoritmos: Guía del programador para escribir mejor código ", de George T. Heineman (O'Reilly). Copyright 2021 George T. Heineman, 978-1-492-09106-6".

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].

Convenciones utilizadas en este libro

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

Cursiva

Indica nuevos términos, URL, nombres de archivo, extensiones de archivo y puntos en los que quiero hacer hincapié.

Constant width

Se utiliza en los listados de programas y dentro de los párrafos para referirse a elementos del programa como nombres de variables o funciones, tipos de datos, sentencias y palabras clave.

Consejo

Este elemento, identificado por la imagen de un lémur de cola anillada, es una punta o sugerencia. Utilizo esta imagen porque los lémures tienen un campo visual combinado de hasta 280°, que es un campo visual más amplio que el de los primates antropoides (como los humanos). Cuando veas este icono de sugerencia, te estoy pidiendo literalmente que abras más los ojos para aprender un nuevo dato o capacidad de Pitón.

Nota

Este elemento, identificado con la imagen de un cuervo, significa una nota general. Numerosos investigadores han determinado que los cuervos son animales inteligentes que resuelven problemas; algunos incluso utilizan herramientas. Utilizo estas notas para definir un término nuevo o llamar tu atención sobre un concepto útil que debes comprender antes de avanzar a la página siguiente.

Advertencia

Este elemento, identificado por la imagen de un escorpión, indica una advertencia o precaución. Como en la vida real, cuando veas un escorpión, ¡detente y mira! Utilizo el escorpión para llamar la atención sobre los retos clave que debes afrontar al aplicar algoritmos.

Aprendizaje en línea O'Reilly

Nota

Durante más de 40 años, O'Reilly Media ha proporcionado formación tecnológica y empresarial, conocimientos y perspectivas para ayudar a las empresas a alcanzar el éxito.

Nuestra red única de expertos e innovadores comparten sus conocimientos y experiencia a través de libros, artículos y nuestra plataforma de aprendizaje online. La plataforma de aprendizaje en línea de O'Reilly te ofrece acceso bajo demanda a cursos de formación en directo, rutas de aprendizaje en profundidad, entornos de codificación interactivos y una amplia colección de textos y vídeos de O'Reilly y de más de 200 editoriales. Para más información, visita http://oreilly.com.

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 https://oreil.ly/learn-algorithms.

Envía un correo electrónico a [e-mail] para comentar o hacer preguntas técnicas sobre este libro.

Para obtener noticias e información sobre nuestros libros y cursos, visita http://oreilly.com.

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

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

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

Agradecimientos

Para mí, el estudio de los algoritmos es la mejor parte de la informática. Gracias por darme la oportunidad de presentaros este material. También quiero dar las gracias a mi mujer, Jennifer, por su apoyo en otro proyecto de libro, y a mis dos hijos, Nicholas y Alexander, que ya tienen edad suficiente para aprender a programar.

Mis editores de O'Reilly -Melissa Duffield, Sarah Grey, Beth Kelly y Virginia Wilson- mejoraron el libro ayudándome a organizar los conceptos y sus explicaciones. Mis revisores técnicos -Laura Helliwell, Charlie Lovering, Helen Scott, Stanley Selkow y Aura Velarde- me ayudaron a eliminar numerosas incoherencias y a aumentar la calidad de las implementaciones y explicaciones de los algoritmos. Todos los defectos que subsisten sonresponsabilidad mía.