Introducción a los Algoritmos

Si hay algo que es basamiento de la teoría de sistemas informáticos es el algoritmo. Y es algo que al mismo tiempo me costo mucho poder aprender. Por eso, una ayudita para todos.

El concepto intuitivo de algoritmo, lo tenemos prácticamente todos: Un algoritmo es una serie finita de pasos para resolver un problema.

Hay que hacer énfasis en dos aspectos para que un algoritmo exista:

  1. El número de pasos debe ser finito. De esta manera el algoritmo debe terminar en un tiempo finito con la solución del problema,
  2. El algoritmo debe ser capaz de determinar la solución del problema.

De este modo, podemos definir algoritmo como un “conjunto de reglas operacionales inherentes a un cómputo“. Se trata de un método sistemático, susceptible de ser realizado mecánicamente, para resolver un problema dado. Sería un error creer que los algoritmos son exclusivos de la informática. También son algoritmos los que aprendemos en la escuela para multiplicar y dividir números de varias cifras. De hecho, el algoritmo más famoso de la historia se remonta a la antigüedad: se trata del algoritmo de Euclides para
calcular el máximo común divisor.

Siempre que se desee resolver un problema hay que plantearse qué algoritmo utilizar. La respuesta a esta cuestión puede depender de numerosos factores, a saber, el tamaño del problema, el modo en que está planteado y el tipo y la potencia del equipo disponible para su resolución.


Características de un algoritmo

  1. Entrada: definir lo que necesita el algoritmo
  2. Salida: definir lo que produce.
  3. No ambiguo: explícito, siempre sabe qué comando ejecutar.
  4. Finito: El algoritmo termina en un número finito de pasos.
  5. Correcto: Hace lo que se supone que debe hacer. La solución es correcta
  6. Efectividad: Cada instrucción se completa en tiempo finito. Cada instrucción debe ser lo suficientemente básica como para que en principio pueda ser ejecutada por cualquier persona usando papel y lápiz.
  7. General: Debe ser lo suficientemente general como para contemplar todos los casos de entrada.

Así podemos, decir que un Algoritmo es un conjunto finito de instrucciones precisas para resolver un problema. Un algoritmo es un método o proceso seguido para resolver un problema. Si el problema es visto como una función, entonces el algoritmo toma una entrada y la transforma en la salida.

Un problema es una función o asociación de entradas con salidas. Un problema puede tener muchos algoritmos. Por tanto, un algoritmo es un procedimiento para resolver un problema cuyos pasos son concretos y no ambiguos. El algoritmo debe ser correcto, de longitud finita y debe terminar para todas las entradas. Un programa es una instanciación de un algoritmo en un lenguaje de programación.


Formulación y Resolución de Problemas

Los algoritmos son los procedimientos que se construyen para la resolución de cualquier problema. De este modo, cuando se refiere a la construcción de un programa, nos estamos refiriéndo a la construcción de un algoritmo. El algoritmo no es un concepto proveniente del campo de la computación, sino
que es un término matemático.

Los algoritmos los encontramos, o mejor, los ejecutamos a lo largo de nuestras actividades diarias; por ejemplo, cuando hacemos una llamada telefónica, tenemos en cuenta un conjunto de instrucciones mínimas y el orden en el cual debemos ejecutarlas para conseguir comunicarnos con alguien en particular; o cuando consultamos un diccionario, cuando se prepara un menú, etc.

Podemos conceptuar que un algoritmo es un procedimiento que contiene un conjunto finito de pasos que se deben ejecutar en un orden específico y lógico, para solucionar los problemas. Un algoritmo puede ser caracterizado por una función lo cual asocia una salida: s= f (E) a cada entrada E.

Se dice entonces que un algoritmo calcula una función f. Entonces la entrada es una variable independiente básica en relación a la que se producen las salidas del algoritmo, y también los análisis de tiempo y espacio.

Cuando se tiene un problema para el cual debemos especificar un algoritmo solución, tendremos en cuenta varios puntos:

  • Si no se conoce un método para solucionar el problema en cuestión, debemos hacer un análisis del mismo para llegar a una solución, después de evaluar alternativas, exigencias y excepciones.
  • Si se conoce un “buen” método de solución al problema, se debe especificar exacta y completamente el método o procedimiento de solución en un lenguaje que se pueda interpretar fácilmente.
  • Los problemas pueden agruparse en conjunto de problemas que son semejantes.
  • En algún sentido, en general, un método para solucionar todos los problemas de un conjunto dado, se considera superior a un método para solucionar solamente un problema del conjunto.

Hay criterios para determinar que tan “buena” es una solución, distintos de ver si trabaja o no, o hasta qué punto es general la aplicabilidad del método. Estos criterios involucran aspectos tales como: eficiencia, elegancia, velocidad, etc. Al definir con exactitud un método de solución para un problema, este debe
estar en capacidad de encontrarla si existe; en caso de que no exista, el método debe reconocer esta situación y suspender cualquier acción.

