60921 unidad 1 conceptos analisis

An´alisis de Algoritmos
Unidad 1: Conceptos de An´alisis
Ing. Matias Valdenegro T.
Universidad Tecnol´
ogica Metropolitana

28 de diciembre de 2011

Introducci´on

Complejidad Algor´ıtmica

Recurrencias

An´alisis Asint´otico

Otros Tipos de An´alisis

Presentaci´on

Profesor: Matias Valdenegro T.
Ingeniero Civil en Computaci´
on menci´
on Inform´atica (2009).
Actualmente trabajo en elLaboratorio de Modelamiento
Matem´atico para Geomecanica del Centro de Modelamiento
Matem´atico, Facultad de Ciencias F´ısicas y Matem´aticas,
Universidad de Chile.
Pueden contactarme en matias.valdenegro@gmail.com

Contenidos del Curso

El contenido del curso esta compuesto de:
1.- Elementos de Analisis.
2.- Algoritmos y Problemas.
3.- Ordenamiento.
4.- El paradigma “divide-y-venceras”.
5.-Clasificacion de Problemas.

Evaluacion

La evaluacion de la asignatura es:
Prueba 1 con un 35 %.
Prueba 2 con un 35 %.
Promedio de notas de Tareas (6), con un 30 %.

Bibliografia

Basica
Algoritmos Computacionales: Introduccion al Analisis y
Dise˜
no. Sara Baase, Allen Van Gelder. Pearson Educacion.
ISBN 970-26-1042-8. (Disponible en Biblioteca).

Complementaria
Introduction to Algorithms, Second Edition.Thomas H.
Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford
Stein. MIT Press. ISBN 978-0-262-03293-3.
Papers y art´ıculos del ´
area, seleccionados por el profesor.

Introducci´on

Complejidad Algor´ıtmica

Recurrencias

An´alisis Asint´otico

Otros Tipos de An´alisis

Que es el An´alisis de Algoritmos?

An´alisis
Un an´alisis en sentido amplio es la descomposici´
on de un todo enpartes para poder estudiar su estructura y/o funciones.

An´alisis de Algoritmos
El an´alisis de algoritmos provee estimaciones te´
oricas para los
recursos necesarios para ejecutar un algoritmo. Generalmente los
recursos considerados son espaciales (Memoria RAM y
Almacenamiento) y tiempo de ejecuci´
on.

Porque?

Comparar algoritmos.
Determinar el mejor algoritmo para resolver un problema dado.Determinar si es posible resolver un problema dadas ciertas
restricciones de recursos.

Ejemplo

Se desea ordenar una base de datos que contiene datos de
personas, usando el RUT como indicador de orden. La base de
datos contiene 108 registros. Entonces:
1. Que algoritmo de ordenamiento se deberia usar?
2. Que requerimientos (cantidad) de memoria se requieren para
ordenar dicha cantidad de datos?
3.Es posible ejecutar ese trabajo en un computador con un
procesador de 2 GHz? Cuanto tiempo tomara
(aproximadamente)?

Algoritmo

Definici´on
Un algoritmo es un procedimiento paso-a-paso para resolver un
problema en una cantidad de tiempo finita.

Definici´on Alternativa
Un algoritmo es una funci´
on que transforma un objeto entrada en
un objeto salida.

Nota Importante
En general, los algoritmosse usan para resolver problemas.

Ejemplo simple

Dado el siguiente algoritmo:
int f ( int n)
{
i f ( n == 0 | | n == 1 ) {
return 1;
} else {
return f ( n − 1) + f ( n − 1 ) ;
}
}
Es posible determinar (estimar) cuanto tiempo de computo tomara
f(10)? f(100)? f(n)?

Ejemplo simple: Gr´afico

Caracterizaci´on del Tiempo de Ejecuci´on

La pregunta es: De que depende el Tiempo de Ejecuci´on de unAlgoritmo?
Cuanto tiempo toma ordenar un arreglo de 10, 100 y 1000
elementos?
Cuanto tiempo toma ordenar un arreglo con elementos
aleatorios? Cuanto tiempo toma ordenar un arreglo ya
ordenado?

Caracterizaci´on del Tiempo de Ejecuci´on

La caracter´ısticas que mas influyen en el Tiempo de Ejecuci´on son:
Del tama˜
no de la entrada (N) del algoritmo.
Largo del arreglo de entrada
Numero de nodos deuna lista
Altura del ´arbol de entrada.

De caracter´ısticas de los valores de la entrada.
Datos ordenados.
Datos con patrones no deseados.

Caracterizaci´on del Tiempo de Ejecuci´on

El tiempo de ejecuci´on crece con el tama˜
no de la entrada.
Existen varios casos para el tiempo de ejecuci´
on:
Mejor caso (Best case).
Caso promedio. (Average case).
Peor caso. (Worst case).

Introducci´on...