Algoritmos Complejos

Cuando solucionamos un problema mediante la construcción de un algoritmo, normalmente podemos atacar el problema desde distintos puntos de vista, aplicando distintas estrategias, y por tanto, llegando a soluciones algorítmicas distintas.Desde el punto de vista computacional, es necesario disponer de alguna forma de comparar una solución algorítmica con otra, para conocer cómo se comportarán cuando las implementemos, especialmente al atacar problemas "grandes".La complejidad algorítmica es una métrica teórica que se aplica a los algoritmos en este sentido. Es un concepto que fundamental para todos los programadores, pero sin embargo, a menudo se desconoce por completo. En muchos cursos y libros se elude el tema porque a menudo se considera farragoso.Pero eso no es necesariamente cierto. La complejidad de un algoritmo es un concepto complicado pero sólo desde un punto de vista estrictamente formal. La obtención y el estudio de la complejidad de un algoritmo requiere ciertamente de unas cuantas destrezas matemáticas que no todos tenemos y la aplicación de una serie de técnicas bastante particulares. Sin embargo, no es un concepto difícil de entender.Por hacer una similitud acerca de lo complicado que es este concepto, la dificultad de la complejidad es -salvando las distancias- como la de la predicción meteorológica: todos intuimos lo complicado que es hacer una predicción meteorológica, miles de datos, fórmulas, modelos y cálculos... sin embargo, cuando un meteorólogo nos explica con algo de gracia la predicción del tiempo, la podemos entender bastante bien. Ya estamos muy acostumbrados a cosas como borrasca, anticiclón, marejadilla, cota de nieve... Lo mismo pasa en cierto modo con la complejidad: enfrentarnos a un algoritmo para hacer un estudio de su complejidad requiere de un gran esfuerzo. Sin embargo, cuando alguien estudia un algoritmo y nos habla de su complejidad, entender el concepto no es tan complicado.Entender la complejidad es importante porque a la hora de resolver muchos problemas, utilizamos algoritmos ya diseñados. Saber valorar su valor de complejidad puede ayudarnos mucho a conocer cómo se va a comportar el algoritmo e incluso a escoger uno u otro.Así que en este artículo, nos vamos a dedicar a intentar exponer qué es la complejidad de un algoritmo desde un punto de vista sencillo y sin pretensiones, intentado distinguir qué impacto tiene el que un algoritmo tenga una u otra complejidad. Y, como de costumbre, adoptamos grandes simplificaciones, con el único ánimo de obtener una visión general de los conceptos. En cuanto a cómo obtener la complejidad de un algoritmo, no nos vamos a meter mucho: los formalismos necesarios quedan totalmente fuera del alcance de éste breve artículo divulgativo.Primeramente, debemos tener claro qué es un algoritmo. Podemos entender por algoritmo una secuencia de instrucciones cuyo objetivo es la resolución de un problema. El término clave aquí es el de problema.Existen multitud de problemas de computación que se pueden resolver mediante un algoritmo (aunque algunos pocos no tienen un algoritmo que los solucione.Para resolver cada problema, podemos obtener más de un algoritmo que lo solucione, pero ¿Cual de ellos es el mejor? Sería conveniente poder aplicar algún tipo de "puntuación" a los algoritmos, y que cuanta más puntuación sacara un algoritmo, pues supondremos que es mejor. Eso es, en cierto modo, la complejidad.Saber si un algoritmo es mejor que otro puede estudiarse desde dos puntos de vista: un algoritmo es mejor cuanto menos tarde en resolver un problema, o bien es tanto mejor cuanta menos memoria necesite.A la idea del tiempo que consume un algoritmo para resolver un problema le llamamos complejidad temporal y a la idea de la memoria que necesita el algoritmo le llamamos complejidad espacial.La complejidad espacial, en general, tiene mucho menos interés. El tiempo es un recurso mucho más valioso que el espacio. (Esto lo podemos ver también en el mundo real: si tienes dinero puedes comprarte una casa más grande, pero no puedes comprarte unos cuantos años más de vida).Así que cuando hablamos de complejidad a secas, nos estamos refiriendo prácticamente siempre a complejidad temporal.La complejidad de un algoritmo es un "valor", por así decirlo, que nos da una idea de cuánto va a tardar un algoritmo en resolver el problema para el que fue diseñado.

Estructuras Selectivas

Concentrando el concepto, se define estructura selectiva como una condición dentro del algoritmo. La misma genera la posibilidad de varias acciones que llevan a diferentes resultados, pero siempre a la misma salida.

Ej:

Algoritmo Inversion

Variables: CI, I, CCI. R(*)

Inicio
Leer CI, I
Si I>700 entonces
CCI= CI+I
Sino
CCI= CI
Imprimir "Su capital con intereses es"; CCI
Fin

(*)Real.

Pseudocódigo

Es lo mismo de un algoritmo común, pero la diferencia es que se realiza en meta lenguaje o en inglés.

Ej:

Program_descuento

Var: P,D,MP, as Real(*)
Const: 0.15 as Real

Begin
Read P
D= P*0.15
MP= P-D
Print "El monto a pagar es"; MP
End

(*)Se declaran las variables y/o constantes numéricas como "real" o "integer" dependiendo de si son reales o enteros.

Diagramas de flujo o Flujogramas

Son una forma gráfica de representar un algoritmo, se ordena de la siguiente forma con las figuras correspondientes a cada nivel:



*Inicio: paso inicial en cada algoritmo.

*Lectura de datos: declaración de variables.

*Proceso(s): operaciones a realizar.

*Salida de información: orden de salida de datos (imprimir, enviar...).

*Fin: paso final de cada algoritmo.

Subalgoritmos

Muchos de nuestros compañeros de clase se vieron mal en esta evaluación al no conseguir información sobre los sublagoritmos. Pero con un poco de insistencia y gracias a algunos contactos, conseguimos información suficiente como para que sea de ayuda a uds.

Tomando un concepto un poco concentrado de la definición primaria, los subalgortimos son simple y sencillamente todas y cada una de las partes de un algoritmo que llevan a la solución de un problema. ¿Sencillo verdad?.

Está demostrado que ante un problema complejo, este se resuelve mejor cuando el mismo se divide en pequeños problemas. Este concepto es aplicable con los algoritmos, dividiéndolos en subalgoritmos, que en su conjunto logran resolver el algoritmo.La programación modular consiste en dividir un programa en partes bien diferenciadas, llamadas subalgoritmos que pueden ser analizados y programados por separado. Existe un algoritmo, que da el control total a los módulos, y una vez éstos se han ejecutado, retoma el control, continuando la ejecución del programa por dónde los llamó.

Esta metodología permite la reutilización de algunos subalgoritmos, para que otros algoritmos hagan uso de ellos. Entre las reglas principales para programar de forma modular (la práctica más conveniente), están:

1-)Cada módulo tiene que tener un punto de entrada y otro de salida. (Es decir, el módulo una vez haya realizado su tarea, debe devolver el control al programa principal desde donde fue llamado).
2-)En el programa principal, se debe definir todos los módulos que se van a utilizar y definirlos en consecuencia.

