UABC Algoritmos

TagsAlgorithmsComputer scienceScience
Created
Updated

Sílabo

Se provee una primera etapa de abstracción y razonamiento lógico matemático para identificar las limitaciones de los modelos actuales de

computación. Esto se enmarca en el área de la teoría de la computación, la cual se encarga de establecer los fundamentos de las

ciencias computacionales de manera formal y realizar un análisis lógico-matemático de las soluciones algorítmicas propuestas para diferentes problemáticas,

así como de proponer soluciones alternativas utilizando técnicas avanzadas de diseño de algoritmos.

Programa de unidad de aprendizaje.

Prefacio

Curso impartido en la UABC. Revisado por el Dr. Everardo Gutiérrez López, escrito por su alumno Carlos Eduardo Sánchez Torres.

Este texto y sus recursos se rigen bajo la licencia CC BY-NC-SA 4.0.

Si estas viendo estas notas como PDF u otros formatos, puedes encontrarlas en: https://sanchezcarlosjr.notion.site/An-lisis-de-Algoritmos-38fac5ca34e740719b43673db9f8b918

Libros de texto

Ecosistema

Esta curso se contexualiza en Ciencias Computacionales:

ACM Computing Classification System

Curso fundamental para ¿Qué es lo que sigue? ¿Cuál es el estado del arte?

¿Por qué estudiar algoritmos?

💡
El software se está volviendo más lento comparado con lo rápido que se está volviendo el hardware. Ley de Wirth, en su artículo de 1995 A Plea for Lean Software, él se la atribuye a Martin Reiser.

Los algoritmos son el centro de estudio de las ciencias computacionales: la algoritmia o algorítmica es la piedra angular de esta ciencia -que lo es-. Este curso tiene como propósito que tú analices algoritmos para su determinar su eficiencia, y técnicas para crearlos.

Como sabrás de tus clases de ingeniería de software, en los sistemas grandes se suele dar preferencia a:

Entonces, ¿por qué es importante estudiar algoritmos y su rendimiento?

Conceptos clave

ConceptoDef.CaracterísticasEjemplos y tipos
Problema computacional o problema. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. The MIT Press, 4ª Ed., 2022Una pregunta general a ser respondida.Un problema es descrito por: Conjunto Instancia, entrada. Discurso de dominio DD descrito por parámetros o variables independentes. Una instancia del problema son valores específicos para estas variables. Solución o salida. Conjunto que satisface el predicado P(x),xDP(x), x \in D.Por foma del conjunto. Decisión. Búsqueda. Optimización. Conteo. Por decibilidad. Indecidibles. Decidibles. Por tratabilidad. Tratable o factibles (fácil o problemas P), si y solo si hay algún algoritmo eficiente. Intratable, si y solo si NO hay algún algoritmo eficiente.
Algoritmo Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. The MIT Press, 4ª Ed., 2022 Def. estipulativa Es un procedimiento computacional bien definido paso por paso que para cada entrada da una salida. Herramienta para resolver problemas computacionales. Def. formal Un algoritmo es una máquina de Turing que dada una cadena de entrada eventualmente para. Advertencia: computacional no refiere a que sea un programa o que deba ser escrito en un lenguaje de programación.Finito. El algoritmo termina, esto es, puede finalizar en una cantidad finita de tiempo. Definido (preciso). Libre de ambigüedad. Entrada. Recibe un conjunto entrada II que I0|I|\ge 0, precondición. Salida. Da un conjunto salida OO que O1|O|\ge1, postcondición. General. El algoritmo funciona para cualquier instancia del problema. Normalmente, aunque no exclusivamente, Determinista. Se espera que sea Correcto. Que el conjunto salida es igual al conjunto solución. Legible. Simple de leer y autocontenido.Por tiempo de ejecución. Tiempo polinomial. T(n)=O(nk),k0T(n)=O(n^k), k\ge0. Tiempo exponencial. T(n)=O(kn),k1T(n)=O(k^n), k\ge1. Por eficiencia. Eficiente. Si T(n)=O(nk),k0T(n)=O(n^k), k\ge0. Ineficiente. En otro caso. Por aleatoriedad. Aleatorios. Deterministas. Por cantidad de procesadores. Secuenciales. Multihilo.
Programa Knuth, D. E. (1997). The art of computer programming (3rd ed.). Addison Wesley.Expresiones de un método computacional en un lenguaje de programación es llamado programa.
Método computacional Knuth, D. E. (1997). The art of computer programming (3rd ed.). Addison Wesley.Es un procedimiento computacional bien definido paso por paso que dada una entrada da una salida que puede NO terminar. Advertencia: NO confundir con los métodos de OOP.

