jueves, 19 de abril de 2012

CARACTERÍSTICAS DE UN ALGORITMO



Características y formas de algoritmos:


Todo algoritmo debe contar forzosamente con tres características básicas:

  1. Preciso.- Debe ser concreto, no tener pasos de más y la solución tiene que ser clara y concreta.
  2.  
  3. Congruente.- Al probar varias veces, los resultados deben ser siempre los mimos.
  4.  
  5. Finito.- Al seguir los pasos debe llegar a la solución , es decir, debe tener término.
Un algoritmo  debe tener 3 partes:
  • Entrada
  • Proceso 
  • Salida.





ANÁLISIS DE ALGORITMOS


El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes.
A la hora de realizar un análisis teórico de algoritmos es común calcular su complejidad en un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La cota superior asintótica, y las notaciones omega (cota inferior) y theta (caso promedio) se usan con esa finalidad. Por ejemplo, la búsqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo, en O(log(n)), coloquialmente "en tiempo logarítmico". 

Normalmente las estimaciones asintóticas se utilizan porque diferentes implementaciones del mismo algoritmo no tienen porque tener la misma eficiencia. No obstante la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado están relacionadas por una constante multiplicativa llamada constante oculta.
La medida exacta (no asintótica) de la eficiencia a veces puede ser computada pero para ello suele hacer falta aceptar supuestos acerca de la implementación concreta del algoritmo, llamada modelo de computación. Un modelo de computación puede definirse en términos de un ordenador abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en una unidad de tiempo. Por ejemplo, si al conjunto ordenado al que aplicamos una búsqueda binaria tiene n elementos, y podemos garantizar que una única búsqueda binaria puede realizarse en un tiempo unitario, entonces se requieren como mucho log2 N + 1 unidades de tiempo para devolver una respuesta.


Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y usan algoritmos, porque tienen más precisión y así les permite saber cuanto tiempo pueden suponer que tomará la ejecución. Para algunas personas, como los desarrolladores de videojuegos, una constante oculta puede significar la diferencia entre éxito y fracaso.


Las estimaciones de tiempo dependen de cómo definamos un paso. Para que el análisis tenga sentido, debemos garantizar que el tiempo requerido para realizar un paso esté acotado superiormente por una constante. Hay que mantenerse precavido en este terreno; por ejemplo, algunos análisis cuentan con que la suma de dos números se hace en un paso. Este supuesto puede no estar garantizado en ciertos contextos. Si por ejemplo los números involucrados en la computación pueden ser arbitrariamente grandes, dejamos de poder asumir que la adición requiere un tiempo constante (usando papel y lápiz, compara el tiempo que necesitas para sumar dos enteros de 2 dígitos cada uno y el necesario para hacerlo con enteros de 1000 dígitos).

REPRESENTACIÓN DE UN ALGORITMO


 

Los algoritmos pueden ser expresados de muchas maneras, incluyendo al lenguaje natural, pseudocódigo, diagramas de flujo y lenguajes de programación entre otros. Las descripciones en lenguaje natural tienden a ser ambiguas y extensas. El usar pseudocódigo y diagramas de flujo evita muchas ambigüedades del lenguaje natural. Dichas expresiones son formas más estructuradas para representar algoritmos; no obstante, se mantienen independientes de un lenguaje de programación específico.
La descripción de un algoritmo usualmente se hace en tres niveles:
 1.Descripción de alto nivel. Se establece el problema, se selecciona un modelo matemático y se explica el algoritmo de manera verbal, posiblemente con ilustraciones y omitiendo detalles.
 2.Descripción formal. Se usa pseudocódigo para describir la secuencia de pasos que encuentran la solución.
 3.Implementación. Se muestra el algoritmo expresado en un lenguaje de programación específico o algún objeto capaz de llevar a cabo instrucciones.
También es posible incluir un teorema que demuestre que el algoritmo es correcto, un análisis de complejidad o ambos. 
 

Los algoritmos pueden ser creados de dos formas:
1)Seudocódigo.- Es un conjunto pequeño y claro de instrucciones; en secuencia, que permite llevar a cabo una tarea.
2)Diagrama de flujo.- Es la representación de la secuencia, a través de símbolos, de la tarea que se va a realizar.
Un ejemplo de algoritmo es el que realizamos para cambiar una llanta a un automóvil:
Inicio
Aflojar tornillos de las llantas
levantar el coche con el gato
Sacar los tornillos de las llantas
Quitar la llanta
Poner la llanta de repuesto
Poner los tornillos
Bajar el gato
Apretar los tornillos
fin

1) ALGORITMO EXPRESADO EN PSEUDOCODIGO


Definición
Mucho se habla del pseudocódigo en las carreras de Analista de Sistemas y Programación. Pero no existe mucha bibliografía al respecto.
Comencemos aclarando que no es una forma de programación. Se trata de una herramienta que los analistas de sistemas utilizan para comunicar a los programadores la estructura del programa que van a realizar, de forma de tener una idea bien clara de lo que se necesita programar.
Digamos que el pseudo código es una forma de diagramar un algoritmo para resolver un determinado problema, sin atenerse a ningún lenguaje de programación en especial.
Un algoritmo es un conjunto de procedimientos que permiten resolver un problema.
En vez de escribir el programa directamente en un lenguaje de programación determinado (C, Basic, etc.), crearemos un borrador entendible para todos, para luego de tener bien en claro lo que se debe hacer, pasar a la programación propiamente dicha.
 
