2 Introducción al análisis de algoritmos con Julia

Este capítulo introduce a los fundamentos de análisis de algoritmos. Se introduce el concepto de modelo de cómputo y la notación asintótica, preparandonos para usar el lenguaje común en el análisis de algoritmos. También se mostrarán algunos de los ordenes de crecimiento más representativos, que nos permitirán comparar algoritmos que resuelvan una tarea dada, así como catalogarlos con respecto a los recursos de computo necesarios para ejecutarlos.

2.1 Concepto de algoritmo y estructura de datos

Los algoritmos son especificaciones formales de los pasos u operaciones que deben aplicarse a un conjunto de entradas para resolver un problema, obteniendo una solución correcta a dicho problema. Establecen los fundamentos de la programación y delinean la manera en como se diseñan los programas de computadoras.

Es común encontrar que un problema puede ser resuelto por múltiples algoritmos, cada uno de ellos con sus diferentes particularidades. Así mismo, un problema suele estar conformado por una cantidad enorme de instancias de dicho problema, por ejemplo, para una lista de $n$ números, existen $n!$ formas de acomodarlos, de tal forma que puedan ser la entrada a un algoritmo cuya entrada sea una lista de números donde el orden es importante. En ocasiones, los problemas pueden tener infinitas de instancias. En este curso nos enfocaremos en problemas que pueden ser simplificados a una cantidad finita instancias.

Cada paso u operación en un algoritmo esta bien definido y puede ser aplicado o ejecutado para producir un resultado. A su vez, cada operación suele tener un costo, dependiente del módelo de computación. Conocer el número de operaciones necesarias para transformar la entrada en la salida esperada, i.e., resolver el problema, es de vital importancia para seleccionar el mejor algoritmo para dicho problema, o aun más, para instancias de dicho problema que cumplen con ciertas características.

Una estructura de datos es una abstracción en memoria de entidades matemáticas y lógicas que nos permite organizar, almacenar y procesar datos en una computadora. El objetivo es que la información representada puede ser manipulada de manera eficiente en un contexto específico, además de simplificar la aplicación de operaciones para la aplicación de algoritmos.

2.2 Modelos de cómputo

Un modelo de cómputo es una abstracción matemática de una computadora o marco de trabajo algorítmico que nos permite estudiar y medir los costos de los algoritmos funcionando en este modelo de tal forma que sea más simple que una computadora física real. Ejemplos de estos modelos:

Todas estos modelos son equivalentes en sus capacidades, pero sus diferentes planteamientos permiten enfocarse en diferentes aspectos de los problemas.

2.2.1 Máquina de Turing

Es un módelo creado por Alan Turing a principios del siglo XX; la idea es un dispositivo que podría ser implementada de manera mecánica si se tuvieran recursos infinitos; esta máquina puede leer y escribir mediante un cabezal en una cinta infinita (ver Figura 2.1) una cantidad de símbolos predeterminada para cada problema siguiendo una serie de reglas simples sobre lo que lee y escribe, dichas reglas y la cienta, forman una máquina de estados y memoria, que pueden realizar cualquier cálculo.

Figura 2.1: Cabezal y cinta.

Una máquina de Turing se puede escribir como una tupla de 7 elementos $M=(Q, \Sigma, \Gamma, s, \epsilon, F, \delta)$ donde:

$Q$ es un conjunto finito de estados.
$\Sigma$ es el alfabeto de entrada, i.e., un conjunto finito de símbolos que no incluye el espacio en blanco.
$\Gamma$ es el alfabeto de la cinta , i.e., un conjunto finito de símbolos $\Sigma \subseteq \Gamma$.
$s \in Q$ es el estado inicial.
$\epsilon \in \Gamma$ es un símbolo especial denominado blanco; y puede llenar la cinta al infinito.
$F \subseteq Q$ conjunto de estados finales de aceptación.
$\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$, es la función de transición, i.e., una función parcial que índica que se debe hacer al leer un símbolo en la posición actual de lectura, esto es, qué se escribe, hacia que estado se cambia, y la dirección de movimiento de la cinta (siempre se mueve en una celda).

Hay muchas variantes de la definición de máquina de Turing, por ejemplo, una cinta especial para lectura y una para escritura, diferentes formas de definir las transiciones, símbolos para no moverse, etc. Hasta ahora, todas las formas son a lo más equivalentes en términos de poder de cómputo, la diferencia viene en la expresividad para definir soluciones.

Es cómun plantear los problemas en forma de lenguajes; esto es, en términos de dada la cadena S ¿la máquina $M$ la acepta?, dónde acepta quiere decir que la máquina es capaz de ir desde el estado inicial al estado de aceptación leyendo/transformando $S$. Si $M$ no termina en un estado de aceptación, entonces se implica el fallo o respuesta negativa.

Nota

Algunas causas de fallo son que la función de transición no este definida para un estado y símbolo particular y el no alcanzar un estado de salida aceptación.

Por ejemplo, sea $M_{01}$ una máquina capaz de detectar $n \geq 0$ ceros terminados por un único $1$. Entonces

\[M_{01} = (\{q_0, q_1, q_2\}, \{\mathtt{0}, \mathtt{1}\}, \{\mathtt{0}, \mathtt{1}, \mathtt{X}, \mathtt{\epsilon} \}, q_0, \mathtt{\epsilon}, \{q_2\}, \delta_{01})\]

donde la función de transición se define como:

\[\begin{align} \delta_{01}(q_0, \mathtt{0}) &= (q_0, \mathtt{X}, \mathtt{R}) \\ \delta_{01}(q_0, \mathtt{1}) &= (q_1, \mathtt{X}, \mathtt{R}) \\ \delta_{01}(q_1, \mathtt{\epsilon}) &= (q_2, \mathtt{\epsilon}, \mathtt{R}) \\ \end{align}\]

Dada la regularidad de la función de transición, es común escribirla como una tabla:

entrada	salida
$(q_0, \mathtt{0})$	$(q_0, \mathtt{X}, \mathtt{R})$
$(q_0, \mathtt{1})$	$(q_1, \mathtt{X}, \mathtt{R})$
$(q_1, \mathtt{\epsilon})$	$(q_2, \mathtt{\epsilon}, \mathtt{R})$

Una máquina de Turing se puede representar mediante un autómata

Figura 2.2: Ejemplo de máquina de Turing que reconoce cadenas $0^n 1$

Supongamos ahora el problema de reconocer cadenas $0^n 1^n$; para esto podemos definir la siguiente máquina de Turing \[M = (\{q_0, q_1, q_2, q_3, q_4\}, \{\mathtt{0}, \mathtt{1}\}, \{\mathtt{0}, \mathtt{1}, \mathtt{X}, \mathtt{Y}, \mathtt{\epsilon}\}, q_0, \mathtt{\epsilon}, \{q_4\}, \delta),\] donde la función de transición es como sigue:

\[\begin{align*} \delta(q_0, \mathtt{0}) &= (q_1, \mathtt{X}, \mathtt{R}) \\ \delta(q_0, \mathtt{Y}) &= (q_3, \mathtt{Y}, \mathtt{R}) \\ \delta(q_1, \mathtt{0}) &= (q_1, \mathtt{0}, \mathtt{R}) \\ \delta(q_1, \mathtt{1}) &= (q_2, \mathtt{Y}, \mathtt{L}) \\ \delta(q_1, \mathtt{Y}) &= (q_1, \mathtt{Y}, \mathtt{R}) \\ \delta(q_2, \mathtt{0}) &= (q_2, \mathtt{0}, \mathtt{L}) \\ \delta(q_2, \mathtt{X}) &= (q_0, \mathtt{X}, \mathtt{R}) \\ \delta(q_2, \mathtt{Y}) &= (q_2, \mathtt{Y}, \mathtt{L}) \\ \delta(q_3, \mathtt{Y}) &= (q_3, \mathtt{Y}, \mathtt{R}) \\ \delta(q_3, \mathtt{\epsilon}) &= (q_4, \mathtt{\epsilon}, \mathtt{R}) \\ \end{align*}\]

Figura 2.3: Ejemplo de máquina de Turing que reconoce cadenas $0^n 1^n$

