domingo, 21 de septiembre de 2008

1.4- seleccion de un algoritmo

1.4- seleccion de un algoritmo
cuando se resuelve un problema y hay la nesesidad de elejir entre varios algoritmos
que nos puedan dar un resultado existen dos objetios que suelen contradesir se para
elejir uno
a)que el algoritmo seafaslde entender , codificar y depurar
b)que el algoritmo use eficientrementelos recursos del computadora y se ejecuten
con mayorr rapides posible

el primer punto se deve elejir cuando se escribe un programa que se vaa utilizar
una o pocas veses ya que el costo del tiempo de programacion no sera tan selevante
ya que solo se ejecutara en pocas ocasiones.
el punto b es masinportante coando se presenta un problema cutya solucion se va
autilizar mucha vese ya que elcostode ejecucion del prigrma nimisara el costo de
escritura.
en conclucion siempre saramas ventajodo del punto de vista economico realisar un
algoritmo complejo siempre y cuando el tiempo de ejecucion del rpogram resulte
significativa mente menor

1.3.2-comlejidasd en el espacio

1.3.2-comlejidasd en el espacio
-complejidad espacial?
esla menoria ue utiliza un programa para su ejecucion lo que inplica que la
eficiencia de memoria de un algoritmo lo indicala cantidad de espacio requerido
par ejecutarloes desir en elpacio en memoria que ocupan todas las variables propias
del algoritmo.

1.3-complejidad

1.3.1-tiempo de ejecucion de un algoritmo
como se mide el tiempo de ejecucion de un programa en funcion de N (numero de datos)?. esta funcion se puede medir fisicsamente calulandola con un reloj o se puede calcular con el codigo contando las intrucciones a ejecutar y multiplicandoli por el tiempo requerido por cada intruccion.


reglas practicas para calcular la omplejidad de un algoritmo
1.-sentencia sencilla:se refiere alas sentencia de asigacion mostrada en la asalida de datos simpre yc cunado no trnaaje sobre estructuras cullo tamano esta relacionado con N. como requiere un tiempo constante de ejecucion su complejidad es del orden 1
2.-secuencia de sentencia: su complejidad esta dada por la suma de las complejidades individuales de acuerdo al tipo de sentencias tomandose en cuneta el orden mas alto.
3.-decision (if): la cindicion suele ser de orden constante O(1), sumando en la peor rama posible ya sea d la del then o l a del else
4.-bucles(ciclos): en los cilcos con contaddor explisito existen dos casos el tamana N forme parte de los limites del ciclo o no

en los cickos multiplicatios com el whiley el do while el inremento de la variable control no es nineal no que ase incrementar el orden de complejidad como en los ejemplos siguientes.

COMPLEJIDAD LOG(log n)
5.-llamdas de procedimientos: la complejidad e llamar a un prosedoimiento esta dada por la cmplejidad del contididdo del proisedimeinto en si , es desir su complejidad depende del tipo de intrucciones o sentencias que existan en el cuerpo del prodedimiento. en clonclucion la comliejidad dein prosedimineto tiende a complidarse si se trata de prosediminetos recursivos


ordenes de complejidad
O(1)constante idela
O(n)lineal eficente
O(log n)logaritmico eficente
O(n log n)casi lineal eficente
O(n*)polinomial tratable
o(K^n)exponencial intratables
o(n!)factorial intratables

1.2aritmetica de la notación 0.

1.2aritmetica de la notación 0.

Notación asitotica “O” grande

Se utiliza para hacer referencia a la velocidad de seguimiento de los valores de una función. La habilidad de anotar esta anotación a en algoritmo es encontrar el limite superior del tiempo de ejecución, es decir el peor caso.

Definición.-

1g(n)1<=1c.f(n), para todo n>=n.

Esto significa que la función g(n) pertenece o es valida para f(n) si solo si existen las constantes c no tales que para N>=n. T(n)<=cn el orden de la magnitud de la función será el orden del termino de la función mas grande de n.

NOTACIOJN ASINTOTICA "OMEGA" GRANDE

LA FUNCION OMEGA GRANDE ITILIZA SE UTILIZA PARA EXPLICAR UNA COTA INFERIOR PARA LA VELOSIDAD DEL DE UNA FUNCION F(N) CUIANDO ESTA EN FUNCION DE N UNA LA DENOTACION T(N) ES OMEGA GRANDE (G(N)) Y SIGNIFICA QUE EXISTE UAN ACONSTANTE C TAN Y QUE T)N(=>C)(G(N))PARFA UN NUMEO INFINITO PARA VALORES DE N.

1.1 Concepto de complejidad de algoritmos.


1.1 Concepto de complejidad de algoritmos.

Teoría de la complejidad computacional.

Es la parte de la teoría de la computación que estudia los recursos necesarios durante el cálculo para resolver un problema. Estos recursos son el tiempo y el espacio clases de complejidad.

Los problemas de decisión (aquellos donde la respuesta posible es si o no) se clasifican en conjunto de complejidad comparable que son (llamados clases de complejidad).

a) Clase de complejidad P:

El conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinomico de una maquina de turning, lo que corresponde al problema que puede ser resuelto a aun en el peor de sus casos.

b) Clases de complejidad NP:

Es el conjunto de los problemas de decisión que pueden ser resueltos por una maquina de turning no determinista en tiempo polinomico la propiedad de que su solución puede ser verificada.

El problema de satisfacción booleana el programa es poco satisfactoria.

c) Clase de complejidad NP-completo:

Es le subconjunto de los problemas NP que se destacan por su extrema complejidad en la cual algunos de ellos en la actualidad no han encintrado una solución satisfactoria.

La suma de subconjuntos dado un conjunto S de enteros ¿existe un subconjunto no vació cuyo electos sumen 0?dos grafos son isomorfos.

Diagrama de la relación entre las clases de complejidad

Problemas de decisión

Presenta à¿las clases p y NP son diferentas o no?


Unidad 1 Análisis de algoritmos.