Algoritmos

CONCEPTO Y CARACTERISTICAS DE ALGORITMOS




El programador de computara es antes que nada una persona que resuelve problemas, por lo que para llegar a ser un programador eficaz se necesita aprender a resolver problemas de modo riguroso y sistemático. La metodología necesaria para resolver problemas mediante programas se llama metodología de la programación.



Un algoritmo es un método para resolver un problema. Aunque la popularización del termino ha llegado con el advenimiento de la era informática.



El profesor Niklaus Wirth inventor de pascal, modula- 2 y Oberon tituló uno de los mas famosos libros, Algoritmos mas estructuras de Datos= programas, significándonos que solo se puede llegar a realizar un buen programa con el diseño de un algoritmo y una correcta estructura de datos. Esta ecuación será una de las hipótesis fundamentales consideradas en esta obra.



La resolución de un problema exige el diseño de un algoritmo que resuelva el problema propuesto.











Los pasos para la resolución de un problema son:



1.- diseño de algoritmo, que describe la secuencia ordenada de pasos sin ambigüedades que conducen a la solución de un problema dado. (Análisis del problema y desarrollo del algoritmo.)

2.- expresar el algoritmo como un programa en un lenguaje de programación adecuado. (Fase de codificación.)

3.- ejecución y validación del programa por la computadora.



Para llegar a la realización de un programa es necesario el diseño previo de un algoritmo, de modo que sin algoritmo no puede existir un programa.

Los algoritmos independientes tanto del lenguaje de programación en que se expresan como de la computadora que los ejecuta. En cada problema el algoritmo se puede expresar en un lenguaje diferente de programación y ejecutarse en una computadora distinta; sin embargo, el algoritmo será siempre el mismo. Así, por ejemplo en una analogía con la vida diaria, una receta de comida se puede expresar en español, ingles o francés, pero cualquiera que sea el lenguaje, los pasos para la elaboración del plato se realizaran sin importar el idioma del cocinero.

En la ciencia de la computación y en la programación, los algoritmos son más importantes que los lenguajes de programación o las computadoras. Un lenguaje de programación es tan solo un medio para expresar un algoritmo y una computadora es solo un procesador para ejecutarlo. Tanto el lenguaje de programación como la computadora son los medios para obtener un fin: conseguir que el algoritmo se ejecute y se efectué el proceso correspondiente.

Dada la importancia del algoritmo es la ciencia de la computacion, un aspecto muy importante será el diseño de algoritmos. El diseño de la mayoría de los algoritmos requiere creatividad y conocimientos profundos de la técnica de la programación. En esencia, la solución de un problema se puede expresar mediante un algoritmo.



CARACTERISTICAS DE LOS ALGORITMOS



Las características fundamentales que debe cumplir todo algoritmo son:



- un algoritmo debe ser preciso e indicar al orden de realización de cada paso.

- Un algoritmo debe estar definido. Si se sigue un algoritmo dos veces, se debe obtener el mismo resultado cada vez.

- Un algoritmo debe ser finito. Si se sigue un algoritmo, se debe terminar en algún momento o sea, debe tener un número finito de pasos.



La definición de un algoritmo debe describir tres partes: entrada, proceso y salida. En el algoritmo de cocina de receta citada anteriormente se tendrá:



Entrada: ingredientes y utensilios empleados.

Proceso: elaboración de la receta en la cocina.

Salida: terminación del plato (por ejemplo, cordero).



DISEÑO DEL ALGORITMO



Una computadora no tiene capacidad para solucionar problemas más que cuando se le proporcionan los sucesivos pasos a realizar. Estos pasos sucesivos que indican las instrucciones a ejecutar por la maquina constituyen, como ya conocemos, el algoritmo.

La información proporcionada al algoritmo constituye su entrada y la información producida por el algoritmo constituye su salida.

Los problemas complejos se pueden resolver mas eficazmente con la computadora cuando se rompen en subproblemas que sean mas fáciles de solucionar que el original. Este método se suele denominar divide y vencerás, y consiste en dividir un problema complejo en otros mas simples.



ESCRITURAS DE ALGORITMOS



Como ya se ha comentado anteriormente, el sistema para describir (escribir) un algoritmo consiste en realizar una descripción paso a paso con un lenguaje natural del citado algoritmo. Recordemos un algoritmo es un método o un conjunto de reglas para solucionar un problema. En cálculos elementales estas reglas tienen las siguientes propiedades.



- deben estar seguidas de alguna consecuencia definida de pasos hasta que se obtengan un resultado coherente.

- Solo puede ejecutarse una operación a la vez.



El flujo de control usual de un algoritmo es secuencial.



Que hacer, para ver la película de harry potter?



- ir al cine

- comprar una entrada (billete o ticket)

- ver la película

- regresan a casa



El algoritmo consta de cuatro funciones básicas, cada una de las cuales debe ser ejecutada antes de realizar la siguiente. En términos de computadora, cada acción se codifica en una o varias sentencias que ejecutan una tarea particular.