Ejemplos

Problema computacionalAlgoritmos
Ordenamiento. Entrada. Sequencia de nn números a1,a2,a2,...,ana_1,a_2,a_2,...,a_n. Salida. Una permutación a1,a2,a2,...,ana_1',a_2',a_2',...,a_n' de la sequencia de entrada tal que a1a2a2...ana_1' \le a_2' \le a_2'\le...\le a_n'. QuickSort BubleSort MergeSort ...
Fibonacci. Entrada. D={nnN}D=\{ n|n \in \mathbb{N} \}. Salida. ana_n tal que an=an1+an2a_n=a_{n-1} + a_{n-2}, nDn \in DFibonacci recursivo. Fibonacci iterativo. Fibonacci en forma cerrada.

Latex y pseudocódigo

Tú también puedes crear algoritmos que se vean bien: https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/11599/clrscode4e.pdf

Herramientas de Análisis de Algoritmos

El análisis de un algoritmo es el proceso de encontrar el tiempo y espacio necesario para ejecutarlo, abstrayendo la velocidad de ejecución de la máquina real, midiéndolo en función del tamaño y forma de la entrada.

Eficiencia (o complejidad) en tiempo y espacio

La función que mide el tiempo de ejecución de un algoritmo es T(n)T(n), que relaciona el número de pasos -operaciones básicas- con el tamaño de la entrada. Por otra parte S(n)S(n) mide el espacio dependiendo del tamaño de la entrada. Asumimos que trabajamos en una RAM (máquina de acceso aleatorio, la cual opera igual que una real) y que sus operaciones básicas operaciones son constantes (para mayor informacion vease un curso de arquitectura de computadoras), esto es, que no varían por el tipo ni por el tamaño de la entrada:

El procedimiento para encontrar T(n)T(n): contar el número de operaciones simples en función del tamaño de entrada (recurrencias, analizado amortizado, conteo, ...), luego pensar en cuales son las condiciones para que el algoritmo ejecuta la mayor, la menor y el promedio de ejecución y por último, encontrar su orden de crecimiento, esto es, su eficiencia asintótica.

El procedimiento para encontrar S(n)S(n): contar el número de unidades de memoria consumidas.

Para esto es crucial que aprendas Finite Calculus.

Análisis empírico de la eficiencia de un algoritmo o benchmarking

Existen maneras empíricas o experimentales para lucidar la eficiencia de un algoritmo, sin embargo, estas no son formales, esto significa que sus resultados no son generalizables, y en algunos casos no son independientes de la máquina. Por tanto, no son objeto de estudio de este curso. Esto implica, que los ejercicios se esperan sean resueltos analíticamente, libres de un lenguaje de programación y computadoras concretas, ... (programar en tu lenguaje favorito y ejecutarlo para un par de casos de prueba no es una demostración).

Puedes ver las notas de Dr. Eduaro Tello en el CINVESTAV y otros enlaces:

https://quick-bench.com/q/MRdilBjmh6-pPnw96rPcOugqEA8

https://docs.python.org/3/library/timeit.html

https://jakevdp.github.io/PythonDataScienceHandbook/01.07-timing-and-profiling.html

https://godbolt.org/

Tipos de tiempos de ejecución de los algoritmos

