Algoritmos
Páginas: 9 (2122 palabras)
Publicado: 17 de septiembre de 2010
PORTAFOLIO UNIDAD 1
03. SEP. 2010
* NADIA NAYELI HERRERA HERNANDEZ.
ANALISIS DE ALGORITMOS.
En la mayoría de los casos la elección de un buen algoritmo
está orientada hacia la disminución del costo que implica la solución del problema; bajo este enfoque es posible dividir los criterios en dos clases:
* Criterios orientados a minimizar el costo de desarrollo: claridad, sencillezy facilidad de implantación, depuración y mantenimiento.
* Criterios orientados a disminuir el costo de ejecución: tiempo de procesador y cantidad de memoria utilizados.
Si el programa que implanta el algoritmo se va a ejecutar unas cuantas veces, el costo de desarrollo es dominante, en este caso se debe dar más peso a los primeros criterios. Por el contrario, si el programa se va autilizar frecuentemente, dominará el costo de ejecución, y por ende, se debe elegir un algoritmo que haga uso de los recursos de la computadora, es decir, se le debe evaluar prioritariamente bajo los criterios de la segunda clase.
CONCEPTO DE COMPLEJIDAD DE ALGORITMOS.
La complejidad de los algoritmos se encuentra en que tiene que dar una eficiencia al programa ya que depende de dos cosas elespacio (la memoria que utiliza) y el tiempo (lo que tarda en ejecutarse).
ARITMÉTICA DE LA NOTACIÓN O
El tiempo de ejecución es proporcional, se saca multiplicando por una constante los tiempos de ejecución propuestos anteriormente y se suman términos mas pequeños.
La notación O-grande ignora los factores constantes, es decir, ignora si se hace una mejor o peor implementación delalgoritmo, además de ser independiente de los datos de entrada del algoritmo, la utilidad de aplicar esta notación a un algoritmo es encontrar un límite superior del tiempo de ejecución.
Los problemas matemáticos se pueden dividir en primera instancia en dos grupos:
* Problemas indecidibles: aquellos que no se pueden resolver mediante un algoritmo.
* Problemas decidibles: aquellos quecuentan al menos con un algoritmo para su cómputo.
Que un problema sea decidible no implica que se pueda encontrar su solución, muchos problemas que disponen de algoritmos para su resolución son inabordables para un computador por el elevado número de operaciones que hay que realizar para resolverlos. Esto permite separar los problemas decidibles en dos:
intratables: aquellos para los que no esfactible obtener su solución.
tratables: aquellos para los que existe al menos un algoritmo capaz de resolverlo en un tiempo razonable.
Los problemas pueden clasificarse también atendiendo a su complejidad. Aquellos problemas para los que se conoce un algoritmo polinomio que los resuelve se denominan clase P. Los algoritmos que los resuelven son deterministas. Para otros problemas, sus mejoresalgoritmos conocidos son no deterministas. Esta clase de problemas se denomina clase NP. Por tanto, los problemas de la clase P son un subconjunto de los de la clase NP, pues sólo cuentan con una alternativa en cada paso.
COMPLEJIDAD.
La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real.Ambos componentes tienen su importancia; pero la del algoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota.
A efectos prácticos o ingenieriles, nos deben preocupar los recursos físicos necesarios para que un programa se ejecute. Aunque puede haber muchos parametros, los mas usuales son el tiempo de ejecución y la cantidad de memoria (espacio).Ocurre con frecuencia que ambos parametros están fijados por otras razones y se plantea la pregunta inversa: ¿cual es el tamano del mayor problema que puedo resolver en T segundos y/o con M bytes de memoria? nos centraremos casi siempre en el parametro tiempo de ejecución, si bien las ideas desarrolladas son fácilmente aplicables a otro tipo de recursos.
TIEMPO DE EJECUCIÓN DE UN ALGORITMO....
03. SEP. 2010
* NADIA NAYELI HERRERA HERNANDEZ.
ANALISIS DE ALGORITMOS.
En la mayoría de los casos la elección de un buen algoritmo
está orientada hacia la disminución del costo que implica la solución del problema; bajo este enfoque es posible dividir los criterios en dos clases:
* Criterios orientados a minimizar el costo de desarrollo: claridad, sencillezy facilidad de implantación, depuración y mantenimiento.
* Criterios orientados a disminuir el costo de ejecución: tiempo de procesador y cantidad de memoria utilizados.
Si el programa que implanta el algoritmo se va a ejecutar unas cuantas veces, el costo de desarrollo es dominante, en este caso se debe dar más peso a los primeros criterios. Por el contrario, si el programa se va autilizar frecuentemente, dominará el costo de ejecución, y por ende, se debe elegir un algoritmo que haga uso de los recursos de la computadora, es decir, se le debe evaluar prioritariamente bajo los criterios de la segunda clase.
CONCEPTO DE COMPLEJIDAD DE ALGORITMOS.
La complejidad de los algoritmos se encuentra en que tiene que dar una eficiencia al programa ya que depende de dos cosas elespacio (la memoria que utiliza) y el tiempo (lo que tarda en ejecutarse).
ARITMÉTICA DE LA NOTACIÓN O
El tiempo de ejecución es proporcional, se saca multiplicando por una constante los tiempos de ejecución propuestos anteriormente y se suman términos mas pequeños.
La notación O-grande ignora los factores constantes, es decir, ignora si se hace una mejor o peor implementación delalgoritmo, además de ser independiente de los datos de entrada del algoritmo, la utilidad de aplicar esta notación a un algoritmo es encontrar un límite superior del tiempo de ejecución.
Los problemas matemáticos se pueden dividir en primera instancia en dos grupos:
* Problemas indecidibles: aquellos que no se pueden resolver mediante un algoritmo.
* Problemas decidibles: aquellos quecuentan al menos con un algoritmo para su cómputo.
Que un problema sea decidible no implica que se pueda encontrar su solución, muchos problemas que disponen de algoritmos para su resolución son inabordables para un computador por el elevado número de operaciones que hay que realizar para resolverlos. Esto permite separar los problemas decidibles en dos:
intratables: aquellos para los que no esfactible obtener su solución.
tratables: aquellos para los que existe al menos un algoritmo capaz de resolverlo en un tiempo razonable.
Los problemas pueden clasificarse también atendiendo a su complejidad. Aquellos problemas para los que se conoce un algoritmo polinomio que los resuelve se denominan clase P. Los algoritmos que los resuelven son deterministas. Para otros problemas, sus mejoresalgoritmos conocidos son no deterministas. Esta clase de problemas se denomina clase NP. Por tanto, los problemas de la clase P son un subconjunto de los de la clase NP, pues sólo cuentan con una alternativa en cada paso.
COMPLEJIDAD.
La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real.Ambos componentes tienen su importancia; pero la del algoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota.
A efectos prácticos o ingenieriles, nos deben preocupar los recursos físicos necesarios para que un programa se ejecute. Aunque puede haber muchos parametros, los mas usuales son el tiempo de ejecución y la cantidad de memoria (espacio).Ocurre con frecuencia que ambos parametros están fijados por otras razones y se plantea la pregunta inversa: ¿cual es el tamano del mayor problema que puedo resolver en T segundos y/o con M bytes de memoria? nos centraremos casi siempre en el parametro tiempo de ejecución, si bien las ideas desarrolladas son fácilmente aplicables a otro tipo de recursos.
TIEMPO DE EJECUCIÓN DE UN ALGORITMO....
Leer documento completo
Regístrate para leer el documento completo.