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 Ω(g(n)),O(g(n)),Θ(g(n))\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]

Entrada
Algoritmo
Salida

Por ejemplo:

63,4,13,6,23,78
Algoritmo de ordenamiento
4,6,13,23,63,78

2. Importancia en el desarrollo de software

Todo el software está hecho de algoritmos.
El centro del desarrollo de software

3. Integración de algoritmos en aplicaciones CRUD

CRUD

ClienteServidor WebServidor de BD1. Obtener usuarios2. Obtener regs tabla Usuarios3. [User1, User2, ..]4. [User1, User2, ..]Ejemplo de petición READClienteServidor WebServidor de BD

4. Medición de la complejidad

Tiempo y espacio

4.1 Función de crecimiento

Funcion de crecimiento

4.2 Notaciones Ω(g(n)),O(g(n)),Θ(g(n))\Omega(g(n)), O(g(n)), \Theta(g(n))

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

4.2.1 Ω(g(n))\Omega(g(n))

Omega(n)

4.2.1 O(g(n))O(g(n))

O(n)

4.2.1 Θ(g(n))\Theta(g(n))

Theta(n)

4.3 Ejemplos

Acceso a un arreglo

SetElement

Buscar un elemento en un arreglo ordenado (busqueda binaria)

Binary Search

Buscar un elemento en un arreglo (fuerza bruta)

Find Element

Ordenamiento - Bubble sort

Bubble Sort

enter image description here

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

Arreglo

5.1.2 Lista

Cola

5.1.3 Cola (FIFO)

Cola

5.1.4 Doble cola

Doble Cola

5.1.5 Pila (FILO)

Pila

5.1.6 Grafo

Grafo

5.1.7 Árbol

Árbol

5.1.8 Tabla hash

Tabla Hash

6. Algoritmos de ordenamiento

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

7. Algoritmos para grafos

Breadth-First Search
Depth-First Search

8. Bibliotecas de algoritmos

QuickGraph
Numerical

9. Conclusiones