Peor caso de ejecuciónCaso promedio de ejecuciónMejor caso de ejecuciónEsperado tiempo de ejecución
El caso donde el algoritmo ejecuta la mayor cantidad de pasos o el máximo tiempo necesario dada una entrada pésima sobre todas las entradas de tamaño nn, esto es, que la T(n)T(n)  sea las más grande posible: T(n)=maxX=nT(X)T(n)=max_{|X|=n}T(X)La cantidad promedio de pasos o el promedio de tiempo necesario para ejecutar el algoritmo dada sobre todas las entradas de tamaño nn. Entonces, buscamos la entrada promedio o típica mediante análisis probabilístico, es decir, la distribución de probabilidad sobre los datos de entrada: Ta(n)=EX=nT(X)=X=nT(X)Pr(X)T_a(n) = E_{|X|=n}T(X)=\displaystyle\sum_{|X|=n}T(X) Pr(X) Advertencia: * No es el promedio del peor caso y el mejor caso.El caso donde el algoritmo ejecuta la menor cantidad de pasos o el menor tiempo necesario dada una entrada óptima de tamaño nn, esto es, que la T(n) sea la menor posible: T(n)=minX=nT(X)T(n)=min_{|X|=n}T(X)Cuando el algoritmo es aleatorio caracterizamos con el tiempo esperado: T(n)=Et[tPr(t)]T(n)=E_t[ t Pr(t)], donde t es el posible tiempo para el algoritmo y la probabilidad Pr(t) de que ese tiempo ocurra. Advertencia: no confundir con el caso promedio de ejecución.

En el curso, buscamos el peor caso porque aunque el caso promedio es el típico, por la Ley de Morphy sabemos que el peor caso es siempre posible.

Caso promedio

Variables aleatorias. Es una función, X: S → N

Variables aleatorias indicadoras Es una función X: S → {1,0}

Esperanza matemática (promedio). E[X]=piXiE[X]=\sum p_i X_i

Distribucion uniforme. nn elementos, pi=1np_i=\dfrac{1}{n}

Ejemplos trabajados

Ejemplo 1 de T(n)

c=1+1;  c1

Ejemplo 2 de T(n)

b=1; c1
c= 1 if 1==b else 2;  c2

Ejemplo 1

S={HH,AA,HA,AH}

X: cantidad de H

X(HH)=2

X(AA)=0

X(HA)=1

X(AH)=1

E[X]=piXi=142+140+141+141=1E[X]=\sum p_i X_i=\dfrac{1}{4}2+\dfrac{1}{4}0+\dfrac{1}{4}1+\dfrac{1}{4}1=1

Ejemplo 2

S={HH,AA,HA,AH}

X: si H aparece 1, si H no aparece 0.

X(HH)=1

X(AA)=0

X(HA)=1

X(AH)=1

E[X]=piXi=141+140+141+141=34E[X]=\sum p_i X_i=\dfrac{1}{4}1+\dfrac{1}{4}0+\dfrac{1}{4}1+\dfrac{1}{4}1=\dfrac{3}{4}

Ejemplo 3

S={H,A}

X: si H aparece 1, si H no aparece 0.

X(H)=1

X(A)=0

E[X]=piXi=121+120=12E[X]=\sum p_i X_i=\dfrac{1}{2}1+\dfrac{1}{2}0=\dfrac{1}{2}

Ejemplo 4

Xi:cantidad de veces que aparece iX_i: \text{cantidad de veces que aparece i} en el arreglo: [1,2,3].

n=3n=3 p(X=1)=13p(X=1)=\dfrac{1}{3}, p(X=2)=13p(X=2)=\dfrac{1}{3}, p(X=3)=13p(X=3)=\dfrac{1}{3}

E[X]=piXi=131+132+133=2E[X]=\sum p_i X_i=\dfrac{1}{3}1+\dfrac{1}{3}2+\dfrac{1}{3}3=2

Ejemplo 5

S={H,T}S=\{H,T\}

Xi=I(i experimentos tal que se encuentra H)X_i= I(\text{i experimentos tal que se encuentra H})

X1(H)=1X_1(H)=1

X1(T)=0X_1(T)=0

X2(HH)=1X_2(HH)=1

X2(HT)=1X_2(HT)=1

X2(TT)=0X_2(TT)=0

X2(TH)=1X_2(TH)=1

...

X=i=1nXiX=\sum^n_{i=1} X_i (el total de Hs en nn experimentos)

E[X]=E[i=1nXi]E[X]=E[\sum^n_{i=1} X_i]

E[X]=i=1nE[Xi]E[X]=\sum^n_{i=1} E[X_i]

