Introducción a los algoritmos
Un algoritmo es una secuencia de pasos que describen cómo se puede resolver un problema. Cada programa de computadora que termina con un resultado se basa básicamente en un Algoritmo. Sin embargo, los algoritmos no solo se limitan para su uso en programas de computadora, sino que también se pueden usar para resolver problemas matemáticos y en muchos asuntos de la vida cotidiana. Según cómo funcionan, podemos dividir los algoritmos en varios tipos. Echemos un vistazo a algunos de los más importantes.
Tipos de algoritmo
Existen muchos tipos de algoritmos, pero los tipos fundamentales de algoritmos son:
1) Algoritmo recursivo
Este es uno de los algoritmos más interesantes, ya que se llama a sí mismo con un valor más pequeño como entradas que obtiene después de resolver las entradas actuales. En palabras más simples, es un algoritmo que se llama a sí mismo repetidamente hasta que se resuelva el problema.
Problemas como la Torre de Hanoi o DFS de un gráfico se pueden resolver fácilmente mediante el uso de estos algoritmos.
Por ejemplo, aquí hay un código que encuentra un factorial usando un Algoritmo de recursión:
Hecho (y)
Si y es 0
volver 1
return (y * Fact (y-1)) / * aquí es donde ocurre la recursividad * /
2) Divide y conquista el algoritmo
Esta es otra forma efectiva de resolver muchos problemas. En los algoritmos Divide and Conquer, divida el algoritmo en dos partes, la primera parte divide el problema en subproblemas más pequeños del mismo tipo. Luego, en la segunda parte, estos pequeños problemas se resuelven y luego se suman (combinan) para producir la solución final del problema.
La clasificación por fusión y la clasificación rápida se pueden hacer con algoritmos de división y conquista. Aquí está el pseudocódigo del algoritmo de clasificación de fusión para darle un ejemplo:
MergeSorting (ar (), l, r)
Si r> l
- Encuentre el punto medio para dividir la matriz dada en dos mitades:
medio m = (l + r) / 2
- Llame a mergeSorting para la primera mitad:
Call mergeSorting (ar, l, m)
- Llame a mergeSorting para la segunda mitad:
Call mergeSorting (ar, m + 1, r)
- Combina las mitades ordenadas en los pasos 2 y 3:
Fusionar llamada (ar, l, m, r)
3) Algoritmo de programación dinámica
Estos algoritmos funcionan recordando los resultados de la pasada ejecución y usándolos para encontrar nuevos resultados. En otras palabras, el algoritmo de programación dinámica resuelve problemas complejos al dividirlo en múltiples subproblemas simples y luego resuelve cada uno de ellos una vez y luego los almacena para su uso futuro.
La secuencia de Fibonacci es un buen ejemplo para los algoritmos de programación dinámica, puede verla funcionando en el pseudocódigo:
Fibonacci (N) = 0 (para n = 0)
= 0 (para n = 1)
= Fibonacci (N-1) + Finacchi (N-2) (para n> 1)
4) Algoritmo codicioso
Estos algoritmos se utilizan para resolver problemas de optimización. En este algoritmo, encontramos una solución óptima localmente (sin tener en cuenta ninguna consecuencia en el futuro) y esperamos encontrar la solución óptima a nivel global.
El método no garantiza que podamos encontrar una solución óptima.
El algoritmo tiene 5 componentes:
- El primero es un conjunto de candidatos del que tratamos de encontrar una solución.
- Una función de selección que ayuda a elegir el mejor candidato posible.
- Una función de viabilidad que ayuda a decidir si el candidato puede ser utilizado para encontrar una solución.
- Una función objetivo que asigna valor a una posible solución o a una solución parcial.
- Función de solución que indica cuándo hemos encontrado una solución al problema.
Huffman Coding y el algoritmo de Dijkstra son dos ejemplos principales en los que se utiliza el algoritmo de Greedy.
En la codificación de Huffman, el algoritmo pasa por un mensaje y, dependiendo de la frecuencia de los caracteres en ese mensaje, para cada carácter, asigna una codificación de longitud variable. Para hacer la codificación de Huffman, primero necesitamos construir un árbol Huffman a partir de los caracteres de entrada y luego atravesar el árbol para asignar códigos a los caracteres.
5) Algoritmo de fuerza bruta
Este es uno de los algoritmos más simples del concepto. Un algoritmo de fuerza bruta itera ciegamente todas las soluciones posibles para buscar una o más de una solución que pueda resolver una función. Piense en la fuerza bruta como el uso de todas las combinaciones posibles de números para abrir una caja fuerte.
Aquí hay un ejemplo de búsqueda secuencial realizada mediante el uso de la fuerza bruta:
Algoritmo S_Search (A (0..n), X)
A (n) ← X
i ← 0
Mientras A (i) ≠ X do
i ← i + 1
si yo <n regreso yo
más devuelve -1
6) Algoritmo de retroceso
Retroceder es una técnica para encontrar una solución a un problema en un enfoque incremental. Resuelve problemas de manera recursiva e intenta llegar a una solución a un problema resolviendo una parte del problema a la vez. Si una de las soluciones falla, la eliminamos y retrocedemos para encontrar otra solución.
En otras palabras, un algoritmo de retroceso resuelve un subproblema y si no resuelve el problema, deshace el último paso y comienza de nuevo para encontrar la solución al problema.
El problema de N Queens es un buen ejemplo para ver el algoritmo Backtracking en acción. El problema de la reina N dice que hay N piezas de reinas en un tablero de ajedrez y tenemos que organizarlas para que ninguna reina pueda atacar a ninguna otra reina en el tablero una vez organizada.
Ahora echemos un vistazo al algoritmo SolveNQ y a las funciones Check Valid para resolver el problema:
CheckValid (tablero de ajedrez, fila, columna)
comienzo
Si hay una Reina a la izquierda de la columna actual, entonces devuelve falso
Si la reina está en la diagonal superior izquierda, entonces devuelve falso
Si la reina está en la diagonal inferior izquierda, entonces devuelve falso
Volver verdadero
Final
SolveNQ (tablero, columna)
comienzo
Si todas las columnas están llenas, devuelve verdadero
Por cada fila presente en el tablero de ajedrez
Hacer
Si, CheckValid (tablero, x, columna), entonces
Establecer la reina en la celda (x, columna) en el tablero
Si SolveNQ (tablero, columna + 1) = Verdadero, entonces devuelve verdadero.
De lo contrario, retire a la reina de la celda (x, columna) del tablero
Hecho
Falso retorno
Final
Conclusión - Tipos de algoritmos
Los algoritmos están detrás de la mayoría de las cosas impresionantes que las computadoras pueden hacer y estos son el núcleo de la mayoría de las tareas informáticas. Ser mejor con los algoritmos no solo lo ayudará a ser un programador exitoso, sino que también será más eficiente.
Artículos recomendados
Esta ha sido una guía de Tipos de Algoritmos. Aquí discutimos los 6 principales tipos importantes de algoritmos con sus funciones. También puede consultar nuestros otros artículos sugeridos para obtener más información:
- Introducción al algoritmo
- Algoritmo en Programación
- Preguntas de entrevista de algoritmo
- Factorial en Python | Tecnicas
- Algoritmos de clasificación rápida en Java
- Los 6 mejores algoritmos de clasificación en JavaScript