Los algoritmos y la computación - 3ra Parte

avatar


Portada.png
La imagen de fondo de la portada es una imagen de libre uso tomada de Pixabay y editada por @abdulmath con Inkscape


Supongamos que los computadore fuesen infinitamente rápidos y que la memoria del computador estuviera libre.

¿Tendría alguna razón para estudiar algoritmos?


La respuesta es , si no es por otra razón que el hecho de que nos gustaría demostrar que el método de solución termina y lo hace con la respuesta correcta.

Si los computadores fuesen infinitamente rápidos, cualquier método correcto para resolver un problema serviría. Probablemente se quiere que la implementación esté dentro de los límites de las buenas prácticas de ingeniería de software (por ejemplo, su implementación debería estar bien diseñada y documentada), pero la mayoría de las veces se utiliza el método más fácil de implementar.

Por supuesto, los computadores pueden ser rápidos, pero no son infinitamente rápidos. Y la memoria puede ser baja, pero no es libre. Por lo tanto, el tiempo de computación es un recurso limitado, al igual que el espacio en la memoria. Hay que utilizar estos recursos con prudencia, y los algoritmos que son eficientes en términos de tiempo o espacio ayudan a que así sean.


time.png
Imagen de Pixabay


Los diferentes algoritmos ideados para resolver el mismo problema suelen diferir drásticamente en su eficacia. Estas diferencias pueden ser mucho más significativas que las debidas al hardware y al software.

Como ejemplo, tenemos dos algoritmos de ordenación.

  • El primero, conocido como ordenación por inserción, tarda un tiempo aproximadamente igual a c1n2 para ordenar n elementos, donde c1 es una constante que no depende de n. Es decir, tarda un tiempo aproximadamente proporcional a n2.
  • El segundo, la ordenación por fusión, tarda aproximadamente igual a c2nlog(n), donde c2 es otra constante que tampoco depende de n.

La ordenación por inserción suele tener un factor constante menor que la ordenación por fusión, de modo que c1c2. Aunque la ordenación por inserción suele ser más rápida que la ordenación por fusión para tamaños de entrada pequeños, una vez que el tamaño de entrada n es lo suficientemente grande, la ventaja de log(n) de la ordenación por fusión frente a n compensará con creces la diferencia de factores constantes. Por mucho que c1 sea más pequeño que c2, siempre habrá un punto de cruce a partir del cual la ordenación por fusión es más rápida.

Para un ejemplo concreto, supongamos que el computador A ejecuta 10.000 millones de instrucciones por segundo y que el computador B sólo ejecuta 10 millones de instrucciones por segundo, por lo que el computaor A es 1000 veces más rápido que el computador B en cuanto a potencia de cálculo. Para hacer para que la diferencia sea aún más dramática, supongamos que un programador más astuto del mundo codifica la ordenación por inserción en lenguaje de máquina para el computador A, y el código resultante requiere 2n2 instrucciones para ordenar n números. Supongamos además que un programador medio implementa la ordenación por fusión, utilizando un lenguaje de alto nivel con un compilador ineficiente, y el código resultante requiere 50nlog(n) instrucciones. Para ordenar 10 millones de números, el computador A necesita

(2)(107)2 instrucciones entre 1010 instrucciones por segundo, lo que se traduce en 20.000 segundos para lograrse.

mientras que el computador B tarda
(50)(107)log(107) instrucciones entre 107 instrucciones por segundo, lo que se traduce en aproximadamente 1.163 segundo para lograrse.


Al utilizar un algoritmo cuyo tiempo de ejecución crece más lentamente, incluso con un compilador deficiente, el computador B funciona más de 17 veces más rápido que el computador A. La ventaja de la ordenación por fusión es aún más pronunciada cuando ordenamos 100 millones de números: mientras que la ordenación por inserción tarda más de 23 días, la ordenación por fusión tarda menos de cuatro horas. En general, a medida que aumenta el tamaño del problema, también lo hace la ventaja relativa de la ordenación por fusión.


clock.png
Imagen de Pixabay


El ejemplo anterior demuestra que debemos considerar los algoritmos, al igual que el hardware informático, como una tecnología. El rendimiento total del sistema depende de la elección de algoritmos eficientes tanto como de la elección de hardware rápido. Al igual que se están produciendo rápidos avances en otras tecnologías informáticas, también se están produciendo en los algoritmos.


Podemos entonces preguntarnos lo siguiente: los algoritmos son realmente tan importantes en los computadores actuales a la luz de otras tecnologías avanzadas, como

  1. arquitecturas informáticas y tecnologías de fabricación avanzadas,
  2. interfaces gráficas de usuario (GUI) fáciles de usar e intuitivas,
  3. sistemas orientados a objetos,
  4. tecnologías web integradas y
  5. redes rápidas, tanto por cable como inalámbricas.


La respuesta es . Aunque algunas aplicaciones no requieren explícitamente contenido algorítmico a nivel de aplicación (como algunas aplicaciones sencillas basadas en la web), muchas sí lo requieren.


Por ejemplo, consideremos un servicio basado en la web que determine cómo viajar de un lugar a otro. Su implementación se basaría en un hardware rápido, una interfaz gráfica de usuario, una red de área amplia y posiblemente también en la orientación a objetos. Sin embargo, también necesitaría algoritmos para determinadas operaciones, como la búsqueda de rutas (probablemente mediante un algoritmo de camino más corto), la representación de mapas y la interpolación de direcciones.

Además, incluso una aplicación que no requiera contenido algorítmico a nivel de aplicación depende en gran medida de los algoritmos.

  • ¿La aplicación depende de un hardware rápido? El diseño del hardware utiliza algoritmos.
  • ¿La aplicación depende de interfaces gráficas de usuario? El diseño de cualquier interfaz gráfica se basa en algoritmos.
    *¿La aplicación depende de la red? El enrutamiento en las redes depende en gran medida de los algoritmos.
    *¿La aplicación está escrita en un lenguaje distinto al código máquina? Entonces fue procesada por un compilador, un intérprete o un ensamblador, todos los cuales hacen un amplio uso de algoritmos.

Los algoritmos son el núcleo de la mayoría de las tecnologías utilizadas en los computadores actuales. Además, con las capacidades cada vez mayores de los computadores, los utilizamos para resolver problemas más grandes que nunca. Como vimos en la comparación anterior entre la ordenación por inserción y la ordenación por fusión, es en los problemas de mayor tamaño donde las diferencias de eficiencia entre los algoritmos se vuelven particularmente importantes.

Tener una base sólida de conocimientos y técnicas algorítmicas es una característica que separa a los programadores verdaderamente hábiles de los novatos. Con la tecnología informática moderna, se pueden realizar algunas tareas sin saber mucho de algoritmos, pero con una buena base de algoritmos, se puede hacer mucho, mucho más.



waves.png
Imagen de Pixabay


Si quedastes fascinado con este apasionante tema de los algoritmos y la computación, no te pierdas la próxima publicación sobre este tema, si deseas ampliar más te invito a leer las siguientes referencias:

  • Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
  • Selim G. Akl. The Design and Analysis of Parallel Algorithms. Prentice Hall, 1989.
  • Mikhail J. Atallah, editor. Algorithms and Theory of Computation Handbook. CRC Press, 1999.
  • Eric Bach and Jeffrey Shallit. Algorithmic Number Theory—Volume I: Efficient Algorithms. The MIT Press, 1996.


HiveFirma.png
cervantes.png



0
0
0.000
1 comments