Inicio

De cero a ninja en algoritmos (Parte 1)

Los algoritmos están en todas partes. Son los que analizan nuestra información para obtener datos importantes. Estos los usa Facebook para ganar mucho dinero. También están analizando toda la información que hay en internet a cada instante. Ese se llama PageRank y es usado por Google. Y ahora hasta son capaces de aprender, como los usados por Spotify para recomendarte cada vez mejores canciones.

Después de tantos años junto a algoritmos, programando algunas cosas menores, se me dio por comprenderlos. Guiado tal vez por la curiosidad de la inteligencia artificial, redes neuronales y otros temas ‘cool’ de la tecnología actual. Comenzaré con esta serie de artículos que van desde cero hasta nivel ninja en algoritmos. Aquí emprendemos el camino hacia la parte difícil, pero emocionante de las ciencias computacionales.🏃‍

Algoritmo ¿Qué es?

No existe un consenso en cuanto a la definición exacta de lo que es un algoritmo. Nosotros aquí lo vamos a definirlo en palabras sencillas, pero luego a partir de ahí iremos desglosando otros conceptos que sí tienen una definición exacta y matemática.

Un algoritmo es un conjunto de procedimientos que toman un valor o conjunto de valores llamados inputs y a partir de ellos genera otro valor o conjunto de valores llamados outputs.

Gráficamente se vería algo así, como un conjunto de pasos a seguir para ir del input al output.

Observamos que para llegar del punto A al punto B pudimos haber tomado dos caminos, quizá uno más eficiente como la linea roja u otro menos eficiente como el camino naranja. Cada camino representa un algoritmo distinto, bajo esta analogía nos damos cuenta de que pueden existir diversos algoritmos, algunos más eficientes y otros no tanto, para un mismo objetivo.

Esa es la razón por la cual se estudia y analizan los algoritmos, para verificar si un algoritmo puede resolver un problema de manera rápida, lenta o quizá no lo puede resolver. Tratamos de buscar esta respuesta a priori, osea antes de implementar nuestro algoritmo en una computadora. De eso se encarga el analisis matemático de algoritmos.

Otra razón por la que estudiamos algoritmos es para aprender tecnicas de resolución de problrmas para luego aplicarlos en otros problemas similares. Por ejemplo, si aprendemos bien los algoritmos de ordenamiento podremos aplicar dichas tecnicas para desarrollar aplicaciones que trabajen con muchos datos pero a la vez sean eficientes al mostrar los datos.

Una forma ordenar nuestra información

Lo primero que aprenderemos son las estructuras de datos. Estos son formas de almacenar los datos de tal forma que sea más facil solucionar un problema. A menudo un algoritmo esta relacionado con una estructura de datos especifica.

Pero… ¿Cómo sé que el algoritmo es correcto?

Para probar si un algoritmo es correcto hace falta algún modo de saber si una respuesta es correcta. Básicamente se trata de comprobar la respuesta usando otro algoritmo. Por ejemplo, puedes hallar la raíz de un número usando un algoritmo, pero puedes comprobar si esa raíz es correcta usando otro algoritmo que simplemente sería elevando el número al cuadrado. Sin embargo, esto no se puede hacer en muchos casos. Es más, si fuera igual de fácil comprobar una respuesta, así como hacer el algoritmo que me de dichas respuestas, estaríamos resolviendo uno de los problemas del milenio, el famoso P vs NP. Pero entonces, a qué llamamos un algoritmo correcto. Para eso comencemos definiendo qué es un input correcto o instancia del problema. Un input especifico que cumple todos los requisitos para ingresar al algoritmo, es conocido como instancia del problema. El número 4 como input para el algoritmo de la raíz es correcto, así que 4 sería una instancia del problema.

Un algoritmo es correcto si para cada instancia del problema nuestro algoritmo es capaz de hallar una salida correcta. Por otro lado, si el algoritmo no se detiene o se detiene, pero proporciona una respuesta incorrecta, el algoritmo es obviamente incorrecto.

