Classification des algorithmes avec des exemples

Il existe de nombreuses façons de classer les algorithmes et quelques-unes d’entre elles sont présentées ci-dessous :

1. Méthode de mise en œuvre
2. Méthode de conception
3. Autres classements

Classification par méthode de mise en œuvre :

1. Récursivité ou itération

• Un algorithme récursif est un algorithme qui s’appelle à plusieurs reprises jusqu’à ce qu’une condition de base soit satisfaite. C’est une méthode courante utilisée dans les langages de programmation fonctionnels comme C, C++, etc.
• Les algorithmes itératifs utilisent des constructions telles que des boucles et parfois d’autres structures de données telles que des piles et des files d’attente pour résoudre les problèmes.
• Certains problèmes sont adaptés pour récursif et d’autres sont adaptés pour itératif. Par exemple, le problème des Tours de Hanoï peut être facilement compris dans une implémentation récursive. Chaque version récursive a une version itérative et vice versa.

2. Procédural ou déclaratif (non procédural)-

• Dans les langages de programmation déclaratifs, nous disons ce que nous voulons sans avoir à dire comment le faire.
• Avec la programmation procédurale, nous devons spécifier les étapes exactes pour obtenir le résultat. Par exemple, SQL est plus déclaratif que procédural, car les requêtes ne spécifient pas les étapes pour produire le résultat. Des exemples de langages procéduraux incluent C, PHP et PERL.

3. Série ou parallèle ou distribué-

• En général, tout en discutant des algorithmes, nous supposons que les ordinateurs exécutent une instruction à la fois. Ceux-ci sont appelés algorithmes série.
• Les algorithmes parallèles tirent parti des architectures informatiques pour traiter plusieurs instructions à la fois. Ils divisent le problème en sous-problèmes et les transmettent à plusieurs processeurs ou threads. Les algorithmes itératifs sont généralement parallélisés.
• Si les algorithmes parallèles sont distribués sur différentes machines, nous appelons de tels algorithmes des algorithmes distribués.

4. Déterministe ou non déterministe-

• Les algorithmes déterministes résolvent le problème avec un processus prédéfini, tandis que les algorithmes non déterministes devinent la meilleure solution à chaque étape grâce à l’utilisation d’heuristiques.

5. Exact ou approximatif-

• Les algorithmes pour lesquels nous sommes capables de trouver les solutions optimales sont appelés algorithmes exacts. En informatique, si on n’a pas la solution optimale, on donne des algorithmes d’approximation.
• Les algorithmes d’approximation sont généralement associés à des problèmes NP-difficiles.

Classification par méthode de conception :

Une autre façon de classer les algorithmes est leur méthode de conception.

1. Méthode gourmande-

• Algorithmes gourmands Travail par étapes.
• À chaque étape, une décision est prise qui est bonne à ce stade, sans se soucier des conséquences futures.
• Généralement, cela signifie que certains meilleurs locaux sont choisis. Il suppose que la meilleure sélection locale constitue également la solution optimale globale.

2. Diviser et conquérir-

La stratégie Diviser pour régner résout un problème en :

1. Diviser : diviser le problème en sous-problèmes qui sont eux-mêmes des instances plus petites du même type de problème.
2. Récursivité : résolution récursive de ces sous-problèmes.
3. Conquérir : combiner de manière appropriée leurs réponses.

Exemples : algorithmes de tri par fusion et de recherche binaire.

3. Programmation dynamique-

• La programmation dynamique (DP) et la mémorisation fonctionnent ensemble. La différence entre DP et diviser pour régner est que dans le dernier cas, il n’y a pas de dépendance entre les sous-problèmes, alors que dans DP, il y aura un chevauchement de sous-problèmes. En utilisant la mémorisation [maintaining a table for already solved sub problems], DP réduit la complexité exponentielle à la complexité polynomiale (O(n2), O(n3), etc.) pour de nombreux problèmes.
• La différence entre la programmation dynamique et la récursivité réside dans la mémorisation des appels récursifs. Lorsque les sous-problèmes sont indépendants et s’il n’y a pas de répétition, la mémorisation ne
• Aide, donc la programmation dynamique n’est pas une solution à tous les problèmes.
• En utilisant la mémorisation [maintaining a table of subproblems already solved], la programmation dynamique réduit la complexité d’exponentielle à polynomiale.

4. Programmation linéaire-

• En programmation linéaire, il existe des inégalités en termes d’entrées et de maximisation (ou de minimisation) d’une fonction linéaire des entrées.
• De nombreux problèmes (exemple : débit maximum pour les graphes orientés) peuvent être discutés en utilisant la programmation linéaire.

5. Réduction [Transform and Conquer]

• Dans cette méthode, nous résolvons un problème difficile en le transformant en un problème connu pour lequel nous avons des algorithmes asymptotiquement optimaux. Dans cette méthode, le but est de trouver un algorithme réducteur dont la complexité ne soit pas dominée par les algorithmes réduits résultants. Par exemple, l’algorithme de sélection pour trouver la médiane dans une liste consiste d’abord à trier la liste, puis à trouver l’élément du milieu dans la liste triée. Ces techniques sont également appelées transformer et conquérir.

Autres classements :

1. Classification par domaine de recherche-

• En informatique, chaque domaine a ses propres problèmes et a besoin d’algorithmes efficaces. Exemples : algorithmes de recherche, algorithmes de tri, algorithmes de fusion, algorithmes numériques, algorithmes de graphes, algorithmes de chaînes, algorithmes géométriques, algorithmes combinatoires, apprentissage automatique, cryptographie, algorithmes parallèles, algorithmes de compression de données, techniques d’analyse, etc.

2. Classification par complexité-

• Dans cette classification, les algorithmes sont classés en fonction du temps qu’ils mettent pour trouver une solution en fonction de leur taille d’entrée. Certains algorithmes prennent une complexité temporelle linéaire (O(n)) et d’autres prennent un temps exponentiel, et certains ne s’arrêtent jamais. Notez que certains problèmes peuvent avoir plusieurs algorithmes avec des complexités différentes.

3. Algorithmes aléatoires-

• Quelques algorithmes font des choix au hasard. Pour certains problèmes, les solutions les plus rapides doivent impliquer le hasard. Exemple : Tri rapide.

Attention lecteur ! N’arrêtez pas d’apprendre maintenant. Obtenez tous les concepts importants de DSA avec le Cours auto-rythmé DSA à un prix adapté aux étudiants et devenez prêt pour l’industrie. Pour compléter votre préparation de l’apprentissage d’une langue à DS Algo et bien d’autres, veuillez vous référer Cours complet de préparation aux entretiens.

Au cas où vous souhaiteriez assister cours en direct avec des experts, veuillez vous référer Cours en direct DSA pour les professionnels en activité et Programmation compétitive en direct pour les étudiants.