E[Xi]=pHXi+pnoHXi=121+120=12E[X_i]=p_HX_i+p_{noH}X_i=\dfrac{1}{2}1+\dfrac{1}{2}0=\dfrac{1}{2}

E[X]=i=1n12=n2E[X]=\sum^n_{i=1} \dfrac{1}{2}=\dfrac{n}{2}

¿Cómo comparamos algoritmos?

Lo anterior significa que nuestro problema de comparar algoritmos se reduce a comparar funciones T1,T2T_1,T_2, tal que si

T1(n)>T2(n)T_1(n)> T_2(n)

El algoritmo con T2T_2  es más rápida que el algoritmo con T1T_1, donde siempre se quiere la función más pequeña -más cercana a 0-, por tener menor tiempo de ejecución.

Ejemplo 1

Ejemplo 2

Ejemplo 3

Ejemplo 4

¿Cómo demostramos que un algoritmo funciona?

Notas

https://www.youtube.com/watch?v=WwOVmvSQu2w&list=PLL1cieOZqlW4EI43XJkKeYobDGsmXtZEM&index=6&ab_channel=smm_oficial

Caso de estudio: suma

Input: Una secuencia de nn números reales [a1,a2,a3,...,an][a_1,a_2,a_3,...,a_n].

Output: Un valor real rr, tal que r=inair=\sum_i^n a_i

SUM(A)
	n = A.length                 c1(1)
  r = A[n]                     c2(1)        
	for j = n-1  downto 1        c3(n)
	     do r = r + A[j]         c4(n-1)
	return r                     c5(1)

Invariante de lazo. En el inicio de cada iteración del bucle for lineas 3-4, rr es igual a la suma de los njn-j últimos elementos de AA.

Por lo tanto, el algoritmo es correcto.

Complejidad temporal.

T(n)=c1+c2+c3n+c4(n1)+c5=(c3+c4)n+(c1+c2c4+c5)T(n)=c_1+c_2+c_3n+c_4(n-1)+c_5=(c_3+c_4)n+(c_1+c_2-c_4+c_5).

T(n)=(c3+c4)n+(c1+c2c4+c5)anT(n)bnT(n)=Θ(n)T(n)=(c_3+c_4)n+(c_1+c_2-c_4+c_5)\\ an\le T(n)\le bn\\ T(n)=\Theta(n)

Caso de estudio: búsqueda binaria

Entrada: Una secuencia de n números A = <a1, a2,..., an> y un valor v.

Salida: Un índice i tal que v=A[i]v = A[i] o el valor especial NIL si v no se encuentra en A.

binary_search(A, v):
  if A[-1] < v:
    return Nil
  p = 0
  r = len(X)
  while p < r:
    mid = (p+r)//2
    if A[mid] == v:
      return mid
    if A[mid] < v:
       p = mid + 1
    if A[mid] > v:
       r = mid - 1 
  return Nil

Notebook

Notas y recursos

Para visualizar alguno de los algoritmos: https://visualgo.net/en o https://algorithm-visualizer.org/

https://tildesites.bowdoin.edu/~ltoma/teaching/cs231/duke_cps130/Lectures/L06.pdf

https://www.cs.stanford.edu/~trevisan/cs254-10/lecture02.pdf

https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/19/Small19.pdf

Preguntas frecuentes y no tan frecuentes

¿Hay θ\theta (theta pequeña)?

No. https://stackoverflow.com/questions/25593619/why-doesnt-small-theta-asymtotic-notation-exist

¿Es lo mismo peor caso, mejor caso y caso promedio que el análisis asintótico?

No.

Técnicas de Diseño de Algoritmos

💡
Las técnicas que se verán no pretenden reducir el diseño a un algoritmo, sino orientar tus esfuerzos hacia la dirección óptima.

La siguiente lista -no exhaustiva- de técnicas, patrones de diseño, métodos o paradigmas son enfoques para encontrar algoritmos óptimos:

Divide y vencerás (divide et impera)

Para resolver problemas con Divide y vencerás consiste en los siguientes tres pasos:

Análisis

💡
Algoritmos recursivos pueden convertise a algoritmos iterativos, y lo inverso. A veces es más fácil, a veces no es obvio.

