
¿Qué es un algoritmo?
â(del árabe al-Khowârizmî, sobrenombre del célebre matemático árabe Mohámed ben Musa). Conjunto ordenado y finito de operaciones que permite encontrar la solución a un problemaâ¦â
Un algoritmo, puede expresarse en términos de un lenguaje de programación, para obtener un programa que resuelve el problema por medio de la computadora.

Cita...
âNo hay un incremento concebible en el poder de las computadoras que pueda saturar la demanda cientÃfica: aún pensando que una computadora posea un ciclo de tiempo subnuclear (10-23 seg.) y densidades de almacenamiento subnucleares (1039 bits/cm3), ésta no podrÃa manejar la mayorÃa de los problemas que son importantes en la investigación cientÃfica básica y aplicada. Por lo tanto, existirá siempre una fuerte presión para incrementar la eficiencia de los programas, para poder incrementar también la cantidad de información últil generada por un programa.â
Ken Wilson, Nóbel de FÃsica 1982

Ãreas de estudio
¿Cómo construir algoritmos?
Técnicas de diseño
¿Cómo expresar algoritmos?
Enfoques de los lenguajes de programación
¿Cómo validar algoritmos?
Verificación formal
¿Cómo analizar algoritmos?
Complejidad computacional, eficiencia, legibilidad, usabilidad, etc...

Análisis de algoritmos
Si se tuvieran 2 programas que hacen lo mismo, ¿cómo se podrÃan comparar?
1. Eficiencia:
Tiempo de ejecución
Uso de espacios de memoria
2. Facilidad de lectura, mantenimiento, rapidez para codificarlo.

Medición del tiempo de ejecución
El tiempo de ejecución depende de:
1. La entrada al programa:
Su tamaño
Sus caracterÃsticas
2. La calidad del código generado para el programa por el compilador .
3. La rapidez de las instrucciones de máquina.
4. La complejidad de tiempo del algoritmo.

¿Cómo medir?
Cantidad de instrucciones básicas (o elementales) que se ejecutan.
Ejemplos de instrucciones básicas:
asignación de escalares
lectura o escritura de escalares
saltos (gotoâs) implÃcitos o explÃcitos.
evaluación de condiciones
llamada a funciones
etc.

Ejemplo
cont = 1;
while (cont <= n) do {
x = x + a[cont];
x = x + b[cont];
cont = cont + 1;
}
1
n+1
n
n
n
n (goto implÃcito)
1 goto en falso.
TOTAL: 5n + 3

Ejemplo
z = 0;
for (int x=1; x<=n; x++)
for (int y=1; y<=n; y++)
z = z + a[x,y];
1
1 asignación + (n+1) comparaciones
(n+2)*n = n2 +2n
n*n = n2
2n2 (incremento + goto implÃcito)
n (goto en falso for y)
2n (incremento + goto implÃcito)
1 (goto en falso for x)
TOTAL: 4n2 + 6n + 4

Consecuenciaâ¦
Se requiere contar con una notación que permita comparar la eficiencia entre los algoritmosâ¦
La NOTACIÃN ASINTÃTICA es la propuesta de notación aceptada por la comunidad cientÃfica para describir el comportamiento en eficiencia (o complejidad) de un algoritmo.
Describe en forma sintética el comportamiento de la función que con la variable de entrada, determina el número de operaciones que realiza el algoritmo.

NOTACIÃN ASINTÃTICA
COMPLEJIDAD TEMPORAL (y ESPACIAL). Tiempo (o espacio) requerido por un algoritmo, expresado en base a una función que depende del tamaño del problema.
COMPLEJIDAD TEMPORAL ASINTÃTICA (y ESPACIAL). Comportamiento lÃmite conforme el tamaño del problema se incrementa. Determina el tamaño del problema que puede ser resuelto por un algoritmo.

Definición
Se dice que la función f(n) âes de orden g(n)â [O(g(n))], si existen constantes positivas c y n0 tales que f(n) <= c g(n) cuando n >= n0
Ejemplos:
n+5 es O(n) pues n+5 <= 2n para toda n >= 5
(n+1)2 es O(n2) pues (n+1)2 <= 4n2 para n>= 1
(n+1)2 NO es O(n) pues para cualquier c > 1 no se cumple que (n+1)2 <= c*n

Ordenes más comunes de los algoritmos
O(1) Constante
O(n) Lineal
O(n2 ) Cuadrático
O(n3 ) Cúbico
O (nm ) Polinomial
O(log(n)) LogarÃtmico
O(nlog(n)) nlog (n)
O(mn ) exponencial
O(n!) factorial

Comportamiento de las funciones
log n
n
n log n
n sqrt(n)
n2

Otro método para calcular el orden de un problema
Consiste en aplicar reglas a los estatutos estructurados:
Secuencia de instrucciones
Decisiones (ejemplo: if)
Ciclos (ejemplo: while)
Recursividad

Regla 1: Secuencia de instrucciones
Ejemplo:
Una secuencia de 3 ciclos:
Ciclo 1 = O(n)
Ciclo 2 = O(log n)
Ciclo 3 = O(n2)
Tendrá como orden totalâ¦
O(n2).
O(g1(n))
O(g2(n))
O(g3(n))
O(gm(n))
Ë O( mayor(g1(n), g2(n), â¦, gm(n) )

Regla 2: Decisiones
Ejemplo:
Una decisión con:
Rama then = O(n log n)
Rama else = O(log n)
Tendrá como orden totalâ¦
O(n log n).
O(g1(n))
O(g2(n))
Ë O( mayor(g1(n), g2(n)) )