Algoritmos en el desarrollo de software

Temario

1. Definición de algoritmo
2. Importancia en el desarrollo de software
3. Integración de algoritmos en aplicaciones CRUD
4. Medición de la complejidad
   4.1 Función de crecimiento
   4.2 Notaciones $\Omega(g(n)), O(g(n)), \Theta(g(n))$
   4.3 Ejemplos
5. Relación con las estructuras de datos
   5.1 Principales estructuras de datos
6. Algoritmos de ordenamiento
7. Algoritmos para grafos
8. Bibliotecas de algoritmos
9. Conclusiones

1. Definición de algoritmo

Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output. [Cormen]

Por ejemplo:

2. Importancia en el desarrollo de software

Todo el software está hecho de algoritmos.

3. Integración de algoritmos en aplicaciones CRUD

4. Medición de la complejidad

4.1 Función de crecimiento

4.2 Notaciones $\Omega(g(n)), O(g(n)), \Theta(g(n))$

Estas notaciones denotan límites inferior, superior y ambos respectivamente.

4.2.1 $\Omega(g(n))$

4.2.1 $O(g(n))$

4.2.1 $\Theta(g(n))$

4.3 Ejemplos

Acceso a un arreglo

Buscar un elemento en un arreglo ordenado (busqueda binaria)

Buscar un elemento en un arreglo (fuerza bruta)

Ordenamiento - Bubble sort

Busqueda en arbol binario (Depth First Search)

5. Relación con las estructuras de datos

El algoritmo definen los pasos a seguir mientras que las estructuras definen la manera de representar la información para su procesamiento.

5.1 Principales estructuras de datos

5.1.1 Arreglo

• Agregar: $O(1)$ <----- Un poco tardado
• Leer: $O(1)$
• Actualizar: $O(1)$
• Eliminar: $O(n)$

5.1.2 Lista

• Agregar:
  • Al inicio o final: $O(1)$
  • En orden: $O(n)$
• Leer: $O(n)$
• Actualizar: $O(n)$
• Eliminar: $O(n)$

5.1.3 Cola (FIFO)

• Encolar: $O(1)$
• Leer: $O(1)$
• Sacar: $O(1)$

5.1.4 Doble cola

• Encolar: $O(1)$
• Leer: $O(1)$
• Sacar: $O(1)$

5.1.5 Pila (FILO)

• Agregar: $O(1)$
• Leer: $O(1)$
• Sacar: $O(1)$

5.1.6 Grafo

• Busqueda DFS: $O(log(n))$
• Árbol generador mínimo:
  • Kruskal: $O(E*log(E)), O(E*log(V))$ donde:
    • $E = número de aristas$
    • $V = número de vértices$

5.1.7 Árbol

• Busqueda DFS:
  • Balanceado: $O(log(n))$
  • No Balanceado: $O(n)$
• Agregar:
  • Balanceado: $O(log(n))$
  • No Balanceado: $O(log(n))$ <----Mas operaciones

5.1.8 Tabla hash

• Inserción: $O(1)$
• Lectura: $O(n)$ <---- Casi nunca llega a $n$

6. Algoritmos de ordenamiento

SelectionSort $O(n^2)$
Insertion Sort $O(n^2)$
Bubble Sort $O(n^2)$
Merge Sort $O(n*log(n))$
Quick Sort $O(n*log(n))$
Comparación

7. Algoritmos para grafos

Breadth-First Search
Depth-First Search

8. Bibliotecas de algoritmos

QuickGraph
Numerical

9. Conclusiones

• Investigar complejidad de funciones que utilizamos
• Ante un problema investigar si existen bibliotecas ya existentes
• En caso de no existir implementar de manera optima lo necesario