Los algoritmos recursivos deben analizarse de manera distintos a otra clase: usamos recurrencias, porque son una manera natural de medir su tiempo.

💡
Existe una idea extendida que los algoritmos iterativos son más rápidos que los algoritmos recursivos, esto a priori no es cierto, por eso debe demostrarse asintóticamente. Sin embargo, supongamos que tenemos dos algoritmos uno recursivo y otro iterativo con la misma complejidad del tiempo, en lenguajes imperativos (C, Java, JavaScript, …) es preferible el iterativo, en lenguajes funcionales (Haskell, Lisp, Erlang…) el recursivo (Stack Overflow). Véase en Jupyter el ejemplo de Merge Sort iterativo vs recursivo donde tienen un tiempo promedio parecido para su peor caso.

Relaciones de recurrencia

Dos maneras de resolver la recurrencia:

Sin embargo, como te darás cuenta en los siguientes ejercicios, el método maestro, aunque bastante rápido, es bastante limitado, asi surgio la necesidad de generalizarlo: método Akra–Bazzi (https://link.springer.com/article/10.1023/A:1018373005182.

Una manera de demostrar nuestra suposición:

Ejemplo 1 con Árbol de recurrencias.

Sum(n) {
    if n == 1
        return 11
    return n + Sum(n-1)
}

Ejemplo 2 con Método maestro

recursiveFun1(n)
{
    if (n <= 0)
        return 11;
    else
        return 11 + recursiveFun1(n/2);
}

Ejemplo 3 con Método maestro

recursiveFun3(n)
{
    if n <= 0
        return 11
    else
        return 11 + recursiveFun3(n/5)
}

Ejemplo 4

int recursiveFun2(int n)
{
    if (n <= 0)
        return 11;
    else
        return 11 + recursiveFun2(n-5);
}

Ejemplo 5

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // T(n)=c1+c2+c3+...=c
    }
    if n <= 0
        return 1
    else
        return 1 + recursiveFun5(n-5)
}

Ejemplo 6

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

Ejemplo 7 Factorial

factorial(n)
{
    if (n == 0)
    {
        return 1
    }
    return n * factorial(n-1);
}

Caso de estudio: Permutación

Encuentra T(n)T(n), Ω(n)\Omega(n) para cualquier algoritmo de permutación y elimina la recursión.

string permute(string str, int index = 0, string acc = "") {
    if (index == str.length() - 1) {
        acc += str + "\n";
        return acc;
    }
    for (int subIndex = index; subIndex < str.length(); subIndex++) {
        swap(str[index], str[subIndex]);
        acc = permute(str, index + 1, acc);
    }
    return acc;
}

Caso de estudio: Máximo común divisor

Encuentra T(n)T(n) y elimina la recursión.

gcd(int a, int b)
  if b == 0
     return a
  return gcd(b, a mod b)

Los problemas, mas no las soluciones, fueron obtenidos en

https://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation

https://github.com/sanchezcarlosjr/uabc/blob/main/src/datastructure-week5-test/PermutationAlgorithm.h

Programación dinámica (PD)

💡
PDmemoizacioˊn+recursividadPD \approx memoización + recursividad

Creada por Richard Bellman en la RAND corporation, programación es, por inglés británico, optimización. Proviene de programación lineal -método tabular- y no refiere a escribir código. El nombre puede ser un poco oscuro, y eso es por cuestiones políticas: el nombre fue eligido para convencer a sus jefes ocultando el hecho de que estaban investigando matemáticas, programación porque estaba de moda y dinámico para que el nombre suene más interesante. El nombre original era: optimally plan multistage processes.

Esta técnica es parecida a divide y vencerás, donde en aquel vimos subproblemas independientes y pequeños (n/bn/b) resueltos recursivamente, en programación dinámica los subproblemas son dependientes, no tan pequeños (nan-a), resueltos iterativamente, y regularmente usado para problemas de optimización (lo cual implica tomar decisiones dirigida a encontrar la mejor solución). En general, convierte algoritmos con tiempo exponencial a tiempo polinomial.

