Introduction aux algorithmes
Un algorithme est une séquence d'étapes qui décrivent comment un problème peut être résolu. Chaque programme informatique qui se termine par un résultat est essentiellement basé sur un algorithme. Cependant, les algorithmes ne se limitent pas à une utilisation dans des programmes informatiques, ils peuvent également être utilisés pour résoudre des problèmes mathématiques et sur de nombreuses questions de la vie quotidienne. En fonction de leur fonctionnement, nous pouvons diviser les algorithmes en plusieurs types. Jetons un coup d'œil à certains des plus importants.
Types d'algorithme
Il existe de nombreux types d'algorithmes, mais les types fondamentaux d'algorithmes sont:
1) Algorithme récursif
C'est l'un des algorithmes les plus intéressants car il s'appelle avec une valeur plus petite comme entrées qu'il obtient après avoir résolu les entrées actuelles. En termes plus simples, c'est un algorithme qui s'appelle à plusieurs reprises jusqu'à ce que le problème soit résolu.
Des problèmes tels que la tour de Hanoi ou le DFS d'un graphique peuvent être facilement résolus en utilisant ces algorithmes.
Par exemple, voici un code qui trouve une factorielle à l'aide d'un algorithme de récursivité:
Fait (y)
Si y est 0
retour 1
return (y * Fact (y-1)) / * c'est là que la récursivité se produit * /
2) Algorithme de division et de conquête
C'est un autre moyen efficace de résoudre de nombreux problèmes. Dans les algorithmes Divide and Conquer, divisez l'algorithme en deux parties, les premières parties divisent le problème en main en sous-problèmes plus petits du même type. Ensuite, dans la deuxième partie, ces problèmes plus petits sont résolus puis additionnés (combinés) pour produire la solution finale du problème.
Le tri par fusion et le tri rapide peuvent être effectués avec des algorithmes de division et de conquête. Voici le pseudocode de l'algorithme de tri par fusion pour vous donner un exemple:
MergeSorting (ar (), l, r)
Si r> l
- Trouvez le point médian pour diviser le tableau donné en deux moitiés:
milieu m = (l + r) / 2
- MergeSorting pour le premier semestre:
MergeSorting d'appel (ar, l, m)
- MergeSorting pour le second semestre:
MergeSorting d'appel (ar, m + 1, r)
- Fusionnez les moitiés triées aux étapes 2 et 3:
Fusion d'appel (ar, l, m, r)
3) Algorithme de programmation dynamique
Ces algorithmes fonctionnent en se souvenant des résultats de la dernière exécution et en les utilisant pour trouver de nouveaux résultats. En d'autres termes, l'algorithme de programmation dynamique résout des problèmes complexes en le divisant en plusieurs sous-problèmes simples, puis il résout chacun d'eux une fois, puis les stocke pour une utilisation future.
La séquence de Fibonacci est un bon exemple pour les algorithmes de programmation dynamique, vous pouvez le voir fonctionner dans le pseudo-code:
Fibonacci (N) = 0 (pour n = 0)
= 0 (pour n = 1)
= Fibonacci (N-1) + Finacchi (N-2) (pour n> 1)
4) Algorithme gourmand
Ces algorithmes sont utilisés pour résoudre des problèmes d'optimisation. Dans cet algorithme, nous trouvons une solution localement optimale (sans aucune considération pour les conséquences futures) et espérons trouver la solution optimale au niveau mondial.
La méthode ne garantit pas que nous serons en mesure de trouver une solution optimale.
L'algorithme comprend 5 composants:
- Le premier est un ensemble de candidats à partir duquel nous essayons de trouver une solution.
- Une fonction de sélection qui permet de choisir le meilleur candidat possible.
- Une fonction de faisabilité qui aide à décider si le candidat peut être utilisé pour trouver une solution.
- Une fonction objective qui attribue de la valeur à une solution possible ou à une solution partielle
- Fonction de solution qui indique quand nous avons trouvé une solution au problème.
Huffman Coding et l'algorithme de Dijkstra sont deux exemples principaux où l'algorithme Greedy est utilisé.
Dans le codage Huffman, l'algorithme passe par un message et en fonction de la fréquence des caractères de ce message, pour chaque caractère, il attribue un codage de longueur variable. Pour effectuer le codage Huffman, nous devons d'abord construire un arbre Huffman à partir des caractères d'entrée, puis parcourir l'arborescence pour attribuer des codes aux caractères.
5) Algorithme de force brute
Il s'agit de l'un des algorithmes les plus simples du concept. Un algorithme de force brute itère aveuglément toutes les solutions possibles pour rechercher une ou plusieurs solutions pouvant résoudre une fonction. Considérez la force brute comme l'utilisation de toutes les combinaisons possibles de nombres pour ouvrir un coffre-fort.
Voici un exemple de recherche séquentielle effectuée à l'aide de la force brute:
Algorithme S_Search (A (0..n), X)
A (n) ← X
i ← 0
Alors que A (i) ≠ X fait
i ← i + 1
si je <n retourne i
sinon retour -1
6) Algorithme de retour en arrière
Le retour en arrière est une technique pour trouver une solution à un problème dans une approche incrémentale. Il résout les problèmes de manière récursive et essaie de trouver une solution à un problème en résolvant une partie du problème à la fois. Si l'une des solutions échoue, nous la supprimons et revenons en arrière pour trouver une autre solution.
En d'autres termes, un algorithme de retour arrière résout un sous-problème et s'il ne parvient pas à résoudre le problème, il annule la dernière étape et recommence pour trouver la solution au problème.
Le problème N Queens est un bon exemple pour voir l'algorithme Backtracking en action. Le problème de la reine N indique qu'il y a N morceaux de reines sur un échiquier et nous devons les organiser de sorte qu'aucune reine ne puisse attaquer une autre reine du plateau une fois organisée.
Voyons maintenant l'algorithme SolveNQ et les fonctions Vérifier la validité pour résoudre le problème:
CheckValid (échiquier, ligne, colonne)
Début
S'il y a une reine à gauche de la colonne actuelle, retournez false
Si la reine est en diagonale supérieure gauche, retournez false
Si la reine est en diagonale en bas à gauche, retournez false
Retour vrai
Fin
SolveNQ (tableau, colonne)
Début
Si toutes les colonnes sont pleines, retournez true
Pour chaque ligne présente sur l'échiquier
Faire
Si, CheckValid (tableau, x, colonne), alors
Placez la reine dans la cellule (x, colonne) du plateau
Si SolveNQ (tableau, colonne + 1) = True, retournez true.
Sinon, retirez la reine de la cellule (x, colonne) du plateau
Terminé
Retour faux
Fin
Conclusion - Types d'algorithmes
Les algorithmes sont à l'origine de la plupart des choses impressionnantes que les ordinateurs peuvent faire et ils sont au cœur de la plupart des tâches informatiques. Être meilleur avec les algorithmes vous aidera non seulement à être un programmeur performant, mais vous deviendrez également plus efficace.
Articles recommandés
Cela a été un guide pour les types d'algorithmes. Ici, nous discutons des 6 principaux types d'algorithmes importants avec leurs fonctions. Vous pouvez également consulter nos autres articles suggérés pour en savoir plus -
- Introduction à l'algorithme
- Algorithme de programmation
- Questions d'entretiens chez Algorithm
- Factorial en Python | Techniques
- Algorithmes de tri rapide en Java
- Top 6 des algorithmes de tri en JavaScript