Todo inicia con una cadena de la forma esperada, e.g., $\mathtt{000111}$, la idea general del algoritmo es aparear $\mathtt{0}$’s y $\mathtt{1}$’s, ya que solo es valido si ambas subcadenas tienen igual longitud. Para esto se marcan los $\mathtt{0}$’s vistos con $\mathtt{X}$ y los $\mathtt{1}$’s con $\mathtt{Y}$. La máquina estará entonces marcando las primeras ocurrencias y moviendose a traves de la cinta para encontrar los correspondientes.

Importante

Las máquinas de Turing son capaces del representar cualquier problema cómputable con una analogía mecánica, lo cual hace evidente su implementación en el mundo físico.

2.2.2 Modelos funcionales

Funciones recursivas. Se basa en funciones que trabajan sobre los números naturales y que definen en conjunto el espacio de funciones computables. Son una herramienta abstracta que permite a los teóricos de la lógica y computación establecer los límites de lo computable.
Cálculo lambda. Es un módelo creado por Alonzo Church y Stephen Kleene a principios del siglo XX, al igual que las funciones recursivas, se fundamenta en el uso de funciones y es una herramienta abstracta con própositos similares, sin embargo el cálculo lambda no se limita a recursiones, y se enfoca en diferentes reglas de reducción y composición de funciones, y es natural la inclusión de operadores de alto nivel, aunque estos mismos sean definidos mediante un esquema funcional.

2.2.3 Máquina de acceso aleatorio (RAM)

Es un módelo que describe una computadora con registros. A diferencia de una computadora física, no tienen limitación en su capacidad, ni en la cantidad de registros, ni en la precisión de los mismos. Cada registro puede ser identicado de manera única y su contenido leído y escrito mediante reglas o instrucciones formando un programa. En particular reconoce las diferencias entre registros de los programas y registros de datos, i.e., arquitectura harvard. Existe un número mínimo de instrucciones necesarias (i.e., incremento, decremento, poner a cero, copiar, salto condicional, parar) pero es común construir esquemas más complejos basados en estas primitivas. Se necesita un registro especial que indica el registro de programa siendo ejecutado. Los accesos a los registros tienen un tiempo constante a diferencia de otros esquemas; es el modelo más cercano a como funciona una computadora moderna entre los que se hemos revisado.

Una computadora moderna difieres de una máquina RAM, por ejemplo, a diferencia de una computadora física se suponen infinitos registros con precisión infinita. Debido a los costos de los semiconductores y la energía necesaría, es conveniente construir computadoras con una jerarquía de memoria: los niveles con mayores prestaciones (e.g., rápidez) son los más escasos. Es importante sacar provecho de esta jerarquía siempre que sea posible. Las operaciones también tienen costos diferentes, dependiendo de su implementación a nivel de circuitería, así como también existe cierto nivel de paralelización que no esta presente en una máquina RAM, tanto a nivel de procesamiento y lectura de datos.

2.3 Sobre la importancia del modelo de cómputo en el curso

En este curso nos enfocaremos en especificaciones de alto nivel, donde los algoritmos son convenientes para una computadora física. Sin embargo, estaremos contando operaciones de interés pensando en costos constantes en el acceso a memoria y en una selección de operaciones, al estilo de una máquina RAM.

La selección de operaciones de interés tiene el espíritu de simplificar el análisis, focalizando nuestros esfuerzos en operaciones que acumulan mayor costo y que capturan la dinámica del resto. Adicionalmente al conteo de operaciones nos interesa el desempeño de los algoritmos en tiempo como magnitud física medible, así como en la cantidad de memoria consumida, por lo que se aboradará el costo realizando mediciones experimentales. Se contrastará con el análisis basado en conteo de operaciones siempre que sea posible.

2.4 Tipos de análisis

La pregunta inicial sería ¿qué nos interesa saber de un algoritmo que resuelve un problema? probablemente, lo primero sería saber si produce resultados correctos. Después, entre el conjunto de las alternativas que producen resultados correctos, es determinante obtener su desempeño para conocer cuál es más conveniente para resolver un problema.

En ese punto, es necesario reconocer que para un problema, existen diferentes instancias posibles, esto es el espacio de instancias del problema, y que cada una de ellas exigirían soluciones con diferentes costos para cada algoritmo. Por tanto existen diferentes tipos de análisis y algoritmos.

Análisis de mejor caso. Obtener el mínimo de resolver cualquier instancia posible, puede parecer poco útil desde el punto de vista de decisión para la selección de un algoritmo, pero puede ser muy útil para conocer un problema o un algoritmo.
Análisis de peor caso. Obtener el costo máximo necesario para resolver cualquier instancia posible del problema con un algoritmo, este es un costo que si nos puede apoyar en la decisión de selección de un algoritmo; sin embargo, en muchas ocasiones, puede ser poco informativo o innecesario ya que tal vez hay pocas instancias que realmente lo amériten.
Análisis promedio. Se enfoca en obtener un análisis promedio basado en la población de instancias del problema para un algoritmo dado.
Análisis amortizado. Se enfoca en análisis promedio pero para una secuencia de instancias.
Análisis adaptativo. Para un subconjunto bien caracterizado del espacio de instancias de un problema busca análizar los costos del algoritmo en cuestión. La caracterización suele estar en términos de una medida de complejidad para el problema; y la idea general es medir si un algoritmo es capaz de sacar provecho de instancias fáciles.

2.5 Notación asintótica

Realizar un conteo de operaciones y mediciones es un asunto complejo que requiere focalizar los esfuerzos. Para este fin, es posible contabilizar solo algunas operaciones de importancia, que se supondrían serían las más costosas o que de alguna manera capturan de manera más fiel la dinámica de costos.

El comportamiento asintótico es otra forma de simplificar y enfocarnos en los puntos de importancia, en este caso, cuando el tamaño de la entrada es realmente grande. Es importante mencionar, que no se esperan entradas de tamaño descomunal, ni tampoco se espera cualquier tipo de entrada.

2.5.1 Notación $\Theta$

Para una función dada $g(n)$ denotamos por $\Theta(g(n))$ el siguiente conjunto de funciones:

\[\begin{align} \Theta(g(n)) &= \left\{ f(n) \mid \text{ existen las constantes positivas }c_1, c_2 \text{ y } n_0 \text{ tal que } \right.\\ ~ & \left. 0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n) \text{ para todo } n \geq n_0 \right\} \\ \end{align}\]

esto es, una función $f(n)$ pertenece al conjunto $g(n)$ si $c_1 g(n)$ y $c_2 g(n)$ pueden cubrirla por abajo y por arriba, para esto deben existen las constantes positivas $c_1$ y $c_2$ y una $n$ lo suficientemente larga, e.g., para eso la constante $n_0$. La notación propiamente de conjuntos puede usarse $f(n) \in \Theta(g(n))$ pero es común en el área usar $f(n) = \Theta(g(n))$ para expresar la pertenencia; este abuso de la notación tiene ventaja a la hora de plantear los problemas de análisis.

2.5.2 Notación $O$

Se utiliza para indicar una cota asintótica superior. Una función $f(n)$ se dice que esta en $O(g(n))$ si esta en el siguiente conjunto:

\[\begin{align} O(g(n)) &= \left\{ f(n) \mid \text{ existen las constantes positivas }c \text{ y } n_0 \text{ tal que } \right.\\ ~& \left. 0 \leq f(n) \leq c g(n) \text{ para todo } n \geq n_0 \right\} \\ \end{align}\]

La notación $O$ se usa para dar una cota superior, dentro de un factor constante. Al escribir $f(n) = O(g(n))$ se indica que $f(n)$ es miembro del conjunto $O(g(n))$; hay que notar que $f(n) = \Theta(g(n))$ implica que $f(n) = O(g(n))$, i.e., $\Theta(g(n)) \subseteq O(g(n))$.

2.5.3 Notación $\Omega$

Al contrario de $O$, la notación $\Omega$ da una cota asintótica inferior. Una función $f(n)$ se dice que esta en $\Omega(g(n))$ si esta en el siguiente conjunto:

\[\begin{align} \Omega(g(n)) = & \left\{ f(n) \mid \text{ existen las constantes positivas }c \text{ y } n_0 \text{ tal que } \right. \\ & \left. 0 \leq c g(n) \leq f(n) \text{ para todo } n \geq n_0 \right\} \\ \end{align}\]