Este paradigma resuelve cada subsubproblema y entonces lo guarda en una tabla, evitando el recálculo cuando los siguientes subproblemas necesiten la respuesta a ese subsubproblema, a esto se le conoce como memoización (no memorizar, memoizar), que es la idea central de PD, que en otras palabras, memoizar significa recordar y reusar soluciones de subproblemas.

Pasos para usar este paradigma:

  1. Caracterizar la estructura de una solución óptima.
  1. Definir recursivamente el valor de una solución óptima.
  1. Calcular el valor de una solución óptima en un esquema bottom-up (iterativo) o top-down (recursivo).
  1. Construir una solución óptima a partir de la información calculada.

O también puedes el marco de trabajo SRBOT:

1. Definir subproblema con palabras.

  • Escribir el subproblema en términos del valor de la solución o de la solución en sí misma -a veces pueden coincidir, pero no son lo mismo-: no es lo mismo el tamaño de la secuencia que la secuencia.

2. Relacionar las soluciones de los subproblema recursivamente.

  • Muchos de las relaciones involucran el uso las funciones min,maxmin,max.
  • Es el paso más difícil.

3. Orden topológico de los subproblemas (en este caso, es un subproblema DAG).

4. Caso base de la relación.

5. Original problema vía subproblemas.

  • Si la relación de recurrencia es lineal, el problema puede ser resuelto en O(1)O(1), véase ecuaciones en diferencias.
  • En otro caso, debe ser un esquema bottom-up (iterativo) o top-down (recursivo).

6. Tiempo de análisis.

Notas y referencias

MIT 6.006 Introduction to Algorithms, Spring 2020

MIT 6.006 Introduction to Algorithms, Fall 2011

Estrategias voraces, ávidas o glotonas (Greedy algorithms)

Al igual que la programación dinámica, los algoritmos voraces buscan una solución con el óptimo resultado, en el primero para algunos problemas determinar la mejor solución global dado el conjunto de pasos en cada paso puede ser muy costoso, en el segundo buscamos la mejor solución en el momento, esto significa, seleccionar soluciones óptimas locales repetidamente con esperanza de que esa sea la solución global, claramente, esto no significa que no siempre dará la solución óptima global.

Pasos para usar este paradigma:

  1. Caracterizar la subestructura óptima del problema.
  1. Desarrollar una solución recursiva.
  1. Mostrar que la elección es voraz, entonces un subproblema pertenece.
  1. Demostrar que es una elección segura.
  1. Desarrollar un algoritmo recursivo que implemente la estrategia voraz.
  1. Convertir el algoritmo recursivo a uno iterativo.

Notas y referencias

Campos, J. (2021). Algoritmos voraces. Universidad de Zaragoza. http://webdiis.unizar.es/asignaturas/AB/material/2-Algoritmos Voraces.pdf

Métodos probabilísticos -Algoritmos aleatorios-

Si un algoritmo, que además de su entrada, usa un generador de números aleatorios o toma decisiones aleatorias en su ejecución, entonces es aleatorio, cuando solo depende de su entrada es determinista. En la práctica, usamos generadores pseudoaleatorios. El tiempo de ejecución y, en otros casos su salida, no son fijos para una entrada dada.

Ejemplos

Ejemplo 1 Algoritmos de Las Vegas (LV)

Entrada. Una secuencia de n elementos a0,a1,...,ana_0,a_1,...,a_n, el elemento aa y aa pertenece a la sequencia.

Salida. ii tal que a=aia=a_i.

buscar_el_elemento(a, A)
 i = 0
 while A[i] != a
    i = RANDOM(0, A.length) #  0 <= i <= A.length, i es aleatorio
 return i

Ejemplo 2 Algoritmos de Monte Carlo (MC)

Entrada. Una secuencia de n elementos a0,a1,...,ana_0,a_1,...,a_n, el elemento aa y kk el límite de iteraciones.

Salida. ii tal que a=aia=a_i.

buscar_el_elemento(a, A, k)
   for i=0 to k
      j=RANDOM(0, A.length) #  0 <= j <= A.length, j es aleatorio
      if A[j] == a
         return j

Notas y referencias

Karp, R. M. (1991). An introduction to randomized algorithms. Discrete Applied Mathematics, 34(1-3), 165-201.

