¿Cuáles son las formas y métodos mejores y fáciles de estudiar algoritmos?

Answer 1

El primer paso para comprender por qué el estudio y el conocimiento de los algoritmos son tan importantes es definir exactamente lo que entendemos por algoritmo. De acuerdo con el popular libro de texto de algoritmos Introducción a los algoritmos (segunda edición de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein), “un algoritmo es cualquier procedimiento computacional bien definido que toma algún valor, o conjunto de valores, como entrada y produce algún valor, o conjunto de valores como salida “. En otras palabras, los algoritmos son como mapas de ruta para realizar una tarea determinada y bien definida. Por lo tanto, una parte del código que calcula los términos de la secuencia de Fibonacci es una implementación de un algoritmo en particular. Incluso una función simple para sumar dos números es un algoritmo en cierto sentido, aunque sea uno simple.

Algunos algoritmos, como los que computan las secuencias de Fibonacci, son intuitivos y pueden integrarse de manera innata en nuestro pensamiento lógico y en nuestras habilidades de resolución de problemas. Sin embargo, para la mayoría de nosotros, los algoritmos complejos se estudian mejor para que podamos usarlos como bloques de construcción para una solución más eficiente de problemas lógicos en el futuro. De hecho, es posible que se sorprenda al saber cuántos algoritmos complejos utilizan las personas cada día cuando revisan su correo electrónico o escuchan música en sus computadoras. Este artículo presentará algunas ideas básicas relacionadas con el análisis de algoritmos y luego las pondrá en práctica con algunos ejemplos que ilustran por qué es importante conocer los algoritmos.

Análisis de tiempo de ejecución
Uno de los aspectos más importantes de un algoritmo es lo rápido que es. A menudo es fácil encontrar un algoritmo para resolver un problema, pero si el algoritmo es demasiado lento, vuelve al tablero de dibujo. Dado que la velocidad exacta de un algoritmo depende de dónde se ejecuta el algoritmo, así como los detalles exactos de su implementación, los científicos informáticos suelen hablar sobre el tiempo de ejecución en relación con el tamaño de la entrada. Por ejemplo, si la entrada consta de N enteros, un algoritmo puede tener un tiempo de ejecución proporcional a N2, representado como O (N2). Esto significa que si ejecutara una implementación del algoritmo en su computadora con una entrada de tamaño N, tomaría C * N2 segundos, donde C es una constante que no cambia con el tamaño de la entrada.

Sin embargo, el tiempo de ejecución de muchos algoritmos complejos puede variar debido a factores distintos al tamaño de la entrada. Por ejemplo, un algoritmo de clasificación puede ejecutarse mucho más rápido cuando se le da un conjunto de enteros que ya están ordenados de lo que lo haría cuando se le da el mismo conjunto de enteros en un orden aleatorio. Como resultado, a menudo se oye a la gente hablar sobre el tiempo de ejecución en el peor de los casos, o el tiempo de ejecución del caso promedio. El peor tiempo de ejecución es el tiempo que tardaría en ejecutarse el algoritmo si se le diera la más insidiosa de todas las entradas posibles. El tiempo de ejecución promedio del caso es el promedio de cuánto tiempo llevaría el algoritmo ejecutarse si se le dieran todas las entradas posibles. De los dos, el peor de los casos es a menudo más fácil de razonar, y por lo tanto, se usa más frecuentemente como un punto de referencia para un algoritmo dado. El proceso de determinar los tiempos de ejecución de caso más desfavorable y promedio para un algoritmo dado puede ser complicado, ya que generalmente es imposible ejecutar un algoritmo en todas las entradas posibles. Hay muchos buenos recursos en línea que pueden ayudarlo a estimar estos valores.
Tiempo aproximado de finalización para algoritmos, N = 100
O (Registro (N)) 10-7 segundosO (N) 10-6 segundosO (N * Registro (N)) 10-5 segundosO (N2) 10-4 segundosO (N6) 3 minutosO (2N) 1014 años.O ( N!) 10142 años.
Clasificación
La clasificación proporciona un buen ejemplo de un algoritmo que los científicos informáticos utilizan con mucha frecuencia. La forma más sencilla de ordenar un grupo de elementos es comenzar por eliminar el elemento más pequeño del grupo y colocarlo primero. Luego retire el siguiente más pequeño, y póngalo a continuación, y así sucesivamente. Desafortunadamente, este algoritmo es O (N2), lo que significa que la cantidad de tiempo que toma es proporcional al número de elementos al cuadrado. Si tuviera que ordenar mil millones de cosas, este algoritmo tomaría alrededor de 1018 operaciones. Para poner esto en perspectiva, una PC de escritorio puede hacer un poco más de 109 operaciones por segundo, y llevaría años terminar de clasificar mil millones de cosas de esta manera.

