Epistemowikia
Revista «Hiperenciclopédica» de Divulgación del Saber
Segunda Época, Año IX
Vol. 8, Núm. 1: de enero a marzo de 2014
Epistemowikia es parte de
Logotipo de CALA Virtual
CALAALA | Communitas | Evolvere
Editio | Epistemowikia | Exercitatio | Fictor | Flor
Epistemowikia no se hace responsable ni se identifica necesariamente con el contenido ni las opiniones expresadas por sus colaboradores.
La Universidad de Extremadura no se hace en ningún caso responsable de los contenidos publicados en Epistemowikia.
La Asociación Conocimiento Comunal (CONOMUN) no se hace en ningún caso responsable de los contenidos publicados por terceros.

Inicio | La revista | Índex | Hemeroteca | Búsquedas | Quiénes somos | Contacto | Publica

Algoritmo

De Epistemowikia

Algoritmo (Quizá del latín tardío algobarismus, y este abreviado del árabe clásico hisābu lḡubār, cálculo mediante cifras arábigas), es el conjunto ordenado y finito de instrucciones que permite hallar la solución a un problema. Es un Método para resolver un problema mediante una serie de pasos precisos, definidos y finitos. Un algoritmo es una serie de operaciones detalladas, en otras palabras, un algoritmo es un conjunto de reglas para resolver una cierta clase de problemas y se puede formular de muchas formas con el cuidado de que no exista ambigüedad.

Tabla de contenidos

Introducción

Un algoritmo tiene que ajustarse a las siguientes pautas:

- Finitud: un algoritmo tiene que terminar de ejecutarse tras un número finitos de pasos. Es aconsejable que el número de veces que se ejecute el algoritmo sea razonable.

- Definibilidad: es necesario una definición precisa del algoritmo, no debe dar lugar a error. Los expresamos mediante un lenguaje formal.

- Entrada: un algoritmo puede tener varias entradas o ninguna, dichas entradas son datos pasados al algoritmo, que pueden ser de distintos tipos numérico, cadenas de texto, etc. Se trata de datos reales que son expresados de forma q el computador los entienda.

- Salida: dependiendo de las entradas y de la función del algoritmo puede devolver una o varias salidas.

- Efectividad: nos referimos al hecho de que una persona pueda desarrollar el algoritmo correctamente en un periodo de tiempo finito.

Los algoritmos necesitan de una correcta organización de los datos, y por ello es necesario el conocimiento de las diferentes estructuras de datos. Las estructuras pueden ser implementadas de muchas formas. El uso de este tipo de estructuras puede facilitar en gran medida la realización de los algoritmos.

Podemos destacar un algoritmo de los más antiguos conocidos que es el de Euclides.

Características

  • Preciso (debe indicar el orden de realización en cada paso y no puede tener ambiguedad).
  • Definido (si se sigue dos veces, obtiene el mismo resultado cada vez)
  • Finito (tiene fin; un número determinado de pasos).
  • Debe ser sencillo , legible.
  • Modular.
  • Eficiente y efectivo.
  • Se ha de desarrollar en el menor tiempo posible.
  • Correcto.
  • Todo Algoritmo debe tener cero o más entradas.
  • Debe tener al menos una salida y ésta debe ser tangible.

Clasificación de los algoritmos

Podemos distinguir dos tipos de algoritmos:

- Deterministas: aquellos en los que en cada iteración se decide de forma única el paso siguiente.

- No deterministas: aquellos en los que en cada iteración podemos decidir entre varias posibilidades y consumirlas todas antes de la siguiente iteración. Como hemos visto en los puntos anteriores los algoritmos tienen diferentes características entre ellas está la necesidad de utilizar una serie de recursos, como son el tiempo y la memoria. Dichos recursos hay que tenerlos muy en cuenta a la hora de implementar los algoritmos en una máquina determinada. Podemos definir: Tiempo: como el período transcurrido desde el inicio de la ejecución del algoritmo hasta el momento que finaliza la ejecución. Memoria: como lo que necesita el algoritmo para su ejecución, puede variar la necesidad de la misma según la máquina. Podemos deducir de esto, que las características de la máquina influirán notablemente en el diseño del algoritmo. Casi todos los problemas tienen un parámetro de entrada que hace referencia al número de datos que trataremos y que normalmente representamos con el símbolo N. El número de recursos del algoritmo es tratado como una función de N, por lo que podemos establecer el tiempo de ejecución del algoritmo.


1: lo que significa que casi todas las instrucciones se ejecutan una sola vez o pocas veces. A este tiempo de ejecución lo conocemos como tiempo de ejecución constante.

logN: podemos decir que el programa es más lento cuanto más crece N, pero apenas se aprecia ya que logN se duplica cuando N llega a N2. A este tiempo de ejecución lo denominamos tiempo de ejecución logarítmico.