Algoritmos de aproximación

Una amplia variedad de problemas importantes son NP-completos (horario de trabajo, el problema del viajero o vendedor, ...), entonces no podemos sencillamente abandonarlos porque no sabemos algoritmos que lo resuelvan en tiempo polinomial. Para esto, diseñamos algoritmos con tiempo polinómico que se acercan a la solución por un factor: radio de aproximación ρ(n)\rho(n) tal que

max(CC,CC)ρ(n)max(\dfrac{C}{C^*},\dfrac{C^*}{C})\le \rho(n)

donde CC^* es el costo de la solución óptima y CC es el costo de producido por el algoritmo.

Preguntas frecuentes

¿Todos los algoritmos recursivos siguen un enfoque divide y vencerás?

No.

¿Estas técnicas son mutuamente excluyentes, esto es, si puedo aplicar una, no puedo aplicar las otras?

Son mutuamente excluyentes.

La RAE no recoge el verbo memoizar ni la memoización, debe ser memorizar y memorización

Notebook

Algoritmos sobre grafos

💡
Los grafos pueden generarse en tiempo de ejecución por lo que sus algoritmos -DFS, BFS, …- pueden ser usados como un paradigma de resolución problemas: optimización, búsqueda, ...

Representación o ¿qué estructura de grafos usamos?

Grafo
Matriz de adyacencia
Lista de adyacencia
{
  "A": {"B", "C"},
  "B": {"A", "C", "D", "E"},
  "C": {"A", "B", "D"},
  "D": {"C", "B", "E"},
  "E": {"D", "B"}
}
Matriz de adyacenciaTabla HashLista de adyacenciaOrientado a objetos
ComentariosPara grafos pequeños suele ser la preferida porque es más simple.Usando en vez de listas tablas hash, conseguimos saber si dos vertices son adyacentes en O(1).En espacio es más eficiente que la matriz de adyacencia.Para guardar atributos como el nombre, distancia, costo, … usamos este enfoque.

Elementales

BFS

DFS

Backtracking, también llamado depth-first search [1].

Notebook

Laberinto

Crea tus propios algoritmos para conseguir ir del punto A al punto B en un un laberinto.

https://graph-theory.sanchezcarlosjr.com/

Notas y referencias

[1] https://arxiv.org/pdf/cs/0011047.pdf. En esto puede llegar a existir confusión.

Preguntas frecuentes

¿Existe un compendio de todos los teoremas, definiciones, ...?

https://people.math.sc.edu/cooper/math776/StudyGuide.pdf

¿Red o grafo?

Grafo es el concepto abstracto matemático.

Red es el grafo que representa objetos del mundo real, los nodos son entidades del sistema y las aristas representan la relacion entre ellos.

Sin embargo, en la literatura puedes encontrarlos indistintamente.

https://bence.ferdinandy.com/2018/05/27/whats-the-difference-between-a-graph-and-a-network/

https://arxiv.org/pdf/1302.4378.pdf

http://networksciencebook.com/

Notas y referencias

Para aprender de manera visual teoría de grafos: https://d3gt.com/unit.html, usar el apéndice de CLRS, o el libro Frank Harary. Graph Theory. Addison-Wesley, 1969.

Ensayo sobre la representación de grafos: https://www.python.org/doc/essays/graphs/

Introducción a la Teoría de la Computación

🔥
Esto se cubrirá en mayor a detalle en un curso de Teoría de autómatas.

Complejidad computacional

Dificultad de un algoritmo.

Notas y referencias

https://plato.stanford.edu/entries/computational-complexity/

Tópicos selectos de aplicación

¿Qué es lo que sigue? ¿Cuál es el estado del arte?

Inmediatamente después:

Si te interesa la investigación:

Si te interesan los retos y las matemáticas:

Si te interesa el open source:

Ambos eventos abren convocatoria a inicio de año y debes pasar por una serie de filtros.

Si te interesa participar en programación competitiva -nivel universitario-:

Si te interesa trabajar en una gran empresa como las FANG, es seguro que te aplicarán entrevistas técnicas -en inglés-. Sitio para practicar gratis: https://leetcode.com/