El pseudo código se refiere a crear un código para orientar a los programadores, pero sin la sintaxis ni la estructura propia de ningún lenguaje.

Utilización en la práctica
En el trabajo de un analista de sistemas, una de las partes más trabajosas es la de determinar que es lo que necesitan de un sistema los usuarios finales. Se dedican muchas horas a hacer un relevamiento de los datos que serán necesarios, los tipos de procesamientos, las salidas, etc. Y debe existir una realimentación entre el diseño y el usuario, para garantizar que el sistema cumpla con los requisitos del usuario.
Supongamos que tenemos un sistema para una empresa que utiliza una interfaz gráfica en Visual Basic, algunas aplicaciones específicas en C, y páginas PHP para trabajo vía Internet. Seguramente que crear un diagrama específico para cada lenguaje sería una tarea tediosa.
Gracias a esta herramienta, podemos reunir a todos los programadores, dar las pautas de trabajo, y mediante el pseudo código, cada programador sabrá lo que hace el sistema, y podrá escribir el código correspondiente.
Incluso dos programadores que dominen el mismo lenguaje pueden tener metodologías de trabajo distintas. Un problema puede ser resuelto de muchas maneras, cada una más o menos eficiente que la otra, pero todas cumplen con el objetivo.
 
El pseudo código elimina estas diferencias, dando libertad a los programadores para que puedan ajustarse a su metodología de trabajo.
Generalmente, este código se escribe con la participación de todos los programadores. Esto representa la ventaja de que muchas opiniones ayudan a elegir la mejor entre todas, logrando una solución efectiva y eficaz al problema planteado.
Ejemplo
seudocódigo
2) EXPRESAR UN ALGORITMO CON UN DIAGRAMA DE FLUJO
DIAGRAMA DE FLUJO
Es un esquema para representar gráficamente un algoritmo. Se basan en la utilización de diversos símbolos para representar operaciones específicas, es decir, es la representación grafica de las distintas operaciones que se tienen que realizar para resolver un problema, con indicación expresa el orden lógico en que deben realizarse.
Se les llama diagramas de flujo porque los símbolos utilizados se conectan por medio de flechas para indicar la secuencia de operación. Para hacer comprensibles los diagramas a todas las personas, los símbolos se someten a una normalización; es decir, se hicieron símbolos casi universales, ya que, en un principio cada usuario podría tener sus propios símbolos para representar sus procesos en forma de Diagrama de flujo. Esto trajo como consecuencia que sólo aquel que conocía sus símbolos, los podía interpretar. La simbología utilizada para la elaboración de diagramas de flujo es variable y debe ajustarse a un patrón definido previamente.
El diagrama de flujo representa la forma más tradicional y duradera para especificar los detalles algorítmicos de un proceso. Se utiliza principalmente en programación, economía y procesos industriales.
Para realizar los diagramas de flujo utilizamos distintas figuras geométricas  en forma de caja de texto, que sirven para distinguir el tipo de tareas que se ejecutan, las flechas indican el flujo del proceso y se valen de determinada simbología específica para facilitar su comprensión
Por otra parte, un algoritmo consta de tres partes, secciones ó módulos principales, en la siguiente figura podemos observar las secciones que constituyen un algoritmo.
 
secciones de un algoritmo

El módulo 1.- representa la operación o acción que permite el ingreso de los datos del programa.
El módulo 2.- representa la operación o conjunto de operaciones secuenciales, cuyo objetivo es obtener la solución al problema.
El módulo 3.- representa una operación o conjunto de operaciones que permiten comunicar al exterior el o los resultados alcanzados.
df

miércoles, 18 de abril de 2012

Y.. ¿QUE ES UN ALGORITMO?...


ALGORITMO


Un algoritmo es una secuencia de pasos lógicos y ordenados con las cuales le damos solución a un problema determinado. 
En la vida diaria cada uno de nosotros diseña y realiza algoritmos para solucionar los problemas cotidianos, es así que al levantarnos de la cama ya tenemos en la mente una serie de pasos que debemos seguir para llegar al sitio de estudio o al sitio de trabajo. Una vez en el sitio de estudio, tenemos en nuestra mente una serie de tareas que debemos realizar en unos horarios ya definidos.
Si quisiéramos realizar una comida especial, en nuestra mente construimos un algoritmo o serie de pasos que debemos seguir en un orden específico para que todo nos salga como queremos. Si quisiéramos transcribir estos pasos en una hoja de papel, para que otra persona realizará las mismas tareas y obtenga el mismo resultado que nosotros, debemos seguir una serie de normas para que esta otra persona nos entienda. Por ejemplo debe estar escrito en el idioma que ella comprende, se deben enumerar los pasos etc. Las normas que se deben seguir al momento de transcribir el algoritmo depende de quien será el encargado de ejecutarlo, por ejemplo si quisiéramos escribir la receta para que la ejecute una persona adulta las normas serán diferentes a las que debemos seguir si quisiéramos escribir la receta para que le ejecute una niña.
ESTA ES UNA FORMA DE REPRESENTAR UN ALGORITMO MEDIANTE UN DIAGRAMA DE FLUJO