Dentro de los subalgoritmos, podemos diferenciar procedimientos y funciones:

*Procedimientos: en palabras mas sencillas, se define como un módulo. Concretamente, como un módulo que no retorna ningún valor, ejecuta lo que tenga que ejecutar y devuelve el control al programa que lo llamó.

*Funciones: Un subalgoritmo que retorna un valor. La llamada de ambas desde un programa, se hace de forma diferente, atendiendo a su definición. Cuando trabajemos con una función, al llamarla no podremos llamarla sin más, si no que deberemos hacerlo en alguna parte en el que el valor devuelto sea evaluable.
Por el contrario, la llamada a un procedimiento se hace en "solitario", y mientras que el procedimiento no devuelve resultados, una función devuelve un solo resultado, producto de la misma. Es decir, que si tenemos una funcion que multiplique 2*3; entonces tenemos que organizar esa operación correctamente en una igualdad (x=2*3), realizarla (2*3=6) y después dar la orden de que el resultado de la operación aparezca reflejada (x=6).

Algoritmos. Definición básica

Para comenzar con el tema, podriamos primero conocer lo que significa la palabra "algoritmo". La palabra algoritmo proviene del vocablo latino "dixit algorithmus", que a su vez desciende del nombre de un matemático persa conocido como "Al-Jwarizmi".

Ya que sabemos lo que significa la palabra en si, veamos su definición: Un algoritmo es en general, una lista organizada, concreta, concisa y finita de los pasos a seguir para darle solución a un problema.

Los mismos se utilizan para cualquier cosa en la vida cotidiana, tanto como para comprar comida, encender un computador, como para resolver las mayores fórmulas, ya sean matemáticas o de otra índole (químicas, fisicas, mecánicas, entre otras).