22/08/19

Análisis de algoritmos

Conjunto de instrucciones precisas y finitas que resuelven un problema.

Es un bien ordenada colección sin ambigüedad y efectivo cuando se ejecuta.

Se realiza una actividad en parejas para ver cuales son los que aciertan más características. El profe da un chocolate a los ganadores.

Algunas de las características son:

*Finito

*Definitivo (No admite ambigüedad)

*Efectivo: Que lo haga != eficiencia

*Eficiencia: Lo hace de la mejor manera. Depende del criterio a evaluar.

*Deterministico: Siempre que se le da un conjunto de entrada, da el mismo conjunto de salida.

¿Como se representa un algoritmo?

*Pseudocodigo

*Lenguaje natural no ambiguo.

*Lenguaje formal: Evito malos entendidos pero es más complicado entenderlo.

¿Qué es un análisis de algoritmos?

Determinar características de un algoritmo. Es una metodología para estimar el consumo de recursos del algoritmo.

Buscamos descubrir características para evaluar si el algoritmo me va a funcionar.

*Clasificar problemas y asignar una dificultad.

*Puedo predecir rendimiento y afinar parámetros.

*Tener un mejor rendimiento de los algoritmos.

Factores que afectan:

CU, Memora, Disco.

*Compilador.

*Sistema Operativo

*Lenguaje de programación.

*Habilidad del desarrollador.

*Aplicaciones que se estén mejorando.

¿Que determinar como medida para saber si un algoritmo es bueno?

*Tiempo(CPU) :Cuanto tarda en un computador especifico. Ejemplo 4GB de RAM a una de 2 GB de RAM.

*Espacio(Disco/Memoria). Cuanto espacio me consume el programa.

¿Hay otras caracteristicas?

*Consumo de Red. *Consumo de Pantalla. *Dispositivos Periféricos. *Cuantas veces debo imprimir. *Cualquier recurso de la computadora es bueno para determinar.

Tres métodos:

Empírico

*Benchmanck

Problema:No es la mejor forma.

Simulacional

Hacer casos de prueba Problema: No se pueden probar todos los casos.

Analítico

Define modelos matemáticos en tiempo y espacio.

Analizar la complejidad computacional:

Complejidad en tiempo.

Representar el algoritmo en función del tamaño del input. 

Se concentra en las operaciones dominantes (aritméticas)

Analiza donde crece la información