domingo, 21 de septiembre de 2008
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
-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.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.
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?