Afortunadamente, hay una serie de mejores algoritmos (quicksort, heapsort y mergesort, por ejemplo) que se han ideado a lo largo de los años, muchos de los cuales tienen un tiempo de ejecución de O (N * Log (N)). Esto reduce la cantidad de operaciones requeridas para clasificar mil millones de elementos a un número razonable que incluso un escritorio barato podría realizar. En lugar de mil millones de operaciones cuadradas (1018), estos algoritmos requieren solo unos 10 mil millones de operaciones (1010), un factor de 100 millones más rápido.

Trayectoria más corta
Los algoritmos para encontrar el camino más corto de un punto a otro se han investigado durante años. Las aplicaciones abundan, pero dejemos las cosas simples diciendo que queremos encontrar el camino más corto desde el punto A al punto B en una ciudad con solo unas pocas calles e intersecciones. Hay bastantes algoritmos diferentes que se han desarrollado para resolver tales problemas, todos con diferentes beneficios e inconvenientes. Sin embargo, antes de profundizar en ellos, consideremos cuánto tiempo tardaría en ejecutarse un algoritmo ingenuo, uno que pruebe todas las opciones posibles. Si el algoritmo considerara todos los caminos posibles de A a B (que no iban en círculos), no terminaría en nuestras vidas, incluso si A y B estuvieran en una pequeña ciudad. El tiempo de ejecución de este algoritmo es exponencial en el tamaño de la entrada, lo que significa que es O (CN) para algunos C. Incluso para valores pequeños de C, CN se vuelve astronómico cuando N se vuelve moderadamente grande.

Uno de los algoritmos más rápidos para resolver este problema tiene un tiempo de ejecución de O (E * V * Log (V)), donde E es el número de segmentos de carretera y V es el número de intersecciones. Para poner esto en perspectiva, el algoritmo tardaría aproximadamente 2 segundos en encontrar la ruta más corta en una ciudad con 10,000 intersecciones y 20,000 segmentos de carretera (generalmente hay alrededor de 2 segmentos de carretera por intersección). El algoritmo, conocido como Algoritmo de Djikstra, es bastante complejo y requiere el uso de una estructura de datos conocida como cola de prioridad. Sin embargo, en algunas aplicaciones, incluso este tiempo de ejecución es demasiado lento (considere encontrar el camino más corto desde la ciudad de Nueva York a San Francisco, hay millones de intersecciones en los EE. UU.), Y los programadores intentan hacerlo mejor utilizando lo que se conoce como heurística. Una heurística es una aproximación de algo que es relevante para el problema y, a menudo, se calcula mediante un algoritmo propio. En el problema de la ruta más corta, por ejemplo, es útil saber aproximadamente a qué distancia se encuentra un punto del destino. Saber esto permite el desarrollo de algoritmos más rápidos (como A *, un algoritmo que a veces puede ejecutarse significativamente más rápido que el algoritmo de Djikstra), por lo que los programadores elaboran heurísticas para aproximar este valor. Al hacerlo, no siempre mejora el tiempo de ejecución del algoritmo en el peor de los casos, pero sí lo hace más rápido en la mayoría de las aplicaciones del mundo real.

