Terminología empleada en algoritmos
Enviado por CHICHOMAN • 3 de Septiembre de 2014 • 5.414 Palabras (22 Páginas) • 293 Visitas
Terminología empleada en algoritmos.
La principal razón para que las personas aprendan lenguajes de
programación es utilizar la computadora como una herramienta para
la solución de problemas.
Dos fases pueden ser identificadas en este proceso.
1- Fase de resolución del problema.
2- Fase de implementación en una microcomputadora.
El resultado de la primera fase es el diseño de un algoritmo para
resolver el problema. Un algoritmo se puede considerar como el
conjunto de instrucciones que conducen a la solución de un problema
determinado. Dichas instrucciones deben tener una secuencia lógica
para poder llegar a la solución real. El algoritmo se puede expresar de
diversas maneras. Mediante símbolos, utilizando un lenguaje
determinado para hablar la solución, describir sintéticamente dicho
lenguaje de programación. La última forma de describir el algoritmo
es a lo que se denomina PROGRAMA.
Definición de problema.
- Clasificación de problemas
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 que cuentan al menos con un
algoritmo para su cómputo.
Sin embargo,que un problema sea decidible no implica que se pueda
encontrar su solución, pues 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 es factible 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 polinómico que los resuelve se denominan clase P. Los
algoritmos que los resuelven son deterministas. Para otros
problemas, sus mejores algoritmos 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.
Un cierto problema tiene solución algorítmica de complejidad lineal
cuando el costo de la solución crece en forma proporcional con la
cantidad de datos. Por ejemplo, en el método de búsqueda del
máximo valor de un conjunto de números, la solución tarda un cierto
tiempo promedio, que depende linealmente de la cantidad de
elementos en la lista, por que le programa ocupa, por ejemplo, diez
veces más tiempo en encontrar el número mayor en la lista de
longitud 100 que en una de longitud 10.
Un problema tiene solución algorítmica de complejidad polinominal
(que espeor en términos generales que la lineal) cuando la ecuación
que describe el costo de la solución es un polinomio (y no una simple
variable o una constante), que suele crecer bastante más rápido que
una ecuación lineal sencilla.
Un algoritmo es de complejidad exponencial cuando la ecuación que
describe su comportamiento tiene exponentes variables, con lo que el
costo de la ejecución del programa se puede disparar y hacerse
inmanejable para ciertos tamaños en la longitud de los datos que
maneja.
Por último, los algoritmos inherentemente complejos exhiben tal
velocidad de crecimiento en su costo de ejecución que resultan del
todo impensables, aun para las más poderosas supercomputadoras.
1.1.2. Definición de algoritmo.
Un algoritmo es el método que emplea un programa para llegar a su
fin y, en términos práctica, constituye el “cómo” funciona una
descripción.
En general, de un algoritmo se pueden decir muchas cosas, entre las
cuales destaca si es correcto o no (o sea, si cumple o no con su
objetivo de describir algo); qué tan eficiente es (cuánto tarda en
llegar a su fin, o bien cuántas celdas de memoria requiere); qué tan
elegante es(es decir, si sigue un camino inteligente o bien planteado para efectuar su trabajo, sin dar rodeos innecesarios o sin emplear
recursos superfluos); qué tan claro es, y otras.
La especificación formal de un algoritmo en términos primitivos o
elementales
...