Dado que la $\Omega$ define una cota superior, basicamente si $f(n) = \Omega(g(n))$, entonces $f(n)$ debe estar por encima de $g(n)$ con las constantes $c$ y $n_0$ adecuadas. Al igual que la notación $O$, la notación $\Omega$ es menos estricta que $\Theta$, esto es $f(n) = \Theta(g(n))$ implica que $f(n) = \Omega(g(n))$, por lo que $\Theta(g(n)) \subseteq \Omega(g(n))$.

Por tanto, si $f(n) = O(g(n))$ y $f(n) = \Omega(g(n))$ entonces $f(n) \in \Theta(g(n))$.

Es importante conocer los ordenes de crecimiento más comunes de tal forma que podamos realizar comparaciones rápidas de costos, y dimensionar las diferencias de recursos entre diferentes tipos de costos. La notación asintótica hace uso extensivo de la diferencia entre diferentes ordenes de crecimiento para ignorar detalles y simplificar el análisis de algoritmos.

2.5.4 Apoyo audio-visual

En los siguientes videos se profundiza sobre los modelos de cómputo y los diferentes tipos de análisis sobre algoritmos.

Parte 1:
Parte 2:
Parte 3:

2.5.5 Ordenes de crecimiento

Dado que la idea es realizar un análisis asintótico, las constantes suelen ignorarse, ya que cuando el tamaño de la entrada es suficientemente grande, los términos con mayor orden de magnitud o crecimiento dominarán el costo. Esto es, es una simplificación necesaría.

Los ordenes de crecimiento son maneras de categorizar la velocidad de crecimiento de una función, y para nuestro caso, de una función de costo. Junto con la notación asimptótica nos permite concentrarnos en razgos gruesos que se mantienen para entradas grandes, más que en los detalles, y no perder el punto de interés. A continuación veremos algunas funciones con crecimientos paradigmáticos; las observaremos de poco en poco para luego verlos en conjunto.

2.5.5.1 Costo constante, logaritmo y lineal

La siguiente figura muestra un crecimiento nulo (constante), logaritmico y lineal. Note como la función logarítmica crece lentamente.

using Plots, LaTeXStrings
n = 300 # 300 puntos

plot(1:n, [10 for x in 1:n], label=L"c")
plot!(1:n, [log2(x) for x in 1:n], label=L"\log{n}")
plot!(1:n, [x for x in 1:n], label=L"n")

2.5.5.2 Costo $n \log n$ y polinomial

A continuación veremos tres funciones, una función con $n\log n$ y una función cuadrática y una cúbica. Note como para valores pequeños de $n$ las diferencias no son tan apreciables para como cuando comienza a crecer $n$; así mismo, observe los valores de $n$ de las figuras previas y de la siguiente, este ajuste de rangos se hizo para que las diferencias sean apreciables.

n = 7 # note que se usan menos puntos porque 300 serían demasiados para el rango

plot(1:n, [x * log2(x) for x in 1:n], label=L"n\log_2{n}")
plot!(1:n, [x^2 for x in 1:n], label=L"n^2")
plot!(1:n, [x^3 for x in 1:n], label=L"n^3")

2.5.5.3 Exponencial

A continuación se compara el crecimiento de una función exponencial con una función polinomial. Note que la función polinomial es de grado 4 y que la función exponencial tiene como base 2; aún cuando para números menores de aproximadamente 16 la función polinomial es mayor, a partir de ese valor la función $2^n$ supera rapidamente a la polinomial.

n = 20

plot(1:n, [x^4 for x in 1:n], label=L"n^4")
plot!(1:n, [2^x for x in 1:n], label=L"2^n")

2.5.5.4 Crecimiento factorial

Vease como la función factorial crece mucho más rápido que la función exponencial para una $n$ relativamente pequeña. Vea las magnitudes que se alcanzan en el eje $y$, y comparelas con aquellas con los anteriores crecimientos.

n = 20

plot(1:n, [2^x for x in 1:n], label=L"2^n")
plot!(1:n, [factorial(x) for x in 1:n], label=L"n!")

2.5.5.5 Un poco más sobre funciones de muy alto costo

n = 10

plot(1:n, [factorial(x) for x in 1:n], label=L"n!")
plot!(1:n, [x^x for x in Int128(1):Int128(n)], label=L"n^n")

Vea la figura anterior, donde se compara $n!$ con $n^n$, observe como es que cualquier constante se vuelve irrelevante rapidamente; aun para $n^n$ piense en $n^{n^n}$.

Note que hay problemas que son realmente costosos de resolver y que es necesario conocer si se comporta así siempre, si es bajo determinado tipo de entradas. Hay problemas en las diferentes áreas de la ciencia de datos, donde veremos este tipo de costos, y habrá que saber cuando es posible solucionarlos, o cuando se deben obtener aproximaciones que nos acerquen a las respuestas correctas con un costo manejable, es decir, mediar entre exactitud y costo. En este curso se abordaran problemas con un costo menor, pero que por la cantidad de datos, i.e., $n$, se vuelven muy costosos y veremos como aprovechar supuestos como las distribuciones naturales de los datos para mejorar los costos.

2.6 El enfoque experimental

La notación asintótica nos permite alcanzar un lenguaje común y preciso sobre los costos de problemas y algoritmos; es de especial importancia para la evaluación de las alternativas en la literatura especializada, y elegir algoritmos aún sin la necesidad de implementación. El análisis asintótico da la posibilidad de conocer el desempeño desde diferentes perspectivas como peor caso o caso promedio, utilizando un módelo de computación, y siempre pensando en entradas lo suficientemente grandes.

En la práctica, existe una múltitud de razones por los cuales los problemas que se resuelven podrian no ser tan grandes como para que un algoritmo domine a otros de manera asintótica, las instancias podrían no ser tan generales como para preocuparse en el peor caso, o el caso promedio general. En muchas situaciones, es importante sacar provecho de los casos fáciles, sobre todo cuando el problema a resolver podría asegurar que dichos casos simples sean abundantes. Dada la complejidad detrás de definir sub-conjuntos de instancias y llevar a cabo un análisis formal, se vuelve imperativo realizar pruebas experimentales.

Por otra parte, dada la complejidad de una computadora moderna, es necesario realizar evaluaciones experimentales de los algoritmos que tengan una complejidad similar. Las computadoras reales tienen una jerarquia de memoria con tamaños y velocidades de acceso divergentes entre sí, con optimizaciones integradas sobre la predicción de acceso y cierto nivel de paralelismo. Incluso, cada cierto tiempo se obtienen optimizaciones en los dispositivos que podrían mejorar los rendimientos, por lo que es posible que con una generación a otra, lo que sabemos de los algoritmos y su desempeño en computadoras y cargas de trabajo reales cambie.

2.6.1 Metodología experimental

Algunos de los algoritmos que se verán en este libro son sumamente rapidos en la práctica para resolver una instancia práctica por lo que medir el desempeño de instancias solas podría no tener sentido. La acumulación de operaciones es fundamental, así como la diversidad de las instancias también lo es. Caracterizar las entradas es de vital importancia ya que la adaptabilidad a las instancias es parte de los objetivos.

Entonces, estaremos probando conjuntos de instancias, caracterizadas y estaremos utilizando tiempos promedios. También estaremos usando conteo de operaciones, por lo que los algoritmos en cuestión muchas veces serán adaptados para poder realizar este conteo.

En Julia etaremos utilizando las siguientes instrucciones:

@time expr macro que mide el tiempo en segundo utilizado por expr, también reporta el número de alojaciones de memoria. Note que reducir la cantidad de memoria alojada puede significar reducir el tiempo de una implementación, ya que el manejo de memoria dinámica es costoso.
@benchmark expr params macro del paquete BenchmarkTools que automatiza la repetición de expr para obtener diferentes mediciones y hacer un reporte, params permite manipular la forma en que se reliza la evaluación.
@btime expr params macro del paquete BenchmarkTools que mimetiza la salida de @time.

a = rand(Float32, 3, 3)
1@time a * a
2@time a * a

1: Todas las fuciones se deben compilar, la primera llamada uncluye los costos de compilación.
2: El costo sin compilación, hay una alojación que es la matriz donde se guarda el resultado.

  0.841567 seconds (2.01 M allocations: 136.608 MiB, 3.33% gc time, 99.97% compilation time)
  0.000005 seconds (1 allocation: 96 bytes)

3×3 Matrix{Float32}:
 0.635295  0.150821  0.310147
 1.02056   0.23071   0.674775
 1.71173   0.369326  1.20393

