ALGORITMO Y DIAGRAMA DE FLUJO
ALGORITMO INFORMÁTICO Y DIAGRAMA DE FLUJO
¿Qué es un algoritmo informático?
Un algoritmo informático
es un conjunto de instrucciones definidas, ordenadas y acotadas para
resolver un problema, realizar un cálculo o desarrollar una tarea. Es
decir, un algoritmo es un procedimiento paso a paso para conseguir un
fin. A partir de un estado e información iniciales, se siguen una serie
de pasos ordenados para llegar a la solución de una situación.
En programación, un algoritmo supone el paso previo a ponerse a escribir el código. Primero debemos encontrar la forma de obtener la solución al problema (definir el algoritmo informático), para luego, a través del código, poder indicarle a la máquina qué acciones queremos que lleve a cabo. De este modo, un programa informático no sería más que un conjunto de algoritmos ordenados y codificados en un lenguaje de programación para poder ser ejecutados en un ordenador. Los algoritmos no son algo exclusivo de los ámbitos de las matemáticas, la lógica y la computación. Utilizamos numerosos algoritmos para resolver problemas en nuestra vida cotidiana. Algunos de los ejemplos más habituales son los manuales de instrucciones o las recetas de cocina.
los algoritmos presentan una serie de características comunes. Son:
- Precisos:Objetivos, sin ambigüedad.
- Ordenados. Presentan una secuencia clara y precisa para poder llegar a la solución.
- Finitos. Contienen un número determinado de pasos.
- Concretos. Ofrecen una solución determinada para la situación o problema planteados.
- Definidos. El mismo algoritmo debe dar el mismo resultado al recibir la misma entrada.
Tipos de algoritmos y ejemplos
Algoritmos de búsqueda
Los algoritmos de búsqueda localizan uno o varios elementos que presenten una serie de propiedades dentro de una estructura de datos.
Ejemplos de algoritmos de búsqueda
Existen diversos tipos de búsquedas, entre las que sobresalen:
- Búsqueda secuencial. En la que se compara el elemento a localizar con cada elemento del conjunto hasta encontrarlo o hasta que hayamos comparado todos.
- Búsqueda binaria. En un conjunto de elementos ordenados, hace una comparación con el elemento ubicado en el medio y, si no son iguales, continúa la búsqueda en la mitad donde puede estar. Y así sucesivamente en intervalos cada vez más pequeños de elementos.
Algoritmos de ordenamiento
Ejemplos de algoritmos de ordenamiento
Algunos algoritmos de ordenamiento son:
- Ordenamiento de burbuja. Compara cada elemento de la lista a ordenar con el siguiente e intercambia su posición si no están en el orden adecuado. Se revisa varias veces toda la lista hasta que no se necesiten más intercambios.
- Ordenamiento por selección. Vamos colocando el elemento más pequeño disponible en cada una de las posiciones de la lista de forma consecutiva.
- Ordenamiento rápido. Elegimos un elemento del conjunto (pivote) y reubicamos el resto a cada uno de sus lados, en función de si son mayores o menores que el elemento que estamos tomando como referencia. Repetimos el procedimiento en cada subconjunto
Algoritmos voraces
Los algoritmos voraces consisten en una estrategia de búsqueda que sigue una heurística en la que se elige la mejor opción óptima en cada paso local con el objetivo de llegar a una solución general óptima. Es decir, en cada paso del proceso escogen el mejor elemento (elemento prometedor) y comprueban que pueda formar parte de una solución global factible. Normalmente se utilizan para resolver problemas de optimización.
Ejemplos de algoritmos voraces
En ocasiones, estos algoritmos no encuentran la solución global óptima, ya que al tomar una decisión solo tienen en cuenta la información de las decisiones que han tomado hasta el momento y no las futuras que puede adoptar. Algunos casos en los que los algoritmos voraces alcanzan soluciones óptimas son:
- Problema de la mochila fraccional (KP). Disponemos de una colección de objetos (cada uno de ellos con un valor y un peso asociados) y debemos determinar cuáles colocar en la mochila para lograr transportar el valor máximo sin superar el peso que puede soportar.
- Algoritmo de Dijkstra. Utilizado para determinar el camino más corto desde un vértice origen hasta los demás vértices de un grafo, que tiene pesos en cada arista.
- Codificación Huffman. Método de compresión de datos sin perder información, que analiza la frecuencia de aparición de caracteres de un mensaje y les asigna un código de longitud variable. Cuanto mayor sea la frecuencia le corresponderá un código más corto.
Programación dinámica
La programación dinámica es un método de resolución de problemas en el que dividimos un problema complejo en subproblemas y calculamos y almacenamos sus soluciones, para que no haga falta volver a calcularlas más adelante para llegar a la solución del problema. La programación dinámica reduce el tiempo de ejecución de un algoritmo al optimizar la recursión.
Eso sí, para poder aplicarse a un problema, éste debe tener subestructuras óptimas y subproblemas superpuestos. Es decir, que en él se puedan usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en su conjunto y que el problema se pueda dividir en subproblemas que se reutilizan para ofrecer el resultado global.
Usos de programación dinámica
Algunos casos en los que se utiliza son:
- La serie de Fibonacci. Sucesión de números que comienza con “0” y “1” y, a partir de ellos, cada número es resultado de la suma de los dos que le preceden. La relación de recurrencia la define.
- Problema de la mochila.
Algoritmos probabilísticos
Es una técnica que usa una fuente de aleatoriedad como parte de su lógica. Mediante un muestreo aleatorio de la entrada llega a una solución que puede no ser totalmente óptima, pero que es adecuada para el problema planteado.
Se utiliza en situaciones con limitaciones de tiempo o memoria y cuando se puede aceptar una buena solución de media, ya que a partir de los mismos datos se pueden obtener soluciones diferentes y algunas erróneas. Para que sea más probable ofrecer una solución correcta, se repite el algoritmo varias veces con diferentes submuestras aleatorias y se comparan los resultados.
Tipos de algoritmos probabilísticos
Existen dos tipos principales de algoritmos probabilísticos:
- Algoritmo de Montecarlo. Dependiendo de la entrada, hay una pequeña probabilidad de que no acierte o no llegue a una solución. Se puede reducir la probabilidad de error aumentando el tiempo de cálculo.
- Algoritmo de Las Vegas.
Se ejecuta en un periodo de tiempo concreto. Si encuentra una solución
en ese tiempo ésta será correcta, pero es posible que el tiempo se agote
y no encuentre ninguna solución.
¿Qué es un diagrama de flujo?
Un diagrama de flujo es un diagrama que describe un proceso, sistema o algoritmo informático. Se usan ampliamente en numerosos campos para documentar, estudiar, planificar, mejorar y comunicar procesos que suelen ser complejos en diagramas claros y fáciles de comprender. Los diagramas de flujo emplean rectángulos, óvalos, diamantes y otras numerosas figuras para definir el tipo de paso, junto con flechas conectoras que establecen el flujo y la secuencia. Pueden variar desde diagramas simples y dibujados a mano hasta diagramas exhaustivos creados por computadora que describen múltiples pasos y rutas. Si tomamos en cuenta todas las diversas figuras de los diagramas de flujo, son uno de los diagramas más comunes del mundo, usados por personas con y sin conocimiento técnico en una variedad de campos. Los diagramas de flujo a veces se denominan con nombres más especializados, como "diagrama de flujo de procesos", "mapa de procesos", "diagrama de flujo funcional", "mapa de procesos de negocios", "notación y modelado de procesos de negocio (BPMN)" o "diagrama de flujo de procesos (PFD)". Están relacionados con otros diagramas populares, como los diagramas de flujo de datos (DFD) y los diagramas de actividad de lenguaje unificado de modelado (UML).
Diagrama de flujo para algoritmos.
Como una representación visual del flujo de datos, los diagramas de
flujo son útiles para escribir un programa o algoritmo y explicárselo a
otros o colaborar con otros en el mismo. Puedes usar un diagrama de
flujo para explicar detalladamente la lógica detrás de un programa antes
de empezar a codificar el proceso automatizado. Puede ayudar a
organizar una perspectiva general y ofrecer una guía cuando llega el
momento de codificar. Más específicamente, los diagramas de flujo
pueden:
- Demostrar cómo el código está organizado.
- Visualizar la ejecución de un código dentro de un programa.
- Mostrar la estructura de un sitio web o aplicación.
- Comprender cómo los usuarios navegan por un sitio web o programa.
A menudo, los programadores pueden escribir un pseudocódigo, una combinación de lenguaje natural y lenguaje informático que puede ser leído por personas. Esto puede permitir más detalle que el diagrama de flujo y servir como reemplazo del diagrama de flujo o como el próximo paso del código mismo.
Los diagramas relacionados que se emplean en el software informático incluyen:
- Lenguaje unificado de modelado (UML): este es el lenguaje de propósito general usado en la ingeniería de software para el modelado.
- Diagramas Nassi-Shneiderman (NSD): usados para la programación informática estructurada. Llevan el nombre de sus creadores: Isaac Nassi y Ben Shneiderman, quienes los desarrollaron en 1972 en la Universidad Estatal de Nueva York en Stony Brook. También se denominan "estructogramas".
- Diagramas DRAKON: DRAKON es un lenguaje de programación visual de algoritmos empleado para crear diagramas de flujo.
Comentarios
Publicar un comentario