Los algoritmos y la computación - Parte Final

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, el emoji es creado con Bitmoji


El orden de crecimiento del tiempo de ejecución de un algoritmo, ofrece una caracterización sencilla de la eficiencia del algoritmo y también permite comparar el rendimiento relativo de algoritmos alternativos.


Una vez que el tamaño de la entrada n es lo suficientemente grande, la ordenación por fusión, con su tiempo de ejecución en el peor de los casos O(nlog(n)) supera a la ordenación por inserción, cuyo tiempo de ejecución en el peor de los casos es O(n2). Aunque a veces podemos determinar el tiempo de ejecución exacto de un algoritmo, la precisión adicional no suele merecer el esfuerzo de calcularla. Para entradas suficientemente grandes, las constantes multiplicativas y los términos de orden inferior de un tiempo de ejecución exacto están dominados por los efectos del propio tamaño de la entrada.


Cuando consideramos tamaños de entrada lo suficientemente grandes como para que sólo sea relevante el orden de crecimiento del tiempo de ejecución, estamos estudiando la eficiencia asintótica de los algoritmos. Es decir, nos interesa saber cómo aumenta el tiempo de ejecución de un algoritmo con el tamaño de la entrada en el límite, a medida que el tamaño de la entrada aumenta sin límite. Normalmente, un algoritmo que es asintóticamente más eficiente será la mejor opción para todas las entradas, excepto las muy pequeñas.


source.png
Imagen de Pixabay y editada por @abdulmath con GIMP, el emoji es creado con Bitmoji.


En la práctica, los números que hay que ordenar rara vez son valores aislados. Cada uno de ellos suele formar parte de una colección de datos denominada registro. Cada registro contiene una clave, que es el valor que hay que ordenar. El resto del registro está formado por datos satélites, que suelen ir acompañados de la clave.


Cuando un algoritmo de ordenación permuta las claves, debe permutar también los datos satélite. Si cada registro incluye una gran cantidad de datos satélite, a menudo permutamos una matriz de punteros a los registros en lugar de los propios registros para minimizar el movimiento de datos.


En cierto sentido, son estos detalles de implementación los que distinguen un algoritmo de un programa completo. Un algoritmo de ordenación describe el método por el que determinamos el orden de clasificación, independientemente de si estamos ordenando números individuales o grandes registros que contienen muchos bytes de datos satélite.


Por lo tanto, cuando nos centramos en el problema de la ordenación, solemos suponer que la entrada consiste sólo en números. Traducir un algoritmo de ordenación de números en un programa de ordenación de registros es conceptualmente sencillo, aunque en una situación de ingeniería determinada, otras sutilezas pueden hacer que la tarea de programación real sea un reto.


brain.png
Imagen de Pixabay y editada por @abdulmath con GIMP, el emoji es creado con Bitmoji.


Nos preguntamos:

¿Por qué la ordenación?

Muchos informáticos consideran que el problema ordenación es el problema más fundamental en el estudio de los algoritmos. Hay varias razones para ello:

  1. A veces, una aplicación necesita intrínsecamente ordenar la información. Por ejemplo, para preparar los extractos de los clientes, los bancos necesitan ordenar los cheques por número de cheque.
  2. Los algoritmos suelen utilizar la ordenación como una subrutina clave. Por ejemplo, un programa que renderiza objetos gráficos superpuestos puede tener que ordenar los objetos según una relación de "arriba" para poder dibujar estos objetos de abajo a arriba.
  3. Podemos elegir entre una gran variedad de algoritmos de ordenación, que emplean un rico conjunto de técnicas. De hecho, muchas técnicas importantes utilizadas en el diseño de algoritmos aparecen en el conjunto de algoritmos de ordenación que se han desarrollado a lo largo de los años. De este modo, la ordenación es también un problema de interés histórico.
  4. Se puede demostrar un límite inferior no trivial para la ordenación. Los mejores límites superiores coinciden asintóticamente con el límite inferior, por lo que sabemos que los algoritmos de ordenación son asintóticamente óptimos. Además, se puede utilizar la cota inferior de la ordenación para demostrar las cota inferiores de otros problemas.
  5. Al implementar los algoritmos de ordenación se plantean muchas cuestiones de ingeniería. El programa de ordenación más rápido para una situación concreta puede depender de muchos factores, como el conocimiento previo sobre las claves y los datos satélites, la jerarquía de memoria (cachés y memoria virtual) del ordenador central y el entorno de software. Muchas de estas cuestiones se tratan mejor a nivel de algoritmo, en lugar de "ajustar" el código.


monitor.png
Imagen de Pixabay y editada por @abdulmath con GIMP, el emoji es creado con Bitmoji.


Cuando analizamos algoritmos, a menudo tenemos que recurrir a un conjunto de herramientas matemáticas. Algunas de estas herramientas son tan simples como el álgebra de la escuela secundaria, pero otras pueden ser nuevas, como notaciones asintóticas y resolver recurrencias.


También se abordan temas sobre métodos para evaluar y acotar las sumas, que aparecen con frecuencia en el análisis de los algoritmos, definiciones y notaciones básicas para conjuntos, relaciones, funciones, gráficos y árboles. También da algunas propiedades básicas de estos objetos matemáticos. Teoría de conteo:

  • permutaciones,
  • combinaciones y
  • similares.
  • definiciones y propiedades de la probabilidad básica.

Así como objetos matemáticos, las matrices, sus operaciones y algunas de sus propiedades básicas.



waves.png
Imagen de Pixabay


Espero que les haya gustado está serie de los algoritmos y la computación, no te pierdas las próximas publicación sobre otros temas interesantes. 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




Final.png





0
0
0.000
1 comments