El algoritmo descrito es muy sencillo; sin embargo, como ya se ha indicado en párrafos anteriores, al algoritmo general se descompondrá en pasos más simples en un procedimiento denominado refinamiento sucesivo, ya que cada acción puede descomponerse a su vez en otras acciones simples.



REPRESENTACION GRAFICA DE LOS ALGORITMOS



Para representar un algoritmo se debe utilizar algún método que permita independizar dicho algoritmo del lenguaje de programación elegido. Ello permitirá que un algoritmo pueda ser codificado indistintamente en cualquier lenguaje. Para conseguir este objetivo se precisa que el algoritmo sea representado grafica o numéricamente, de modo que las sucesivas acciones no dependan de la sintaxis de ningún lenguaje de programación, sino que la descripción pueda servir fácilmente para su transformación en un programa, es decir su codificación.



1.- diagrama de flujo.

2.- diagrama N-S (Nassi- Schneiderman).

3.- lenguaje de especificacion de algoritmos: pseudocódigo.

4.- lenguaje español, inglês...

5.- formula.



Los métodos 4 y 5 no suelen ser fáciles de transformar en programas. Una descripción en español narrativo no es satisfactoria, ya que es demasiado prolija y generalmente ambigua. Una formula, sin embarga, es buen sistema de representación. Por ejemplo, las formulas para la solución de una ecuación cuadrática (de segundo grado) es un medio sucinto de expresar el procedimiento algorítmico que se debe ejecutar para obtener las raíces de dicha ecuación.



DIAGRAMAS DE FLUJO



Un diagrama de flujo (flowchart) es una de las técnicas de representación de algoritmos más antigua y a la vez más utilizada, aunque su empleo ha disminuido considerablemente, sobre todo desde la aparición de lenguaje de programación estructurada. Un diagrama de flujo es un diagrama que utiliza los símbolos (cajas).



SIMBOLOS DE DIAGRAMA DE FLUJO



Cada símbolo visto anteriormente indica el tipo de operación a ejecutar y el diagrama de flujo ilustra gráficamente la secuencia en la que se ejecutan las operaciones.



Las líneas de flujo (flecha) representa el flujo secuencial de la lógica del programa.

Un rectángulo significa algún proceso en la computadora, es decir, acciones a realizar (sumar dos números, calcular la raíz cuadrada de un número, etc.).

El paralelogramo es un símbolo de entrada/salida que representa cualquier tipo de entrada o salida desde el programa o sistema; por ejemplo, entrada de teclado, salida en impresora o pantalla, etc.



El símbolo rombo es una caja de decisión que representa respuesta si/no o en diferentes alternativas 1, 2, 3, 4,… etc.

Cada diagrama de flujo comienza y termina con un símbolo Terminal.























No



Si



























































TIPOS DE ALGORITMOS SEGÚN SU FUNCIÓN



ALGORITMO DE ORDENAMIENTO



En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos.

Desde los comienzos de la computación, el problema del ordenamiento ha atraído gran cantidad de investigación, tal vez debido a la complejidad de resolverlo eficientemente a pesar de su planteamiento simple y familiar. Por ejemplo, BubbleSort fue analizado desde 1956.1 Aunque muchos puedan considerarlo un problema resuelto, nuevos y útiles algoritmos de ordenamiento se siguen inventado hasta el día de hoy (por ejemplo, el ordenamiento de biblioteca se publicó por primera vez en el 2004). Los algoritmos de ordenamiento son comunes en las clases introductorias a la computación, donde la abundancia de algoritmos para el problema proporciona una gentil introducción a la variedad de conceptos núcleo de los algoritmos, como notación de O mayúscula, algoritmos divide y vencerás, estructuras de datos, análisis de los casos peor, mejor, y promedio, y límites inferiores.

CLASIFICACIÓN



Los algoritmos de ordenamiento se pueden clasificar de las siguientes maneras:

• La más común es clasificar según el lugar donde se realice la ordenación

o Algoritmos de ordenamiento interno: en la memoria del ordenador.

o Algoritmos de ordenamiento externo: en un lugar externo como un disco duro.

• Por el tiempo que tardan en realizar la ordenación, dadas entradas ya ordenadas o inversamente ordenadas:

o Algoritmos de ordenación natural: Tarda lo mínimo posible cuando la entrada está ordenada.

o Algoritmos de ordenación no natural: Tarda lo mínimo posible cuando la entrada está inversamente ordenada.

• Por estabilidad: un ordenamiento estable mantiene el orden relativo que tenían originalmente los elementos con claves iguales. Por ejemplo, si una lista ordenada por fecha se reordena en orden alfabético con un algoritmo estable, todos los elementos cuya clave alfabética sea la misma quedarán en orden de fecha. Otro caso sería cuando no interesan las mayúsculas y minúsculas, pero se quiere que si una clave aBC estaba antes que AbC, en el resultado ambas claves aparezcan juntas y en el orden original: aBC, AbC. Cuando los elementos son indistinguibles (porque cada elemento se ordena por la clave completa) la estabilidad no interesa. Los algoritmos de ordenamiento que no son estables se pueden implementar para que sí lo sean. Una manera de hacer esto es modificar artificialmente la clave de ordenamiento de modo que la posición original en la lista participe del ordenamiento en caso de coincidencia.

