Introduccion a el blog

Algoritmo y programación

Un algoritmo es una serie de instrucciones secuenciales es decir, que van uno después del otro que permiten ejecutar acciones o programas. 

Partes de un algoritmo

Input o entrada. El ingreso de los datos que el algoritmo necesita para operar.

Proceso. Se trata de la operación lógica formal que el algoritmo emprenderá con lo recibido del input.

Output o salida. Los resultados obtenidos del proceso sobre el input, una vez terminada la ejecución del algoritmo

¿Para que sirve un algoritmo?

Su función en pocas palabras, es hacer unos ordenamientos previos de la programación. También es visto como la especie de un borrador programático, ya que no incluye lenguajes, sino lo que queremos que se haga en el orden correcto.

Características de un algoritmo

● 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. 

Ejemplos:

-ejemplo

Un par de ejemplos posibles de algoritmo son:

Algoritmo para elegir unos zapatos de fiesta:

INICIO

Entrar a la tienda y buscar la sección de zapatos de caballero.

Tomar un par de zapatos.

¿Son zapatos de fiesta?

     SI: (ir al paso 5) – NO: (volver al paso 3)

¿Hay de la talla adecuada?

     SI: (ir al paso 6) – NO: (volver al paso 3)

¿El precio es pagable?

     SI: (ir al paso 7) – NO: (volver al paso 3)

Comprar el par de zapatos elegido.

FIN

Algoritmo para calcular el área de un triángulo rectángulo:

INICIO

Hallar las medidas de la base (b) y altura (h)

Multiplicar: base por altura (b x h)

Dividir entre 2 el resultado (b x h) / 2

TIPOS DE ALGORITMOS

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. 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

Reorganizan los elementos de un listado según una relación de orden. Las más habituales son el orden numérico y el orden lexicográfico. Un orden eficiente optimiza el uso de algoritmos como los de búsqueda y facilitan la consecución de resultados legibles por personas y no solo máquinas.

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.

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.

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. 

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.

Algoritmos cualitativos y cuantitativos

Algoritmo Cualitativo:

Son aquellos en los que se describen los pasos de forma Narrada

Ejemplo de Algoritmo Cualitativo - Realizar un puré de papas.

1. Buscar utensilios.

2. Lavar las papas.

3. Llenar la olla con agua.

4. Colocar las papas dentro de la olla.

5. Encender la estufa.

6. Colocar la olla en la estufa.

7. Esperar a que hiervan.

8. Retirar las papas.

9. Pelar las papas.

10. Triturar las papas.

11. Agregar queso, mantequilla y leche.

12. Mezclar.

13. Agregar sal al gusto.

14. Servir.

Algoritmo Cuantitativo: 

Son aquellos en los que se utilizan cálculos numéricos para definir los pasos del proceso.

Ejemplos de Algoritmos Cuantitativos.

a) Obtener la suma de 2 números.

1. Inicio

2. Declarar (a,b,c)

3. Ingresar (a,b)

4. c=a+b

5. Mostrar (c)

6. Fin

b) Obtener el área de un triángulo.

1. Inicio

2. Declarar (b,h,a)

3. Ingresar (b,h)

4. a=(b*h)/2

5. Mostrar (a)

6. Fin

c) Ingresar una edad. Obtener el año en que nació.

1. Inicio

2. Declarar (e,a)

3. Ingresar (e)

4. a=2012-e

5. Mostrar (a)

6. Fin