Y exactamente cómo se miden

Para esto necesitamos calcular la eficiencia del algoritmo. Una forma de hacerlo seria programando el algoritmo y tomando el tiempo de cuanto demora en hallar una respuesta para un input determinado. Sin embargo, esta medida solo sería valida para la computadora que lo comprobó, ya que, al cambiar de computadora el tiempo calculado podría variar, ya sea por cambios de procesador, lenguaje de programación u otros factores. Es por esto que surgen métodos para calcular la eficiencia del algoritmo según el tiempo de ejecución, independientemente de la máquina en la que se ejecute el algoritmo.

El tiempo que un algoritmo tarda en resolver un problema de input de tamaño n se llama Tiempo de ejecución T(n). La unidad del T(n) no puede ser una magnitud de tiempo real como el segundo. Expliquemos el porqué. Un algoritmo puede demorar un segundo en una computadora A y 2 segundos en una computadora B para el mismo problema, pero para nuestro análisis el tiempo sería el mismo, ya que se trata del mismo algoritmo y el mismo input. La diferencia de tiempos es por culpa de la computadora y nosotros tratamos de medir los tiempos independientemente de esta. Es por esto que no usamos una magnitud de tiempo real. En su lugar usamos el número de operación elemental (OE) realizadas por el algoritmo, bajo el supuesto de que cada una de estas operaciones elementales se realizan en una unidad de tiempo.

A continuación comienza lo emocionante de este tema, las definiciones matemáticas para lograr una rigurosidad en todo lo que decimos. No se preocupen trataré de ser lo más claro posible en cada definición. Así que continuemos.

Definición matemática de T

TT es una función cuyo conjunto de entrada es AA y conjunto de salida son los reales positivos R+\mathbb{R}^+. Donde TT asigna un elemento αA\alpha \subset A al elemento T(α)T(\alpha ).

T:AR+T: A\rightarrow \mathbb{R}^{+} αT(α)\alpha \mapsto T(\alpha )

AA es el conjunto donde se encuentran los inputs para el algoritmo, por esta razón es el conjunto de partida. El conjunto de llegada al ser la suma de las operaciones elementales no puede tomar un valor negativo, por lo tanto son todos los reales positivos R+\mathbb{R}^{+}.

Es básicamente la notación matemática de una función. No restemos valor a esta notación pues es la manera formal de definir la función TT, mostrando claramente sus conjuntos de partida y de llegada y de qué forma se relacionan sus elementos.

Sin embargo, en matemáticas siempre se busca simpleficar los modelos para su mejor entendimiento y estudio. En la definición que dimos el conjunto AA que puede contener números, matrices, palabras, etc. Este conjunto de entrada se puede simplificar a un número natural que nos indique el tamaño de la entrada, al cual llamaremos nn, este por su naturaleza deberá ser un número natural.

Principio de invarianza

Este principio nos dice que si tenemos dos máquinas o dos implementaciones de un mismo algoritmo, una de estas solo puede resolver un problema 2, 3, 4 o cc veces más veloz que otra máquina menos potente, donde c es un número real positivo. Es decir, solo un cambio en el algoritmo, más no en su implementación o en la computadora en la que se implemente, nos proporcionará un aumento diferenciado y no solo multiplicativo en el tiempo de ejecución.

Formalmente:

Dado un algoritmo y dos implementaciones suyas I1I_1 e I2I_2 que tardan T1(n)T_1(n) y T2(n)T_2(n) respectivamente. El principio de invarianza afirma que existe una constante real c>0c>0 y un número natural n0n_0 tales que para todo nnn\geqslant n se verifica que:

T1(n)cT2(n)T_1(n)\leqslant c\cdot T_2(n)

La gráfica de algunos tiempos de ejecución pueden ser más altos que otros solo hasta cierto punto y despues disminuir o viceversa, por eso usamos el valor de n0n_0 el cual indicará a partir de que número se cumple la desigualdad.

Continuará…