Mejor respuesta
Clasificación por propósito
Cada algoritmo tiene un objetivo, por ejemplo, el propósito del algoritmo de clasificación rápida es ordenar los datos en orden ascendente o descendente. Pero el número de objetivos es infinito y tenemos que agruparlos por tipo de propósito.
Clasificación por implementación
Un algoritmo puede implementarse de acuerdo con diferentes principios básicos.
- Recursivo o iterativo Un algoritmo recursivo es aquel que se llama a sí mismo repetidamente hasta que una determinada condición coincide. Es un método común a la programación funcional. Los algoritmos iterativos utilizan construcciones repetitivas como bucles. Algunos problemas se adaptan mejor a una implementación u otra. Por ejemplo, el problema de las torres de hanoi se comprende bien en la implementación recursiva. Cada versión recursiva tiene una iterativa equivalente iterativa y viceversa.
- Lógica o procedimental Un algoritmo puede verse como una deducción lógica controlada. Un componente lógico expresa los axiomas que pueden usarse en el cálculo y un componente de control determina la forma en que se aplica la deducción a los axiomas. Esta es la base de la programación lógica. En los lenguajes de programación de lógica pura, el componente de control es fijo y los algoritmos se especifican al suministrar solo el componente lógico.
- Serial o paralelos generalmente se discuten asumiendo que las computadoras ejecutan una instrucción de un algoritmo a la vez. Este es un algoritmo en serie, a diferencia de los algoritmos paralelos, que aprovechan las arquitecturas de computadora para procesar varias instrucciones a la vez. Dividen el problema en subproblemas y los pasan a varios procesadores. Los algoritmos iterativos son generalmente paralelizables. Los algoritmos de clasificación se pueden paralelizar de manera eficiente.
- determinista o no determinista Los algoritmos deterministas resuelven el problema con un proceso predefinido, mientras que el algoritmo no determinista debe realizar estimaciones de la mejor solución en cada paso mediante el uso de heurísticas.
Clasificación por paradigma de diseño
Un paradigma de diseño es un dominio en la investigación o clase de problemas que requiere un tipo de algoritmo dedicado:
- Divide y vencerás Un algoritmo de divide y vencerás reduce repetidamente una instancia de un problema a una o más instancias más pequeñas del mismo problema (generalmente de forma recursiva), hasta que las instancias sean lo suficientemente pequeñas para resolver fácilmente. Un ejemplo de divide y vencerás es la clasificación por combinación. La clasificación se puede hacer en cada segmento de datos después de dividir los datos en segmentos y la clasificación de los datos completos se puede obtener en la fase de conquista fusionándolos. El algoritmo de búsqueda binaria es un ejemplo de una variante de dividir y conquistar llamada algoritmo de disminución y conquista , que resuelve un subproblema idéntico y utiliza la solución de este subproblema para el problema más grande.
- Programación dinámica La ruta más corta en un gráfico ponderado se puede encontrar usando la ruta más corta a la meta desde todas las vértices. Cuando la solución óptima a un problema se puede construir a partir de soluciones óptimas a subproblemas, el uso de programación dinámica evita volver a calcular soluciones que ya se han calculado. – La principal diferencia con el enfoque de «divide y vencerás» es que los subproblemas son independientes en el divide y vencerás, mientras que la superposición de subproblemas ocurre en la programación dinámica. – La programación dinámica y la memorización van juntas. La diferencia con la recursividad sencilla está en el almacenamiento en caché o la memorización de llamadas recursivas. Donde los subproblemas son independientes, esto es inútil. Al utilizar la memorización o mantener una tabla de subproblemas ya resueltos, la programación dinámica reduce la naturaleza exponencial de muchos problemas a la complejidad polinomial.
- El método codicioso Un algoritmo codicioso es similar a un algoritmo de programación dinámica, pero la diferencia es que no es necesario conocer las soluciones a los subproblemas en cada etapa. En cambio, se puede hacer una elección «codiciosa» de lo que parece ser la mejor solución por el momento. El algoritmo codicioso más popular es encontrar el árbol de expansión mínimo proporcionado por Kruskal.
- Programación lineal El problema se expresa como un conjunto de desigualdades y luego se intenta maximizar o minimizar las entradas. Esto puede resolver muchos problemas, como el flujo máximo para gráficos dirigidos, sobre todo mediante el uso del algoritmo simplex.Una variante compleja de la programación lineal se llama programación de números enteros, donde el espacio de la solución está restringido a todos los números enteros.
- Reducción también llamada transforma y conquista Resuelve un problema transformándolo en otro problema. Un ejemplo simple: encontrar la mediana en una lista sin clasificar es primero traducir este problema en un problema de clasificación y encontrar el elemento del medio en una lista ordenada. El objetivo principal de la reducción es encontrar la transformación más simple posible.
- Usando gráficos Muchos problemas, como jugar al ajedrez, pueden modelarse como problemas en gráficos. Se utilizan algoritmos de exploración de gráficos. Esta categoría también incluye los algoritmos de búsqueda y el retroceso.
- El paradigma probabilístico y heurístico Probabilístico Aquellos que toman algunas decisiones al azar. Genético Intente encontrar soluciones a los problemas imitando los procesos biológicos evolutivos, con un ciclo de mutaciones aleatorias que producen sucesivas generaciones de «soluciones». Por lo tanto, emulan la reproducción y la «supervivencia del más apto». Heurístico cuyo propósito general no es encontrar una solución óptima, sino una solución aproximada donde el tiempo o los recursos para encontrar una solución perfecta no son prácticos.
Clasificación por complejidad
Algunos algoritmos se completan en tiempo lineal y otros en una cantidad de tiempo exponencial, y algunos nunca se completan.
Fuente: Clasificación de algoritmos
Aprendizaje supervisado: clasificación
Respuesta
La siguiente es otra forma de clasificar algoritmos.
En la programación competitiva, hay 4 problemas principales: resolviendo paradigmas.
En otras palabras, dado un problema, aquí están los diferentes enfoques / herramientas que debe tomar para resolverlo.
- Fuerza bruta / Búsqueda completa: Un método que analiza todas las posibilidades y selecciona la mejor solución.
- Pros: simple, siempre debe encontrar la solución ya que está buscando en todas las posibilidades
- Contras : inviable como el el número de posibilidades crece exponencialmente a medida que aumenta el número de elementos
- Dividir y conquistar: Método que divide el problema en partes más pequeñas y luego las resuelve partes. Piense en la búsqueda binaria.
- Enfoque codicioso: Método que elige la mejor opción en el momento actual, sin ninguna consideración para el futuro.
- Ventajas: rápido, simple, puede obtener la mejor solución o acercarse un poco
- Contras: la mayoría de las veces, no obtendremos la mejor solución
- Programación dinámica: Método que se acumula en una solución utilizando subsoluciones previamente encontradas. Definitivamente una de las técnicas más avanzadas, pero extremadamente poderosa y aplicable.
- Ventajas: encuentra la solución óptima a muchos problemas en tiempo polinomial ( mientras que la fuerza bruta sería exponencial)
- Contras : difícil de comprender y aplicar, requiere tiempo para comprender los distintos estados y la recurrencia
Fuentes
Halim, Steven y Felix Halim. Programación competitiva: el nuevo límite inferior de los concursos de programación . Lulu, 2013.