Formular y resolver problemas constituye una actividad esencial de la vida. Los modelos educativos se han dedicado a plantear problemas y enseñar como solucionarlos. Sin embargo, no se enseña nunca técnicas de cómo resolver problemas en general.

La formulación y resolución de problemas ha sido preocupación de los psicólogos cuando hablan de la inteligencia del hombre. Ellos han concebido esta capacidad como el concurso de ciertas destrezas mentales relacionadas con lo que ya se ha aprendido y que incluyen:

  • Capacidad de analizar los problemas.
  • La rapidez y precisión con que acude al pensamiento.
  • Una organización de ideas para garantizar que se posee la información esencial que asegura el aprendizaje.
  • Una retención clara del incremento de conocimiento.

No se trata de almacenar problemas y sus correspondientes soluciones, sino de desarrollar una capacidad para hacer frente con éxito a situaciones nuevas o desconocidas en la vida del hombre. Ante situaciones nuevas, el que no sabe buscar soluciones se sentirá confuso y angustiado y entonces no busca una estrategia y dará una primera solución para poner punto final a su agonía.

El que sabe buscar soluciones, selecciona la estrategia que le parece más cercana a la requerida y hace una hábil adaptación que se ajusta a la nueva demanda.

Al movernos dentro de la informática no siempre encontramos los problemas a punto de resolverlos, es necesario empezar por hacer su formulación. Se exige hacerlo en términos concisos y claros partiendo de las bases o supuestos que se dispone para especificar sus requerimientos.

Sólo a partir de una buena formulación será posible diseñar una estrategia de solución. Es necesario aprender a desligar estos dos procesos. No se deben hacer formulaciones pensando paralelamente en posibles soluciones. Es necesario darle consistencia e independencia para determinar con precisión a qué se quiere dar solución y luego canalizar una gama de alternativas posibles.

Si ya se ha realizado la formulación del problema podemos cuestionarla con el fin de entender bien la naturaleza del problema.

En nuestra área, el análisis de un problema tiene dos etapas claramente definidas y relacionadas:

  • Formulación o planteamiento del problema.
  • Resolución del problema.

A su vez, la formulación la podemos descomponer en tres etapas:

  • Definición del problema.
  • Supuestos: aserciones y limitaciones suministradas.
  • Resultados esperados.

La fase de planteamiento del problema lo que pretende un algoritmo es sintetizar de alguna forma una tarea, cálculo o mecanismo antes de ser  transcrito al computador. Los pasos que hay que seguir son los siguientes:

  • Análisis previo del problema.
  • Primera visión del método de resolución.
  • Descomposición en módulos.
  • Programación estructurada.
  • Búsqueda de soluciones parciales.
  • Ensamblaje de soluciones finales.

La fase de resolución del problema se puede descomponer en tres etapas:

  • Análisis de alternativas y selección de la solución.
  • Especificación detallada del procedimiento solución.
  • Adopción o utilización de una herramienta para su implementación, si es necesaria.

Hay que notar que el computador es un medio y no es el fin en la solución de problemas. En otras palabras, no es el computador el que soluciona los problemas, somos nosotros quienes lo hacemos y de alguna manera le contamos como es la cosa para que él con su velocidad y exactitud trabaje con grandes volúmenes de datos.

En el campo de las ciencias de la computación la solución de problemas se describe mediante el diseño de procedimientos llamados algoritmos, los cuales posteriormente se implementan como programas. Los programas son procedimientos que solucionan problemas y que se expresan en un lenguaje conocido por el computador.

Se pueden dar problemas que por su tamaño es necesario subdividirlos en problemas más simples para solucionarlos, utilizando la filosofía de “Dividir para conquistar”. Se parte del principio de que es más fácil solucionar varios problemas simples como partes de un todo que seguir una implantación de “Todo o Nada”. Desarrollar la capacidad de formular y resolver problemas nos prepara para enfrentar situaciones desconocidas.


Razones para Estudiar los Algoritmos

Con el logro de computadores cada vez más rápidos se podría caer en la tentación de preguntarse si vale la pena preocuparse por aumentar la eficiencia de los algoritmos. ¿No sería más sencillo aguardar a la siguiente generación de computadores?. Vamos a demostrar que esto no es así.

Supongamos que se dispone, para resolver un problema dado, de un algoritmo que necesita un tiempo exponencial y que, en un cierto computador, una implementación del mismo emplea 10-4 x 2n segundos.