Tanto @benchmark como @btime aceptan interpolación de variables con el prefijo $ para controlar la evaluación de una expresión se debe contar como parte de lo que se quiere medir o no. Se puede combinar con el parametro setup para controlar de manera precisa las entradas para evaluar cada una de las repeticiones de expr.

using BenchmarkTools

@benchmark a * a setup=(a=rand(Float32, 3, 3))

BenchmarkTools.Trial: 10000 samples with 985 evaluations.
 Range (min … max):  46.417 ns …  2.232 μs  ┊ GC (min … max): 0.00% … 96.36%
 Time  (median):     48.330 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   51.039 ns ± 35.694 ns  ┊ GC (mean ± σ):  2.23% ±  3.83%

  ▁▃▂▃██▄▃▅▄▃▃▂▂▂▂▃▃▃▃▃▃▂▁▁▁▁▁                                ▂
  ████████████████████████████████▇▇▇▆▇▆▆▇▆▅▆▇▆▆▅▅▅▄▅▅▁▄▄▄▅▄▅ █
  46.4 ns      Histogram: log(frequency) by time      67.6 ns <

 Memory estimate: 96 bytes, allocs estimate: 1.


a = rand(Float32, 3, 3)
@btime a * a setup=(a=$a)

  47.875 ns (1 allocation: 96 bytes)

3×3 Matrix{Float32}:
 0.575313  0.847652  0.395764
 0.417129  0.719546  0.322025
 0.375838  0.367533  0.22682

El parametro sample controla el número máximo de muestras que se tomarán para el análisis, y seconds limita el tiempo sobre el cual se tomarán muestras; se asegura que al menos se tomará una muestra, se debe tener en cuenta que puede costar más que seconds.¹

a = rand(Float32, 3, 3)
b = rand(Float32, 3, 3)
@benchmark a * b setup=(a=$a, b=$b) samples=1000 seconds=0.33

BenchmarkTools.Trial: 1000 samples with 980 evaluations.
 Range (min … max):  63.631 ns … 880.123 ns  ┊ GC (min … max): 0.00% … 89.30%
 Time  (median):     70.518 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):   77.375 ns ±  38.616 ns  ┊ GC (mean ± σ):  1.79% ±  3.96%

  █▆▆▆▅▄▂▂▂▃▂                                                   
  ████████████▅▄▆▄▅▁▅▅▅▅▅▄▅▅▁▄▄▅▅▁▁▄▁▁▁▁▁▁▁▅▁▁▁▁▄▄▄▄▁▅▁▄▁▁▄▄▄▄ █
  63.6 ns       Histogram: log(frequency) by time       209 ns <

 Memory estimate: 96 bytes, allocs estimate: 1.

2.6.2 Ejemplo del cálculo de máximo de un arreglo y diferentes tipos de costo.

–


1function maximo(col)
    maxpos = 1
    actualizaciones = 1
    i = 2

    while i < length(col)
        if col[maxpos] < col[i]
            maxpos = i
            actualizaciones += 1
        end
        i += 1
    end

    maxpos, actualizaciones
end

1: Función que encuentra el máximo en una secuencia y devuelve su posición, y además devuelve el número de veces que se actualizó el máximo en el recorrido.

maximo (generic function with 1 method)

a = rand(UInt32, 128)
1@benchmark maximo($a) samples=100 seconds=3

1: Un análisis de desempeño usando @benchmark; probando con máximo 100 samples en 3 segundos.

BenchmarkTools.Trial: 100 samples with 875 evaluations.
 Range (min … max):  154.687 ns … 215.714 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     160.295 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):   162.588 ns ±   8.815 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

  █        ▂         ▁                                           
  █▆▃▃▃▅▁▁▃██▃▃▄▃▃▄▃▁█▄▁▁▁▁▃▁▁▁▃█▃▃▁▁▁▁▁▁▁▁▃▃▁▁▁▁▃▁▁▁▁▁▁▁▁▁▃▁▁▃ ▃
  155 ns           Histogram: frequency by time          188 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

Note que aunque se tiene un análisis muy detallado del desempeño, otras medidas de costo caen fuera del diseño del paquete, por lo que es necesario hacerlas por otros medios. Por ejemplo, suponga que el número de actualizaciones es nuesta medida de desempeño, un código donde se capturen las actualizaciones

1using StatsBase
2a = [maximo(rand(UInt32, 128))[2] for i in 1:100]
3quantile(a, [0.0, 0.25, 0.5, 0.75, 1.0])

1: Inclusión de un paquete para cálculo de estadísticas básicas.
2: Definición de 100 experimentos que calculan maximo sobre arreglos aleatorios.
3: Cálculo del mínimo, cuantiles 0.25, 0.5, 0.75, y el máximo, para determinar el desempeño.

5-element Vector{Float64}:
 1.0
 4.0
 5.0
 6.0
 9.0

2.7 Actividades

Comparar mediante simulación en un notebook de Jupyter o Quarto los siguientes órdenes de crecimiento:

$O(1)$ vs $O(\log n)$
$O(n)$ vs $O(n \log n)$
$O(n^2)$ vs $O(n^3)$
$O(a^n)$ vs $O(n!)$
$O(n!)$ vs $O(n^n)$
Escoja los rangos adecuados para cada comparación, ya que como será evidente después, no es práctico fijar los rangos.
Cree una figura por comparación, i.e., cinco figuras. Discuta lo observado por figura.
Cree una tabla donde muestre tiempos de ejecución simulados para algoritmos ficticios que tengan los órdenes de crecimiento anteriores, suponiendo que cada operación tiene un costo de 1 nanosegundo.
- Use diferentes tamaños de entrada $n=100$, $n=1000$, $n=10000$ y $n=100000$.
- Note que para algunas fórmulas, los números pueden ser muy grandes, tome decisiones en estos casos y defiendalas en el reporte.
Discuta las implicaciones de costos de cómputo necesarios para manipular grandes volúmenes de información, en el mismo notebook.

2.7.1 Entregable

Su trabajo se entregará en PDF y con el notebook fuente; deberá estar plenamente documentado, con una estructura que permita a un lector interesado entender el problema, sus experimentos y metodología, así como sus conclusiones. Tenga en cuenta que los notebooks pueden alternar celdas de texto y código.

No olvide estructurar su reporte, en particular el reporte debe cubrir los siguientes puntos:

Título del reporte, su nombre.
Introducción.
Código cercano a la presentación de resultados.
Figuras y comparación de los órdenes de crecimiento.
Análisis y simulación de costo en formato de tabla.
Conclusión. Debe abordar las comparaciones hechas y la simulación; también toque el tema de casos extremos y una $n$ variable y asintóticamente muy grande.
Lista de referencias. Nota, una lista de referencias que no fueron utilizadas en el cuerpo del texto será interpretada como una lista vacía.

2.8 Bibliografía

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). Introduction to Algorithms (2nd ed.). MIT Press.

Parte I: Cap. 1, 2, 3

Se recomienda visitar el sitio https://juliaci.github.io/BenchmarkTools.jl/stable/ para más información sobre el paquete BenchmarkTools, y en particular para sus parametros, como guardar información de corridas.↩︎