Algoritmos aproximados
A veces, sin embargo, incluso el algoritmo más avanzado, con las heurísticas más avanzadas, en las computadoras más rápidas es demasiado lento. En este caso, se deben hacer sacrificios relacionados con la corrección del resultado. En lugar de intentar obtener la ruta más corta, un programador podría estar satisfecho con encontrar una ruta que sea como máximo un 10% más larga que la ruta más corta.

De hecho, existen bastantes problemas importantes para los cuales el algoritmo más conocido que produce una respuesta óptima no es lo suficientemente rápido para la mayoría de los propósitos. El grupo más famoso de estos problemas se llama NP, que significa polinomio no determinista (no te preocupes por lo que eso significa). Cuando se dice que un problema es NP-completo o NP-duro, significa que nadie sabe una buena manera de resolverlos de manera óptima. Además, si alguien descubriera un algoritmo eficiente para un problema NP-completo, ese algoritmo sería aplicable a todos los problemas NP-completos.

Un buen ejemplo de un problema difícil de NP es el famoso problema del vendedor ambulante. Un vendedor quiere visitar N ciudades, y él sabe cuánto tiempo se tarda en llegar de una ciudad a otra. La pregunta es “¿qué tan rápido puede visitar todas las ciudades?” Dado que el algoritmo más rápido conocido para resolver este problema es demasiado lento, y muchos creen que esto siempre será cierto, los programadores buscan algoritmos suficientemente rápidos que ofrezcan soluciones buenas, pero no óptimas.

Algoritmos aleatorios
Otro enfoque para algunos problemas es aleatorizar un algoritmo de alguna manera. Mientras que hacerlo no mejora el algoritmo en el peor de los casos, a menudo hace muy buenos algoritmos en el caso promedio. Quicksort es un buen ejemplo de un algoritmo en el que a menudo se utiliza la aleatorización. En el peor de los casos, quicksort ordena un grupo de elementos en O (N2), donde N es el número de elementos. Sin embargo, si se incorpora la aleatorización en el algoritmo, las posibilidades de que ocurra el peor de los casos se vuelven cada vez más pequeñas y, en promedio, la ordenación rápida tiene una duración de O (N * Log (N)). Otros algoritmos garantizan un tiempo de ejecución de O (N * Log (N)), incluso en el peor de los casos, pero son más lentos en el caso promedio. Aunque ambos algoritmos tienen un tiempo de ejecución proporcional a N * Log (N), quicksort tiene un factor constante menor, es decir, requiere operaciones C * N * Log (N), mientras que otros algoritmos requieren más como 2 * C * N * Log (N) operaciones.

Otro algoritmo que usa números aleatorios encuentra la mediana de un grupo de números con un tiempo de ejecución promedio de O (N). Esta es una mejora significativa en la clasificación de los números y la toma del medio, que toma O (N * Log (N)). Además, aunque existen algoritmos deterministas (no aleatorios) para encontrar la mediana con un tiempo de ejecución de O (N), el algoritmo aleatorio es atractivamente simple y, a menudo, más rápido que los algoritmos determinísticos.

La idea básica del algoritmo de la mediana es elegir uno de los números del grupo al azar, y contar cuántos de los números del grupo son menos que eso. Digamos que hay N números, y K de ellos son menores o iguales al número que elegimos al azar. Si K es menor que la mitad de N, entonces sabemos que la mediana es el número (N / 2-K) que es mayor que el número aleatorio que seleccionamos, por lo que descartamos los números K menores o iguales al número aleatorio . Ahora, queremos encontrar el número más pequeño (N / 2-K), en lugar de la mediana. Sin embargo, el algoritmo es el mismo, y simplemente seleccionamos otro número al azar y repetimos los pasos anteriores.