N: este tiempo de ejecución es lineal, lo que significa que si en un momento N vale 20 la ejecución tardará el doble que si N vale 10.

N*logN: este tiempo de ejecución es propio de algoritmos como el Quick Sort, o algoritmos del tipo Divide y Vencerás. En ellos si la N se duplica, el tiempo de ejecución del algoritmo llega a ser mayor del doble. Se le conoce como tiempo de ejecución de N*logN.

N2: conocido como tiempo de ejecución cuadrático. Podemos encontrarlo en aquellos algoritmos en los que se trabajan con pares de datos, como un bucle doblemente anidado. En estos casos si N llega a duplicarse el tiempo de ejecución crece cuatro veces.

N3: conocido como tiempo de ejecución cúbico. Como en el caso anterior podemos recurrir al ejemplo de anidamientos, en esta caso un bucle anidado triple. Si N crece de forma que se duplique el tiempo de ejecución se multiplicará por 8.

2N: llamado tiempo de ejecución exponencial. No es útil en la práctica debido a su elevado tiempo de ejecución. Si N crece de forma que se duplique, el tiempo de ejecución se eleva al cuadrado.


- Polinomiales: son factibles en general y son proporcionales a Nk.

- Exponenciales: no suelen ser factibles a no ser que el tamaño de entrada sea muy pequeño. Son proporcionales a KN.

Clasificación de problemas

Los problemas planteados por la matemática se pueden dividir en una primera lectura en dos grandes grupos:

  • Problemas indecidibles: aquellos problemas los cuales no se pueden solucionar a través de un algoritmo.
  • Problemas decidibles: aquellos problemas que cuentan al menos con un algoritmo para su cómputo o solución.

Sin embargo, que un problema sea decidible no implica que pueda ser resuelto, existen gran cantidad de problemas que cuentan con algoritmos para su resolución, pero son inabordables para un computador por el gran número de operaciones que hay que realizar para hallar su solución. Esto permite separar los problemas decidibles en dos:

  • Intratables: aquellos para los que no es factible obtener su solución.
  • Tratables: aquellos para los que existe al menos un algoritmo capaz de resolverlo en un tiempo razonable.

También podemos llevar a cabo otra clasificación de los problemas matemáticos atendiendo a su complejidad:

  • Clase P: en la que encajaríamos los problemas para los que existe un algoritmo polinómico que los soluciona. Estos algoritmos son deterministas.
  • Clase NP:en la que englobaríamos los problemas cuyos algoritmos son no deterministas.

Podemos concluir que los problemas correspondientes a la clase P sería un subconjunto de los de la clase NP, ya que solo cuentan con una alternativa en cada iteración.

Ejemplos

A continuación citamos dos ejemplos (Joyanes, 1990):

  • Ejemplo 1: «Un cliente ejecuta un pedido a una fábrica. La fábrica examina en su banco de datos la ficha del cliente, si el cliente es solvente entonces la empresa acepta el pedido; en caso contrario, rechazará el pedido. El algoritmo resultante será:
  1. Inicio.
  2. Leer el pedido.
  3. Examinar la ficha del cliente.
  4. Si el cliente es solvente, aceptar pedido; en caso contrario, rechazar pedido.
  5. Fin.»
  • Ejemplo 2: «Escribir un algoritmo para saber si un número es primo o no. Un número es primo si sólo puede dividirse por sí mismo y por la unidad). Por ejemplo, 9,8,6,4,12,16,20, etc. no son primos, ya que son divisibles por números distintos a ellos mismos y a la unidad. El algoritmo sería:
  1. Inicio.
  2. Poner X igual a 2 (X=2, X, variable que representa a los divisores del número que se busca N).
  3. Dividir N por X.
  4. Si el resultado de N/X es entero, entonces N no es un número primo y bifurcar al punto 7; en caso contrario, continuar el proceso.
  5. Suma 1 a X (X<-X+1)
  6. Si X es igual a N (o X = N div 2), entonces N es un número primo; en caso contrario bifurcar al punto 3.
  7. Fin.»

En otros idiomas

  • Alemán: Algorithmus.
  • Catalán: Algorisme.
  • Esperanto: Algoritmo.
  • Francés: Algorithme.
  • Gallego: Algoritmo.
  • Inglés: Algorithm.
  • Italiano: Algoritmo.
  • Latín: Algorithmus.
  • Occitano: sin datos.
  • Portugués: Algoritmo.
  • Vasco: sin datos.

Fuentes

Licencia









Esta obra se publica multilicenciadamente con las siguientes licencias. Por tanto, usted es libre de reproducir, distribuir, comunicar públicamente, interpretar y transformar, por cualquier medio, con o sin ánimo de lucro, la presente obra, en cualquier momento o lugar, licenciando o multilicenciando, según sea el caso, la obra original o la obra derivada, con una de las siguientes licencias o con un subconjunto de ellas:





Herramientas personales