LOS ALGORITMOS SE DISTINGUEN POR LAS SIGUIENTES CARACTERÍSTICAS:

• Complejidad computacional (peor caso, caso promedio y mejor caso) en términos de n, el tamaño de la lista o arreglo. Para esto se usa el concepto de orden de una función y se usa la notación O(n). El mejor comportamiento para ordenar (si no se aprovecha la estructura de las claves) es O(n log n). Los algoritmos más simples son cuadráticos, es decir O(n²). Los algoritmos que aprovechan la estructura de las claves de ordenamiento (p. ej. bucket sort) pueden ordenar en O(kn) donde k es el tamaño del espacio de claves. Como dicho tamaño es conocido a priori, se puede decir que estos algoritmos tienen un desempeño lineal, es decir O(n).

• Uso de memoria y otros recursos computacionales. También se usa la notación O(n).

LISTADO DE ALGORITMOS DE ORDENAMIENTO



Algunos algoritmos de ordenamiento agrupados según estabilidad tomando en cuenta la complejidad computacional.

Estables

Nombre traducido Nombre original Complejidad Memoria Método

Ordenamiento de burbuja

Bubblesort O(n²)

O(1)

Intercambio

Ordenamiento de burbuja bidireccional

Cocktail sort O(n²)

O(1)

Intercambio

Ordenamiento por inserción

Insertion sort O(n²)

O(1)

Inserción

Ordenamiento por casilleros

Bucket sort O(n)

O(n) No comparativo

Ordenamiento por cuentas

Counting sort O(n+k)

O(n+k) No comparativo

Ordenamiento por mezcla

Merge sort O(n log n)

O(n)

Mezcla

Ordenamiento con árbol binario

Binary tree sort O(n log n)

O(n) Inserción

Pigeonhole sort

O(n+k)

O(k)

Ordenamiento Radix

Radix sort O(nk)

O(n) No comparativo

Distribution sort

O(n³) versión recursiva O(n²)

Gnome sort

O(n²)



Inestables

Nombre traducido Nombre original Complejidad Memoria Método

Ordenamiento Shell

Shell sort O(n1.25)

O(1)

Inserción

Comb sort

O(n log n)

O(1)

Intercambio

Ordenamiento por selección

Selection sort O(n²)

O(1)

Selección

Ordenamiento por montículos

Heapsort O(n log n)

O(1)

Selección

Smoothsort

O(n log n)

O(1)

Selección

Ordenamiento rápido

Quicksort Promedio: O(n log n),

peor caso: O(n²) O(log n)

Partición

Several Unique Sort

Promedio: O(n u),

peor caso: O(n²);

u=n; u = número único de registros

Cuestionables, imprácticos

Nombre traducido Nombre original Complejidad Memoria Método

Bogosort

O(n × n!), peor: no termina

Pancake sorting

O(n), excepto en

máquinas de Von Neumann



Randomsort







ALGORITMO DE BÚSQUEDA



Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento concreto dentro de una estructura de datos. Consiste en solucionar un problema de existencia o no de un elemento determinado en un conjunto finito de elementos, es decir, si el elemento en cuestión pertenece o no a dicho conjunto, además de su localización dentro de éste.

Este problema puede reducirse a devolver la existencia de un número en un vector.









BÚSQUEDA SECUENCIAL



Se utiliza cuando el contenido del vector no se encuentra o no puede ser ordenado. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del arreglo hasta que éste se encuentre, o hasta que se llegue al final del arreglo. La existencia se puede asegurar desde el momento que el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del arreglo. A continuación se muestra el pseudocódigo del algoritmo:

Datos de Entrada:

vec: vector en el que se desea buscar el elemento

tam: tamaño del vector

dato: elemento que se quiere buscar.



Variables

pos: posición actual en el arreglo



pos = 0

Mientras pos < tam:

Si vec[pos]== dato devolver verdadero y/o pos, de lo contrario:

pos = pos + 1



Fin (Mientras)

Devolver falso





BÚSQUEDA BINARIA (DICOTÓMICA)



Se utiliza cuando el vector en el que queremos determinar la existencia o no de un elemento está ordenado, o puede estarlo, este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente con el número de iteraciones.

Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del arreglo (normalmente el elemento central), si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del arreglo que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del arreglo que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible, con el elemento buscado como elemento central. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en el arreglo.

A continuación se presenta el pseudocódigo del algoritmo, tomando como elemento inicial el elemento central del arreglo.

Datos de Entrada:

vec: vector en el que se desea buscar el elemento

tam: tamaño del vector

dato: elemento que se quiere buscar.



Variables

centro: elemento central del intervalo

inf: limite inferior del intervalo

sup: limite superior del intervalo



inf = 0

sup = tam



Mientras inf <= sup:

centro = ((sup + inf) / 2) /* división entera: se trunca la parte decimal */

Si vec[centro] == dato devolver verdadero y/o pos, de lo contrario:

Si dato < vec[centro] entonces:

sup=centro-1

En caso contrario:

inf=centro+1



Fin (Mientras)

Devolver Falso