--- engine: julia lang: es-MX --- # Introducción al análisis de algoritmos con Julia {#sec-analisis} Este capítulo introduce a los fundamentos de análisis de algoritmos. Se introduce el concepto de modelo de cómputo y la notación asintótica, preparandonos para usar el lenguaje común en el análisis de algoritmos. También se mostrarán algunos de los ordenes de crecimiento más representativos, que nos permitirán comparar algoritmos que resuelvan una tarea dada, así como catalogarlos con respecto a los recursos de computo necesarios para ejecutarlos. ## Concepto de algoritmo y estructura de datos Los algoritmos son especificaciones formales de los pasos u operaciones que deben aplicarse a un conjunto de entradas para resolver un problema, obteniendo una solución correcta a dicho problema. Establecen los fundamentos de la programación y delinean la manera en como se diseñan los programas de computadoras. Es común encontrar que un problema puede ser resuelto por múltiples algoritmos, cada uno de ellos con sus diferentes particularidades. Así mismo, un problema suele estar conformado por una cantidad enorme de instancias de dicho problema, por ejemplo, para una lista de $n$ números, existen $n!$ formas de acomodarlos, de tal forma que puedan ser la entrada a un algoritmo cuya entrada sea una lista de números donde el orden es importante. En ocasiones, los problemas pueden tener infinitas de instancias. En este curso nos enfocaremos en problemas que pueden ser simplificados a una cantidad finita instancias. Cada paso u operación en un algoritmo esta bien definido y puede ser aplicado o ejecutado para producir un resultado. A su vez, cada operación suele tener un costo, dependiente del módelo de computación. Conocer el número de operaciones necesarias para transformar la entrada en la salida esperada, i.e., resolver el problema, es de vital importancia para seleccionar el mejor algoritmo para dicho problema, o aun más, para instancias de dicho problema que cumplen con ciertas características. Una estructura de datos es una abstracción en memoria de entidades matemáticas y lógicas que nos permite organizar, almacenar y procesar datos en una computadora. El objetivo es que la información representada puede ser manipulada de manera eficiente en un contexto específico, además de simplificar la aplicación de operaciones para la aplicación de algoritmos. ## Modelos de cómputo Un modelo de cómputo es una abstracción matemática de una computadora o marco de trabajo algorítmico que nos permite estudiar y medir los costos de los algoritmos funcionando en este modelo de tal forma que sea más simple que una computadora física real. Ejemplos de estos modelos: - [La máquina de Turing](https://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing). - [Funciones recursivas](https://es.wikipedia.org/wiki/Funci%C3%B3n_recursiva). - [Cálculo lambda](https://es.wikipedia.org/wiki/C%C3%A1lculo_lambda). - [Máquina de acceso aleatorio (RAM)](https://en.wikipedia.org/wiki/Random-access_machine). Todas estos modelos son _equivalentes_ en sus capacidades, pero sus diferentes planteamientos permiten enfocarse en diferentes aspectos de los problemas. ### Máquina de Turing Es un módelo creado por Alan Turing a principios del siglo XX; la idea es un dispositivo que podría ser implementada de manera mecánica si se tuvieran recursos infinitos; esta máquina puede leer y escribir mediante un cabezal en una cinta _infinita_ (ver @fig-turing-cinta) una cantidad de símbolos predeterminada para cada problema siguiendo una serie de reglas simples sobre lo que lee y escribe, dichas reglas y la cienta, forman una máquina de estados y memoria, que pueden realizar cualquier cálculo. ```{dot} //| label: fig-turing-cinta //| echo: false //| fig-width: 60% //| fig-cap: | //| Cabezal y cinta. //| digraph TuringTape { rankdir=TB; node [shape=box, fixedsize=true, width=0.5]; // Celdas de la cinta subgraph cluster_tape { label="cinta"; style=filled; color=lightgrey; nodesep=0.02; node [margin=0.1]; start [label=""]; // Celda vacía al inicio 01 [label="0"]; 02 [label="0"]; 03 [label="0"]; 11 [label="1"]; 12 [label="1"]; 13 [label="1"]; end [label=""]; // Celda vacía al final // Organizar las celdas en una línea horizontal { rank=same; nodesep=0.02; start -> 01 -> 02 -> 03 -> 11 -> 12 -> 13 -> end [style=invis, width=0.02]; } } // Cabezal de la máquina de Turing node [shape=invhouse, label="cabezal", color=red, style=filledk, width=1, height=0.5]; head; // Conectar el cabezal a la celda que se lee head -> 01; } ``` Una máquina de Turing se puede escribir como una tupla de 7 elementos $M=(Q, \Sigma, \Gamma, s, \epsilon, F, \delta)$ donde: - $Q$ es un conjunto finito de estados. - $\Sigma$ es el alfabeto de entrada, i.e., un conjunto finito de símbolos que no incluye el espacio en blanco. - $\Gamma$ es el alfabeto de la cinta , i.e., un conjunto finito de símbolos $\Sigma \subseteq \Gamma$. - $s \in Q$ es el estado inicial. - $\epsilon \in \Gamma$ es un símbolo especial denominado _blanco_; y puede llenar la cinta al infinito. - $F \subseteq Q$ conjunto de estados finales de aceptación. - $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$, es la función de transición, i.e., una función parcial que índica que se debe hacer al leer un símbolo en la posición actual de lectura, esto es, qué se escribe, hacia que estado se cambia, y la dirección de movimiento de la cinta (siempre se mueve en una celda). Hay muchas variantes de la definición de máquina de Turing, por ejemplo, una cinta especial para lectura y una para escritura, diferentes formas de definir las transiciones, símbolos para no moverse, etc. Hasta ahora, todas las formas son a lo más equivalentes en términos de poder de cómputo, la diferencia viene en la expresividad para definir soluciones. Es cómun plantear los problemas en forma de lenguajes; esto es, en términos de _dada la cadena S ¿la máquina $M$ la acepta?_, dónde _acepta_ quiere decir que la máquina es capaz de ir desde el estado inicial al estado de aceptación leyendo/transformando $S$. Si $M$ no termina en un estado de aceptación, entonces se implica el fallo o respuesta negativa. ::: {.callout-note} Algunas causas de fallo son que la función de transición no este definida para un estado y símbolo particular y el no alcanzar un estado de salida aceptación. ::: Por ejemplo, sea $M_{01}$ una máquina capaz de detectar $n \geq 0$ ceros terminados por un único $1$. Entonces $$M_{01} = (\{q_0, q_1, q_2\}, \{\mathtt{0}, \mathtt{1}\}, \{\mathtt{0}, \mathtt{1}, \mathtt{X}, \mathtt{\epsilon} \}, q_0, \mathtt{\epsilon}, \{q_2\}, \delta_{01})$$ donde la función de transición se define como: \begin{align} \delta_{01}(q_0, \mathtt{0}) &= (q_0, \mathtt{X}, \mathtt{R}) \\ \delta_{01}(q_0, \mathtt{1}) &= (q_1, \mathtt{X}, \mathtt{R}) \\ \delta_{01}(q_1, \mathtt{\epsilon}) &= (q_2, \mathtt{\epsilon}, \mathtt{R}) \\ \end{align} Dada la regularidad de la función de transición, es común escribirla como una tabla: | entrada | salida | |----------|--------------| | $(q_0, \mathtt{0})$ | $(q_0, \mathtt{X}, \mathtt{R})$ | | $(q_0, \mathtt{1})$ | $(q_1, \mathtt{X}, \mathtt{R})$ | | $(q_1, \mathtt{\epsilon})$ | $(q_2, \mathtt{\epsilon}, \mathtt{R})$ | Una máquina de Turing se puede representar mediante un autómata ```{dot} //| label: fig-turing //| echo: false //| fig-width: 60% //| fig-cap: | //| Ejemplo de máquina de Turing que reconoce cadenas $0^n 1$ digraph G { rankdir=LR; // Nodos de los estados node [shape = doublecircle]; q0; node [shape = circle]; q1; node [shape = doublecircle, style=filled, fillcolor=lightgreen]; q2; //node [shape = doublecircle, style=filled, fillcolor=lightgreen]; // Transiciones q0 -> q0 [label = "0 → X, R"]; q0 -> q1 [label = "1 → X, R"]; q1 -> q2 [label = "ϵ → ϵ, R"]; } ``` Supongamos ahora el problema de reconocer cadenas $0^n 1^n$; para esto podemos definir la siguiente máquina de Turing $$M = (\{q_0, q_1, q_2, q_3, q_4\}, \{\mathtt{0}, \mathtt{1}\}, \{\mathtt{0}, \mathtt{1}, \mathtt{X}, \mathtt{Y}, \mathtt{\epsilon}\}, q_0, \mathtt{\epsilon}, \{q_4\}, \delta),$$ donde la función de transición es como sigue: \begin{align*} \delta(q_0, \mathtt{0}) &= (q_1, \mathtt{X}, \mathtt{R}) \\ \delta(q_0, \mathtt{Y}) &= (q_3, \mathtt{Y}, \mathtt{R}) \\ \delta(q_1, \mathtt{0}) &= (q_1, \mathtt{0}, \mathtt{R}) \\ \delta(q_1, \mathtt{1}) &= (q_2, \mathtt{Y}, \mathtt{L}) \\ \delta(q_1, \mathtt{Y}) &= (q_1, \mathtt{Y}, \mathtt{R}) \\ \delta(q_2, \mathtt{0}) &= (q_2, \mathtt{0}, \mathtt{L}) \\ \delta(q_2, \mathtt{X}) &= (q_0, \mathtt{X}, \mathtt{R}) \\ \delta(q_2, \mathtt{Y}) &= (q_2, \mathtt{Y}, \mathtt{L}) \\ \delta(q_3, \mathtt{Y}) &= (q_3, \mathtt{Y}, \mathtt{R}) \\ \delta(q_3, \mathtt{\epsilon}) &= (q_4, \mathtt{\epsilon}, \mathtt{R}) \\ \end{align*} ```{dot} //| label: fig-turing //| echo: false //| fig-width: 60% //| fig-cap: | //| Ejemplo de máquina de Turing que reconoce cadenas $0^n 1^n$ digraph G { rankdir=LR; // Nodos de los estados node [shape = doublecircle] q0; node [shape = circle]; q1, q2, q3; node [shape = doublecircle, style=filled, fillcolor=lightgreen]; q4; // Transiciones q0 -> q1 [label = "0 → X, R"]; q0 -> q3 [label = "Y → Y, R"]; q1 -> q1 [label = "0 → 0, R"]; q1 -> q1 [label = "Y → Y, R"]; q1 -> q2 [label = "1 → Y, L"]; q2 -> q2 [label = "Y → Y, L"]; q2 -> q2 [label = "0 → 0, L"]; q2 -> q0 [label = "X → X, R"]; q3 -> q3 [label = "Y → Y, R"]; q3 -> q4 [label = "ϵ → ϵ, R"]; } ``` Todo inicia con una cadena de la forma esperada, e.g., $\mathtt{000111}$, la idea general del algoritmo es aparear $\mathtt{0}$'s y $\mathtt{1}$'s, ya que solo es valido si ambas subcadenas tienen igual longitud. Para esto se marcan los $\mathtt{0}$'s vistos con $\mathtt{X}$ y los $\mathtt{1}$'s con $\mathtt{Y}$. La máquina estará entonces marcando las primeras ocurrencias y moviendose a traves de la cinta para encontrar los correspondientes. ::: {.callout-important} Las máquinas de Turing son capaces del representar cualquier problema cómputable con una analogía mecánica, lo cual hace evidente su implementación en el mundo físico. ::: ### Modelos funcionales - [Funciones recursivas](https://es.wikipedia.org/wiki/Funci%C3%B3n_recursiva). Se basa en funciones que trabajan sobre los números naturales y que definen en conjunto el espacio de funciones computables. Son una herramienta abstracta que permite a los teóricos de la lógica y computación establecer los límites de lo computable. - [Cálculo lambda](https://es.wikipedia.org/wiki/C%C3%A1lculo_lambda). Es un módelo creado por Alonzo Church y Stephen Kleene a principios del siglo XX, al igual que las funciones recursivas, se fundamenta en el uso de funciones y es una herramienta abstracta con própositos similares, sin embargo el cálculo lambda no se limita a recursiones, y se enfoca en diferentes reglas de reducción y composición de funciones, y es natural la inclusión de operadores de alto nivel, aunque estos mismos sean definidos mediante un esquema funcional. ### Máquina de acceso aleatorio (RAM) Es un módelo que describe una computadora con registros. A diferencia de una computadora física, no tienen limitación en su capacidad, ni en la cantidad de registros, ni en la precisión de los mismos. Cada registro puede ser identicado de manera única y su contenido leído y escrito mediante reglas o instrucciones formando un programa. En particular reconoce las diferencias entre registros de los programas y registros de datos, i.e., [arquitectura harvard](https://en.wikipedia.org/wiki/Harvard_architecture). Existe un número mínimo de instrucciones necesarias (i.e., incremento, decremento, poner a cero, copiar, salto condicional, parar) pero es común construir esquemas más complejos basados en estas primitivas. Se necesita un registro especial que indica el registro de programa siendo ejecutado. Los accesos a los registros tienen un tiempo constante a diferencia de otros esquemas; es el modelo más cercano a como funciona una computadora moderna entre los que se hemos revisado. ::: {.margin-column} Una computadora moderna difieres de una máquina RAM, por ejemplo, a diferencia de una computadora física se suponen infinitos registros con precisión infinita. Debido a los costos de los semiconductores y la energía necesaría, es conveniente construir computadoras con una jerarquía de memoria: los niveles con mayores prestaciones (e.g., rápidez) son los más escasos. Es importante sacar provecho de esta jerarquía siempre que sea posible. Las operaciones también tienen costos diferentes, dependiendo de su implementación a nivel de circuitería, así como también existe cierto nivel de paralelización que no esta presente en una máquina RAM, tanto a nivel de procesamiento y lectura de datos. ::: ## Sobre la importancia del modelo de cómputo en el curso En este curso nos enfocaremos en especificaciones de alto nivel, donde los algoritmos son convenientes para una computadora física. Sin embargo, estaremos contando operaciones de interés pensando en costos constantes en el acceso a memoria y en una selección de operaciones, al estilo de una máquina RAM. La selección de operaciones de interés tiene el espíritu de simplificar el análisis, focalizando nuestros esfuerzos en operaciones que acumulan mayor costo y que capturan la dinámica del resto. Adicionalmente al conteo de operaciones nos interesa el desempeño de los algoritmos en tiempo como magnitud física medible, así como en la cantidad de memoria consumida, por lo que se aboradará el costo realizando mediciones experimentales. Se contrastará con el análisis basado en conteo de operaciones siempre que sea posible. ## Tipos de análisis La pregunta inicial sería ¿qué nos interesa saber de un algoritmo que resuelve un problema? probablemente, lo primero sería saber si produce resultados correctos. Después, entre el conjunto de las alternativas que producen resultados correctos, es determinante obtener su desempeño para conocer cuál es más conveniente para resolver un problema. En ese punto, es necesario reconocer que para un problema, existen diferentes instancias posibles, esto es el espacio de instancias del problema, y que cada una de ellas exigirían soluciones con diferentes costos para cada algoritmo. Por tanto existen diferentes tipos de análisis y algoritmos. - _Análisis de mejor caso_. Obtener el mínimo de resolver cualquier instancia posible, puede parecer poco útil desde el punto de vista de decisión para la selección de un algoritmo, pero puede ser muy útil para conocer un problema o un algoritmo. - _Análisis de peor caso_. Obtener el costo máximo necesario para resolver cualquier instancia posible del problema con un algoritmo, este es un costo que si nos puede apoyar en la decisión de selección de un algoritmo; sin embargo, en muchas ocasiones, puede ser poco informativo o innecesario ya que tal vez hay pocas instancias que realmente lo amériten. - _Análisis promedio_. Se enfoca en obtener un análisis promedio basado en la población de instancias del problema para un algoritmo dado. - _Análisis amortizado_. Se enfoca en análisis promedio pero para una secuencia de instancias. - _Análisis adaptativo_. Para un subconjunto _bien caracterizado_ del espacio de instancias de un problema busca análizar los costos del algoritmo en cuestión. La caracterización suele estar en términos de una medida de complejidad para el problema; y la idea general es medir si un algoritmo es capaz de sacar provecho de instancias _fáciles_. ## Notación asintótica Realizar un conteo de operaciones y mediciones es un asunto complejo que requiere focalizar los esfuerzos. Para este fin, es posible contabilizar solo algunas operaciones de importancia, que se supondrían serían las más costosas o que de alguna manera capturan de manera más fiel la dinámica de costos. El comportamiento asintótico es otra forma de simplificar y enfocarnos en los puntos de importancia, en este caso, cuando el tamaño de la entrada es realmente grande. Es importante mencionar, que no se esperan entradas de tamaño descomunal, ni tampoco se espera cualquier tipo de entrada. ### Notación $\Theta$ Para una función dada $g(n)$ denotamos por $\Theta(g(n))$ el siguiente conjunto de funciones: \begin{align} \Theta(g(n)) &= \left\{ f(n) \mid \text{ existen las constantes positivas }c_1, c_2 \text{ y } n_0 \text{ tal que } \right.\\ ~ & \left. 0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n) \text{ para todo } n \geq n_0 \right\} \\ \end{align} esto es, una función $f(n)$ pertenece al conjunto $g(n)$ si $c_1 g(n)$ y $c_2 g(n)$ pueden _cubrirla_ por abajo y por arriba, para esto deben existen las constantes positivas $c_1$ y $c_2$ y una $n$ lo suficientemente larga, e.g., para eso la constante $n_0$. La notación propiamente de conjuntos puede usarse $f(n) \in \Theta(g(n))$ pero es común en el área usar $f(n) = \Theta(g(n))$ para expresar la pertenencia; este abuso de la notación tiene ventaja a la hora de plantear los problemas de análisis. ### Notación $O$ Se utiliza para indicar una cota asintótica superior. Una función $f(n)$ se dice que esta en $O(g(n))$ si esta en el siguiente conjunto: \begin{align} O(g(n)) &= \left\{ f(n) \mid \text{ existen las constantes positivas }c \text{ y } n_0 \text{ tal que } \right.\\ ~& \left. 0 \leq f(n) \leq c g(n) \text{ para todo } n \geq n_0 \right\} \\ \end{align} La notación $O$ se usa para dar una cota superior, dentro de un factor constante. Al escribir $f(n) = O(g(n))$ se indica que $f(n)$ es miembro del conjunto $O(g(n))$; hay que notar que $f(n) = \Theta(g(n))$ implica que $f(n) = O(g(n))$, i.e., $\Theta(g(n)) \subseteq O(g(n))$. ### Notación $\Omega$ Al contrario de $O$, la notación $\Omega$ da una cota asintótica inferior. Una función $f(n)$ se dice que esta en $\Omega(g(n))$ si esta en el siguiente conjunto: \begin{align} \Omega(g(n)) = & \left\{ f(n) \mid \text{ existen las constantes positivas }c \text{ y } n_0 \text{ tal que } \right. \\ & \left. 0 \leq c g(n) \leq f(n) \text{ para todo } n \geq n_0 \right\} \\ \end{align} Dado que la $\Omega$ define una cota superior, basicamente si $f(n) = \Omega(g(n))$, entonces $f(n)$ debe estar por encima de $g(n)$ con las constantes $c$ y $n_0$ adecuadas. Al igual que la notación $O$, la notación $\Omega$ es menos estricta que $\Theta$, esto es $f(n) = \Theta(g(n))$ implica que $f(n) = \Omega(g(n))$, por lo que $\Theta(g(n)) \subseteq \Omega(g(n))$. Por tanto, si $f(n) = O(g(n))$ y $f(n) = \Omega(g(n))$ entonces $f(n) \in \Theta(g(n))$. ::: {.margin-column} Es importante conocer los ordenes de crecimiento más comunes de tal forma que podamos realizar comparaciones rápidas de costos, y dimensionar las diferencias de recursos entre diferentes tipos de costos. La notación asintótica hace uso extensivo de la diferencia entre diferentes ordenes de crecimiento para ignorar detalles y simplificar el análisis de algoritmos. ::: ### Apoyo audio-visual En los siguientes videos se profundiza sobre los modelos de cómputo y los diferentes tipos de análisis sobre algoritmos. - Parte 1: <iframe width="560" height="315" src="https://www.youtube.com/embed/uUZnpaoEQXs" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> - Parte 2: <iframe width="560" height="315" src="https://www.youtube.com/embed/CkvfliomNqk" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> - Parte 3: <iframe width="560" height="315" src="https://www.youtube.com/embed/zRtjk2X2aDE" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> ### Ordenes de crecimiento <iframe width="560" height="315" src="https://www.youtube.com/embed/mX7mZH0Dz8s" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> Dado que la idea es realizar un análisis asintótico, las constantes suelen ignorarse, ya que cuando el tamaño de la entrada es suficientemente grande, los términos con mayor orden de magnitud o crecimiento dominarán el costo. Esto es, es una simplificación necesaría. Los ordenes de crecimiento son maneras de categorizar la velocidad de crecimiento de una función, y para nuestro caso, de una función de costo. Junto con la notación asimptótica nos permite concentrarnos en razgos gruesos que se mantienen para entradas grandes, más que en los detalles, y no perder el punto de interés. A continuación veremos algunas funciones con crecimientos paradigmáticos; las observaremos de poco en poco para luego verlos en conjunto. #### Costo constante, logaritmo y lineal La siguiente figura muestra un crecimiento nulo (constante), logaritmico y lineal. Note como la función logarítmica crece lentamente. ```{julia} #| fig-width: 90% using Plots, LaTeXStrings n = 300 # 300 puntos plot(1:n, [10 for x in 1:n], label=L"c") plot!(1:n, [log2(x) for x in 1:n], label=L"\log{n}") plot!(1:n, [x for x in 1:n], label=L"n") ``` #### Costo $n \log n$ y polinomial A continuación veremos tres funciones, una función con $n\log n$ y una función cuadrática y una cúbica. Note como para valores pequeños de $n$ las diferencias no son tan apreciables para como cuando comienza a crecer $n$; así mismo, observe los valores de $n$ de las figuras previas y de la siguiente, este ajuste de rangos se hizo para que las diferencias sean apreciables. ```{julia} #| fig-width: 90% n = 7 # note que se usan menos puntos porque 300 serían demasiados para el rango plot(1:n, [x * log2(x) for x in 1:n], label=L"n\log_2{n}") plot!(1:n, [x^2 for x in 1:n], label=L"n^2") plot!(1:n, [x^3 for x in 1:n], label=L"n^3") ``` #### Exponencial A continuación se compara el crecimiento de una función exponencial con una función polinomial. Note que la función polinomial es de grado 4 y que la función exponencial tiene como base 2; aún cuando para números menores de aproximadamente 16 la función polinomial es mayor, a partir de ese valor la función $2^n$ supera rapidamente a la polinomial. ```{julia} #| fig-width: 90% n = 20 plot(1:n, [x^4 for x in 1:n], label=L"n^4") plot!(1:n, [2^x for x in 1:n], label=L"2^n") ``` #### Crecimiento factorial Vease como la función factorial crece mucho más rápido que la función exponencial para una $n$ relativamente pequeña. Vea las magnitudes que se alcanzan en el _eje_ $y$, y comparelas con aquellas con los anteriores crecimientos. ```{julia} #| fig-width: 90% n = 20 plot(1:n, [2^x for x in 1:n], label=L"2^n") plot!(1:n, [factorial(x) for x in 1:n], label=L"n!") ``` #### Un poco más sobre funciones de muy alto costo ```{julia} #| fig-width: 90% n = 10 plot(1:n, [factorial(x) for x in 1:n], label=L"n!") plot!(1:n, [x^x for x in Int128(1):Int128(n)], label=L"n^n") ``` Vea la figura anterior, donde se compara $n!$ con $n^n$, observe como es que cualquier constante se vuelve irrelevante rapidamente; aun para $n^n$ piense en $n^{n^n}$. Note que hay problemas que son realmente costosos de resolver y que es necesario conocer si se comporta así siempre, si es bajo determinado tipo de entradas. Hay problemas en las diferentes áreas de la ciencia de datos, donde veremos este tipo de costos, y habrá que saber cuando es posible solucionarlos, o cuando se deben obtener aproximaciones que nos acerquen a las respuestas correctas con un costo manejable, es decir, mediar entre exactitud y costo. En este curso se abordaran problemas con un costo menor, pero que por la cantidad de datos, i.e., $n$, se vuelven muy costosos y veremos como aprovechar supuestos como las distribuciones naturales de los datos para mejorar los costos. ## El enfoque experimental La notación asintótica nos permite alcanzar un lenguaje común y preciso sobre los costos de problemas y algoritmos; es de especial importancia para la evaluación de las alternativas en la literatura especializada, y elegir algoritmos aún sin la necesidad de implementación. El análisis asintótico da la posibilidad de conocer el desempeño desde diferentes perspectivas como peor caso o caso promedio, utilizando un módelo de computación, y siempre pensando en entradas lo suficientemente grandes. En la práctica, existe una múltitud de razones por los cuales los problemas que se resuelven podrian no ser tan grandes como para que un algoritmo domine a otros de manera asintótica, las instancias podrían no ser tan generales como para preocuparse en el peor caso, o el caso promedio general. En muchas situaciones, es importante sacar provecho de los casos _fáciles_, sobre todo cuando el problema a resolver podría asegurar que dichos casos simples sean abundantes. Dada la complejidad detrás de definir sub-conjuntos de instancias y llevar a cabo un análisis formal, se vuelve imperativo realizar pruebas experimentales. Por otra parte, dada la complejidad de una computadora moderna, es necesario realizar evaluaciones experimentales de los algoritmos que tengan una complejidad similar. Las computadoras reales tienen una jerarquia de memoria con tamaños y velocidades de acceso divergentes entre sí, con optimizaciones integradas sobre la predicción de acceso y cierto nivel de paralelismo. Incluso, cada cierto tiempo se obtienen optimizaciones en los dispositivos que podrían mejorar los rendimientos, por lo que es posible que con una generación a otra, lo que sabemos de los algoritmos y su desempeño en computadoras y cargas de trabajo reales cambie. ### Metodología experimental Algunos de los algoritmos que se verán en este libro son sumamente rapidos en la práctica para resolver una instancia práctica por lo que medir el desempeño de instancias solas podría no tener sentido. La acumulación de operaciones es fundamental, así como la diversidad de las instancias también lo es. Caracterizar las entradas es de vital importancia ya que la adaptabilidad a las instancias es parte de los objetivos. Entonces, estaremos probando conjuntos de instancias, caracterizadas y estaremos utilizando tiempos promedios. También estaremos usando conteo de operaciones, por lo que los algoritmos en cuestión muchas veces serán adaptados para poder realizar este conteo. En Julia etaremos utilizando las siguientes instrucciones: - `@time expr` macro que mide el tiempo en segundo utilizado por `expr`, también reporta el número de alojaciones de memoria. Note que reducir la cantidad de memoria alojada puede significar reducir el tiempo de una implementación, ya que el manejo de memoria dinámica es costoso. - `@benchmark expr params` macro del paquete `BenchmarkTools` que automatiza la repetición de `expr` para obtener diferentes mediciones y hacer un reporte, `params` permite manipular la forma en que se reliza la evaluación. - `@btime expr params` macro del paquete `BenchmarkTools` que mimetiza la salida de `@time`. ```{julia} a = rand(Float32, 3, 3) @time a * a # <1> @time a * a # <2> ``` 1. Todas las fuciones se deben compilar, la primera llamada uncluye los costos de compilación. 2. El costo sin compilación, hay una alojación que es la matriz donde se guarda el resultado. Tanto `@benchmark` como `@btime` aceptan interpolación de variables con el prefijo `$` para controlar la evaluación de una expresión se debe contar como parte de lo que se quiere medir o no. Se puede combinar con el parametro `setup` para controlar de manera precisa las entradas para evaluar cada una de las repeticiones de `expr`. ```{julia} using BenchmarkTools @benchmark a * a setup=(a=rand(Float32, 3, 3)) ``` ```{julia} a = rand(Float32, 3, 3) @btime a * a setup=(a=$a) ``` El parametro `sample` controla el número máximo de muestras que se tomarán para el análisis, y `seconds` limita el tiempo sobre el cual se tomarán muestras; se asegura que al menos se tomará una muestra, se debe tener en cuenta que puede costar más que `seconds`.[^btools] [^btools]: Se recomienda visitar el sitio <https://juliaci.github.io/BenchmarkTools.jl/stable/> para más información sobre el paquete `BenchmarkTools`, y en particular para sus parametros, como guardar información de corridas. ```{julia} a = rand(Float32, 3, 3) b = rand(Float32, 3, 3) @benchmark a * b setup=(a=$a, b=$b) samples=1000 seconds=0.33 ``` ### Ejemplo del cálculo de máximo de un arreglo y diferentes tipos de costo. -- ```{julia} function maximo(col) # <1> maxpos = 1 actualizaciones = 1 i = 2 while i < length(col) if col[maxpos] < col[i] maxpos = i actualizaciones += 1 end i += 1 end maxpos, actualizaciones end ``` 1. Función que encuentra el máximo en una secuencia y devuelve su posición, y además devuelve el número de veces que se actualizó el máximo en el recorrido. ```{julia} a = rand(UInt32, 128) @benchmark maximo($a) samples=100 seconds=3 # <1> ``` 1. Un análisis de desempeño usando `@benchmark`; probando con máximo 100 samples en 3 segundos. Note que aunque se tiene un análisis muy detallado del desempeño, otras medidas de costo caen fuera del diseño del paquete, por lo que es necesario hacerlas por otros medios. Por ejemplo, suponga que el número de `actualizaciones` es nuesta medida de desempeño, un código donde se capturen las actualizaciones ```{julia} using StatsBase # <1> a = [maximo(rand(UInt32, 128))[2] for i in 1:100] # <2> quantile(a, [0.0, 0.25, 0.5, 0.75, 1.0]) # <3> ``` 1. Inclusión de un paquete para cálculo de estadísticas básicas. 2. Definición de 100 experimentos que calculan `maximo` sobre arreglos aleatorios. 3. Cálculo del mínimo, cuantiles 0.25, 0.5, 0.75, y el máximo, para determinar el desempeño. ## Actividades Comparar mediante simulación en un notebook de Jupyter o Quarto los siguientes órdenes de crecimiento: - $O(1)$ vs $O(\log n)$ - $O(n)$ vs $O(n \log n)$ - $O(n^2)$ vs $O(n^3)$ - $O(a^n)$ vs $O(n!)$ - $O(n!)$ vs $O(n^n)$ - Escoja los rangos adecuados para cada comparación, ya que como será evidente después, no es práctico fijar los rangos. - Cree una figura por comparación, i.e., cinco figuras. Discuta lo observado por figura. - Cree una tabla donde muestre tiempos de ejecución simulados para algoritmos ficticios que tengan los órdenes de crecimiento anteriores, suponiendo que cada operación tiene un costo de 1 nanosegundo. - Use diferentes tamaños de entrada $n=100$, $n=1000$, $n=10000$ y $n=100000$. - Note que para algunas fórmulas, los números pueden ser muy grandes, tome decisiones en estos casos y defiendalas en el reporte. - Discuta las implicaciones de costos de cómputo necesarios para manipular grandes volúmenes de información, en el mismo notebook. ### Entregable Su trabajo se entregará en PDF y con el notebook fuente; deberá estar plenamente documentado, con una estructura que permita a un lector interesado entender el problema, sus experimentos y metodología, así como sus conclusiones. Tenga en cuenta que los notebooks pueden alternar celdas de texto y código. No olvide estructurar su reporte, en particular el reporte debe cubrir los siguientes puntos: - Título del reporte, su nombre. - Introducción. - Código cercano a la presentación de resultados. - Figuras y comparación de los órdenes de crecimiento. - Análisis y simulación de costo en formato de tabla. - Conclusión. Debe abordar las comparaciones hechas y la simulación; también toque el tema de casos extremos y una $n$ variable y asintóticamente muy grande. - Lista de referencias. Nota, una lista de referencias que no fueron utilizadas en el cuerpo del texto será interpretada como una lista vacía. ## Bibliografía Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). Introduction to Algorithms (2nd ed.). MIT Press. - Parte I: Cap. 1, 2, 3

