Terminología empleada en algoritmos

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 es una tarea eminentemente teórica y de gran interés

matemático, porque resulta que existen varias categorías de ellos, de

acuerdo consu complejidad: algoritmos lineales, polinominales,

exponenciales, e “inherentemente complejos”.

Una definición informal (no se considera aquí una definición formal,

aunque existe): conjunto finito de reglas que dan una secuencia de

operaciones para resolver todos los problemas de un tipo dado. De

forma más sencilla, podemos decir que un algoritmo es un conjunto

de pasos que nos permite obtener un dato. Además debe cumplir

estas condiciones:

• Finitud: el algoritmo debe acabar tras un número finito de pasos.

Es más, es casi fundamental que sea en un número razonable de

pasos.

• Definibilidad: el algoritmo debe definirse de forma precisa para

cada paso, es decir, hay que evitar toda ambigüedad al definir cada

paso. Puesto que el lenguaje humano es impreciso, los algoritmos se

expresan mediante un lenguaje formal, ya sea matemático o de

programación para un computador.

• Entrada: el algoritmo tendrá cero o más entradas, es decir,

cantidades dadas antes de empezar el algoritmo. Estas cantidades

pertenecen además a conjuntos especificados de objetos. Por

ejemplo, pueden ser cadenas de caracteres, enteros, naturales,

fraccionarios, etc. Se trata siempre de cantidades representativas del

mundo real expresadas de tal forma que sean aptas para su

interpretación por el computador.

• Salida: el algoritmo tiene una o más salidas, en relación con las

entradas.

• Efectividad: se entiende por esto que una persona sea capaz de

realizar el algoritmo de modo exacto y sin ayuda de una máquina en

un lapso de tiempo finito.

Amenudo los algoritmos requieren una organización bastante

compleja de los datos, y es por tanto necesario un estudio previo de

las estructuras de datos fundamentales. Dichas estructuras pueden

implementarse de diferentes maneras, y es más, existen algoritmos

para implementar dichas estructuras. El uso de estructuras de datos

adecuadas pueden hacer trivial el diseño de un algoritmo, o un

algoritmo muy complejo puede usar estructuras de datos muy

simples.

Uno de los algoritmos más antiguos conocidos es el algoritmo de

Euclides. El término algoritmo proviene del matemático Muhammad

ibn Musa al-Khwarizmi, que vivió aproximadamente entre los años

780 y 850 d.C. en la actual nación Iraní. El describió la realización de

operaciones elementales en el sistema de numeración decimal. De al-

Khwarizmi se obtuvo la derivación algoritmo.

1.1.3. Características de los algoritmos.

- Clasificación de algoritmos

* Algoritmo determinista: en cada paso del algoritmo se determina de

forma única el siguiente paso.

* Algoritmo no determinista: deben decidir en cada paso de la

ejecución entre varias alternativas y agotarlas todas antes de

encontrar la solución.

Todo algoritmo tiene una serie de características, entre otras que

requiere una serie de recursos, algo que es fundamental considerar a

la hora de implementarlos en una máquina. Estos recursos son

principalmente:

• El tiempo: período transcurrido entre el inicio y la finalización del

algoritmo.

• La memoria: la cantidad (la medida varía según la máquina) que

necesita el algoritmopara su ejecución.

Obviamente, la capacidad y el diseño de la máquina pueden afectar al

diseño del algoritmo.

En general, la mayoría de los problemas tienen un parámetro de

entrada que es el número de datos que hay que tratar, esto es, N. La

cantidad de recursos del algoritmo es tratada como una función de N.

De esta manera puede establecerse un tiempo de ejecución del

algoritmo que suele ser proporcional a una de las siguientes

funciones:

• 1 : Tiempo de ejecución constante. Significa que la mayoría de las

instrucciones se ejecutan una vez o muy pocas.

• logN : Tiempo de ejecución logarítmico. Se puede considerar como

una gran constante. La base del logaritmo (en informática la más

común es la base 2) cambia la constante, pero no demasiado. El

programa es más lento cuanto más crezca N, pero es inapreciable,

pues logN no se duplica hasta que N llegue a N2. • N : Tiempo de ejecución lineal. Un caso en el que N valga 40,

tardará el doble que otro en que N valga 20. Un ejemplo sería

...