Compresión
Otra clase de algoritmo trata situaciones como la compresión de datos. Este tipo de algoritmo no tiene un resultado esperado (como un algoritmo de clasificación), sino que intenta optimizar algunos otros criterios. En el caso de la compresión de datos, el algoritmo (LZW, por ejemplo) intenta hacer que los datos se usen lo menos posible, de tal manera que se puedan descomprimir a su forma original. En algunos casos, este tipo de algoritmo utilizará las mismas técnicas que otros algoritmos, lo que dará como resultado un resultado bueno, pero potencialmente subóptimo. La compresión de JPG y MP3, por ejemplo, ambos comprimen los datos de una manera que hace que el resultado final sea de menor calidad que el original, pero crean archivos mucho más pequeños. La compresión de MP3 no conserva todas las características del archivo de la canción original, pero intenta mantener suficientes detalles para capturar la mayor parte de la calidad, al tiempo que garantiza el tamaño del archivo significativamente reducido que todos conocemos y amamos. El formato de archivo de imagen JPG sigue el mismo principio, pero los detalles son significativamente diferentes, ya que el objetivo es la imagen en lugar de la compresión de audio.

La importancia de conocer los algoritmos
Como científico informático, es importante comprender todos estos tipos de algoritmos para que uno pueda usarlos correctamente. Si está trabajando en una pieza importante de software, es probable que tenga que poder estimar qué tan rápido se ejecutará. Dicha estimación será menos precisa sin una comprensión del análisis de tiempo de ejecución. Además, debe comprender los detalles de los algoritmos involucrados para poder predecir si hay casos especiales en los que el software no funcionará rápidamente o si producirá resultados inaceptables.

Por supuesto, a menudo hay momentos en que se encuentra con un problema que no se ha estudiado previamente. En estos casos, debe crear un nuevo algoritmo o aplicar un algoritmo antiguo de una manera nueva. En este caso, cuanto más sepa sobre los algoritmos, mayores serán sus posibilidades de encontrar una buena manera de resolver el problema. En muchos casos, un problema nuevo puede reducirse a un problema anterior sin demasiado esfuerzo, pero tendrá que tener una comprensión fundamental del problema anterior para poder hacer esto.

Como ejemplo de esto, consideremos lo que hace un interruptor en Internet. Un interruptor tiene N cables enchufados y recibe paquetes de datos provenientes de los cables. El conmutador debe analizar primero los paquetes y luego enviarlos nuevamente a los cables correctos. Un interruptor, como una computadora, se ejecuta mediante un reloj con pasos discretos: los paquetes se envían a intervalos discretos, en lugar de de manera continua. En un cambio rápido, queremos enviar tantos paquetes como sea posible durante cada intervalo para que no se acumulen y se caigan. El objetivo del algoritmo que queremos desarrollar es enviar tantos paquetes como sea posible durante cada intervalo, y también enviarlos para que los que llegaron antes se envíen antes. En este caso, resulta que un algoritmo para un problema que se conoce como “coincidencia estable” es directamente aplicable a nuestro problema, aunque a primera vista esta relación parece poco probable. Sólo a través de un conocimiento y comprensión algorítmicos preexistentes se puede descubrir una relación de este tipo.

Más ejemplos del mundo real
Abundan otros ejemplos de problemas del mundo real con soluciones que requieren algoritmos avanzados. Casi todo lo que haces con una computadora se basa de alguna manera en un algoritmo en el que alguien ha trabajado muy duro para entenderlo. Incluso la aplicación más simple en una computadora moderna no sería posible sin los algoritmos utilizados detrás de la escena para administrar la memoria y cargar datos desde el disco duro.

Hay docenas de aplicaciones de algoritmos complicados, pero voy a discutir dos problemas que requieren las mismas habilidades que algunos problemas anteriores de TopCoder. El primero se conoce como el problema de flujo máximo, y el segundo está relacionado con la programación dinámica, una técnica que a menudo resuelve problemas aparentemente imposibles en la velocidad de fuego.