Este programa podrá resolver un ejemplar de tamaño n=10 en una décima de segundo. Necesitará casi 10 minutos para resolver un ejemplar de tamaño 20. Un día entero no bastará para resolver uno de tamaño 30. En un año de cálculo ininterrumpido, a duras penas se resolverá uno de tamaño 38 Imaginemos que necesitamos resolver ejemplares más grandes y compramos para ello un computador cien veces más rápido. El mismo algoritmo conseguirá resolver ahora un ejemplar de tamaño n en sólo 10-6 2n
segundos. ¡Qué decepción al constatar que, en un año, apenas se consigue resolver un ejemplar de tamaño 45!

En general, si en un tiempo dado se podía resolver un ejemplar de tamaño n, con el nuevo computador se resolverá uno de tamaño n+7 en ese mismo tiempo.

Imaginemos, en cambio, que investigamos en algorítmica y encontramos un algoritmo capaz de resolver el mismo problema en un tiempo cúbico. La implementación de este algoritmo en el computador inicial podría necesitar, por ejemplo, 10-2 n3 segundos. Ahora se podría resolver en un día un ejemplar de un tamaño superior a 200. Un año permitiría alcanzar casi el tamaño 1500.

Por tanto, el nuevo algoritmo no sólo permite una aceleración más espectacular que la compra de un equipo más rápido, sino que hace dicha compra más rentable.

Dado estos argumentos, podemos resumir las siguientes razones para justificar el estudiar los algoritmos:

  1. Evitar reinventar la rueda.
    Para algunos problemas de programación ya existen buenos algoritmos para solucionarlos. Para esos algoritmos ya fueron analizadas sus propiedades. Por ejemplo, confianza en su correctitud y eficiencia.
  2. Para ayudar cuando desarrollen sus propios algoritmos.
    No siempre existe un algoritmo desarrollado para resolver un problema. No existe regla general de creación de algoritmos. Muchos de los principios de proyecto de algoritmos ilustrados por algunos de los algoritmos que estudiaremos son importantes en todos los problemas de programación. El conocimiento de los algoritmos bien definidos provee una fuente de ideas que pueden ser aplicadas a nuevos algoritmos.
  3. Ayudar a entender herramientas que usan algoritmos particulares. Por ejemplo, herramientas de compresión de datos:
    · Pack usa Códigos Huffman.
    · Compress usa LZW.
    · Gzip usa Lempel-Ziv.
  4. Útil conocer técnicas empleadas para resolver problemas de determinados tipos.

Formas de Representación de Algoritmos

Existen diversas formas de representación de algoritmos, pero no hay un consenso con relación a cuál de ellas es mejor. Algunas formas de representación de algoritmos tratan los problemas a un nivel lógico, abstrayéndose de detalles de implementación, muchas veces relacionados con un lenguaje de programación específico. Por otro lado, existen formas de representación de algoritmos que poseen una mayor  riqueza de detalles y muchas veces acaban por oscurecer la idea principal, el
algoritmo, dificultando su entendimiento.

Dentro de las formas de representación de algoritmos más conocidas, sobresalen:

  • La descripción narrativa
  • El Flujograma convencional
  • El diagrama Chapin
  • El pseudocódigo, o también conocido como lenguaje estructurado.


La Máquina de Turing

Alan Turing, en 1936 desarrolló su Máquina de Turing (la cual se cubre en los cursos denominados Teoría de la Computación o Teoría de Automátas), estableciendo que cualquier algoritmo puede ser representado por ella.

Turing mostró también que existen problemas matemáticos bien definidos para los cuales no hay un algoritmo. Hay muchos ejemplos de problemas para los cuales no existe un algoritmo. Un problema de este tipo es el llamado problema de paro (halting problem):

Dado un programa de computadora con sus entradas, ¿parará este alguna vez?

Turing probó que no hay un algoritmo que pueda resolver correctamente todas las instancias de este problema. Alguien podría pensar en encontrar algunos métodos para detectar patrones que permitan examinar el programa para cualquier entrada. Sin embargo, siempre habrá sutilezas que escapen al análisis correspondiente.

Alguna persona más suspicaz, podría proponer simplemente correr el programa y reportar éxito si se alcanza una declaración de fin. Desgraciadamente, este esquema no garantiza por sí mismo un paro y en consecuencia el problema no puede ser resuelto con los pasos propuestos.

Como consecuencia de acuerdo con la definición anterior, ese último procedimiento no es un algoritmo, pues no se llega a una solución. Muchas veces aunque exista un algoritmo que pueda solucionar correctamente cualquier instancia de un problema dado, no siempre dicho algoritmo es satisfactorio porque puede requerir de tiempos exageradamente excesivos para llegar a la solución.

Ya sé que es mucho, pero seguimos la semana que viene.

3 pensamientos en “Introducción a los Algoritmos”

  1. Pingback: Introducción a los Algoritmos – Parte II – Eficiencia de Algoritmos – La Compu Del Vecino

Dejá un comentario