Introducción al análisis de algoritmos
El Curso Introductorio de Análisis de Algoritmos con Julia (Téllez Avila 2025) de Eric Sadit Téllez Avila presenta una introducción a algoritmos básicos de ordenamiento y búsqueda de información, que constituyen la base de los sistemas de búsqueda. El libro desarrolla los conceptos de una forma incremental y fácil de seguir, incluso para una persona con un nivel inicial básico en la materia, como fue mi caso. Aunque la exposición del material no requiere el uso de un lenguaje de programación específico, los ejemplos se presentan en Julia, lo que constituye una oportunidad de aprender este lenguaje para una persona que maneje lenguajes similares como R o Python, aunque también plantea desafíos en lo que respecta a la facilidad de uso de este lenguaje con otros programas.
El Dr. Téllez es investigador del Sistema Nacional de Investigadores, nivel 2, adscrito al Centro de Investigación e Innovación en Tecnologías de la Información y Comunicación desde 2014. Sus líneas de investigación son la similitud en espacios métricos, la categorización automática de texto y la inteligencia computacional. Sobre estos temas, ha publicado al menos 23 artículos en revistas indexadas y participado en diversos congresos especializados.1
Aunque los algoritmos que se analizan en el Curso tratan sobre sus líneas de investigación, no es claro para un estudiante cuál es el enfoque del curso sino hasta el final del material. En efecto, en el último video del último capítulo del libro, plantea que los algoritmos se insertan dentro del área de Recuperación de Información y permiten realizar eficientemente multiplicación de matrices dispersas, útiles en el cálculo de distancias en espacios métricos como los obtenidos mediante encajes vectoriales de un corpus y un texto de búsqueda. Si bien este conocimiento no es relevante para entender los algoritmos desarrollados a lo largo del curso, presenta una aplicación práctica que puede ser motivacional al momento de estudiarlos (Téllez Avila 2025, sec. 6.1).
De cualquier modo, conocer esta aplicación al final permite obtener perspectiva sobre el desarrollo del libro, que resulta bastante útil para el aprendizaje. Esta perspectiva no se observa durante el camino, que es así:
El capítulo 1 introduce al estudiante de forma general al lenguaje
Julia, al señalar las principales estructuras de datos, controles de flujo, programación de funciones, entre otras. Aunque esta sección contiene los elementos principales del lenguaje, puede resultar muy general para un primer acercamiento al mismo. Yo encontré muy útil el estudio de Downey y Lauwens (2018) para aprender a utilizar el programa; además, dado que sigue muy de cerca la estructura de Downey (2024), es muy útil para que un estudiante que ya dominePythonpueda comparar cómo se realizan operaciones en ambos lenguajes.El capítulo 2 establece las bases de la notación asintótica, que permite identificar cuáles algoritmos son mejores que otros en la ejecución de una tarea. En el post sobre órdenes de crecimiento se analizan las funciones de crecimiento planteadas en dicho capítulo. Este material se utiliza en todos los capítulos subsiguientes, al considerar cuál es el costo de ejecución de cada algoritmo de ordenamiento, comparación e intersección y sirve para determinar la preferencia por algoritmos adaptativos a las instancias del problema.
El capítulo 3 trata sobre las estructuras de datos comunmente utilizadas para representar la información, tales como listas y conjuntos. Estos últimos se analizan detalladamente en el último capítulo, pero su representación en memoria es simplemente como una lista de elementos únicos organizados. Además de estos, resulta de interés la definición de estructuras de datos en
Juliaque se introduce en este capítulo. También resultan de interés las matrices, que son fundamentales para la aplicación práctica que se señaló en el párrafo anterior. Sobre estas, en el post sobre operaciones matriciales se profundizan las diferentes operaciones.La representación de conjuntos como un arreglo ordenado de elementos únicos es un concepto clave, pues aunque no es explícito en el texto, todo el resto del material se basa en esta interpretación: hay un capítulo sobre algoritmos para odenar elementos, otro sobre búsqueda para insertar un elemento sin dañar la propiedad de ordenamiento de una lista ordenada y otro sobre unión e intersección de conjuntos. Este último, es útil para realizar las operaciones matriciales que se señalaron antes, pero sobre matrices dispersas, como las que se obtienen en el área de Recuperación de Información.
El capítulo 4 trata sobre algoritmos que se utilizan para ordenar una lista de elementos. Algunos algoritmos utilizan estructuras de datos especializadas para facilitar el ordenamiento de la información, tales como las pilas y las “SkipLists”, por lo que se aplica parte de lo planteado en el capítulo anterior. En el post sobre algoritmos de ordenamiento se realizan diversos experimentos sobre estos algoritmos, en los cuales se obtuvieron resultados cercanos a los teóricamente esperados, según el análisis de ellos en el capítulo.
El capítulo 5 analiza modelos de búsqueda por comparación, en los que se parte de un arreglo ordenado y se busca la posición en la que se debería insertar un valor de interés, de forma tal que el arreglo se mantenga ordenado después de la inserción.2 En el capítulo se desarrollan modelos que permiten obtener el resultado de forma rápida en arreglos extremadamente grandes; estos no dependen del tamaño del arreglo sino de la respuesta del problema. Aunque en el post sobre algoritmos de búsqueda estos fueron implementados, en los experimentos realizados no se obtuvo el rendimiento teórico esperado, por lo que es necesario un análisis más detallado sobre los mismos.
Finalmente, el capítulo 6 analiza problemas de unión e intersección de conjuntos. Para ello, cada elemento de un conjunto (el más pequeño, si son de tamaños muy diferentes) se busca en el otro mediante los algoritmos del capítulo anterior y, al verificar si el elemento de este último es igual, menor o mayor, se determina si debe incorporarse o no al conjunto de respuesta. Debido a que los algoritmos son adaptables, se obtienen rendimientos teóricos eficientes al hacer este ejercicio. No obstante, en el post sobre unión e intersección de conjuntos, no se observaron líneas de tendencia tan claras como las que se esperaban teóricamente.
Aunque el libro no continúa con el desarrollo del problema, el capítulo 6 es importante porque sienta las bases necesarias para realizar la multiplicación de matrices dispersas. Como se analizó en el post sobre operaciones matriciales, si \(A = (a_{ij}), \, B = (b_{ij})\) son matrices conformables, entonces \(AB = C = (c_{ij}) = \left(\sum_k a_{ik} b_{kj}\right)\). Sin embargo, los elementos de la sumatoria en el último paréntesis solo resultan relevantes para esta cuando \(a_{ik} \neq 0\) y \(b_{kj} \neq 0\). Esta última condición se puede verificar a partir de los algoritmos señalados en el último capítulo si se representan la k-ésima fila de \(A\) como un conjunto de tuplas \(\{(k, a_{ik}): a_{ik} \neq 0\}\) y la k-ésima columna de \(B\) de forma similar como \(\{ (k, b_{kj}): b_{kj} \neq 0 \}\), en cuyo caso los elementos de la sumatoria son los que corresponden a la intersección, respecto al primer elemento ordenado de la tupla, de ambos conjuntos. A partir de este resultado, se simplifica enormemente el cómputo de multiplicaciones de matrices que contienen encajes vectoriales de un corpus sobre el que se desea localizar información, con otras que contienen los encajes de las búsquedas que se desean realizar. Este último, es un problema básico para encontrar la distancia coseno entre los textos, que es la base de los motores de búsqueda modernos.
El uso de Julia resulta interesante, pero no es necesario para el curso. Es interesante, pues se trata de un lenguaje de alto nivel pero de alto rendimiento, al ser compilado. En este sentido, combina la facilidad de uso de lenguajes como R, al que se parece mucho, con la rapidez de otros más complejos como C. Sin embargo, puede resultar muy complejo utilizarlo con otro tipo de software, pues hay fallas en su integración con VSCode o Quarto que no se encuentran completamente solucionadas. Por ejemplo, en mi trabajo me encontré ocasionalmente con problemas de kernel muerto que no pude solucionar fácilmente en Windows, por lo que debía renderizar los documentos generados en Ubuntu; este tipo de problemas resultan frustrantes y pueden hacer más lento el proceso de aprendizaje.
En resumen, se puede decir que el curso de Téllez Avila (2025) es una introducción al análisis de algoritmos útil en el campo de la recuperación de información. Incluso si el estudiante no tiene experiencia previa con esta clase de algoritmos, el enfoque incremental del material permite que puedan desarrollarse las habilidades necesarias para continuar hasta el final. Sin embargo, un área de oportunidad para el libro es plantear con mayor claridad la motivación del orden en que se desarrolla el material: la forma en que los algoritmos se insertan en el área general de recuperación de información.