entrada	salida
\((q_0, \mathtt{0})\)	\((q_0, \mathtt{X}, \mathtt{R})\)
\((q_0, \mathtt{1})\)	\((q_1, \mathtt{X}, \mathtt{R})\)
\((q_1, \mathtt{\epsilon})\)	\((q_2, \mathtt{\epsilon}, \mathtt{R})\)

2.1 Concepto de algoritmo y estructura de datos

2.2 Modelos de cómputo

2.2.1 Máquina de Turing

2.2.2 Modelos funcionales

2.2.3 Máquina de acceso aleatorio (RAM)

2.3 Sobre la importancia del modelo de cómputo en el curso

2.4 Tipos de análisis

2.5 Notación asintótica

2.5.1 Notación \(\Theta\)

2.5.2 Notación \(O\)

2.5.3 Notación \(\Omega\)

2.5.4 Apoyo audio-visual

2.5.5 Ordenes de crecimiento

2.5.5.1 Costo constante, logaritmo y lineal

2.5.5.2 Costo \(n \log n\) y polinomial

2.5.5.3 Exponencial

2.5.5.4 Crecimiento factorial

2.5.5.5 Un poco más sobre funciones de muy alto costo

2.6 El enfoque experimental

2.6.1 Metodología experimental

2.6.2 Ejemplo del cálculo de máximo de un arreglo y diferentes tipos de costo.

2.7 Actividades

2.7.1 Entregable

2.8 Bibliografía