Flujo máximo
El problema del flujo máximo tiene que ver con determinar la mejor manera de obtener algún tipo de cosas de un lugar a otro, a través de una red de algún tipo. En términos más concretos, el problema surgió por primera vez en relación con las redes ferroviarias de la Unión Soviética, durante los años cincuenta. Estados Unidos quería saber con qué rapidez la Unión Soviética podría obtener suministros a través de su red ferroviaria a sus estados satélites en Europa del Este.

Además, EE. UU. Quería saber qué vías podría destruir con mayor facilidad para cortar los estados satélites del resto de la Unión Soviética. Resultó que estos dos problemas estaban estrechamente relacionados, y que resolver el problema del flujo máximo también resuelve el problema del corte mínimo de descubrir la manera más barata de cortar a la Unión Soviética de sus satélites.

El primer algoritmo eficiente para encontrar el flujo máximo fue concebido por dos científicos de la computación, llamados Ford y Fulkerson. El algoritmo fue posteriormente llamado el algoritmo Ford-Fulkerson, y es uno de los algoritmos más famosos en la informática. En los últimos 50 años, se han realizado una serie de mejoras al algoritmo Ford-Fulkerson para hacerlo más rápido, algunas de las cuales son sumamente complejas.

Desde la primera vez que se planteó el problema, se han descubierto muchas aplicaciones adicionales. El algoritmo tiene una relevancia obvia para Internet, donde es importante obtener la mayor cantidad de datos posible de un punto a otro. También aparece en muchos entornos comerciales, y es una parte importante de la investigación de operaciones. Por ejemplo, si tiene N empleados y N trabajos que deben realizarse, pero no todos los empleados pueden hacer todos los trabajos, el algoritmo de flujo máximo le indicará cómo asignar sus empleados N a los trabajos de tal manera que se realicen todos los trabajos. , siempre que sea posible. La graduación, de SRM 200, es un buen ejemplo de un problema de TopCoder que se presta a una solución que utiliza el flujo máximo.

Comparacion de secuencias
Muchos programadores siguen toda su carrera sin tener que implementar un algoritmo que usa programación dinámica. Sin embargo, la programación dinámica aparece en una serie de algoritmos importantes. Un algoritmo que la mayoría de los programadores han usado, aunque no lo hayan conocido, encuentra diferencias entre dos secuencias. Más específicamente, calcula el número mínimo de inserciones, eliminaciones y ediciones necesarias para transformar la secuencia A en la secuencia B.

Por ejemplo, consideremos dos secuencias de letras, “AABAA” y “AAAB”. Para transformar la primera secuencia en la segunda, lo más sencillo es eliminar la B en el medio y cambiar la A final a la B. Este algoritmo tiene muchas aplicaciones, incluidos algunos problemas de ADN y detección de plagio. Sin embargo, la forma en que muchos programadores lo utilizan es cuando se comparan dos versiones del mismo archivo de código fuente. Si los elementos de la secuencia son líneas en el archivo, este algoritmo puede decirle a un programador qué líneas de código se eliminaron, cuáles se insertaron y cuáles se modificaron para pasar de una versión a la siguiente.

Sin la programación dinámica, tendríamos que considerar un número de transformaciones exponenciales para pasar de una secuencia a otra. Sin embargo, tal como está, la programación dinámica genera un algoritmo con un tiempo de ejecución de solo O (N * M), donde N y M son los números de elementos en las dos secuencias.

Conclusión
Los diferentes algoritmos que las personas estudian son tan variados como los problemas que resuelven. Sin embargo, es muy probable que el problema que está tratando de resolver sea similar a otro problema en algunos aspectos. Al desarrollar una buena comprensión de una amplia gama de algoritmos, podrá elegir el correcto para un problema y aplicarlo correctamente. Además, resolver problemas como los encontrados en las competiciones de TopCoder te ayudará a perfeccionar tus habilidades al respecto. Muchos de los problemas, aunque pueden no parecer realistas, requieren el mismo conjunto de conocimientos algorítmicos que surgen todos los días en el mundo real.