Analisis de algoritmos

I. Introducción al
Análisis de Complejidad
Problemas y Algoritmos
Métodos de Análisis y Diseño de Algoritmos
Crecimiento de Funciones
Métodos para la Solución de Recurrencias
Métodos Probabilísticos
Tópicos Selectos (Ordenamiento, Ordenamiento
Lineal, Estadísticas de Orden, Tablas Hash)
1

Problemas y Algoritmos
Algoritmo. (RAE, 22 edición).
Conjunto ordenado y finito de operacionesque permite hallar la
solución de un problema.
Método y notación en las distintas formas del cálculo.
a

Algoritmo (computacional). (Cormen et al., 2001)
Procedimiento que toma un valor, o conjunto de valores, como entrada
y produce un valor, o conjunto de valores como salida. Un algoritmo es
entonces una secuencia de pasos computacionales que transforman
una entrada en una salida.Herramienta para resolver un problema computacional bien
especificado. La descripción del problema especifica en términos
generales la relación entrada/salida deseada. El algoritmo describe un
procedimiento computacional específico para lograr esa relación
entrada/salida.
Análisis de Algoritmos – Introducción al Análisis de Complejidad
Dr. Everardo Gutiérrez López

2

Problemas y AlgoritmosProblemas (ejemplos).
Proyecto del Genoma Humano: determinación de las información
contenida, almacenamiento de esa información en bases de datos y
desarrollo de herramientas para su análisis.
Internet: acceso y recuperación eficiente de grandes cantidades de
información, determinación de rutas para el intercambio de información
y máquinas de búsqueda.
Comercio electrónico: manejo deinformación confidencial, criptografía,
firmas digitales, etc.
Manufactura: asignación y distribución de recursos.

Características.
Poseen un conjunto de soluciones candidatas.
Tienen aplicaciones prácticas.

Análisis de Algoritmos – Introducción al Análisis de Complejidad
Dr. Everardo Gutiérrez López

3

Problemas y Algoritmos
Problema (computacional).
Conjunto de casos descritos pormedio de una secuencia de datos de entrada.

Caso de un problema.
Datos de entrada, que satisfacen las restricciones relativas a la definición del
problema, necesarios para el computo de una solución del problema.

Ejemplo: Ordenamiento ascendente de n números reales.
Definición:
• Entrada: Una secuencia de n números reales .
• Salida: Una permutación (reordenamiento) de la secuenciade entrada tal que a’1 ≤ a’2 ≤ … ≤ a’n.

Dada la secuencia de entrada (caso) , un algoritmo de
ordenamiento ascendente regresa como salida la secuencia .

Análisis de Algoritmos – Introducción al Análisis de Complejidad
Dr. Everardo Gutiérrez López

4

Problemas y Algoritmos
Corrección. Se dice de un algoritmo que es correcto si,
para cada caso del problema, termina con la salidacorrecta.
Un algoritmo correcto resuelve el problema computacional dado.
Un algoritmo incorrecto podría no terminar o podría terminar con una salida
diferente a la deseada para algunos casos del problema.

Un algoritmo puede ser especificado de diferentes
maneras: lenguaje natural, programa computacional,
diseño de hardware, etc.
Tenemos como único requerimiento el que la especificación debeproveer una
descripción precisa del procedimiento computacional a seguir.
En este curso utilizaremos pseudo-código para expresar los algoritmos,
siguiendo la notación establecida en Cormen et al., 2001.

Análisis de Algoritmos – Introducción al Análisis de Complejidad
Dr. Everardo Gutiérrez López

5

Problemas y Algoritmos
Eficiencia. La eficiencia de los algoritmos se mideprincipalmente
considerando el tiempo de ejecución y el espacio en memoria que
requieren para resolver un problema. Esta eficiencia suele expresarse
en función del tamaño de la entrada del problema.
En tiempo.
En espacio.

Problemas NP-completos. (Garey y Johnson, 1979)
Considerando la medida de eficiencia más utilizada (tiempo), existen algunos
problemas para los cuales no se conocen actualmente...